40. File system Implementation

 

inode ?

 

• 한 process에서 file을 구분하는 unique한 number

 

 

The Way To Think

• file system을 구현하는 방법

1. Data structures

• linear한 disk를 자료구조를 이용하여 data를 저장하게끔 만듬

2. Access methods

• file system에 제공할 API 필요
• open()
• read()
• write()

 

 

Overall Organization

• disk의 linear한 공간을, block 단위로 잘라서 사용
• Block size = 4KB
• disk가 커도, file system은 총 64개의 block만 관리 => 총 4KB * 64 = 256KB 관리 

 

 

Data region in file system

• user가 write를 했을 때, data를 저장하는 공간(경우에 따라 file system이 쓰기도 함)

• block 하나당 4KB라고 했으니, 만약 7K면, block 두개를 사용하여 저장하는 방식
• 그렇다면, 이렇게 block에 저장한 file이, 어느 위치에 저장 됐는지 어떻게 알 수 있을까?
• => inode table을 이용하여 file이 저장된 위치를 저장

 

 

Inode table in file system

• inode table에 메타 정보를 저장(어느 block을 어느 file이 쓰고 있는지 같은..)

• 총 5개의 block을 inode table 공간으로 활용한다고 해보자.
• inode size = 256byte
• 즉, 4KB block 하나 당 inode를 16개씩 저장할 수 있음 (2^12 / 2^8 = 2^4 =16)
• 그러한 block을 총 5개 사용하고 있으니, inode를 총 16*5=80개 저장 가능

 

 

allocation structures

• bit map을 사용하여, 어떤 공간에 할당 할 지 정할 수 있음(bit map은 0으로 초기화) 
• inode bit map과 data bit map 존재 => bit map 자체도 1개에 block에 할당 => 4KB의 공간(4096byte)을 가짐
• data bitmap : data region이 할당 되어 있으면 1, 아니면 0 => 4096 byte * 8(1byte = 8bit) 개의 block 관리 가능
• inode bitmap : 어떤 inode의 entry가 사용 되었는지 => 마찬가지로 4096 * 8 개의 inode 관리 가능

 

 

 

Superblock

• file system의 특정 정보 저장
• 가장 첫 block을 superblock으로 지정
• inode의 개수, inode table의 시작 위치 등을 저장한다.
• file system이 mounting을 할 때, 가장 먼저 superblock을 확인하고, 정보를 초기화 함

 

 

File Organization : The inode

• file의 기본 구조
• 만약 inode number가 32라면, 그 inode가 저장된 위치의 주소 = (32 * sizeof(inode)==256) = 8192(8K)
• inode table이 12KB 부터 시작하므로 실제 inode의 위치 = 12KB + 8KB = 20KB
• 이 주소로 가서 inode를 확인하면, inode 내부에 저장된 정보로 인해 실제 file이 data region 어디에 저장됐는지 알 수 있음

• 사실 disk는 byte address가 아닌 sector address 이므로, disk의 관점에서는 위치를 다르게 계산

• 어렵게 써놨는데, 사실 실제로 따지면 그냥 위에서 구한 byte address(20KB)에서 sector size로 나눠주면 됨
• 20KB / sectorsize(512bytes) =  40
• 40번째 sector에 inode number = 32가 존재한다고 보면 된다.

 

 

inode

• inode는 file에 대한 정보를 담고 있다
• File type
• file size(얼마나 많은 block이 할당 되었는지)
• protection information
• time information
• 등등..

• block == 실제 data region의 주소(pointer)를 담고 있는 정보 
• 4byte 크기의 pointer를 15개 담을 수 있는 구조이다.

 

 

 

The multi-level index

• 위에서 pointer 15개를 저장할 수 있다고 했는데, 이 중 12개는 direct pointer 이다
• direct pointer == 저장된 바로 그 block의 주소 
• 나머지 3곳은, data region의 한 block을 가리키는데, 그 block이 또 다른 block을 가리키는 구조로 구성
• => indirect, double indirect, triple indirect

• 4byte 짜리 pointer 15개를 담는 block 구조(60byte)
• 이중 12개는 direct로, 1개당 4KB 짜리 block 하나를 가리킴 => 총 48KB 크기의 file까지 저장 가능 
• 만약 48KB를 넘어가는 file이라면, indirect를 사용해야 함
• indirect 는 4KB 짜리 block 하나를 가리키는데, 이 block은 4byte pointer를 1024개 담을 수 있음
• => 즉 4KB 짜리 block을 1024개 가리킬 수 있게 됨 => 4KB * 1024 크기의 file까지 저장 가능
• double indirect는 이걸 한번 더 해서, 1024 * 1024 * 4KB 크기의 file까지 저장이 가능해진다.

=> 그래서 만약 double indirect까지 쓰게 된다면, (12 + 1024 + 1024^1024) * 4KB = 4GB file까지 저장 가능해짐

 

 

• 기본적으로 file은 매우 작아서 보통 2KB 정도만 쓴다고 가정하고 만든 구조
• 대부분은 다 작은 파일인데, 큰 애들만 엄청나게 크게 쓴다고 생각하고 만든 구조
• 아무튼 보통은 indirect를 안쓴다고 생각하고 만들었다.

 

 

Directory Organization

• loot 의 inode의 block에 저장되어있는 정보들
• loot directory는 sub directory를 가질 수 있고 이 sub directory 들도 각자 sub directory와  file을 가질 수 있음
• 그러한 하위 node들의 정보를 loot 에 적어놨다고 보면 됨.

 

 

Free Space Management

• bit map을 통해서 관리 할 수 있다.
• file system은 어떤 inode와 data block이 free 한 지 아닌지를 찾음 
• 만약 어떤 file을 새로 만들었으면, inode bitmap을 보면서, 0으로 되어있는 곳에 inode 할당 후 bitmap update

 

 

 

Access Paths: Reading a File From Disk

• /foo/bar 라는 file을 어떻게 읽을 것인지

1. root의 inode read
2. root의 data block으로 가서 sub directory 인 foo의 inode 정보 read
3. foo의 inode read
4. foo의 data block으로 가서 내부 file인 bar의 inode 정보 read
5. bar의 inode read

• 이후 bar의 inode를 알았으면, read를 하기 위해 inode를 읽고, 그 file이 저장된 block을 찾아서 읽음
• 그리고 inode 정보 update(write) => access 한 시간같은 것도 저장 되어 있어서 update 해줘야 함

 

 

Access Paths : Writing to Disk

• bar 라는 file을 새로 만들고, 그 file에 write를 하는 작업
• foo의 data block을 읽는 것 까진 read와 동일
• 이후 inode bitmap 를 read 해서, 비어 있는 곳을 찾고 wirte 해서 새로운 inode 할당
• foo의 data block에 bar inode 추가(bar가 foo의 내부 file이니까)
• 그리고 bar inode를 read(왜 read하는진 모름) 하고 새로 할당된 bar inode를 write
• 여기까지 하고 foo의 inode update
• 이제 bar file이 만들어졌으니까, bar의 inode를 읽고, data bitmap에서 새로 write를 할 공간을 찾고 할당을 해줌
• 할당을 했으면 bar의 block으로 가서 data를 써주고
• bar의 inode update(새롭게 쓴 block의 위치정보와 time update)

 

 

Caching and Buffering

• Caching : 자주 쓰는 inode를 disk에서 작업하지 말고 memory로 올려서 작업 => 빨라짐
• => 예전에는 cache size를 정해놓고 했는데, 요즘에는 dynamic으로 size 조정
• Buffering : write를 할 때, 바로바로 적는게 아니라, 기다렸다가 한꺼번에 적음
• => 한꺼번에 적는게 더 효율적이고
• => 모아진 data들의 sector 위치를 잘 어떻게 계획해서 적으면 더 효율적으로 적을 수 있고
• => 그러면 쓸 때마다 write 하는걸 피할 수 있어서 아무튼 이게 더 빠르다..고 

• 근데 database 같은 곳은, 이렇게 기다렸다가 적으면, 중간에 data가 날라갈 위험이 있어서 buffering 안함
• => fsync() 를 사용하여, 바로바로 data를 적어준다.