12. File System Implementation

File에는 다음의 정보가 저장되어 있다.

Inode number	Path	File descriptor
Inode에는 meta data가 저장되어 있다.	Hierarchical으로 구성되어 있다.	빈번하게 path를 검색하는 것을 방지하기 위해서 사용된다.

 

가령 file descriptor는 다음처럼 사용된다.

int fd = open(char *path, int flat, mode_t mode)
read(int fd, void *buf, size_t nbyte)
write(int fd, void *buf, size_t nbyte)
close(int fd)

 

Disk Structure

Disk는 large array로 구성되어 있다. Data를 이 array에 잘 mapping하는 것이 주요 포인트이다. Allocation 전략에는 여러가지가 있다.

• Contiguous
• Extent-based
• Linked
• File-allocation tables
• Indexed
• Multi-level indexed

 

평가요소로는 다음의 내용이 있다.

• Fragmentation 얼마나?
• File grow가 얼마나 잘 되니?
• Sequential access performance
• Random access performance
• Wasted space for meta data overhead

 

Contiguous allocation

• Meta data: 시작지점
• 그냥 냅다 이어서 저장

• Grow: 안될때 있음
• Fragmentation: external 
• Sequential access: 굳
• Random access: 간단한 계산 필요
• Wasted space: 적음

 

Small # of extents

• Meta data: 쪼개진 친구를 위한 맵핑 데이터 추가됨
• 최대한 적게 데이터 쪼개서 저장

• Grow: 가능
• Fragmentation: reduced external 
• Sequential access: 나쁘지 않음
• Random access: 간단한 계산 필요
• Wasted space: 적음

 

Linked allocation

• Meta data: First block 위치만
• 다음 데이터 위치를 data block에 같이 저장해둠

• Grow: 가능
• Fragmentation: external 없음, internal 있음(근데 뭐 어쩔 수 없음)
• Sequential access: 나쁘지 않음
• Random access: 쉣
• Wasted space: block마다 pointer 추가로 쓰임

 

File-allocation table (FAT)

• Meta data: First block 위치만
• Block에 pointer 저장하지 말고, 따로 table에 저장한 linked allocation

• Performance: Linked랑 동일
• 단점 추가: disk 2번 접근
  • Main memory에 cache로 그나마 최적화 가능

 

Indexed allocation

• Meta data: Block pointer 저장
• 앞에서 하던 짓 그만하고 그냥 다 pointer로 맵핑

• Grow: 가능
• Fragmentation: external 없음, internal 있음(근데 뭐 어쩔 수 없음)
• Sequential access: 좋음
• Random access: 좋음
• Wasted space: Meta data 저장하는 크기가 매우 커짐(일반적으로 file 크기가 매우 작음, 낭비하는 게 아닌가 싶음)

 

Multi-level indexing

• Meta data: 사용하는 block의 pointer
• 실제 사용되는 친구만 pointer 사용

• Waste space가 줄어듦
• 단점: indirect를 읽음으로써 disk read가 추가됨 -> main memory에 올리기

 

Flexible # of extents

현대 file system에서는 최대한 contiguous하게 file region을 잡아준다. 다만 동적으로 변할 수 있으며 항상 그렇게 잡지는 않는다. 또, multi-level tree로 구현하면 meta data로 인한 waste space도 최대한 줄일 수 있게 된다.

 

On-Disk structure

64 blocks (block = 4KB)

Disk는 data array이다. 이중에서 몇개는 inode, 몇개는 data block이 된다.

 

Inode

하나의 inode는 보통 256 bytes이기 때문에, 4KB disk block을 표현하기 위해서는  16개의 inodes가 필요하다. Inode에는 다음의 내용이 들어가 있다.

• Type : file vs dir
• uid : owner
• rwx : 권한
• size 
• blocks : 몇개 사용?
• time : access
• ctime : create
• links_count : # paths
• addrs[N] : N data block

하나의 indoe 크기가 256B이다. 4B address를 관리한다고 할 때, 얼마나 큰 file을 관리할 수 있을까?

• 256 / 4 = 64개의 pointer 관리 가능
• 1개의 disk block = 4KB
• 따라서 64 * 4KB 관리 가능

 

물론 indirect로 더 많은 파일을 관리할 수도 있다. Directory의 경우 lists나 B-tree로 파일을 bit 관리한다.

 

Bitmap

Bitmap으로 inode와 data의 사용 여부를 빠르게 판단한다. 

 

Superblock

File system이 disk의 구조를 파악하기 위한 정보가 저장되어 있는 곳이 superblock이다. Block size, # of inodes, data blocks, start address of inode table 등의 정보가 저장된다.

 

File opreation

Create

Create /foo/bar

 

Open

open foo/bar

 

Write

write /foo/bar/sth.txt

 

Read

read /foo/bar

 

Close

Disk에서는 별도로 할 일이 없다. 뭐 물론 저널링 이런거 해야 하는데 내용이 많으니 넘어간다.

 

Efficiency

Read, write는 매우 오래 걸리기 때문에 한번에 처리할 수 있으면 한번에 하면 좋다. 보통 buffer로 관리한다.