파일시스템의 할당 이론

파일을 사용 후 보조 저장장치에 영구적으로 저장하게 됩니다. 저장공간에 어떻게 파일 시스템을 적용하여 할당, 반납 그리고 파일의 구조를 정하는지 설명합니다. 

 여기서 파일 시스템이 적용되는 보조 저장장치의 특성은 대용량이며 별다른 작업이 없는 한 영구적입니다. 과거 하드디스크, 테이프가 주류였다면 현재는 비휘발성 메모리(NVM)도 점유율도 높아지고 있습니다. SSD의 동작, 알고리즘은 전혀 다른 방식을 사용하기에 하드디스크와 별다른 제어 방법이 필요합니다. 

 

파일 시스템 기본

 NVM 구조는 기존 디스크와 다르기 때문에 다른 방식을 사용합니다. 여기서는 디스크의 기준으로 설명합니다. 파일 시스템은 쉽게 데이터를 저장하고 찾기 위한 작업을 효율적으로 사용하게끔 합니다. 파일 시스템에서 단계를 나누면 논리적 파일 시스템 / 파일 - 구성 무듈 -기본 파일 시스템 - 입출력 제어 - 장치로 나눌 수 있습니다.

 논리 파일 시스템에서는 파일이 어떤 것인지에 대한 메타 데이터를 가집니다.

 기본 파일 시스템에서는 장치 드라이버에게 저장장치의 블록을 읽고 쓰는 명령을 내립니다. I/O 스케줄링을 고려하여 논리 블록을 주소를 기반으로 명령을 내립니다. 또한 파일 시스템, 디렉터리와 데이터 블록을 저장하는 메모리 버퍼와 캐시를 관리합니다.

 입출력 제어층은 장치 드라이버 루틴과 인터럽트 핸들러로 이루어져 있습니다. 때문에 메모리와 디스크 시스템 간 정보 전송을 수행합니다. 장치 드라이버가 어떤 명령을 받으면 그 명령어에 맞게 하위 수준으로 변환합니다. 보통 입출력 제어기 메모리의 특정 위치에 비트를 설정합니다. 입출력 장치의 구조는 추후에 정리합니다.

 

파일 시스템 구조 요소

파일 제어블록 FCB

 통상 파일 제어 블록은 다음을 가집니다. 파일 권한, 파일 날짜, 파일 소유자, 크기, 데이터 블록 혹은 데이터 블록을 가리키는 포인터

통상적인 FCB 구조

부트 블록

 시스템이 해당 파티션에서 운영체제를 부팅하기 위한 필요한 정보를 가지는 곳입니다. 일반적으로 첫 번째 블록에 할당하며 운영체제를 가지지 않는 파티션의 경우 비워둡니다. windows 운영체제에서는 파티션 부트섹터라 합니다.

볼륨 제어블록

볼륨의 블록 수, 블록의 크기, 가용 블록의 수와 포인터, 가용 FCB와 포인터 등 같은 볼륨 정보를 가집니다.

 

 

할당 방법

 파일들을 저장공간에 어떻게 배치하느냐에 따라 혹은 어떤 방식의 알고리즘을 사용하에 따라 성능과 저장공간의 효율적인 할당을 할 수 있습니다. 여기서 연속 할당, 연결 할당, 인덱스 기법을 설명합니다.

 

연속 할당

 연속 할당은 파일들이 연속적으로 할당하게끔 합니다. 하드디스크의 경우 찾기 할 때 우수한 성능을 가질 수 있습니다. 불필요한 탐색을 줄이게 되면서 탐색 시간이 최소화됩니다. 

연속할당

 연속 할당 기법을 쓴다면 발생하는 문제로 가용 공간을 어떻게 찾고 관리하는 문제가 발생합니다. 이것은 메모리 관리에서 동적 할당 문제와 같은 유형으로 볼 수 있습니다. 상황에 따라 최초 적합과 최적 적합을 전략을 사용할 수 있습니다.

 연속 할당에서 할당을 하다 보면 외부 단편화가 발생합니다. 외부 단편화를 해결하기 위해서 블록들을 다시 재할당 시켜 밀집화를 시키는 방법이 존재합니다.

 또 다른 문제로는 최적 적합으로 할당을 했다면 확장하기 어렵다는 점이 있습니다.  더 많은 공간을 할당하고 이전 할당을 해제해야 합니다. 이런 방법은 매우 비효율 적이고 시스템을 느리게 합니다. 이 문제는 추가 블록을 사용하여 추가 할당의 경우 추가 블록을 사용하여 포인터로 기록하는 방법을 사용할 수 있습니다. 유닉스 파일 시스템의 경우 이 방법을 사용합니다. 

 

 

연결 할당

 연결 할당은 연속 할당의 대부분의 문제를 해결 가능합니다. 연속 할당의 추가 확장하는 문제도 연결 할당의 일부라 할 수 있습니다. 이 기법은 연결 리스트 형태로 저장하고 실제 공간은 흩어져서 할당됩니다.

연결 할당

 연결 할당 기법은 디스크 밀집화를 할 필요도 없고 추가 확장 문제도 문제없이 수행 가능합니다. 다만 직접 접근을 할 때 매우 비효율적이라는 단점이 존재합니다. 순차 접근의 경우에만 효과적이며 직접 접근의 경우 HDD 탐색이 필요하게 됩니다.

 포인터로 인한 저장공간 차지 문제가 발생합니다.

 신뢰성에 문제도 존재합니다. 포인터를 잃어버리게 되면 모든 데이터를 잃게 됩니다.

 직접 접근 문제의 경우 클러스터 단위 할당을 통해 어느 정도 해결 가능합니다. 여러 블록을 한 번에 묶어 순차적으로 할당하는 방법입니다. 보통 4블록 정도를 묶어 클러스터 단위로 할당하는 방식입니다. 이렇게 되면 포인터로 사용되는 공간이 줄어들고 HDD 탐색 또한 줄어들게 됩니다.

 

 

색인 할당

 연결 할당은 직접 접근 방식이 어렵습니다. 파일 할당 테이블을 지원하지 않는 한 연결 할당은 직접 접근에서 최악의 효율을 보여줍니다. 그 해결로 색인 할당방법이 존재합니다. 연결 할당의 포인터들을 한 블록에 모은 것과 같습니다. 

색인할당

 

각 파일은 색인 블록을 가지게 되고 색인 블록의 n번째는 x블록을 가리킵니다. 처음 할당될 때 모든 포인터는 null로 초기화됩니다. 그 후 가용 블록 관리자로부터 블록을 할당받고 그 블록의 주소를 인덱스 블록에 저장합니다. 색인 할당의 문제는 색인 블록의 오버헤드가 크다는 점입니다. 이는 연결 할당의 낭비보다 큰 수준입니다.

 

 그 해결 실 사례로 inode가 있습니다. 

inode