파일 할당 방법에 대해서 설명하기에 앞서 파일(File)에 대해서 알아야 할 필요가 있습니다.
파일은 컴퓨터에서 흔히 이용하신 적이 있을 것입니다.
간단하게 설명하자면, 하드 디스크나 SSD같은 보조기억장치에 저장된 의미 있고 관련 있는 정보를 모은 논리적 단위를 말합니다.
그리고 이런 파일들을 일목요연하게 관리하기 위해 디렉터리(Directory)를 이용하며, 윈도우 운영체제에서 디렉터리를 폴더(Folder)라고 부릅니다.
파일과 디렉터리를 보조기억장치에 일목요연하게 저장하고 접근할 수 있게 하는 운영체제 내부 프로그램을 파일 시스템이라고 합니다.
즉, 보조기억장치가 데이터를 관리하는 방식이라고도 생각할 수 있습니다.
운영체제는 파일과 디렉터리를 블록(Block)단위로 읽고 씁니다.
컴퓨터 구조에서 하드 디스크에 대해서 설명했듯이,
가장 작은 단위는 섹터지만, 운영체제는 하나 이상의 섹터를 블록 단위로 묶은 뒤 블록 단위로 파일과 디렉터리를 관리합니다.
하드 디스크내에는 여러 블록이 있다고 가정하며, 파일을 블록에 할당해야 합니다. 이런 상황에서 파일을 보조기억장치에 할당하는 방법에는 크게 두 가지가 있습니다.
연속 할당과 불연속 할당이 존재합니다.
📌 연속 할당
연속 할당(Contiguous Allocation)은 단순하게 연속된 블록에 할당하는 것을 말합니다.
이 연속 할당의 장점은 디스크의 헤더의 이동을 최소화할 수 있기 때문에 I/O 성능을 높일 수 있습니다. 또한 연속 할당에는 특징이 두 가지가 존재합니다.
첫 번째는 순서대로 파일을 읽을 수 있는 순차 접근(Sequential Access)의 특징을 가지고 있고, 두 번째는 직접 접근(Direct Access)이 가능합니다. 순차적으로 저장되어 있으므로 운영체제는 파일의 정보가 담긴 디렉토리에서 얻은 시작 블록 번호로 원하는 블록에 바로 접근할 수 있습니다.
연속 할당은 치명적인 단점이 존재하기 때문에 현재 사용하지 않는 방식입니다.
그 단점은 할당된 파일을 지우고 반복하다보면 중간 중간에 빈 공간이 발생하게 된다는 것입니다. 연속 할당은 연속된 공간을 찾아야 하기 때문에 메모리 할당에서 발생하는 외부 단편화 문제가 발생합니다.
이 외부 단편화가 발생하면 디스크 공간 낭비가 심해집니다.
이외에도 다른 문제는 파일을 저장할 때, 실제 크기를 알 수 없다는 점입니다. 계속해서 사용하는 파일의 경우 크기가 계속 증가 할 수 있기 때문에 이를 연속적으로 할당하기에는 매우 적절하지 못합니다.
📌 불연속 할당
불연속 할당에는 크게 연결 할당과 색인 할당이 존재합니다.
⚡ 연결 할당
연결 할당(Linked Allocation)은 연속 할당의 문제를 해결하기 위해 나온 방식입니다.
바로 Linked List 방식으로 파일을 할당합니다.
각 블록의 마지막에 주소를 저장하는 포인터 공간(4 Bytes)이 존재하며, 여기서 다음 블록 공간을 가리킵니다. 마지막 블록에는 끝임을 나타내는 값이 저장되게 됩니다.
연결 할당을 사용해서 새로운 파일을 할당할 때는 비어있는 임의의 블록을 첫 블록으로 선택하며, 만약 파일이 커지는 경우 다른 블록을 할당해서 기존의 블록과 연결만 해주면 됩니다. 연결 할당은 위치와 상관없이 할당이 가능하므로 외부 단편화 문제가 없다는 특징이 있습니다.
하지만 연결 할당에도 문제점이 존재합니다.
파일의 블록들은 모두 흩어져있기 때문에 시작 블록 번호를 가지고는 원하는 위치의 블록에 바로 접근할 수는 없습니다. 즉, 순차 접근은 가능하지만 직접 접근은 불가능합니다.
또한 포인터를 저장하는 4 bytes 이상의 손실이 발생하게 됩니다.
그리고 중간 블록의 포인터가 끊어지면 그 이후의 모든 블록에 접근하지 못하는 낮은 신뢰성과 블록이 모두 흩어져 있으므로 디스크 헤더의 움직임이 그 만큼 많이 발생하기 때문에 속도가 느리다는 문제점이 존재합니다.
이러한 문제점을 개선하기 위해 나온 것이 같은 연결 할당 방식인 FAT(File Allocation Table) 시스템입니다. FAT 시스템은 다음 블록으로 가리키는 포인터들만 모아서 하나의 테이블(FAT)을 만들어 한 블록에 저장하는 방식입니다.
FAT 시스템을 사용하면 기존의 연결 할당의 문제점 대부분을 해결할 수 있습니다.
FAT을 한 번만 읽으면 직접 접근이 가능하고, FAT만 문제가 없다면 중간 블록에 문제가 생겨도 FAT를 통해 그 다음 블록은 여전히 읽을 수 있습니다.
그렇지만 FAT는 일반적으로 메모리 캐싱을 사용하여 블록 위치를 찾는데는 빠르지만 실제 디스크 헤더가 움직는 것은 블록이 흩어져 있으므로 여전히 느리다고 볼 수 있습니다.
마지막으로 FAT는 매우 중요한 정보이므로 손실 시 복구를 위해 이중 저장을 해야합니다.
FAT의 각 인덱스 크기는 전체 블록의 개수를 저장할 만큼의 크기를 가지고 있어야 하는데, 현재는 일반적으로 32Bit 크기를 사용하며, 이를 FAT32라고 부릅니다.
⚡ 색인 할당
색인 할당 (Indexed Allocation)은 연결 할당과 같이 데이터를 랜덤한 블록 번호에 할당하지만 할당된 블록 번호를 하나의 블록 번호에 저장합니다.
이러한 블록을 인덱스 블록이라고 합니다.
파일 당 하나의 인덱스 블록이 존재합니다. 색인 할당은 디렉토리 정보가 다른 할당과 다르며, 시작 블록 번호를 저장하는 것이 아니라 인덱스 블록 번호를 저장합니다.
색인 할당은 인덱스 블록에 할당된 블록을 순서대로 저장하기 때문에 직접 접근이 가능합니다. 또한 연속적으로 할당할 필요가 없으므로 외부 단편화 문제 또한 발생하지 않습니다.
색인 할당은 Unix/Linux에서 주로 사용합니다.
하지만 색인 할당의 단점도 존재하며, 작은 크기의 파일인 경우에도 하나의 블록을 인덱스 블록으로 사용하기 때문에 저장 공간이 손실되게 됩니다. 그리고 하나의 인덱스 블록을 가지고는 크기가 큰 파일을 저장할 수 없습니다.
이를 해결하기 위한 방법이 존재합니다.
인덱스 블록을 여러 개 만들어 연결 할당을 하는 것과 같은 방식인 Linked이 있습니다. 각 인덱스 블록의 마지막은 다음 인덱스 블록을 가리키는 포인터가 저장되어 있습니다.
또한 계층을 두는 방법으로 하나의 인덱스 블록의 모든 포인터가 다른 인덱스 블록을 가리키는 MultiLevel Index방식이 있습니다.
또 다른 방법은 Linked와 MultiLevel Index 방식을 합친 Combinded 방식이 존재합니다. 한 인덱스 블록의 포인터들은 데이터 블록과 또 다른 인덱스 블록 둘 다 가리킬 수 있습니다.
리눅스는 Combined 방식을 사용합니다.
이상으로 파일 할당 방법에 대해서 간단히 알아봤습니다.
참고
- KOCW - 운영체제, 양희재 교수님
- 혼자 공부하는 컴퓨터구조 + 운영체제
