클러스터와 FAT

요약

디스크는 같은 크기의 상자가 줄지어 놓인 창고와 같다. 파일은 상자 여러 개에 나눠 담기고, 창고 입구의 장부 한 권에 “이 상자 다음은 몇 번 상자”가 적혀 있다. 그래서 상자가 여기저기 흩어져 있어도 장부만 따라가면 파일을 끝까지 읽는다. 대신 상자를 통째로만 쓸 수 있어서 마지막 상자의 빈 자리는 버려지고, 파일의 뒷부분을 읽으려면 장부를 앞에서부터 따라가야 한다.

예시로 보기

파일 크기는 제각각인데 디스크의 빈 자리는 계속 생겼다 없어진다. 바이트 단위로 자리를 내주면 “어디가 비었고 어느 조각이 누구 것인지”를 적는 일이 감당이 안 된다. 그래서 파일 시스템은 디스크를 같은 크기의 덩어리로 잘라 덩어리 단위로만 내준다.

디스크에서 한 번에 읽고 쓰는 가장 작은 조각을 섹터라 부른다. 붙어 있는 섹터 한 개 이상을 묶은 것이 클러스터이고, 파일이 차지하는 공간의 가장 작은 단위다. 아래 그림에서는 섹터 1~4가 클러스터 1, 섹터 5~8이 클러스터 2다.

섹터:      | 1 | 2 | 3 | 4 | --> | 5 | 6 | 7 | 8 |
           +---------------+     +---------------+
              클러스터 1            클러스터 2

파일은 아무리 작아도 클러스터 하나를 쓴다. 클러스터가 4,096바이트(4K)일 때 8,200바이트 파일을 넣어 보자.

클러스터	담긴 양	빈 자리
1	4,096바이트	0
2	4,096바이트	0
3	8바이트	4,088바이트

두 개로는 8,192바이트까지만 들어가서 8바이트가 남는다. 이 8바이트 때문에 클러스터 하나를 더 쓰고, 그 안의 4,088바이트는 다른 파일이 쓸 수 없다.

검증: 8,200바이트의 클러스터 수 3과 빈 자리 4,088, 아래 16칸 표의 두 사슬(7개, 5개), 빈 칸, 카드 C2·C3의 답 — 48_fat-file-system_verify.py. 실제 디스크를 읽은 것이 아니라 이 문서의 숫자를 파이썬으로 다시 센 것이다.

파일 이름에서 섹터까지

파일 시스템은 세 가지 일을 한다. 쓴 공간과 빈 공간을 적어 두고, 디렉터리와 파일 이름을 관리하고, 파일과 디렉터리가 어느 섹터에 있는지 적어 둔다. 파일 이름 하나가 실제 섹터로 이어지는 길은 이렇다.

flowchart TD
  FS[파일 시스템] -->|목록으로 갖고 있다| FN[파일 이름]
  FN -->|적혀 있는 곳| DIR[디렉터리]
  FN -->|이어진다| CC[클러스터 사슬]
  CC -->|적혀 있는 곳| FAT[파일 할당 표 FAT]
  CC -->|이어진다| LS[논리 섹터]
  LS -->|이어진다| PS[물리 섹터]

디렉터리는 파일 이름을, FAT는 그 파일의 클러스터들이 어떤 순서로 이어지는지를 적는다. 클러스터 번호를 알면 그 안의 섹터 번호(논리 섹터)가 나오고, 디스크가 그것을 실제 위치(물리 섹터)로 바꾼다.

파일 할당 표

파일 할당 표(FAT)는 디스크의 모든 클러스터를 한 줄로 늘어놓은 표다. 칸 하나가 클러스터 하나다. 칸에는 “이 파일의 다음 클러스터 번호”가 적힌다. 마지막 클러스터의 칸에는 끝 표시(eof)가 적힌다. 이렇게 번호로 이어진 줄을 클러스터 사슬이라 부른다.

16칸짜리 표에 파일 두 개가 들어 있다고 하자. File1은 클러스터 1에서 시작해 7개를 쓰고, File2는 5에서 시작해 5개를 쓴다. 두 사슬을 한 표에 적으면 다음과 같다.

클러스터 번호	1	2	3	4	5	6	7	8	9	10	11	12	13~16
칸에 적힌 값	2	3	4	8	6	7	11	9	10	eof	12	eof	(빈 칸)
주인	File1	File1	File1	File1	File2	File2	File2	File1	File1	File1	File2	File2	없음

File1: 1 → 2 → 3 → 4 → 8 → 9 → 10 → 끝. 4번 칸에 8이 적혀 있어서 5, 6, 7을 건너뛴다.
File2: 5 → 6 → 7 → 11 → 12 → 끝. 8, 9, 10은 File1이 쓰고 있어서 7번 칸에 11이 적혀 있다.

File1처럼 한 파일의 클러스터가 떨어져 있으면 읽는 동안 디스크의 읽기 머리가 건너뛰어야 한다. 이런 파일을 조각난 파일이라 부른다: 디스크 스케줄링.

칸 하나가 몇 비트인지에 따라 FAT-12, FAT-16, FAT-32 세 종류가 있다. 칸이 \(n\)비트면 적을 수 있는 번호가 \(2^n\)가지다. 12비트면 4,096가지, 16비트면 65,536가지다¹. 클러스터 크기는 파일 시스템의 종류와 디스크 구역(파티션)의 크기에 따라 정해진다.

활용

필요한 클러스터 수는 파일 크기를 클러스터 크기로 나눠 올림한 값이다. 버려지는 자리는 (클러스터 수 × 클러스터 크기) − 파일 크기다. 클러스터가 클수록 작은 파일이 버리는 자리가 커진다.
사슬의 \(k\)번째 클러스터를 찾으려면 표를 \(k - 1\)번 따라가야 한다. 연결 리스트에서 \(k\)번째 원소를 찾는 것과 같다¹.
운영체제 과목은 같은 구조를 “연결 할당”이라는 이름으로 배운다. 다음 번호를 덩어리 안이 아니라 표 하나에 모아 둔 것이 FAT다: 파일 할당.

연결

사슬을 따라가는 방식: 연결 리스트
다른 할당 방식과의 비교: 파일 할당
섹터를 직접 읽거나 디렉터리를 만드는 MS-DOS 함수: INT 21h 파일·디스크 함수

확인 문제

C1 섹터, 클러스터, 클러스터 사슬, FAT가 각각 무엇인지 한 문장씩 쓰라.

답: 섹터는 디스크에서 읽고 쓰는 가장 작은 조각이다. 클러스터는 붙어 있는 섹터 한 개 이상을 묶은 것으로, 파일이 쓰는 공간의 가장 작은 단위다. 클러스터 사슬은 한 파일의 클러스터들이 “다음 번호”로 이어진 줄이다. FAT는 모든 클러스터마다 칸을 하나씩 두고 그 다음 번호를 적어 둔 표다.

C2 클러스터가 4,096바이트일 때 10,000바이트 파일은 클러스터를 몇 개 쓰고, 몇 바이트가 버려지는가?

답: 3개, 2,288바이트.
이유: \(10000 \div 4096 \approx 2.44\)라서 올림하면 3이다. \(3 \times 4096 - 10000 = 2288\).
흔한 오답: 2개. 내림하면 뒤쪽 1,808바이트가 들어갈 곳이 없다.

C3 위 16칸 표에서 File2의 네 번째 클러스터는 몇 번인가? 표의 어느 칸들을 읽어서 알았는가?

답: 11번. 시작이 5이므로 5번 칸(6), 6번 칸(7), 7번 칸(11)을 차례로 읽는다.
이유: 다음 번호는 앞 칸에만 적혀 있어서 세 번을 따라가야 네 번째가 나온다.

C4 File1의 4번 칸에는 왜 5가 아니라 8이 적혀 있는가? 이렇게 되면 무엇이 나빠지는가?

답: File1이 다섯 번째 클러스터를 달라고 했을 때 5, 6, 7은 이미 File2가 쓰고 있었고, 그다음 빈 칸이 8이었다. 파일이 디스크의 떨어진 자리에 나뉘어 놓이므로 읽기 머리가 건너뛰어야 해서 읽기가 느려진다.

숫자는 검증 코드로 확인했다. ↩ ↩²