[Chapter 11. 파일 시스템 구현] 파일 시스템, 디스크 공간 할당 방법과 자유 공간의 관리

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

가상 메모리 시스템은 파일의 추상화를 기반으로 동작한다.

 

즉, exe 파일을 구성하는 블록들이 프로세스의 페이지로 맵핑되어 하나의 프로세스로 나타나도록 추상화되는 것이다.

* exe 파일 : 컴퓨터의 실행 파일

 

또한 모든 입출력 장치들은 장치 파일이라는 개념으로 일관성 있게 추상화된다.

예를 들어, 동작 센서도 특수한 형태의 파일로 생각하여

이에 대해서도 일반적인 파일에 대한 조작인 open/close 및 read/write 등의 조작을 하게 된다.

 

이 추상화의 실현을 위하여 파일 시스템이 존재하는 것이다.

 

파일 시스템 (File System)

---

파일 시스템은 데이터를 쉽게 저장하고, 찾고, 인출할 수 있게 함으로써 디스크를 보다 효율적이고 편리하게 사용할 수 있게 한다.

 

저장 장치는 선형적인 주소를 가진 바이트의 블록만을 저장하는데,

파일 시스템은 저장 장치와 응용 프로그램 간의 자료구조 차이점을 해결해준다.

 

파일 시스템의 추상화 제공 방법

 

 

저장 장치는 파일을 블록들로 나누어 섹터에 저장한다.

 

* Stream-block Translation

기억 장치의 블록을 음수가 아닌 정수 값을 갖는 연속된 주소를 가진 바이트의 집합으로 변환한다.

다양한 추상화를 제공해주기 위한 핵심 부분

 

* Record-stream Translation

바이트 스트림 파일을 응용 프로세스의 자료구조로 변환한다.

* 바이트 스트림 파일 : 정수 주소를 갖는 바이트의 집합

 

디스크 공간 할당 방법

---

디스크의 직접 접근 특성이 파일의 구현에 융통성을 허용한다.

파일들을 디스크 공간에 어떻게 배치하느냐에 따라 해당 공간을 효율적으로 사용할 수 있고, 파일들을 더 빨리 접근할 수 있다.

 

디스크 공간을 할당하기 위해서는 크게 연속 할당, 연결 할당, 색인(인덱스) 할당 기법이 존재한다.

 

일부 시스템들은 세 가지 모두를 제공하지만, 일반적으로 한 가지 기법만을 사용한다.

 

연속 할당 (Contiguous Allocation)

연속 할당은 각 파일이 디스크 내에서 선형적으로 연속된 블록을 차지하도록 할당해주는 방법이다.

한 파일의 연속 할당은 디스크 주소와 블록 단위의 길이로 정의된다.

 

 

장점

1. 연속하는 논리적 블록들이 물리적으로 인접하여 있기 때문에 탐색 시간이 최소화된다.

 

2. 순차 접근, 직접 접근이 가능하다.

파일의 길이가 n 블록이고 블록 b에서 시작한다고 하자.

블록 b에서 시작하는 파일의 'i번째 블록을 직접 접근'하기 위해서는 블록 b+i를 즉시 접근할 수 있다.

 

 

3. 디렉터리는 구현이 단순화된다.

단순하게 시작 블록의 주소와 블록 개수만 유지하면 된다.

 

단점

1. 새로운 파일의 생성을 위해서는 필요 공간의 크기를 미리 명시해야 한다.

만약 원하는 만큼의 연속된 공간이 확보되지 않으면 파일 생성이 불가능해진다.

 

2. 한 파일이 사용 중에 할당된 공간보다 커질 때, 그 파일이 들어갈 수 있는 새로운 영역으로 옮겨가야 한다.

 

3. 단편화가 발생한다.

(1) 외부 단편화

파일의 생성과 삭제가 반복되면서 가용 공간의 단편화가 발생하기 때문에 주기적인 압축이 필요해진다.

 

(2) 내부 단편화

예상되는 확장을 대비하기 위해 사용자는 필요한 공간보다 더 많은 여분의 공간을 확보하려고 하기 때문에

기억 공간의 낭비가 생긴다.

 

4. 파일의 크기가 계속 변하는 경우 구현이 복잡해진다.

 

연속된 공간을 할당해야 하기 때문에 여러 문제가 발생하게 된다.

 

연결 할당 (Linked Allocation)

한 파일의 저장을 위한 블록들이 디스크 내의 어느 곳에 흩어져 있어도 접근이 가능한 동적 할당 기법이다.

 

파일은 디스크 블록의 연결 리스트 형태로 저장되고, 각 블록은 다음 블록을 가리키는 포인터를 포함한다.

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

 

 

장점

연결 할당은 연속 할당의 모든 문제를 해결한다.

 

연결 할당에서는 압축이 필요하지 않으며,

어떤 파일이 더 확장되어야 할 때 가용 공간 리스트로부터 블록을 얻어 리스트에 추가하기만 하면 된다. (단편화가 발생하지 않음)

 

단점

1. 파일의 블록들이 디스크 전체에 분산되어 있으므로 검색에 긴 시간이 필요하다.

순차적 접근 파일에만 효과적으로 사용될 수 있고, 직접 접근 방식은 지원이 불가하다.

 

2. 연결된 리스트 내에 있는 포인터들을 위한 공간이 필요하기 때문에 기억 장소가 낭비된다.

 

3. 신뢰성의 문제

각 블록들이 전체 디스크에 흩어져 연결되기 때문에

오류나 하드웨어 고장으로 하나의 포인터를 잃어버리거나, 잘못된 포인터 값을 가지게 된다면 모든 데이터를 잃어버리게 될 수도 있다.

 

이 경우, 이중 연결 리스트(doubly linked list)를 사용하거나

블록마다 파일 이름과 상대적인 블록 번호를 저장하는 대안책들이 존재하지만

이들은 오버헤드를 필요로 한다.

 

---

위의 단점들을 보완하기 위해서 파일 할당 테이블(File Allocation Table, FAT)을 사용한다.

(MS-DOS에서부터 사용)

 

각 파티션의 시작 부분이 FAT로 사용된다.

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

 

디렉터리 항목은 각 파일의 첫 번째 블록 번호를 가리키고,

FAT 항목이 다음 블록의 블록 번호를 가리키는 것으로 사슬 역할을 한다.

 

이러한 사슬은 마지막 블록까지 계속되며, 마지막 블록의 테이블 항은 파일의 끝을 나타내는 특수한 값을 갖고 있다.

 

 

 

파일에 새로운 블록을 할당할 경우, 값이 0인 테이블 항을 찾아 이전 파일의 끝 값을 새로운 블록의 주소로 대체하면 된다.

 

색인 할당 (Indexed Allocation)

연결 할당은 연속 할당의 단편화 문제와 파일 크기(size) 선언 문제를 해결했지만, FAT가 없다면 직접 접근 방식을 지원할 수 없다.

이 문제점을 해결하는 것이 색인 할당 방법이다.

 

각 파일들은 디스크 블록 주소(= 포인터, 섹터 주소)를 모아놓은 배열인 색인 블록(index block)을 가진다.

* 색인 블록의 기능은 메모리 경영에서의 페이지 테이블의 기능에 해당

 

i번째 블록을 읽기 위해서는 색인 블록 항목에 있는 i번째 항목에서 포인터를 얻어 그 블록을 읽는다.

* 페이징 기법과 유사

 

디렉터리는 그 디렉터리에 속한 각 항목의 색인 블록에 대한 포인터를 소유한다.

 

 

장점

1. 탐색이 색인 블록 자체에서 일어나기 때문에 속도가 빠르다.

색인 블록을 주 기억 장치에 유지시켜 탐색 시간을 더 줄일 수 있다.

 

2. 단편화 없이 직접 접근을 제공한다.

 

단점

1. 파일을 중간에 삽입하고자 할 경우 색인 블록을 완전히 재구성해야 한다.

 

2. 공간의 낭비가 문제가 된다.

작은 파일에도 하나의 색인 블록이 할당되어야 하며,

향후 파일 삽입을 위해 색인 블록을 비워둔 채로 남겨 놓기도 하는데 이는 기억 장치의 낭비를 일으킨다.

 

2. 하나의 색인 블록으로 모든 블록을 색인할 수 없을 정도의 큰 파일은 저장할 수 없다.

 

---

색인 할당 방법은 파일 크기에 대한 단점이 있었다.

이를 보완하는 UNIX-기반 파일 시스템에서 사용되는 방법으로 혼합 색인(combined scheme) 방법이 있다.

(직접 블록 + 간접 블록)

 

 

파일의 inode에 색인 블록의 15개 포인터를 유지한다.

* inode : 전통적인 유닉스 계통 파일 시스템에서 사용하는 자료구조

 

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

 

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

 

 

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

 

1. 첫 번째 포인터는 단일 간접 블록(single indirect block)을 가리키는데,

이 블록은 데이터를 저장하고 있는 블록의 주소를 저장하는 것이다.

 

2. 두 번째 포인터는 이중 간접 블록(double indirect block)을 가리키는데,

이 블록은 실제 데이터 블록을 가리키는 포인터를 저장하고 있는 블록의 주소를 저장한다.

 

3. 마지막 포인터는 삼중 간접 블록(triple indirect block)의 주소를 저장한다.

 

 

자유 공간의 관리 (Free-Space Management)

---

디스크의 공간은 제한되어 있기 때문에 삭제된 파일들이 차지하던 공간들은 새로운 파일들을 위해 재사용되어야 한다.

시스템은 이런 자유 공간들을 자유 공간 리스트로 유지하고 관리한다.

 

새로운 파일을 만들기 위해서는 자유 공간 리스트를 탐색하여 공간을 할당받아야 하며, 이때 해당 공간은 리스트에서 제거된다.

추후 이 파일이 삭제되면 그 파일이 쓰던 공간은 자유 공간 리스트에 추가된다.

 

연결 리스트 (Linked List)

모든 자유 디스크 블록들을 연결시키는 방법이다.

 

맨 먼저 나오는 빈 공간(자유 블록)에 대한 포인터를 운영체제가 알고 있고,

그로부터 다음 빈 공간에 대한 포인터를 가지게 한다.

 

 

적당한 위치의 자유 블록을 찾기 위해서 포인터를 따라가야 한다는 성능상의 한계가 존재한다.

 

하지만 자유 공간 리스트를 탐색하는 일은 빈번하게 일어나지 않고, 통상 하나의 자유 블록만을 요청한다.

따라서 리스트의 첫 번째 블록을 할당해주는 것으로 해결이 가능하다.

 

그룹핑 (Grouping)

다수 개의 자유 블록 주소를 찾기 위해서 포인터를 계속 따라가야 하는 연결 리스트 방법의 단점을 보완하는 방법이다.

 

맨 처음 자유 블록 내에 n개의 블록 주소를 저장한다.

 

이 중 n-1개는 실제로 비어있는 블록의 주소이며,

마지막 한 개는 다른 n개의 빈 공간의 주소를 포함하는 블록의 주소를 기입하는 것으로 서로를 연결한다.

 

그룹핑을 통해 많은 양의 사용 가능 공간을 빨리 찾을 수 있다.

 

 

비트맵(Bit Map) / 비트 벡터(Bit Vector)

자유 공간 리스트는 흔히 비트맵 또는 비트 벡터로 구현된다.

 

각 블록은 1비트로 표현된다.

블록이 자유로워지면 1, 블록이 할당되어 있다면 0이다.

ex. 블록 2, 3, 5, 6이 사용 중이라면 011011...

 

비트 벡터는 그 전체가 주 메모리 내에 존재해야 효율적으로 사용될 수 있다.

 

계수 (Counting)

계수 방식은 일반적으로 공간이 할당되거나 회수될 때 연속된 블록 단위로 이루어진다는 점을 이용하는 방식이다.

 

모든 사용 가능 블록에 대한 주소를 갖고 있지 않고,

연속된 자유 블록의 첫 번째 블록 주소와 연속된 블록의 개수(count)만 기록한 리스트를 관리한다.

 

이를 통해 자유 공간 리스트의 크기는 작아진다.

 

공간 맵 (Space Map)

Oracle의 ZFS에서 사용하는 방식이다.

 

해당 운영체제의 파일 시스템은 대규모의 파일, 디렉터리, 심지어 파일 시스템도 저장할 수 있도록 설계되었다.

이러한 큰 규모에서는 메타데이터 입출력이 성능에 커다란 영향을 미치게 된다.

 

ZFS는 자유 공간을 관리할 때 자료 구조의 크기를 제어하고,

이 자료 구조를 관리하기 위해 필요한 입출력을 최소화하기 위해서 여러 기법을 조합하여 사용한다.

 

1. 대용량의 공간을 관리 가능한 크기의 덩어리로 나누기 위해 메타 슬랩(metaslabs)을 생성한다.

한 볼륨은 수백 개의 메타 슬랩을 포함하며, 각 메타 슬랩은 연관된 영역의 공간 맵을 가진다.

 

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