운영체제::파일 시스템 구현

HDD와 NVM의 파일 저장과 접근을 둘러싼 이슈에 대해 다룬다.

이 장에서는
파일 사용 구조화, 저장장치 공간 할당, 반납된 공간 재사용,
데이터의 위치를 추적, 운영체제의 다른 부분과 저장장치와 연결하는 방법에 대해 다룬다.

이장의 목표

• 지역 파일 시스템 및 디렉터리 구조 구현에 대한 세부 사항을 설명한다.
• 블록 할당과 가용 블록 알고리즘 및 그의 절충에 대해 논의한다.
• 파일 시스템의 효율 및 성능 문제를 탐색한다.
• 파일 시스템 장애로부터의 복구를 살펴본다.
• 구체적인 예로서 WAFL 파일 시스템을 설명한다.

14.1 파일 시스템 구조

파일 시스템은 데이터의 저장, 탐색, 인출을 쉽게 할 수 있도록 해준다.
이는 저장장치를 효율적이고 사용하기 쉽게 해준다.

파일 시스템은 크게 두 가지의 설계 문제를 제기한다.
첫 번째는 파일 시스템이 유저에게 어떻게 보여야 할지를 정하는 것이다.
즉, 파일은 무엇이며, 파일 속성, 디렉터리 구조, 파일에 허용되는 연산 등을 포함한다.

두 번째는 논리 파일 시스템을 물리적인 저장장치로 사상하는 알고리즘과 자료구조를 만드는 것이다.

파일 제어 블록은 파일에 대한 메타 데이터를 담기 위한 자료구조인데,
UNIX에선 inode로 구현된다.

14.2 파일 시스템 구현

파일 시스템 연산을 구현하는 데 사용되는 구조와 연산에 대해 알아보자.

파일 시스템은 운영체제 부트 방법, 블록의 총수,
가용 블록의 수와 위치, 디렉터리 구조, 개별 파일에 대한 정보를 디스크 상에 가지고 있다.

사용법

open(file_name)은 파일명을 받아 파일시스템에 이를 넘긴다.
우선 범 시스템 오픈 파일 테이블에서 찾아보고
있으면 그 포인터를 프로세스 별 오픈 파일 테이블에 기록한다.

못 찾으면 메모리에 캐싱돼있는 디렉토리에서 저장장치에 있는 FCB에 대한 포인터를 얻는다.
이 FCB를 범 시스템 테이블에다 복사한다.
이 때, 이 파일을 오픈한 프로세스 수도 기록한다.

다음으로 범 시스템 테이블의 항목(즉, 방금 연 파일)에 대한 포인터와
몇 가지 추가 필드를 갖는 항목이 프로세스별 테이블에 생성된다.
추가 필드로는 파일안의 현재 위치, 오픈된 접근 모드 등이 있다.
open()은 프로세스별 테이블의 항목에 대한 포인터를 반환한다.
UNIX에선 이것을 파일 디스크립터라 부르고,
Windows에선 파일 핸들이라고 한다.

read(fd)는 fd로 프로세스 별 테이블에서 파일을 찾아
해당 항목에 대한 범 시스템 테이블에 대한 포인터를 얻어 읽는다.
여기엔 FCB가 있어 그걸로 저장장치의 데이터 블록에 접근해서 데이터를 읽을 수 있다.

실제 데이터 블록을 제외한 오픈 파일에 대한 모든 정보는 메모리 내에 존재한다.

14.3 디렉터리 구현

디렉터리 공간의 할당과 관리는 파일시스템의 효율, 성능, 신뢰성에 큰 영향을 미친다.
이에 대한 알고리즘과, 연관된 문제점들을 알아보자.

선형 리스트

디렉터리를 구현하는 가장 간단한 방법.
단점은 탐색이 오래 걸린다는 점이다.
이를 위해 정렬 해놓고 써도 되지만 이는 파일 생성 및 삭제의 복잡성을 증가시킨다.

해시 테이블

해시와 선형리스트를 함께 사용한다.
파일 이름에 대한 해시 값으로 리스트 노드에 대한 포인터를 얻는다.

해시 테이블의 문제로는 해시 테이블이 고정 크기를 갖는다는 점과
해시 테이블의 크기에 따라 해시 기능도 제한을 받는다는 점이다.

대안으로 체인 해시 테이블을 사용할 수도 있다.
충돌 해결을 위해 속도는 살짝 느려지지만 여전히 선형리스트보단 빠르다.

14.4 할당 방법

파일들을 저장장치 공간에 어떻게 배치해야 공간을 효율적으로 사용 및 파일에 빠르게 접근할 수 있을까.
할당의 주된 3가지 방법인 연속, 연결, 인덱스 기법에 대한 각각의 장단점들을 알아보자.

연속 할당

연속할당은 각 파일이 저장장치 내에 연속적인 공간을 차지하도록 요구한다.
이는 디스크 헤드의 이동을 최소화할 수 있다.
연속할당은 구현이 쉽지만 한계가 있어서 최신 파일 시스템에선 사용하지 않는다.

연속할당의 문제로는 새로운 파일을 위한 가용공간을 찾는게 어렵다.
이에 대한 방법으로 최초 적합과 최적적합이 가장 일반적인 전략이다.

이 두 전략 모두 외부 단편화 문제가 있다.

외부 단편화에 대한 하나의 해결책으로는
전체 파일 시스템을 다른 장치로 복사하는 것이다.
그러면 장치는 완전히 비어 하나의 커다란 가용공간이 된다.
이제 여기다 할당받고 원래 파일들을 다시 복사해온다.
다만 이 방법은 시간과 비용이 매우 많이 든다.

연속할당의 또 다른 문제로는 파일을 위해 얼마의 공간을 할당해줘야 할지 결정하는 것이다.
보통 만들어질 파일의 크기를 예측하는 것은 어렵다.

공간을 작게 할당했다면 파일이 커졌을 때 문제가 된다. (연속 할당이기 때문에)

이에 대한 해결법으로는 그냥 오류를 띄우고 다시 할당받게 하는 방법과
보다 큰 조각을 찾아 거기로 파일을 복사하고 기존의 공간을 비우는 방법이 있다.

연결 할당

연결할당은 연속할당의 모든 문제를 해결한다.
연결할당에서 파일은 저장장치 블록의 연결 리스트형태로 저장된다.

디렉터리는 파일의 첫 번째와 마지막 블록에 대한 포인터를 가진다.
다음 블록을 가리키는 포인터는 사용자가 사용할 수 없다.

그러나 이 방법도 단점이 있다.
가장 중요한 단점은 순차적 파일 접근에만 효과적이고 직접 접근 방식에는 매우 비효율적이다.
(연결 리스트이기 때문에)

또 다른 단점은 포인터들을 위한 공간이 필요하다는 것이다.

이 문제에 대한 일반적인 해결책은 블록이 아닌 클러스터로 단위를 키우는 것이다.
이러면 포인터의 공간 비율이 줄어든다.

이 해결책의 문제는 단위가 커진만큼 내부 단편화 문제가 증가한다.
또한 소량의 데이터 요청이 많은 데이터 전송을 유발해 임의 I/O 성능이 저하된다.

또 다른 문제로는 각 블록이 흩어져 있으므로
중간에 하나의 포인터를 잃어버리면 모든 데이터를 잃는다는 점이다.

이에 대한 변형으로 파일 할당 테이블 FAT가 있다.
각 파티션의 시작 부분이 FAT로 사용되고,
이 FAT 테이블은 디스크 블록 번호를 인덱스로
각 블록마다 한 개의 항목을 가지고 있다.
디렉터리의 항목은 각 파일의 첫 번째 블록을 가리키고,
그 블록 번호를 가지고 FAT 테이블로 가면
그 항목은 다음 블록의 블록 번호를 가리킨다.
이렇게 마지막 블록까지 가면 eof를 나타내는 특수한 값을 가지고 있다.

FAT기법은 FAT가 캐시 되지 않았으면 상당한 수의 디스크 찾기를 유발한다.
장점으론 FAT에서 바로 블록 위치를 알 수 있어 무작위 접근 시간이 개선된다는 점이다.

index 할당

연결할당은 연속할당의 외부 단편화 문제와 파일 크기 선언 문제를 해결했다.
그러나 연결 할당은 FAT가 없으면 직접 접근 방식을 지원할 수 없다

색인 할당은 모든 포인터들을 하나의 index block으로 관리함으로써 이 문제를 해결한다.

각 파일은 블록 주소를 모아놓은 배열인 index block을 가진다.
i번째 항목은 파일의 i번째 블록을 가리킨다.

디렉터리는 index 블록의 주소를 가지고 있다.

인덱스 할당은 외부 단편화 없이 직접 접근을 지원하지만
공간 낭비가 있다.
일반적으로 연결 할당의 포인터 오버헤드보다 크다.
(보통의 파일은 1~2개의 블록만 가진다.)

인덱스 블록의 크기를 결정하는 것도 문제다.
인덱스 블록이 너무 작으면 포인터를 많이 못 담는데,
이에 대한 해결책으로는 다음과 같은 기법들이 있다.

• 연결 기법 : 여러 개의 인덱스 블록을 연결한다.
• 다중 수준 인덱스 : 여러개의 2 level 인덱스 블록들의 집합을 가리키기 위해 1 level 인덱스 블록을 사용한다.
  2 level은 실제 블록을 가리킨다.
• 결합 기법 : 파일의 inode에 인덱스 블록의 15개 포인터를 유지하는 것이다.
  처음 12개는 직접 블록들의 주소를 가리킨다.
  따라서 12블록보다 작은 파일은 추가 인덱스 블록이 필요없다.

만약 12블록보다 크다면 다음 3개의 포인터가 간접적으로 블록은 가리키게 된다.

인덱스 할당 기법은 연결할당과 동일한 성능 문제를 갖는다.
특히 인덱스 블록은 캐시될 수 있지만 데이터 블록은 전체에 널리 퍼져 있을 수 있다.

성능