운영체제 - File system (2) File system implementation (정글사관학교 86일차 TIL)

File system Implementation 1

 

파일 접근 방법(Access Method)

 

파일 접근 방법은 시스템이 제공하는 파일 정보의 접근 방식을 뜻한다. 디스크가 파일에 접근하는 방식은 순차접근과 직접 접근 두 가지 방식이 있다.

 

1) 순차 접근(sequential access): 카세트 테이프를 사용하는 것처럼 접근하는 방식이다. a-b-c 순으로 정보가 저장되어 있다고 하면, a, c만 접근하고 싶다고 해도 c에 접근하기 위해서는 반드시 b를 거쳐가야 한다.

 

2) 직접 접근(direct access, random access): LP 레코드판과 같이 해당 위치에 다이렉트로 이동해 접근하는 방식을 뜻한다. 임의로 접근한다기보다 어디에 있든 해당 위치로 바로 접근하는 방식을 뜻한다. 예컨대 1-2-3-...-10의 순으로 파일이 나열되어 있다고 하면 파일 1에 접근했다가 곧바로 10으로 갈 수도 있고, 5에 있다가 10으로 갈 수도, 9에 있다가 10으로 갈 수도 있다. 하지만 세 가지 방식 모두 한방에 이동하는 것이며 출발지가 임의이기 때문에 random access라고 생각하면 될듯하다.

 

Allocation of File data in Disk

 

디스크에 파일을 저장하는 방법은 3가지가 있다. 그전에, 파일의 형태를 생각해보자. 모든 파일은 그 크기가 균일하지 않다. 어떤 애는 엄청나게 클 수도, 어떤 놈은 무지막지하게 작을 수도 있다. 하지만 모두 동일한 크기의 섹터 단위로 파일을 저장한다.즉, 블록 단위로 나누어서 파일을 저장한다.

 

참고로 섹터는 디스크의 최소 저장 단위로, 크기는 512바이트이다. 블록 역시 동일한 크기인데, 섹터는 물리 디스크에서 가리키는 물리적 최소 저장 단위이며 블록은 파일 시스템에서 논리적인 최소 저장 단위라고 보면 될 듯 하다.(참고: 섹터와 블록의 차이)

 

1. Contiguous Allocation(연속 할당)

하나의 파일이 디스크 상에 연속적으로 저장되는 방식을 뜻한다. 아래 이미지를 보자.

 

위 이미지를 보면, contiguous 방식으로 파일을 저장했을 때, 블록 n개로 구성되는 파일은 디스크 상에서 n개 블록에 연속으로 걸쳐서 저장된다. (0-1, 6-7, 14-16, 19-14, 28-31) 오른쪽에는 디렉토리가 표시되어 있는데, 해당 디렉토리 내에는 디스크에 저장되어 있는 파일의 이름, 해당 파일이 디스크 상에서 어디에 위치해있는지에 대한 시작 위치, 그리고 파일의 길이(=length)를 나타내고 있다.

 

이러한 방식을 어디서 많이 보지 않았나 싶을텐데, 메모리에서 세그멘테이션 기법이 이에 해당했다. 당연히 여기서와 단점이 동일한데, 바로 외부 단편화이다. 위에서 말했듯, 파일의 크기는 균일하지 않다. 그런데 연속으로 할당해버리면 만약 3개 블록 차지하는 파일을 저장한다고 했을 때, 위 이미지에서 17-18에 해당하는 위치에는 여기가 비어있음에도 활용할 수 없다.

 

만약 디스크 내 모든 공간이 한 칸 짜리 파일로 저장되어 한 칸씩 떨어져서 빈 공간이 만들어진 상황이라고 가정해보자. 이 경우에는 2칸 이상짜리 블록을 차지하는 파일은 절대 저장할 수 없게 된다.

 

여기에 한 가지 더 문제가 발생하는데, file grow가 어렵다는 점이다. 파일은 중간에 크기가 변할 수 있다. 크기가 커질수도, 작아질 수도 있는데 위와 같은 방식에서는 파일을 수정해 크기를 늘리기가 어렵다. 연속 할당이라는 규칙에서는 뒷 블록에 다른 파일이 자리하고 있으면 거기를 넘어 크기를 늘릴 수 없기 때문이다.

 

이를 위해 미리 빈 공간(hole)을 확보하는 전략은 어떨까? 이 역시 두 가지 문제가 발생하는데, 1) file 생성 시 얼마나 큰 hole을 배정해줄 것인가에 대한 고민이 필요하며 2) 어찌어찌 할당해서 grow가 가능하게 하더라도 그만큼 내부 단편화가 발생해 공간을 낭비하게 된다.

 

반면 장점도 있는데, 첫번째는 Fast I/O이다. 하드디스크 같은 매체는 대부분 차지하는 시간이 헤드가 이동하는 시간(seek)이다. 읽거나 쓰는데 드는 시간은 큰 차이가 없다. 여기저기에 데이터를 흩뿌려 저장하는 방식과 달리, 연속 저장 방식에서는 한 번의 seek/rotation으로(한 번 위치 정하면 인접 영역만 읽으면 되고 다른 위치로 헤드를 이동할 필요가 없음) 많은 바이트를 읽어 전송할 수 있다.

 

또 한 가지 장점은 Direct access가 가능하다는 것이다. 위 이미지에서 mail이라는 파일(19-24번 블록 차지)에서 21번 블록에 곧바로 접근한다고 해보자. 시작 위치(19)에서 2만큼 더해 O(1)으로 해당 위치로 이동할 수 있다.

 

 

2. Linked Allocation(링크 연결 할당)

contiguous 방식의 가장 큰 단점은 중간에 hole이 생겨 저장 공간을 효율적으로 사용하지 못한다는 점이었다. 이를 방지하기 위해 그림과 같이 임의 블록에 파일을 배치한 다음 각 블록을 연결하는 방식이 linked allocation이다.

 

위 이미지에서 디렉토리를 보면 jeep 파일이 저장되어 있다. 이 jeep 파일은 시작 위치가 9번 블록이고 끝 위치가 25번 블록이다. 해당 파일을 읽어들이려면 시작 블록으로 이동해서 순차적으로 연결된 블록을 하나씩 읽어들여 끝 블록까지 읽어들인다. 이때, 각 블록에는 해당 파일 자체 정보뿐만 아니라 다음 블록의 위치 역시 저장되어 있다.

 

이 방식의 장점은 외부 단편화가 발생하지 않는다는 점이다. 하지만 이 역시 많은 단점이 존재한다. 첫번째는 직접 접근이 되지 않는다는 점이다. 앞에서 네 번째 블록에 찾아간다고 해보자. 무조건 첫번째 블록부터 순차적으로 하나씩 탐색해야 네번째 블록에 도달할 수 있다.

 

또 한 가지 문제는 더 심각한데, reliability 문제이다. 디스크에서는 간혹 bad sector가 발생할 수 있다. 그런데 만약 파일을 구성하는 섹터 수가 1000개인데 중간에 501번째 섹터에 bad sector가 발생한다고 해보자. 그 이후 섹터에는 아예 접근을 할 수 없다. 501번째 섹터에 그 다음 번째 섹터 위치가 저장되어 있는데 여기에 불량이 터져버리면 502번째 위치를 전혀 알 수 없게 되기 때문이다. 즉, 한 섹터만 고장나도 그 이후의 pointer가 유실되어 많은 내용을 잃게 된다.

 

마지막 문제는 공간 효율성이다. 여기서도 공간 비효율 문제가 발생한다고? 그럴 수밖에 없는 게, 각 블록에는 파일 정보뿐만 아니라 포인터 정보도 함께 저장해야 하기 때문이다. 포인터를 위한 공간이 블록 일부가 되기 때문에 공간 효율서이 떨어진다. 하나의 블록 크기가 512바이트일 때, 포인터 크기를 4바이트로만 해도 나름 적지 않은 공간을 차지하게 된다. 나중에 설명하겠지만 FAT 파일 시스템에서는 포인터를 별도 위치에 보관해 reliability와 공간 효율성 문제를 해결한다.

 

3. Indexed Allocation(인덱스 할당)

마지막은 인덱스 할당 방식. 디렉토리에 파일 위치 정보를 바로 저장하지 않고 별도의 인덱스 블록을 만들어 거기에 저장한다. 위 이미지에서는 19번 블록이 이에 해당한다. 디렉토리 안에 들어있는 블록은 인덱스 블록의 위치이다.

 

인덱스 블록은 이 파일이 어디어디에 저장되어있다는 위치 정보를 갖고 있는 블록으로, 블록 하나에 위치 정보를 모두 열거해놨다. 첫번째 파일은 9번 블록에, 두 번째 파일은 16번 블록에,... 이런식이다. 이렇게 하면 linked allocation의 단점이었던 직접 접근을 하지 못하는 문제를 해결할 수 있다. 19번 블록에서 해당 인덱스만큼 이동하면 블록 번호를 알아낼 수 있기 때문이다. 또한, 순차 접근에서 생겼던 문제인 hole 역시도 해결해 외부 단편화 문제도 방지한다.

 

하지만 역시 단점이 있는데, 최소 공간으로 2블록이 필요하다는 점(공간 비효율)이다. 기본적으로 인덱스 블록은 무조건 필요하고 이어서 실제 파일을 저장하는 블록이 필요하다. 아무리 작은 파일이어도 2개의 블록을 필요로 하는 문제가 있는데, 만약 2~3바이트라던가 하는 파일임에도 2블록(1024바이트, 1KB)을 할당해줘야 하니 공간 낭비가 심하다.

 

또한, 만약 파일 크기가 엄청 크다고 가정해보자. 하나의 인덱스 블록만 가지고 모든 블록 위치를 다 저장할 수 없는 문제가 발생할 수도 있다. 예컨대 하나의 블록에는 512 바이트가 필요한데 저장할 수 있는 인덱스 개수에도 한계가 있다. 이를 해결하는 방안으로는 1) linked scheme, 2)multi-level index(인덱스 블록을 여러 개 두는 방식)이 있는데 이정도만 정리하고 넘어간다.

 

여기까지는 이론상의 파일 시스템 구현이다. 그렇다면 실제 파일 시스템에서는 어떤 방식을 쓸까? UNIX 파일 시스템과 FAT 파일 시스템에 대해 알아보자.

 

 

UNIX 파일 시스템 구조

 

위 이미지는 UNIX의 파일 시스템 구조이다. 물리 디스크를 크게 4개의 논리 디스크인 파티션으로 구분한다.

 

 

1. Boot block 

 

부트 블록은 컴퓨터 부팅 관련한 총체적인 정보가 들어있는 디스크로, 디스크 가장 앞쪽에 위치해있다. UNIX뿐만 아니라 어떤 파일 시스템이건 Boot block이 가장 맨 앞에 있다. 어떤 파일 시스템을 쓰던 0번 블록에 부팅에 필요한 정보(Bootstrap loader)를 메모리에 올리면 복잡한 로직 없이 부팅을 바로 진행할 수 있기 때문이다.

 

2. Super block

 

파일 시스템과 관련한 총체적인 정보를 담고 있다. 어디가 비어있는 블록이고 어디가 실제 사용 중인 블록인지에 대한 정보를 담고 있다고 보면 된다.

 

3. Inode list

 

파일 이름을 제외한 파일의 모든 메타 데이터를 저장하는 영역이다.

원래 파일 메타데이터는 어디에 저장되어 있을까? 디렉토리 파일 내부에 저장되어 있다.

하지만 실제 파일 시스템에서는 파일의 메타데이터를 모두 디렉토리 파일이 갖고 있지 않다. 유닉스 파일 시스템의 경우 디렉토리는 지극히 일부분(파일 이름 등)만 갖고 있고 실제 파일의 메타데이터는 별도 공간에 따로 보관하는데, 여기가 inode list이다.

 

아래 이미지를 보면 inode list 안에 빨간 블록이 여러 개 들어있는데, 이 하나하나가 inode에 해당한다. inode 하나당 파일 하나가 매핑되는데, 이 inode에는 매핑된 파일의 메타데이터가 들어있다. (이때 주의! 파일의 이름은 디렉토리가 갖고 있다.)

아래 direct block은 파일 내 블록에 직접 접근할 수 있는 블록 위치를 저장하는 영역이다. 이렇게 direct block으로 각 블록 별 위치 정보를 저장하고 있으면 모든 데이터에 직접 접근이 가능해진다는 장점이 있다. 가장 아랫쪽의 single/double/triple indirect 블록은 파일의 크기가 클 경우 inode list 안에 모든 direct 블록을 다 담을 수 없기 때문에 중간에 거쳐갈 수 있는 자료구조를 담는 영역이다.

 

 

4. Data block

 

파일의 실제 내용을 보관하는 영역이다.

 

예컨대 데이터 블록 내에 디렉토리 파일을 하나 열었다고 해보자. 해당 디렉토리 파일 내에는 파일 메타데이터가 들어있는데, 각각 file 이름과 inode 번호이다. 나머지 파일 메타데이터는 inode 번호를 통해 찾아갈 수 있는 inode list에 보관되어 있다.

 

 

FAT 파일 시스템 구조

FAT 파일 시스템은 UNIX 파일 시스템 구조와 비슷해보이지만 두 가지가 다르다. 1) Inode list 대신 FAT이 들어가 있으며 2) super block 대신 Root directory가 들어가 있다.

 

1. Boot block

 

부트 블록은 동일한 개념이므로 패스.

 

2. FAT

 

파일 메타데이터 중 일부를 FAT에 저장한다. 여기서 FAT에 저장하는 일부 데이터는 파일 위치 정보에 해당하며, 나머지 메타데이터는 루트 디렉토리에 저장한다. 따라서 FAT을 확인해보면 데이터 블록에 있는 해당 파일 contents로 곧바로 접근이 가능하다. 이 역시 직접 접근이 가능한 구조에 해당한다.

 

예를 들어 파일의 네 번째 블록을 본다고 해보자. FAT은 부팅이 시작되고 나면 통째로 메모리에 올라와 있다. 이 파일의 네 번째 블록을 가려면 메모리 내 FAT 테이블 안에서 위치를 계속 확인해 최종 위치까지 갈 수 있다. 여기서 핵심은 디스크 헤드를 움직이는 게 아니라 FAT 테이블을 메모리에 올려놓고 메모리 안에서 왔다갔다해서 찾아내는 방식이라는 점이다.

 

이와 같은 방식을 적용하면 포인터가 하나 유실되더라도 FAT에 위치 데이터가 보관되어 있으니 문제되지 않는다. 게다가, FAT는 매우 중요한 정보기 때무에 여러 copy를 디스크 내에 저장해두고 있다. 즉, 하나만 있지 않다. 이를 통해 reliability를 개선할 수 있다. 또한, FAT를 통해 직접 접근이 가능하므로 linked allocation 문제 역시 해결한다.

 

3. Root directory

 

FAT 구조에서는 루트 디렉토리에 위치를 제외한 나머지 파일 메타데이터를 저장하고 있다.

 

4. Data block

 

Unix와 마찬가지로 파일 자체 정보를 갖고 있는 블록이다.