[WEEK13] Pintos에서의 FAT 구현 (Pintos PROJECT4 : FILE SYSTEM)

발표자료 슬라이드를 바탕으로, FAT이 어떤 것이며 Pintos에서 어떻게 구현되어 있는지를 간략하게 살펴보자.

 

FAT이란, File Allocation Table의 약자이다. 말 그대로 파일의 할당 정보를 표현한 테이블이라고 할 수 있다.

MS-DOS 시절부터 쓰여 왔는데, Windows에 들어서면서 FAT형식의 파일시스템 자체를 가리키는 용어가 되었다.

FAT area와 FAT filesystem의 혼동을 주의하여야 한다.

 

PROJECT3까지 PINTOS에서 사용하던 파일 시스템은 Free-map 방식이었다.

이는 한 덩어리를 연속된 디스크 공간에 한번에 할당하는 방식이다.

이렇게 하면 외부 단편화가 심해진다.

위의 그림처럼, 주황색 블럭 두 개를 저장할 빈 공간이 남아 있음에도 불구하고 할당할 수 없는데,

free-map 방식에서는 한 덩어리를 반드시 연속된 영역에만 할당할 수 있기 때문이다.

 

FAT 방식에서는, 덩어리를 일정 크기로 쪼개어 저장하기 때문에 외부 단편화가 덜해진다.

마치 가상 메모리의 페이지 단위처럼 FAT에서는 클러스터 단위로 쪼개어 저장하게 된다.

어떤 면에서는 가상 메모리와 비슷하다는 생각이 들 수 있는데, 덩어리를 쪼갠다는 발상만 비슷하고 나머지는 다르다.

 

가상 주소(va)는 물리 주소(pa)와 1대1로 매핑되어 있었다.

그랬기 때문에 서로 떨어져 있는 공간임에도 불구하고 마치 연결되어 있는 것처럼 사용할 수 있었다.

 

FAT은, 가상이 따로 없고 다 실제 물리 섹터이다.

다만 몇 개의 섹터를 클러스터로 묶고 (KAIST-PINTOS에서는 단순화를 위해 클러스터 하나에 섹터 하나만 존재한다)

한 클러스터에는 다음 클러스터에 대한 연결정보가 기록되어 있어서, 이것이 마치 체인처럼 연결되어 있게 된다.

 

위의 그림에서 시작 클러스터 clst를 1번이라고 치면,

각 클러스터에 쓰인 숫자가 다음 클러스터에 대한 연결 정보이다.

그리고 마지막 클러스터에는 EOChain (End Of Chain) 숫자가 기록되어 있어서,

해당 클러스터가 마지막 클러스터라는 사실을 식별할 수 있다.

 

이 정보들을 disk의 FAT 영역에 기록해 두었다가,

부팅 시에 메모리에 로드하여 사용하는 것이 FAT 파일시스템의 구현 방법이다.

 

PINTOS에서는 FAT32 방식으로 구현하면 된다.

FAT32 방식에서 연결정보 하나는 4바이트 크기이다.

그러므로 1개 섹터(512바이트)에는 128개의 클러스터 정보를 저장할 수 있다.

 

PINTOS의 filesys_disk는 약 9.8MiB 크기를 가지고 있는데, 이를 섹터로 환산하면 20,160개이다.

20,160개의 연결정보는 FAT32방식을 사용하면 157개의 섹터에 저장이 가능하다.

약 9.8MiB의 indexing을 위해 78.5KiB의 공간만 투자하면 되니, 꽤 많이 절약한 거라고 볼 수 있겠다(disk의 각 inode에 linked-list 형태로 기록하는 것보다는 훨씬 비용이 적다).

 

그런데 20,160을 128로 나누면 157.5 이니까 158개의 섹터를 사용해야 할 것 같은데,

어떻게 157개에 저장해도 된다는 계산 결과가 나왔을까?

 

이는 FAT의 세부 구현과 관련이 있다.

디스크에서 0번 섹터는 BOOT SECTOR로 쓰인다.

BOOT SECTOR는 운영체제의 부팅 과정에서 디스크에 대한 정보를 불러오기 위해 예약된 공간이다.

그러므로 1개 섹터를 뺀 20,159개에 대한 정보를 저장하면 된다.

 

그런데 사실, 이들 FAT 정보를 저장하는 섹터도 디스크에서 비워 주어야만 한다.

그 공간을 FAT area라고 하는데, 아까 보았듯 128개의 정보 당 섹터 하나가 더 필요하다.

그래서 128에 1을 더한 129로 나누어 주는 것이다.

그러면 20,159 / 129 는 약 156.27인데, PINTOS에서는 부동소수점 연산을 하지 않고 내리므로 156이 된다.

그러므로 올림을 위해 1을 더해주면 157이 된다.

 

---

 

덧붙이는 글

나만의 무기 프로젝트에서 리더를 맡게 되었다.

핑계라면 핑계겠지만, 그 때문에 이번주 PINTOS 프로젝트에 집중하지 못했다.

이제까지는 다 구현했었는데 마지막 유종의 미를 거두지 못한 것 같아 아쉬울 따름이다.

리더로서, 이번 프로젝트에서 아쉬웠던 만큼 다가올 나만무를 열심히 이끌어보자!