filesystem implementation
on-disk data structure
disk 내에서 file을 어떻게 저장할 것인지가 역시 이슈이다. 그냥 block에 연속되게 저장할 수도 있고 방법은 많다. 똑똑하신 분들이 고안한 여러 방법이 있는데 이를 차례대로 살펴보도록 하자
1. contiguous allocation
역시 제일 먼저 생각할 수 있는 방법이다. file을 disk block에 연속되게 저장하는 것이다
metadata : 각 file의 시작 block과 크기
- Fragmentation : huge external fragmentation
- file growth : 힘들다
2. extent
파일을 작은 크기의 extent로 나눠서 disk에 흩뿌려서 배치한다
metadata : 각 파일 마다 extent의 시작 위치와 크기
- fragmentation : 연속 저장보단 덜함
3. Linked Allocation
파일을 block단위로 나눠서 저장하는데, 각 block은 file의 다음 block을 가리키게 됨
meta data : 각 파일의 시작 위치, per-block pointer
- fragmentation : external은 없지만 하나의 block에 4byte 포인터 저장하며 internal fragmentation은 존나 큼
- file growth : good
- sequential access : layout에 따라 달라짐
- random access : 존나 구림
4. File Allocation Table(FAT)
각 파일의 block의 위치를 나타내는 linked list를 maintain
meta data : 각 파일의 시작 위치, fat
- fragmentation : X
- sequential access : block의 layout에 따라 달라짐
- random access : good
제일 큰 단점 : 한 block에 접근할 때 마다 무조건 fat에 접근해서 확인해야 함. 메모리에 캐시하는 방법도 있지만 file system이 커지는 경우엔 이것도 어렵
5. Indexed Allocation
각 파일의 block의 위치를 나타내는 fixed-size array maintain
meta data : fixed-size array
다른 거 다 괜찮은데 얘의 문제는 fixed-size array란 것. 파일이 작으면 작은 대로 낭비고, 크면 더 이상 할당할 공간이 없음
6. Multi-Level Indexed Allocation
그래서 마지막으로 나온 게 multi-level indexed allocation
fixed-size array를 작게 하고, 모자라면 single indirect, 더 모자라면 double indirect allocation을 하도록 함
disk operation
create /foo/bar
- root inode read
- root data read
- foo inode read
- foo data read
- inode bitmap read
- inode bitmap write
- foo data write
- bar inode read
- bar inode write
- foo inode write
open /foo/bar
- root inode read
- root data read
- foo inode read
- foo data read
- bar inode read
write /foo/bar
- root inode read
- root data read
- foo inode read
- foo data read
- bar inode read
- data bitmap read
- data bitmap write
- bar data write
- bar inode write
read /foo/bar
- root inode read
- root data read
- foo inode read
- foo data read
- bar inode read
- bar data read
- bar inode write
close
disk에서 할 거 없음
efficiency
위에 예시에서 보면 디렉토리 하나 들어갈 때마다 inode 읽고, directory file 읽고 반복하는데, 이렇게 disk에 한번 읽고 쓰려면 갱장히 비효율적인 걸 알 수 있음
따라서 os 차원에서 몇 가지 해결 방법을 생각해봤음!
write buffering
write할 걸 메모리 버퍼에 모아뒀다가 나중에 한번에 disk에 write operation을 issue하는 것!
buffer cache
메모리의 10% 정도에 disk block을 캐시해서 사용하는 것
page cache
disk의 각 page frame에 Disk block도, virtual page도 들어갈 수 있음!
