[운영체제] 25. File system Implementation

Reference - Operating Systems: Three Easy Pieces

 

 

https://pages.cs.wisc.edu/~remzi/OSTEP/

Operating Systems: Three Easy Pieces

 

 

File System Implementation

 

파일 시스템을 어떻게 만들 수 있을까?

자료구조 - 데이터와 메타데이터를 구성하기 위해 어떤 디스크 구조를 사용할 것인가

접근 방법 - open(), write()등의 syscall을 어떻게 처리할지, 얼마나 효율적으로 수행할지

 

4KB block 64개가 있다고 가정해보자.

메타데이터 inode를 앞의 5개 block에, 유저 데이터를 위한 data region을 뒤 block에 저장한다.

그리고 특정 공간에 inode, data를 저장할 수 있는지 여부를 알려주는 정보를 저장해야 한다.

이를 bitmap이라고 한다. inode table과 data region 두 영역을 위해 각각의 block이 필요하다.

남은 하나의 block엔 super block이 필요하다. super block은 inode block 수, data block 수, inode table이 시작되는 위치, data region이 시작되는 위치, 파일 시스템 종류를 구분하기 위한 magic number가 들어있다. fs를 위한 메타데이터라고 볼 수 있다. 실제론 SuperBlock 앞에 Boot Sector가 있는데, BIOS에서 Boot Sector의 image를 로딩시킨다.

 

이제 inode를 중심으로 실행 과정을 살펴보자. inode 32번을 읽고 싶다면 파일 시스템은 먼저 inode table이 시작되는 위치를 super에서 알아낸다. 알아낸 위치(12KB)에서 inode size * 32를 해준 값을 더하면 inode 32의 주소를 알 수 있다.

inode 32는 실제 데이터 위치를 가리키고, 그곳으로 가서 데이터를 읽을 수 있다.

 

inode에는 file type, file size, index of data blocks allocated to it, protection, time 정보 등이 있다.

우리는 index에 대한 정보를 잘 살펴봐야한다.

 

Single level index : 13개의 pointer를 가질 때 52KB까지 지원. pointer 하나하나가 데이터 블락을 가리키면

포인터가 인덱스를 가리키게 하는 multi level index를 통해 해결.

 

indirect pointer - 한번 indirect block pointer를 사용하면 4KB * 1024 = 4MB를 지원하고, double indirect를 하면 4GB를 지원할 수 있다. 단점은 그전엔 4KB를 읽기 위해 inode만 읽어도 됐지만 이제는 더 읽어야된다는 점이다. 파일 시스템은 두 pointer를 모두 사용하여 적절한 속도와 크기를 갖도록 한다.

 

어떻게 효율적으로 할까?

작은 (접근하는 데이터가 적은) 파일의 경우 앞 block만 쓸 확률이 크기 때문에  앞 공간은 direct blocks로, 뒤에는 indirect block으로 사용한다. (4KB 읽고 4MB 읽고-방식으로 trade off를 잘 조절해야 한다)

Access Paths: reading a file from disk

open("/foo/bar", ReadONLY) 일 때 루트부터 시작해야돼서 inode number 2(=root)를 먼저 read.

inode를 읽으면 메타데이터가 있기에 index를 보고 데이터 블록을 읽는다. 그럼 foo가 있을 것이고 foo의 inode를 읽는다.

그럼 bar가 있을 것이다. bar를 찾으면 permission을 check하고, file descriptor를 os가 user에게 return한다.

 

read()를 한다고하면, file의 first block을 읽고 그 뒤 inode accses time 등의 update를 수행하기 위해 write를 해야한다.

write()는 inode를 읽고, data bitmap을 읽고, data bitmap을 write하고, inode를 write하고, actual block을 write 해야한다.

create에서 write 할 공간이 사용중이면 bar가 있는 sector를 read 해야 한다.

bar가 생겼으니까 foo에서 directory entry를 update하기 위해 write 해야 한다.

위 그림에서 첫번째 write()를 수행할때 bar inode에 쓰고 bar data[0]을 업데이트하거나 반대로 업데이트하고 쓰는 것의 순서는 상관없다. 부하를 줄이려면 read의 경우 지속되는 read를 빠른 메모리에 cache해놓으면 된다.

write는 batch write라고, buffer에 모아둔다음 한번에 write를 수행하여 효율을 높인다.

 

delayed write는 기록을 바로 쓰지 않기 때문에 데이터를 손실할 가능성이 높다는 단점이 있다. 이를 해결하기 위해 fsync() 를 통해 직접적으로 데이터를 flush하라고 하거나 direct I/O를 할 수 있다.