보통 파일 시스템은 많은 양의 자료를 보관하도록 설계된 보조저장장치에 영구적으로 상주합니다.

범용 운영체제는 여러 파일 시스템을 제공한다. 또한 많은 운영체제에서 관리자나 사용자가 파일 시스템을 추가할 수 있습니다.

이렇게 많은 파일 시스템이 존재하는 이유는 기능, 성능, 안정성 및 설계 목표를 포함하여 여러 측면에서 다양하며 다른 파일 시스템은 다른 목적을 가지고 수행하기 때문입니다.

1. 파일 시스템 구조

파일 시스템을 유지하기 위한 보조저장장치로 디스크가 대부분 사용됩니다.

디스크가 보조저장장치로 사용되는 데에는 다음과 같은 2가지 특성이 있기 때문입니다.

1. 디스크는 추가 장소를 사용하지 않고 재기록이 가능합니다.
2. 디스크에 있는 임의의 블록의 정보를 직접 접근할 수 있습니다. 따라서 임의의 파일을 순차적 또는 무작위 방법으로 쉽게 접근할 수 있습니다.

비휘발성 메모리(NVM) 장치는 파일 저장 및 파일 시스템의 장소로 점점 더 많이 사용되고 있습니다.

하드 디스크와는 달리 재기록이 불가능하며 성능 특성이 다릅니다.

I/O 효율성을 향상하기 위해 메모리와 대용량 스토리지 간의 I/O 전송이 블록 단위로 수행됩니다.

파일 시스템의 목적은 쉽게 데이터를 저장하고, 찾고 또한 인출할 수 있게 함으로써 저장장치를 더욱 효율적이고 편리하게 사용할 수 있게 하기 위함에 있습니다.

따라서, 이것을 위해 설계를 할 때 고려해야 할 2가지 사항이 있습니다.

1. 사용자에게 어떻게 보여줄지에 대한 인터페이스 정의
2. 논리 파일 시스템을 물리적인 2차 저장장치로 사상하는 알고리즘과 데이터 구조를 만드는 것

파일 시스템을 효과적으로 설계하기 위해서 계층 설계를 고려할 수 있습니다.

• 입/출력 제어 층:
  장치 드라이버 루틴들과 인터럽트 핸들러로 이루어져 있어서 메모리와 디스크 시스템 간의 정보 전송을 담당합니다.
• 기본 파일 시스템 층:
  적절한 장치 드라이버에게 저장장치상의 블록을 읽고 쓰도록 일반적인 명령을 내리는 층입니다.
  이 층은 또한 I/O 요청 스케줄링을 고려하며 다양한 파일 시스템, 디렉터리 및 데이터 블록을 저장하는 메모리 버퍼와 캐시를 관리합니다.
• 파일-구성 모듈 층:
  파일과 상응하는 논리 블록을 관리하고, 가용 공간 관리자도 포함하고 있어 파일 구성 모듈이 요구할 때 이들 블록을 제공합니다.
• 논리 파일 시스템 층:
  메타데이터 정보를 관리합니다. 파일 이름을 심볼릭하게 줄 경우 처리하여 하위층인 파일 구성 모듈에 필요한 정보를 넘겨주기 위해 디렉터리 구조를 관리합니다. 파일 구조는 파일 제어 블록(file control block, FCB)를 통해 유지됩니다.

즉, 정리를 하자면 응용 프로그램이 파일 시스템의 특정 연산을 실행시켰을 경우

1. 메타데이터 탐색

응용 프로그램이 요청한 파일 연산을 시작하기 위해, 파일 시스템은 먼저 디렉터리 구조를 탐색하여 해당 파일의 메타데이터(FCB)를 찾습니다.

이 메타데이터에는 파일의 크기, 위치, 접근 권한 등의 정보가 포함되어 있습니다.

2. 논리 블록 탐색

파일 구성 모듈(또는 파일 시스템의 다른 구성 요소)은 파일의 메타데이터를 기반으로 파일이 저장된 논리 블록(또는 데이터 블록)의 위치를 결정합니다.

이 과정에서 파일 시스템은 필요한 데이터를 실제 저장 장치에서 어떻게 찾을지 결정합니다.

3. 장치 드라이버와의 상호작용

해당 파일에 대한 I/O 요청을 처리하기 위해, 파일 시스템은 적절한 장치 드라이버를 선택하고 I/O 요청을 드라이버에 전달합니다.

이때, 비동기적인 I/O 처리를 위해 요청은 대기 큐에 추가될 수 있으며, 장치 드라이버 또는 I/O 스케줄러가 요청을 처리할 순서를 결정합니다.

4. 버퍼 관리와 요청 처리

장치 드라이버는 요청을 처리하기 위한 준비를 하며, 필요한 경우 시스템 버퍼 또는 캐시를 할당하여 데이터를 임시 저장합니다.

이 과정에서 CPU 할당과는 별개로, 주로 메모리 관리와 I/O 처리에 초점을 맞춥니다.

5. 연산 실행

장치 드라이버는 논리적 연산을 실제 장치에서 실행할 수 있는 명령으로 변환하고, 해당 명령을 스토리지 장치로 전송합니다. 데이터 읽기 또는 쓰기와 같은 연산이 실제로 수행됩니다.

6. 완료 및 응답 처리

연산이 완료되면, 장치 드라이버 또는 시스템은 완료 상태를 응용 프로그램에게 통지할 수 있습니다.

필요한 경우, 데이터를 응용 프로그램으로 전송하고, 사용했던 자원을 정리합니다.

이러한 계층 구조를 사용함으로써, 코드의 중복을 최소화하며 유연한 설계를 가능하게 해줍니다.

하지만 이것은 더 많은 운영체제 오버헤드를 야기하며 성능을 저하합니다.

2. 파일 시스템 구현

2.1 개요

파일 시스템은 저장장치에 저장된 운영체제를 어떻게 부트시키는지, 그리고 블록의 총수, 가용 블록의 수와 위치, 디렉터리 구조 그리고 개별 파일에 대한 정보를 디스크 상에 가지고 있습니다.

디스크상의 구조는 다음을 포함합니다.

• 부트 제어 블록

부트 제어 블록은 일반적으로 한 파티션의 첫 번째 블록입니다. UFS(Unix File System)에서는 부트 블록, NTFS(Windows NT 파일 시스템)에서는 파티션 부트 섹터라 불립니다.

• 볼륨 제어 블록

볼륨의 블록의 수, 크기, 가용 블록의 수와 포인터, 그리고 가용 FCB 수와 포인터 같은 볼륨 정보를 포함합니다.

UFS에서는 슈퍼블록, NTFS에서는 마스터 파일 테이블(master file table)라고 불립니다.

• 디렉터리 구조는 파일을 조직화하는 데 사용됩니다.

• 파일별 FCB는 자세한 파일 정보를 가지고 있으며, 디렉터리 항목과의 연결을 위하여 고유한 식별 번호를 가지고 있습니다.

다수의 자료구조 유형이 이 안에 포함됩니다.

• 메모리 내 파티션 테이블은 마운트된 모든 파티션 정보를 포함합니다.
• 메모리 내 디렉터리 구조는 최근 접근된 디렉터리의 디렉터리 정보를 가집니다.
• 범 시스템 오픈 파일 테이블은 다른 정보와 더불어 오픈된 각 파일의 FCB의 복사본을 가지고 있습니다.
• 프로세스별 오픈 파일 테이블은 프로세스가 연 모든 파일에 대해 다른 정보뿐만 아니라 범 시스템 오픈 파일 테이블 내의 해당 항목에 대한 포인터를 포함합니다.
• 버퍼는 파일 시스템이 파일 시스템으로부터 읽혀지거나 써질 때 파일 시스템 블록을 저장합니다.

2.2 사용법

어떻게 사용되는지 확인하기 위해 open() 시스템 콜의 동작을 자세히 살펴봅시다.

1. open() 시스템 콜은 논리적 파일 시스템에 파일 이름을 넘겨줍니다.
2. 다른 프로세스에 의해 사용 중인지 확인하기 위해 범 시스템 오픈 파일 테이블을 검색합니다.
3. 사용 중이면, 기존 범 시스템 오픈 파일 테이블을 가리키는 프로세스별 오픈 파일 테이블 항목이 생성됩니다.
4. 만약 파일이 오픈되지 않았다면, 주어진 파일 이름을 디렉터리 구조에서 찾습니다.
5. 파일이 발견되면 FCB가 메모리내의 범 시스템 오픈 파일 테이블에 복사됩니다.
6. 범 시스템 오픈 파일 테이블에 항목에 대한 포인터와 몇 개의 다른 필드를 갖는 새로운 항목이 프로세스별 오픈 파일 테이블 안에 만들어집니다.
7. open() 시스템 콜은 프로세스별 파일 시스템 테이블 내의 해당 항목에 대한 포인터를 찾아 돌려줍니다.

일단 해당 FCB를 디스크에서 찾으면 시스템은 파일 이름을 더는 사용하지 않기 때문에, 파일 이름은 오픈 파일 테이블의 한 부분이 아닙니다.

그러나 이것은 같은 파일에 대한 다중 오픈 연산을 빠르게 하기 위하여 캐시될 수 있습니다. 이 항목은 다양한 이름을 갖습니다.

UNIX 시스템에서는 이것을 파일 디스크립터라 부르고, Windows는 파일 핸들이라 합니다.

프로세스가 파일을 닫을 때, 프로세스별 테이블 항이 삭제되며 범 시스템 항목의 오픈 계수는 감소합니다.

오픈했던 모든 사용자가 파일을 닫으면 디스크 기반 디렉터리 구조에 업데이트 된 파일 정보가 복사되며, 범 시스템 오픈 파일 테이블에서 그 항목이 삭제됩니다.

이러한 기법을 사용함으로써 실제 데이터 블록을 제외한 오픈 파일에 대한 모든 정보는 메모리 내에 존재합니다.

3. 디렉터리 구현

여기서는 디렉터리 공간을 어떻게 할당하고 관리하는가에 대한 알고리즘을 살펴볼 것입니다.

다음 두 가지 방법을 확인할 것입니다.

1. 선형 리스트
2. 해시 테이블

3.1 선형 리스트

디렉터리를 구현하는 가장 간단한 방법은 파일 이름과 데이터 블록에 대한 포인터들의 선형 리스트를 디렉터리에 사용하는 것입니다.

이 방법은 프로그램이 쉽지만 실행 시간이 길어집니다.

새로운 파일을 생성하기 위해서는 먼저 디렉터리를 탐색하여 같은 이름을 가진 파일이 존재하지 않는다는 것을 확인한 후, 디렉터리 끝부분에 새로운 항목을 첨가하면 됩니다.

이것은 삭제 연산에서 또한 유사합니다.

삭제할 파일을 찾은 뒤에, 별도의 동작을 수행하여 공간을 방출해야 하는데 여기서는 몇 가지 방법이 존재합니다.

• 항목을 미사용으로 표시
• 가용 디렉터리 항목 리스트에 추가

해당 기법의 가장 큰 단점은 선형 탐색으로 인한 지연이고, 이를 위해서 고려할 수 있는 것은 캐시를 사용하는 것 외에 정렬하는 것을 고려할 수 있습니다.

정렬된 리스트는 이진 탐색을 통한 빠른 탐색을 가능하게 해주지만 이것을 유지하는 것은 쉽지 않습니다.

이를 위해서 B-트리와 같은 자료 구조를 고려할 수 있습니다.

3.2 해시 테이블

선형 리스트에 디렉터리 항목들이 저장되기는 하지만 해시 자료구조도 함께 사용됩니다.

파일 이름을 제시하면 해시로부터 값을 얻어서 그것을 포인터로 활용하여 이 리스트를 직접 접근할 수 있습니다.

해시 테이블의 심각한 문제점은 해시 테이블이 고정된 크기를 갖는다는 점과 해시 테이블의 크기에 따라 해시 기능도 제한을 받는다는 점입니다.

이 문제점을 해결하기 위해서 체인 오버플로우 해시 테이블의 사용을 고려할 수 있고, 이것은 각 해시 항목을 하나의 값이 아닌 연결 리스트로 구현하여 새로운 항목을 연결 리스트에 추가함으로써 충돌을 해결합니다.

4. 할당 방법

저장장치 공간을 할당하는 방법으로 세 가지 주요 방법이 있습니다.

1. 연속 할당
2. 연결 할당
3. 인덱스 기법

4.1 연속 할당

연속 할당(Contiguous Allocation)은 각 파일이 저장장치 내에서 연속적인 공간을 차지하도록 요구합니다.

만약 보조저장장치가 HDD라면 연속 할당된 파일들을 접근하기 위해서 필요한 디스크 탐색(seek)의 횟수를 최소화할 수 있으며(논리적 주소가 근접한 블록은 물리적으로도 근접하다고 가정하면), 결국 탐색이 필요한 경우라도 탐색 시간이 최소화됩니다.

연속 할당 기법에는 몇 가지 치명적인 문제를 가지고 있습니다.

한 가지 어려운 점은 새로운 파일을 위한 가용 공간을 찾는 일입니다.

해당 기법에서 공간 할당을 위해 동적 공간 할당 방식인 세 가지 기법이 고려될 수 있습니다.

• 최초 적합(first fit)
• 최적 적합(best fit)
• 최악 적합(worst fit)

최악 적합보다는 최초 적합과 최적 적합의 속도가 더 빠릅니다.

이들 알고리즘은 모두 외부 단편화(external fragmentation) 때문에 어려움이 있습니다.

외부 단편화로 인한 공간의 상당한 양의 공간 손실의 방지하는 하나의 정책은 전체 파일 시스템을 다른 장치로 복사하는 것이빈다.

원래의 장치는 완전히 비게 되어 하나의 커다란 연속적인 가용공간이 됩니다. 그런 후에 이 공간으로부터 할당받으면서 파일들을 원래의 장치로 다시 복사하게 됩니다.

효과적인 방법처럼 보일 수 있지만, 대용량 저장장치의 경우 시간과 비용이 매우 많이 들 것입니다.

또한, 마운트를 해제한 상태에서 작업을 수행해야 하는 문제가 있습니다.

또 다른 문제점으로 파일을 위해서 얼마나 많은 공간을 주어야 하는지 결정하는 것입니다.

특히 최적 적합 방법을 공간을 할당했다면 양 끝에 인접한 공간이 모두 사용중이기 때문에 파일을 그 자리에서 확장할 수 없습니다.

이에 대한 해결 방법으로는 두 가지 방법이 있습니다.

1. 프로그램을 종료한 후 재실행하여 새롭게 더 넓은 공간을 할당하는 방법
2. 보다 더 큰 조각을 찾아 그곳으로 파일을 복사하고 이전의 공간을 비우는 방법

4.2 연결 할당

연결 할당(Linked Allocation)은 연속 할당의 모든 문제를 해결합니다.

연결 할당의 경우 파일은 저장장치 블록의 연결 리스트 형태로 저장되고, 이 블록들은 장치 내에 흩어져 저장될 수 있습니다.

디렉터리는 파일의 첫 번째와 마지막 블록에 대한 포인터를 가지고 있습니다.

각 블록은 다음 블록을 가리키는 포인터를 포함하고 있고, 이들 포인터가 차지하는 영역은 사용자가 사용할 수 없습니다.

새 파일을 생성하려면 단순히 디렉터리 내에 새로운 항목(entry)을 만듭니다.

연결 할당의 경우 각 디렉터리 항목은 파일의 첫 블록에 대한 포인터를 갖고 있습니다.

이 포인터는 처음에는 빈 파일을 표시하기 위해 null 값으로 초기화되고, 크기 필드 역시 0으로 설정 됩니다.

파일 쓰기가 일어나면 가용 블록을 할당받아 쓰기를 수행한 후 파일의 끝에 연결합니다.

이 방법도 단점을 가지고 있는데 가장 중요한 단점은 순차적 접근 파일에만 효과적으로 사용될 수 있고 직접 접근 방식에는 매우 비효율적입니다.

$i$번째 블록을 찾으려면 그 파일의 첫 블록 한 번의 저장장치 읽기와 때로는 HDD 탐색이 필요합니다.

이 문제에 대한 일반적인 해결책은 블록을 모아 클러스터(cluster)라고 하는 단위로 만들고 블록이 아닌 클러스터를 할당하는 것입니다.

클러스터로 할당 시에 포인터는 파일 공간의 훨씬 적은 비율을 사용하고, 블록 할당 및 가용 리스트 관리에 필요한 공간이 줄어듭니다.

이는 HDD 처리량이 향상되게 됩니다.

하지만 클러스터가 부분적으로 가득찬 경우 더 많은 공간이 낭비되므로 이 방법의 비용은 내부 단편화의 증가입니다. 또한 소량의 데이터 요청이 많은 양의 데이터 전송을 유발하기 때문에 임의 I/O 성능이 저하됩니다.

마지막으로 연속 할당의 또 다른 문제점은 신뢰성의 문제입니다.

각 블록이 전체 장치에 흩어져 연결되기 떄문에 오류나 하드웨어의 고장으로 인하여 하나의 포인터를 잃어버리거나 잘못된 포인터 값을 가지게 되면 결국 모든 데이터를 잃는 결과를 초래할 수 있습니다.

이 경우 이중 연결 리스트를 사용하거나 블록마다 파일 이름과 상대 블록 번호 등을 저장하는 방법을 같이 쓸 수도 있겠으나 이러한 기법들은 더 많은 오버헤드를 필요로 합니다.

한 가지 중요한 변형은 파일 할당 테이블(file allocation table, FAT)을 사용하는 것입니다.

단순하지만 효율적인 이 방법은 MS-DOC 운영체제에서 사용됩니다. 각 파티션의 시작 부분이 FAT로 사용됩니다.

이 FAT 테이블은 각 블록마다 한 개의 항목을 가지고 있고 이 항목은 디스크 블록 번호를 인덱스로 찾습니다.

디렉터리의 항목은 각 파일의 첫 번째 블록 번호를 가리킵니다.

그 블록번호를 가지고 FAT 테이블로 가면 그 항목은 다음 블록의 블록 번호를 가리킵니다. 이러한 사슬은 마지막 블록까지 계속되며, 마지막 블록의 테이블 항은 파일의 끝을 나타내는 특수한 값을 갖고 있습니다.

이 방법의 장점은 무작위(random) 접근의 시간이 개선된다는 것입니다. 인덱스를 활용하여 캐싱해놓고 추적이 가능하고, 디스크 헤드가 FAT의 정보를 읽어 임의의 블록 위치를 알아낼 수 있게 된 것입니다.

4.3 색인 할당

색인 할당(Indexed Allocation)은 모든 포인터들을 하나의 장소 즉, 색인 블록으로 관리합니다.

각 파일은 저장장치 블록 주소를 모아놓고 배열인 색인(index) 블록을 가집니다. 색인 블록의 $i$번째 항목은 파일의 $i$번째 블록을 가리킵니다.

디렉터리는 색인 블록의 주소를 가지고 있습니다.

저장장치의 어느 블록이든 더 많은 공간의 요청을 만족시킬 수 있기 때문에 색인 할당은 외부 단편화 없이 직접 접근을 지원합니다.

그러나 색인 할당은 공간 낭비로 인한 어려움을 겪습니다. 색인 블록의 포인터 오버헤드는 일반적으로 연결 할당의 포인터 오버헤드보다 큽니다.

모든 파일에는 색인 블록이 있어야 하므로 색인 블록을 최대한 작게 만려고 합니다. 하지만 너무 작으면 큰 파일에 대한 충분한 포인터를 보유할 수 없으므로 이 문제를 처리하는 기법이 함께 제공되어야 합니다.

이러한 목적을 위한 기법은 다음과 같습니다.

• 연결 기법(linked scheme)

하나의 색인 블록은 통상 한 저장장치 블록입니다.

파일의 크기가 크면 여러 개의 색인 블록을 연결합니다. 예를 들면, 한 색인 블록이 파일의 이름을 나타내는 헤더와 첫 100개의 디스크 블록을 수록하고, 다음 주소(인덱스 블록의 마지막 항)은 작은 파일의 경우 null, 큰 파일의 경우 다음 인덱스 블록에 대한 포인터가 됩니다.

• 다중 수준 색인(multilevel index)

연결 기법의 변형으로서 여러 개의 두 번째 수준 색인 블록들의 집합을 가리키기 위하여 첫 번째 수준의 색인 블록을 사용합니다.

두 번째 수준의 색인 블록은 실제 파일 블록들을 가리킵니다.

• 결합 기법(combined scheme)

UNIX-기반 파일 시스템에서 사용되는 또 다른 대안은 파일의 inode에 색인 블록의 15개 포인터를 유지하는 것입니다.

이 포인터들의 처음 12개는 직접 블록(direct block)을 가리키는데, 즉 이 포인터들은 파일의 데이터를 저장하고 있는 블록들의 주소를 저장합니다.

따라서 12 블록보다 크기가 크지 않은 파일의 경우 추가 색인 블록이 필요 없습니다.

그 다음 3개의 포인터는 간접 블록(indirect block)을 가리키는 포인터입니다.

1. 단일 간접 블록(single indirect block): 데이터가 아니라 데이터를 저장하고 있는 블록의 주소를 저장
2. 이중 간접 블록(double indirect block): 실제 데이터 블록을 가리키는 포인터를 저장하는 블록의 주소를 저장
3. 삼중 간접 블록(triple indirect block)

4.4 성능

3가지 방법의 할당 방법을 살펴봤습니다.

연속 할당은 블록을 얻기 위해 한 번의 액세스만 필요하고, 파일의 시작 주소를 메모리에 쉽게 유지할 수 있으므로 $i$번째 블록의 주소를 즉시 계산하여 직접 읽을 수 있습니다.

연결 할당은 다음 블록의 주소를 메모리에 유지하고 직접 읽을 수 있습니다. 이 방법은 순차적 액세스에 적합하지만 $i$번째 블록에 직접 액세스 하려면 $i$번의 블록 읽기가 필요할 수 있습니다.

색인 할당의 경우 색인 블록이 메모리 내에 상주한다면 직접 접근이 가능합니다. 그러나 메모리 내의 색인 블록을 전부 상주시키는 것은 많은 양의 메모리를 필요로 합니다.

만약 이 메모리 공간을 사용할 수 없다면 먼저 색인 블록을 읽은 후 원하는 자료 블록을 읽어야 합니다.

일부 시스템은 연속 할당과 색인 할당을 결합하여 작은 파일(크기가 3~4 블록)은 연속 할당하고 파일이 더 커지면 자동으로 색인 할당으로 전환합니다.

NVM 장치의 경우 디스크 헤드 탐색이 없으므로 다른 방식의 알고리즘과 최적화가 필요합니다. 존재하지 않은 헤드 이동을 피하고자 많은 CPU 사이클을 소비하는 오래된 알고리즘을 사용하는 것은 매우 비효율적입니다.

이를 위해 새로운 파일 시스템을 만들고 있으며, 이러한 개발은 저장장치와 데이터에 접근하는 응용 프로그램 액세스 간의 명령어 개수와 실행 경로를 줄이는 것을 목표로 합니다.

5. 가용 공간의 관리

새로운 파일을 만들려면 가용 공간 리스트를 탐핵하여 새로운 파일을 위한 공간을 할당받아야 합니다.

그러면 이렇게 할당되는 공간은 가용 공간 리스트로부터 삭제됩니다. 추후 이 파일이 삭제되면, 그 파일이 쓰던 공간은 가용 공간 리스트에 추가됩니다.

5.1 비트 벡터

가용 공간 리스트는 흔히 비트맵(bit map) 또는, 비트 벡터(bit vector)로서 구현됩니다.

여기서 각 블록은 1비트로 표현되며, 블록이 비어있으면 그 비트는 1이 되고, 만약 블록이 할당되어 있다면 그 비트는 0이 됩니다.

이 방법의 큰 이점은 첫 번째 가용 블록 또는 n개의 연속된 가용 블록들을 찾는 일이 상대적으로 간편하고 효율적이라는 점입니다.

이 방식의 문제는 하드웨어의 기능이 소프트웨어의 기능을 좌우한다는 사실입니다.

비트 벡터는 그 전체가 메인 메모리 내에 존재하지 않으면 비효율적입니다. 물론 복구할 때를 위하여 때때로 파일 시스템을 저장하고 있는 장치에 기록되기는 하더라도 메모리에 존재해야 합니다.

작은 디스크의 경우 비트 벡터를 메모리에 유지하는 것이 가능하지만 용량이 큰 디스크의 경우에도 그렇다고 할 수는 없습니다.

5.2 연결 리스트

두 번째 방법은 모든 가용 블록들을 함께 연결하는 것인데 첫 번째 가용 블록은 다음 가용 블록을 가리키는 포인터를 가집니다.

시스템은 첫 번째 가용 블록에 대한 포인터를 파일 시스템의 특정 위치에 두고 또한 메모리에 캐싱하면 됩니다.

HDD에서 이 기법은 리스트를 순회하려면 매번 디스크에 접근해야 하므로 효율적이지 못합니다. 그러나 가용 리스트 순회는 그다지 빈번하게 일어나는 일은 아닙니다.

통상 운영체제는 단순히, 파일에 할당할 하나의 가용 블록이 필요하므로 가용 리스트의 첫 블록을 사용하게 됩니다. FAT 기법은 가용 블록 어카운팅과 할당 자료구조를 결합하여 사용합니다. 따라서 별도의 기법이 필요 없습니다.

5.3 그룹핑

가용 리스트 방식의 변형으로 첫 번째 가용 블록 내에 n개의 블록 주소를 저장하는 방법이 있습니다.

이 중 처음 n-1 개는 실제로 비어있는 블록의 주소입니다. 그러나 마지막 1개는 자신과 마찬가지로 n-1 개의 빈 블록 주소를 가지고 있는 가용 블록을 가리킵니다.

이 방법은 연결 리스트 방법과는 달리, 다수 개의 가용 블록 주소들을 쉽게 찾을 수 있다는 장점이 있습니다.

5.4 계수

또 다른 방법은 일반적으로 디스크 공간의 할당과 반환이 여러 연속된 블록 단위로 이루어진다는 이점을 이용하는 것으로 특히 연속 할당 알고리즘이나 클러스터링을 통해 공간을 할당할 경우 유용합니다.

그러한 경우 모든 블록을 일일이 추적할 필요가 없이 연속된 가용 블록의 첫 번째 블록의 주소와 연속된 블록의 개수(count)만 유지하면 보다 효율적입니다.

가용 공간을 추적하는 이 방법은 블록 할당의 범위(extent) 방법과 유사합니다. 이 항들은 효율적인 검색, 삽입, 삭제를 위하여 연결 리스트가 아닌 균형 트리 형태로 저장될 수 있습니다.

5.5 공간맵

Oracle의 ZFS 파일 시스템은 대규모의 파일, 디렉터리, 심지어 파일 시스템(파일 시스템의 계층 구조도 생성할 수 있음)을 저장할수 있도록 설계되었습니다.

이러한 규모에서는 메타데이터 입출력이 성능에 지대한 영향을 미치게 됩니다.

예를 들어, 가용 공간 리스트가 비트맵으로 구현되었다고 하면, 비트맵은 할당과 반환 시에 매번 수정되어야 합니다. 1TB 디스크에서 1GB 데이터를 반환할 경우, 반환 블록들이 디스크 전체에 산재하여 있을 수 있기 때문에 수천 개의 비트맵 블록이 갱신되어야 합니다.

분명하게 이러한 시스템에서 사용되는 자료구조는 크고 비효율적일 수 있습니다.

ZFS는 가용 공간을 관리할 때 자료구조 크기를 제어하고 이 자료구조를 관리하기 위해 필요한 입출력을 최소화합니다.

우선, ZFS는 메타슬랩(metaslabs)을 생성하여 장치의 공간을 관리 가능한 크기의 덩어리로 나눕니다.

각 메타슬랩은 연관된 공간맵을 가지고 있습니다. ZFS는 가용 블록에 관한 정보를 저장하기 위하여 계수 알고리즘을 사용합니다.

디스크 계수 구조를 기록하는 것이 아니라 로그-구조 파일 시스템 기법을 사용하여 이 정보를 저장합니다.

공간맵은 할당과 반환의 모든 블록의 활동을 계수 형식으로 시간 순서로 기록합니다.

메타슬랩으로부터 공간을 할당하거나 반환하려고 할 때, 관련된 공간맵을 변위에 따라 색인된 균형-트리 형태로 메모리에 적재하고, 로그를 재실행하여 이 구조에 반영합니다. 이를 통해 메타슬랩의 할당과 반환 상태를 정확히 표현합니다.

또한 ZFS는 연속된 가용 블록을 결합하여 하나의 항으로 만들어 맵을 가능한 한 압축합니다.

마지막으로 ZFS의 트랜잭션 기반 연산의 일부분으로 디스크에 존재하는 가용 공간 리스트가 갱신됩니다.

5.6 사용하지 않는 블록 트림

HDD 및 기타 저장 매체는 업데이트를 위해 블록을 덮어 쓸 수 있도록 가용 공간 관리를 위한 가용 리스트만 필요합니다.

NVM 플래시 기반 저장장치와 같이 덮어쓰기를 허용하지 않는 저장장치는 동일한 알고리즘을 적용하면 굉장히 고생해야 합니다.

이러한 장치는 다시 쓰기 전에 삭제해야 하며 이러한 삭제는 큰 청크 단위로 이루어져야 하며 읽기 또는 쓰기와 비교할 때 상대적으로 오랜 시간이 걸립니다.

파일 시스템이 페이지가 비어 있고 페이지를 포함하는 블록이 완전히 비어있는 경우 삭제될 수 있다는 것을 장치에 알릴 수 있는 기법이 있다면, 저장장치가 가득 차기 전에 가비지 수집과 삭제 단계를 수행할 수 있을 것입니다.

이러한 기능을 제공하는 것이 TRIM 혹은 unallocate 명령입니다.

이후 저장장치공간의 할당을 위한 기법으로 inode의 사용과 cluster에 대해서 설명하고 있습니다. 또한 성능을 위해서 프로세스를 위한 메모리와 파일을 위한 메모리의 버퍼를 구분하지 않고 통합 버퍼 캐시를 사용함으로써 페이지 캐시를 통해 효율을 높입니다. 이것은 이중 캐싱(double caching)을 피하게 해줍니다.

쓰기 작업의 경우 버퍼 캐시에 쓰여지고, 후에 캐시에 저장된 데이터가 저장 장치에 반영되는 비동기식 쓰기로 동작한다는 것을 명심해두자. 메타데이터 쓰기 작업은 통상 동기식으로 수행된다.

마지막으로 저장장치의 복구를 위해서 로그 구조 파일 시스템과 스냅샷에 대해서 언급하고 있습니다. 로그 기반을 사용하는 방식은 실제로 많이 사용되고 있는 방식이며 높은 견고성을 가지고 있고, 빠르다는 이점을 가지고 있습니다.

참고한 자료

• 운영체제[공룡책]