[운영체제] 파일 시스템

오늘은 파일 시스템에 대해서 알아보겠습니다.

 

 

 

   파일 시스템

파일 시스템은 파일을 저장하는 거대 자료구조로, 여러 물리적인 파일의 종류별로 효율적인 관리를 위해 사용되는 시스템입니다.

 

리눅스 운영체제 기준으로 파일 시스템에는 boot block, super block, FCB list(inode list), data blocks가 있습니다.

 

 

Boot Block

boot block은 최초 운영체제 실행 시, 보조기억 장치에서 운영체제 이미지를 불러와 실행시키는 역할을 합니다. 

 

운영체제 최초 실행 시, boot block을 메인 메모리로 복사하고 OS의 위치를 파악합니다. 이후, 보조기억장치에서 OS의 위치로 접근하여 OS를 메모리에 로드합니다. 이렇게 되면 OS가 최초로 실행하는 다양한 작업(프로세스 생성, 이미지 압축 해제 등)을 마친 후 사용자가 운영체제를 접근할 수 있습니다.

 

 

 

Super Block(Partition Control Block)

file system에 대한 정보를 갖습니다.

 

file system의 사이즈가 얼마인지, file system 내의 어느 data block이 비어있는지, FCB는 몇개인지.. 등과 같은 여러 메타데이터를 저장하는 영역입니다.

 

 

FCB List

FCB를 리스트로 연결하여 저장합니다. FCB에 대한 내용은 아래 링크를 참고해주세요!

2023.10.28 - [Computer Science/운영체제] - [운영체제] File

 

 

Data Blocks

실질적인 파일의 데이터가 저장되는 곳입니다. block들의 연결로 구성되어 있고, 각 block마다 파일의 내용이 들어있습니다. 하나의 block당 통상 4Kb이며 운영체제는 파일의 내용을 어느 block에 할당해야하는지와 같은 File Allocation의 방식을 선택해야합니다.

 

 

 

   Methods of File Allocation

파일의 내용을 block에 할당하는 방식으로 3가지를 소개합니다.

 

   Contiguous allocation

어느 block의 주소부터 시작하여 어디까지 파일의 내용을 차지하고 있는지를 File Allocation Table을 통해 나타냅니다. 각 file은 연속적인 주소값으로존재합니다. 아래와 같은 예시가 되겠습니다.

 

Contiguous Allocation

 

File Allocation Table에는 어떤 파일이 어느 block의 시작부터 몇개를 차지하는지를 나타냅니다. 왼쪽의 data blocks에 각 파일들이 배정된 모습을 볼 수 있죠.

 

하지만 이 방식은 단점이 너무 많아 현재는 사용하지 않습니다. 해당 방법의 장단점을 알아봅시다.

 

+) Direct access

마치 배열 형태로 저장되는 것으로 볼 수 있는 방식입니다. 왜냐하면 이 방식은 어떤 파일의 시작 주소로부터 연속적인 주소로 데이터가 존재하므로, 우리가 원하는 index를 매우 빠르게 접근할 수 있기 때문입니다.

 

-) File grow problem

위 상황에서 만약 파일 C에 추가적인 데이터를 저장한다면 어떻게 될까요?? 아마 연속적으로 저장이 불가능하므로, Data Blocks에서 증가된 File C의 길이를 수용할 수 있는 연속적인 data block 길이를 찾을 것입니다. 찾았다면 해당 파일을 그대로 복사하여 진행해야하므로 매우 큰 단점으로 작용합니다.

 

-) External Fragmentation

Fragment는 어떤 저장공간에 데이터 할당이 불가능한 작은 빈 공간을 의미합니다. 이러한 작은 빈 공간이 생기는 현상이 Fragmentation이고, Fragmentation이 파일 외부에 생기는 현상을 External Fragmentation이라고 합니다.

 

위의 그림에서 마치 29번 block과 같은 부분이 external Fragmentation이 되겠군요(다른 것도 가능합니다). 이 현상은 Contiguous Allocation에서 아주 큰 단점입니다.

 

우리가 block 5개를 차지하는 어떤 file을 작성하고 싶다면 아마 위 그림에서의 data blocks에는 작성할 수 없을 것입니다. 빈공간이 저렇게도 많은데 말이죠.

 

 

따라서 이 방식은 현재 사용되지 않는 방식입니다.

 

 

   Chained Allocation

Linked List를 이용하여 해당 block에서 다음 저장된 데이터의 block 주소를 저장하여 연결하는 방식입니다.

 

마치 트리 자료구조를 구현할 때 배열을 사용할지, Linked List를 사용할지와 같은 차이라고 봐도 되겠습니다.

아래와 같은 방식이 될 것입니다.

Chained Allocation

File Allocation Table에 저장되는 내용은 동일하지만, 각 block에 다음 block을 가리키는 주소가 저장되게 됩니다.

 

장단점을 알아봅시다.

+) No External Fragmentation

한 블럭이라도 비어있기라도 한다면, 연속하여 배정할 수 있으므로 이 문제를 해결할 수 있습니다.

 

+) No File Grow Problem

이 또한 위와 동일합니다.

 

-) No Direct access

Linked List를 이용하므로 데이터 block의 직접 접근이 불가능하게 됩니다.

 

-) Poor data Safety

만약 데이터가 이어지는 중간에 어느 한 block이 access error가 났다면, 그 다음 데이터조차도 읽을 수 없게 됩니다.

 

 

   Indexed Allocation

최근 가장 많이 사용되는 방식으로, block 중 하나를 File에 쓰이는 block의 주소를 저장하는 용도로 씁니다. 아래 그림을 보고 계속 설명하겠습니다.

앞서 두가지 방식과는 조금 다른 형태의 File Allocation Table을 갖고있음을 알 수 있습니다. 여기서는 어떤 File의 정보가 어떤 block에 쓰여있는지를 나타냅니다. 즉, File B에 대한 block 정보는 24번에 쓰여있죠.

 

24번 block에 쓰여있는 정보 순서대로 데이터들이 존재하게 되고, OS는 이것을 보고 원하는 데이터를 읽어올 수 있게 되는 것입니다.

 

장단점을 알아봅시다!

+) No File Grow Problem

Linked List의 성질을 그대로 이용하므로 성립합니다.

 

+) Direct Access

24번 block에 배열 형태로 File의 block 순서를 기록하였으므로 빠르게 접근할 수 있습니다.

 

+) No External Fragmentation

Linked List의 성질을 그대로 이용하므로 성립합니다.

 

-) Capacity of Block

File의 block 정보를 나타내기 위해 block 1개를 더 소모해야하므로, 전체 수용량이 적어집니다.

 

 

   Free-Space Management

만약 파일을 작성한다면, 해당 파일을 어느 block에 배정할지를 결정하기 위해서 어느 block이 비어있는지(free 상태인지)에 대한 정보를 가지고 있어야합니다.

 

그러한 관리방법을 다뤄보겠습니다. 사실 이 방식은, 파일을 할당하는 방식과 유사한 부분이 많아 간단하게 설명하겠습니다.

 

Counting

Contiguous Allocation 방식과 유사합니다. Free block의 주소와 해당 block으로부터 몇개까지가 free한지를 나타내는 table을 갖고있으면 됩니다.

Free Block Table

 

 

Linked List(Free List)

Chained Allocation 방식과 유사합니다. 가장 head에 어느 block이 비어있는지를 가리키고, 해당 block으로 가면 다음 비어있는 block이 어디인지를 가리키는 방식으로 진행됩니다.

 

 

여기서는 Direct Access가 단점으로 작용하지 않습니다.

 

우리가 빈 공간을 파악하는 이유는 단지 비어있는 공간에 데이터를 작성하기 위해서이지, 빈 block 중 어디에 배치해야할지를 고려할 필요는 없기 때문입니다.

 

따라서, 여기서는 head가 가리키는 block을 계속 할당해주는 방식으로 진행합니다.

 

 

 

 

 

Grouping

Indexed Allocation과 유사합니다.

 

Super Block List에 비어있는 block의 주소를 순차적으로 저장하는데, 만약 Super Block List의 최대 크기인 4Kb를 넘을만큼 많은 free-block이 있다면, 우리는 Super Block List의 가장 앞에 가리키는 주소에 추가적으로 free-block의 정보를 저장합니다. 아래와 같은 방식이 되겠습니다.

Super Block의 제일 첫 109번은 계속해서 free-block을 나타내는 block을 가리킵니다. 여기서는 Super Block, 109번 block, 211번 block에 free-block을 저장하고 있습니다.

 

데이터를 작성하고 싶다면 Super Block의 가장 끝에서부터 진행합니다. 4번이 쓰여지고, 5번이 쓰여지고... 이런 식으로 반복하다보면, Super Block이 비게 되는 경우가 있을 것입니다.

위의 그림의 상태에서 block에 내용을 작성해야한다면, Super Block List가 비어있게 됩니다. 이 때는, 109번 block에 있는 내용을 Super Block List에 그대로 복사한 후에, 109번지에 우리가 쓰고싶은 내용을 작성하는 방식으로 진행됩니다.

 

아래와 같은 형태로 변경될 것입니다.

 

Bit Vector

모든 block의 개수만큼의 비트를 갖고, 해당 비트를 통해서 block이 free인지 아닌지를 저장합니다.

만약 i번째 비트가 free하다면 1의 값을 갖고, 그렇지 않다면 0의 값을 갖습니다.

 

통상 우리는 free할 때 0의 값을 가질텐데 왜 이렇게 설정했는지 의문점이 들 수 있는데, 이유는 0을 확인하는 것이 1을 확인하는 것보다 더 빠르기 때문입니다. 따라서, 사용 중인 block은 빠르게 pass할 수 있기 때문이죠.