요약

운영체제는 파일을 디스크의 어느 블록들에 놓을지, 그리고 아직 비어 있는 블록이 어디인지를 관리한다. 블록을 붙여서 한 줄로 주면(연속) 읽기는 빠르지만 빈틈이 쪼개져 큰 파일을 못 넣게 되고, 흩어진 블록을 사슬로 이으면(연결) 빈틈 문제는 없지만 중간 블록을 찾으려면 앞에서부터 따라가야 한다. 블록 번호 목록(색인)을 따로 두면 둘의 장점을 얻는 대신 목록을 저장할 공간이 든다. 메모리 관리의 분할·페이징과 같은 맞바꿈이다.

예시로 보기

블록 16개짜리 디스크에서 2, 3, 7, 11, 12번이 쓰이고 있다. 빈 블록은 11개인데, 연속으로 비어 있는 구간은 0~1(2개), 4~6(3개), 8~10(3개), 13~15(3개)뿐이다.

방식 4블록짜리 파일을 넣으면
연속 할당 빈 블록이 11개나 있는데 넣을 수 없다. 연속 4칸이 없기 때문이다(외부 단편화). 압축으로 파일들을 몰아야 한다
연결 할당 0 → 1 → 4 → 5처럼 아무 빈 블록이나 이어 담는다
색인 할당 색인 블록에 [0, 1, 4, 5]를 적고 그 블록들에 담는다 
 블록 번호   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
 사용 중           #  #           #           #  #
 빈 구간    [ 0~1 ]      [ 4~6  ]   [ 8~10 ]       [13~15 ]

 연결 할당:  블록 0 → 블록 1 → 블록 4 → 블록 5 → 끝
             (다음 블록 번호를 각 블록 안에 적음)

 색인 할당:  색인 블록 [0, 1, 4, 5]
                        |  |  |  |
                        v  v  v  v
                       블록 0, 1, 4, 5
             (순서를 색인 블록 한 곳에 모아 적음)

연속 할당이 실패하는 이유는 맨 위 줄에서 보인다. 빈 구간이 모두 4칸보다 짧다. 연결과 색인은 같은 블록 0, 1, 4, 5를 쓰지만, 다음 블록의 위치를 적어 두는 곳이 다르다1.

이 파일의 100번째 블록을 읽으려면, 연속 할당은 시작 + 99를 계산해 1번에, 연결 할당은 포인터를 따라 100번에, 색인 할당은 색인 1번 + 데이터 1번으로 2번에 읽는다.

검증: 위 디스크의 빈 구간, 연속 할당 실패와 흩어진 할당, 읽기 횟수, 비트 표 크기 — 60_file-allocation_impl.py

정확히 말하면

운영체제는 파일에 블록을 나눠 주고, 남은 공간을 추적해야 한다. 정할 것은 넷이다.

  1. 파일을 만들 때 최대 공간을 한꺼번에 줄까(선할당), 필요할 때마다 줄까(동적 할당)? 선할당은 최대 크기를 미리 알아야 하는데 믿을 만하게 추정하기 어렵고, 모자랄까 봐 크게 잡아 공간이 낭비된다.
  2. 공간을 연속된 조각(portion)으로 더한다면 조각의 크기는? 파일 전체를 담는 큰 조각과 블록 하나씩의 두 극단 사이에서, 파일 하나의 효율과 시스템 전체 효율을 맞바꾼다.
  3. 조각들을 추적할 자료 구조는? → 파일 할당 표(FAT)
  4. 빈 공간은 어떻게 추적할까? → 디스크 할당 표

세 가지 할당 방식

방식 파일 할당 표에 적는 것 좋은 점 나쁜 점
연속 시작 블록과 길이 (항목 하나) 차례로 읽기와 아무 블록 바로 읽기가 모두 빠르다 외부 단편화가 생겨 압축이 필요하다. 파일을 만들 때 크기를 알아야 한다(선할당)
연결 시작 블록과 길이 (항목 하나). 블록마다 다음 블록을 가리키는 포인터 아무 빈 블록이나 사슬에 더하면 되므로 외부 단편화가 없다. 차례로 처리하는 파일에 가장 좋다 특정 블록을 찾으려면 사슬을 따라가야 한다. 블록들이 흩어져 지역성을 살리지 못하므로 주기적으로 파일을 모아 정리하기도 한다
색인 파일마다 색인이 든 블록의 번호. 색인에는 할당된 조각마다 항목이 하나 연속·연결의 문제를 대부분 푼다. 차례로 읽기와 바로 읽기를 모두 지원한다 색인 블록만큼 공간이 들고, 접근마다 색인을 거친다

색인 할당은 고정 크기 블록이나 가변 크기 조각으로 할 수 있다. 블록 단위면 외부 단편화가 없고, 가변 조각이면 지역성이 좋아진다. 둘 다 가끔 정리가 필요하다.

빈 공간 관리

할당된 공간뿐 아니라 할당되지 않은 공간도 관리해야 한다. 그래서 파일 할당 표 말고 디스크 할당 표가 필요하다.

방법 내용 특징
비트 표 디스크 블록마다 비트 하나. 0이면 빈 블록, 1이면 사용 중 어떤 할당 방식과도 잘 맞고 가능한 한 작다
빈 조각 사슬 빈 조각마다 포인터와 길이를 적어 사슬로 잇는다 공간 부담이 거의 없고 모든 할당 방식에 맞지만, 단편화를 부른다
색인 빈 공간을 파일처럼 보고 색인 표를 둔다. 효율을 위해 블록이 아닌 가변 조각 단위로, 빈 조각마다 항목 하나 모든 할당 방식을 효율적으로 지원한다
빈 블록 목록 블록에 차례로 번호를 매기고 빈 블록 번호 목록을 디스크의 예약 영역에 둔다  

비트 표의 크기는 블록 수 ÷ 8바이트다. 디스크 1 TB, 블록 4 KB면 블록이 \(2^{40}/2^{12} = 2^{28}\)개이고, 비트 표는 \(2^{28}/8\)바이트 = 32 MB다.

볼륨. 운영체제나 응용이 데이터 저장에 쓸 수 있는, 주소로 가리킬 수 있는 섹터의 모음이다. 물리 장치에서 섹터가 이어져 있을 필요는 없고 운영체제에 이어져 보이기만 하면 된다. 작은 볼륨들을 모아 만들 수도 있다. 본질적으로 논리 디스크다.

스스로 설명해 보기

  1. 연속 할당은 빈 블록이 충분해도 파일을 못 넣을 수 있다.
    근거

    연속 할당은 한 줄로 이어진 빈 구간이 필요하다. 빈 블록이 흩어져 있으면 합이 충분해도 그만한 연속 구간이 없다. 메모리의 동적 분할과 같은 외부 단편화다.

  2. 연결 할당에서 100번째 블록을 읽으려면 100번 읽는다.
    근거

    다음 블록의 위치는 앞 블록 안에만 적혀 있다. 99번째 블록을 읽어야 100번째 위치를 알고, 99번째 위치를 알려면 98번째를 읽어야 한다. 결국 앞에서부터 모두 읽는다.

  3. 색인 할당은 블록 단위로 하면 외부 단편화가 없다.
    근거

    어떤 빈 블록이든 색인에 번호를 적기만 하면 파일에 들어간다. 연속 구간이 필요 없다. 페이징의 페이지 표와 같은 원리다.

    • 핵심 아이디어는?
답

파일의 논리적 순서와 디스크의 물리적 위치를 떼어 놓는다. 떼어 놓는 정보를 어디에 두느냐(블록 안 포인터 vs 따로 둔 색인)에 따라 바로 읽기 성능이 갈린다.

  • 같은 생각을 쓰는 다른 곳은?
    답

    메모리 관리: 연속 할당 ↔ 동적 분할, 색인 할당 ↔ 페이징(페이지 표). 연결 할당은 자료구조의 연결 리스트와 같아 k번째 원소 접근이 \(O(k)\)다.

활용

  • MS-DOS·USB 메모리의 FAT 파일 시스템은 연결 할당이다. 다만 다음 블록 포인터를 각 블록 안이 아니라 디스크 앞쪽의 표(FAT) 하나에 모아 두어, 표를 메모리에 올리면 사슬을 디스크를 읽지 않고 따라갈 수 있다.
  • UNIX는 색인 할당이고, 색인의 일부를 아이노드 안에 둔다 → UNIX 아이노드
  • NTFS는 섹터 하나 이상을 묶은 클러스터 단위로 할당한다. 볼륨이 클수록 클러스터가 크다. 예: 512 MB 이하는 512바이트, 32 GB 초과는 64 KB.
  • 계산 연습: 파일 할당과 아이노드 예제 사다리

연결

자주 하는 오해

“연결 할당은 외부 단편화가 없으니 모든 면에서 연속 할당보다 낫다”

틀렸다. 외부 단편화는 없지만, 파일 중간의 블록을 바로 읽을 수 없어 사슬을 처음부터 따라가야 한다. 블록이 디스크 여기저기 흩어져 차례로 읽을 때도 탐색이 많아진다. 포인터 하나가 망가지면 그 뒤 블록을 모두 잃는다는 위험도 있다. 무작위 접근이 잦은 파일에는 연속이나 색인이 낫다.

과목별 관점

어셈블리어 (2-1학기). 연결 할당을 MS-DOS의 FAT로 배운다. 위의 “블록”을 FAT에서는 클러스터라 부른다. 클러스터는 붙어 있는 섹터 한 개 이상을 묶은 것이고, 파일이 쓰는 공간의 가장 작은 단위다. 다음 블록의 번호를 블록 안에 적지 않고, 디스크의 모든 클러스터마다 칸이 하나씩 있는 표(FAT)에 모아 적는다. 한 파일의 번호들이 이어진 줄을 클러스터 사슬이라 부르고, 칸의 비트 수(12, 16, 32)에 따라 FAT-12, FAT-16, FAT-32로 나눈다. 16칸짜리 FAT 표를 따라가는 예와 클러스터 크기 때문에 버려지는 자리 계산은 클러스터와 FAT에 있다.

확인 문제

C1 세 할당 방식에서 파일 할당 표에 무엇을 적는지 쓰라.

답: 연속: 시작 블록과 길이. 연결: 시작 블록과 길이(나머지는 블록 안 포인터). 색인: 색인이 든 블록의 번호.

C2 다음에 가장 맞는 할당 방식은? ① 처음부터 끝까지 한 번 읽고 마는 로그 파일, 크기를 미리 모름 ② 아무 위치나 자주 읽는 데이터베이스 파일, 크기가 자주 바뀜 ③ 한 번 기록하고 바뀌지 않는 CD-ROM

답: ① 연결(차례로 읽기에 좋고 크기를 몰라도 됨) ② 색인(바로 읽기가 빠르고 블록을 아무 데나 더할 수 있음) ③ 연속(크기가 고정이라 단편화가 생기지 않고 가장 빠름).

C3 디스크 1 TB, 블록 4 KB일 때 비트 표의 크기는?

답: 블록 수 \(2^{40}/2^{12} = 2^{28}\), 비트 표 \(2^{28}\)비트 = \(2^{25}\)바이트 = 32 MB.

C4 블록 16개 디스크에서 2, 3, 7, 11, 12번이 쓰인다. 최초 적합 연속 할당으로 3블록 파일을 넣으면 어느 블록인가? 그다음 3블록 파일은?

답: 첫 파일 4~6(처음 만나는 3칸 이상 빈 구간). 다음 파일 8~10.

  1. “예시로 보기”의 블록 16개 예(문서의 보충 예, 각주 s1)를 ASCII로 그렸다. ↩