File System Implementation

File System을 Implement하는데 있어서는 두가지를 해 주어야 합니다.

 

1. Data structures
   • On-disk File Structure를 설계해 주어야 합니다.
2. Access methods
   • open(), read(), write()등을 어떻게 처리할지 설계해 주어야합니다.

 

Data Structures

 

Disk를 Blocks로 나누는 것에서 시작합니다.

 

각 블록들은 Data Region, Innode Table, Bitmap, Superblock, Boot Sector로 구분되어 할당됩니다.

 

• Data Region
  • User data를 저장하기 위한 장소입니다.
• Inode Table
  • Inode 를 저장하는 장소입니다.
    • Inode에는 File type, File size, Index of data blocks allocated to it, Protection information, Time information 등이 포함됩니다. (metadata)
• Bitmap
  • 어떤 Block이 free여서 데이터를 저장할 수 있는지 Mapping해주는 곳입니다
    • Data bitmap, Inode bitmap이 따로 존재합니다.
• Superblock
  • Superblock은 이것이 어떤 file system인지에 대한 정보를 담는 곳입니다.
    • Inode의 개수나, Inode Table의 위치와 같은 것을 저장합니다
    • Mounting이 될때 OS는 superblock을 읽습니다.

그래서 이걸 통해서 어떻게 파일을 찾을까요?

 

각 Inode는 Inode number로 referred 됩니다.

Inode number를 통해 file system은 inode가 어디에 있는지 알아낼 수 있다는 뜻이죠.

 

 

그래서 inode에서 각 파일의 위치를 가르키는 포인터는 어떤 방식으로 저장될까요?

Page table처럼 index가 있어서 이를 찾아가면 됩니다.

 

아래 그림은 Single Level Table입니다.

그런데 이러한 방식으로 저장하게 되면 큰 파일을 저장할 수 없게 됩니다.

Single Level Index 같은 경우에는 만약 13개의 pointer만 존재한다면  13X4KB인 52KB의 파일을 저장하는것이 최대겠죠?

 

그래서 multi level index라는 방식이 사용됩니다.

이것을 위해서 Indirect Pointer라는 것을 사용하게 되죠. Indirect pointer는 Pointer를 담고 있는 또 다른 Index Block을 가르키는 방식입니다.

 

Access Methods

 

일단 Directory는 (User_readable_name, inode number) 가 담긴 리스트라고 말씀드렸죠?

 

이것은 기본적으로 자기 자신과 자신의 부모 디렉토리를 ( . , inode number of myself ) ( .. , inode number of parents )로 포함하고 있습니다.

 

이제 한번 Open&Read 를 해볼까요?

 

Open("/foo/bar", O_RDONLY)

1. file system의 root directory로 찾아갑니다.
   • 보통 Unix에서는 root inode number은 2 입니다.
   • inode number를 통해 root directory를 찾았으니 그 리스트에서 foo를 찾아서 inode number를 알아냅니다.
2. bar를 찾을때까지 다음 과정을 recursively하게 반복합니다.
3. bar가 찾아졌다면 permission check를 하고 파일 디스크립터를 하나 할당해준 다음 return 해줍니다.
4. last access time과 같은 것들을 update해 줍니다.

그렇다면 파일을 닫아주기도 해야겠죠?

 

닫으면 descriptor가 반환될 뿐 Disk I/O는 하지 않습니다.

 

그렇다면 write()는 어떻게 해 주어야 할까요?

• File은 새로운 블록을 할당받아야 합니다. ( 안 쓰더라도 말이죠 )
• Inode , Data block, Data bitmap을 업데이트 해주어야 합니다.
• 5개의 I/O를 하게 됩니다.
  1. 한개는 inode를 읽어옵니다
  2. 한개는 data bitmap을 읽습니다
  3. data bitmap을 업데이트 해줍니다
  4. inode를 업데이트 해줍니다
  5. 새로 할당받은 블록에 write해줍니다.
• 매우 많은 오버헤드가 들게 됩니다.

Write연산이 매우 많은 오버헤드가 들기 때문에 우리는 Caching과 Buffering을 사용을 해 줍니다.

 

Caching

• Reading과 Writing을 해주는 것은 매우 비싼 연산입니다, 많은 I/O를 사용하기 때문이죠.
  • pathname이 (1/2/3/4/.../100/file.txt)를 읽는 경우
    • 적어도 한개의 디렉토리를 읽을때 한번의 I/O를 하게 됩니다.
    • 총 100개 이상의 I/O를 합니다.
• I/O Traffic을 줄이기 위해서 DRAM을 적극 활용합니다.
  • 예전의 파일 시스템은 고정된 사이즈의 cache를 popular block을 저장하는데 사용하였습니다. (Static)
  • 요즘은 Dynamic partitioning approach를 해서 unified page cache를 사용합니다.
• 만약 Cache가 크다면 Read의 I/O는 피할 수 있는 선택입니다.

Buffering

• Write traffic은 Caching으로는 피해질 수 없습니다. 왜냐면 Disk에 무조건 Write을 해 주어야 하기 때문입니다.
• 그래서 Buffering을 걸어줍니다.
  • Writing을 Delay 해주는 것입니다.
  • 작은 것을 반복해서 쓰면서 생기는 I/O를 줄여 줄 수 있습니다.
• 만약 즉시쓰기를 해야하는 문제일 경우 fsync()나 direct I/O를 사용해서 flush해 줄 수 있습니다.