[운영체제] File System Implementation

파일 시스템은 디스크로의 효율적이고 편리한 접근을 제공합니다. 하지만 이 파일 시스템을 설계함에 있어서는 2가지 고려해야 할 사항이 존재합니다. 첫 번째는 파일 시스템이 사용자에게 어떻게 보여야 할지 정의하는 것입니다. 다시 말해, 파일의 이름이나 id와 같은 속성, 파일에 허용된 연산, 디렉터리 구조 등을 정의하는 것입니다. 두 번째는 파일들을 실제 저장 장치인 디스크에 어떻게 저장하느냐 하는 것입니다. 즉 디스크의 어떤 블록에 해당 파일을 저장할지를 결정해주는 것입니다. 이 글에서는 이 두 번째 문제에 집중하여 파일 시스템의 구현을 다뤄볼까 합니다.

 

1. 파일 시스템 자료 구조 (Data Structure for File System)

우선 디스크에서 블록이 무엇인지부터 살펴보겠습니다. 블록(block)이란 정보를 담는 디스크의 한 물리적인 공간을 뜻합니다. 일반적으로는 512B의 크기를 가지며, 하나 이상의 섹터(sector)로 이루어져 있습니다. 디스크와 메모리 사이에 데이터 전송을 실행할 때 이 블록을 최소 단위로 사용합니다.

 

우선 디스크 상의 구조(On-disk Structure)에 대해 살펴보겠습니다. 디스크는 파티션 또는 볼륨이라는 독립적인 공간들로 나누어서 사용됩니다. 그리고 지금 알아볼 구조는 한 볼륨을 구성하는 요소에 대한 것입니다. 파티션과 볼륨은 의미적으로 조금 차이가 있긴 하지만, 굳이 나누지 않고 같은 개념으로 보겠습니다.

 

 

부트 제어 블록 (Boot control block): 해당 파티션의 운영체제가 시스템을 부트 시키는 데에 필요한 정보를 가지고 있습니다. 디스크가 운영체제를 가지고 있지 않다면, 당연히 부트 제어 블록은 비어있게 됩니다.

 

볼륨 제어 블록 (Volume control block, Super block): 파티션에 속한 블록의 수, 블록의 크기 등 파티션에 대한 정보를 저장하고 있습니다.

 

FCB(File Control Block): Unix와 Linux에서는 i-node라고도 불리는 FCB는 파일의 메타 데이터, 즉 파일에 대한 자세한 정보를 담고 있습니다. 파일의 타입, 소유자, 소유 그룹, 접근 허용 정보, 시간 정보, 파일의 크기 등의 정보를 가지며, 가장 중요한 데이터 블록에 대한 포인터들을 가집니다. 

 

데이터 블록: 실제 데이터를 저장하는 역할을 합니다.

 

2. 파일 생성 및 파일 열기

파일을 생성하고 여는 과정을 한번 공부해보는 것으로 위에서 공부한 내용을 정리해 보겠습니다. 

 

사용자가 creat() 함수와 같은 파일 생성 명령어를 실행시키면 운영체제는 FCB Table 중에서 비어있는 하나의 블록을 골라서 FCB(i-node)를 만들어줍니다. 그리고 그 FCB에 만들고자 하는 파일의 정보들을 입력해 줍니다. 그리고 파일을 저장하는 데에 필요한 만큼의 데이터 블록들을 할당받고, 할당받은 블록들에 대한 블록 번호를 FCB에 저장해줍니다. 그리고 운영체제가 디렉터리를 업데이트해주면 파일 생성이 완료됩니다.

 

파일을 열 때는 우선 커널에 있는 system-wide open-file table에 원하는 파일의 FCB가 있는 지 찾아봅니다. 그리고 존재한다면, 해당 FCB에 대한 인덱스 값을 per-process open-file table로 가져와서 추가시켜 줍니다. System-wide open file table은 전체 시스템에서 열려있는 파일들에 대한 FCB를 저장하고 있는 테이블이고, per-process open-file table은 말 그대로 프로세스가 열고 있는 파일의 목록에 대한 테이블입니다.

 

만일 원하는 파일이 system-wide open file table에 없다면, 디렉터리 구조에서 검색을 해야합니다. FCB 테이블에서 원하는 FCB를 찾아서 system-wide open file table과 per-process open-file table에 차례로 등록을 시켜준 뒤, 해당 인덱스를 반환해줍니다. 

 

3. 디스크 블록 할당 방법 (Disk Block Allocation Methods)

이번에는 디스크의 블록을 어떻게 할당하는지에 대한 여러가지 방법들을 알아보겠습니다.

 

1. Continuous Allocation

 

말 그대로 연속적인 블록들을 할당하는 방법입니다. 무조건 15번 블록부터 19번 블록과 같은 형태로 이어진 순서의 블록들을 할당해 줄 수 있습니다. 시작 블록의 번호와 몇 개의 블록을 사용하는지를 이용해 블록들을 정의할 수 있으며, 블록들이 모두 바로 옆에 있기 때문에 디스크 탐색 시간이 줄어든다는 장점이 있습니다. 대신 앞에서 메모리에서 배웠던 것처럼 External fragmentation이 발생할 수 있고, 얼마나 많은 공간을 사용할지를 미리 알고 할당을 시켜줘야 합니다.

 

2. Linked Allocation

 

연결 리스트처럼 시작 블록을 지정하고, 각 블록들은 다음 블록에 대한 포인터 값을 가지는 것으로 디스크 공간 할당을 진행할 수 있습니다. 블록들은 꼭 붙어 있을 필요가 없고 여기저기에 흩어져있지만, 서로를 포인터로 연결하고 있는 형태입니다. 이러한 경우에는 external fagmentation이 발생할 일이 없고, 굳이 처음에 얼마만큼의 공간을 사용할지 지정을 해주지 않아도 됩니다. Sequential 한 형태의 접근에는 효과적이지만, 중간에 있는 특정 블록에 접근하기 위해서는 첫 블록부터 차례로 따라가서 접근해야 하기 때문에 비효율적일 수 있습니다.

 

3. Indexed Allocation

 

Linked Allcation처럼 블록들은 여기저기 흩어져있지만, 이를 연결 리스트로 연결하는 것이 아닌, 모든 블록들의 주소를 하나의 블록에 저장하고 관리하는 형태입니다. 이렇게 파일의 모든 블록들의 인덱스를 저장하고 있는 블록을 index block이라고 하고, 특정 블록에 접근하기 용이해집니다. 하지만 정말 작은 파일을 저장할 때도 index block을 만들어야 하기 때문에 공간을 낭비할 수 있습니다.

 

4. Free-Space Management

마지막으로 살펴볼 내용은 할당되지 않은 공간을 관리하는 방법입니다. 어떤 디스크의 공간이 비었는지를 알고 있어야 필요할 때 할당을 해 줄 수 있기 때문에, 이 할당되지 않은 공간을 모두 알고 있어야 합니다.

 

첫 번째 방법은 bit vector를 이용하는 방법입니다. 그냥 모든 블록들을 쭉 나열해서 쓰고 있는 블록은 1, 아직 쓰지 않는 블록은 0으로 표시하여 나타내는 방법입니다. 당연히 구현이 간단하고 효율적이지만, 디스크 사이즈가 커지면, bit vector의 크기도 커지게 되고, 메모리에 담을 수 없을 수 있습니다.

 

두 번째는 연결 리스트를 사용하는 방법입니다. 비어있는 블록들 중 가장 앞에 있는 블록으로부터 시작해, 다음 비어있는 블록을 가리키는 포인터를 만들어서 연결하는 방법입니다. 위에서 살펴본 Linked Allocation과 동일한 문제점들을 가지고 있고, 각각의 블록들이 포인터를 저장할 공간을 따로 가지고 있어야 합니다.

 

세 번째는 grouping입니다. 비어있는 블록들 중 하나의 블록이 n게의 비어있는 블록의 포인터를 저장하고 있는 형태입니다. 그리고 저장된 블록들 중 마지막 블록이 다음 n개의 블록의 포인터를 저장할 블록에 대한 인덱스를 가집니다. 이 방법을 이용하면 중간에 비어있는 블록을 찾을 때 훨씬 빠르게 찾을 수 있습니다.

 

마지막으로 counting은 Continuous Allocation에서 사용할 수 있는 방법으로, 비어있는 블록들의 시작 블록의 주소만 저장하고 있는 형태입니다.

 

 

 

 

여기까지 운영체제의 전반적인 공부를 마쳤습니다. 운영체제에 대한 마지막 글이다 보니 조금 빠르게 넘어간 감이 없지 않아 있긴 하지만, 조금이나마 운영체제 공부에 도움이 되었으면 좋겠습니다. 읽어주셔서 감사합니다.