Implementing file system

File System Structure

- 파일 시스템은 많은 다른 레이어들로 구성되어 있다. (아래쪽은 물리적 장치에 가까움)

  파일+디렉토리 와 비슷하다

* Application programs : record

* Logical file system : 파일 시스템에 필요한 모든 meta-data 가짐(파일 내용 빼고). directory structure을 저장

* file-organization module : 논리적 파일 블록 주소를 대응하는 물리적 파일 블록 주소로 변환

* basic file system : 파일 시스템, 디렉토리, 데이터블락을 가진 버퍼들을 할당, 유지

* I/O control : device drivers and interrupt handlers

Opening and Accessing Files

a) file open

b) file read

Directory Implementation

- Linear List

* maintain an on-disk doubly-linked list of names and pointers to FCB(File control block) structures

* the list can be kept sorted according to file name

* Upon deletion of a file, the corresponding entry can be recycled

* problem is slow

- Hash table

* more complex to maintain

* faster search

Allocation Method

1 Continuous allocation

* 각 파일은 디스크에서 연속적인 블락을 차지한다

* 디렉토리는 starting location(block #)와 length(# of blocks) 정보만 가지면 된다

* Random access

* Potential problems

+ Dynamic storage allocation problem : first/best/worst fit

+ External fragmentation : compaction/defragmentation -> expensive

+ Determination of the size of the file in advance : 필요한 만큼의 공간이 찾아지고 할당 될 수 있도록 한다 internal fragmentation을 통해

2 Linked allocation

* 각 파일은 디스크 블럭들의 linked list - 블록들은 디스크에 아무렇게

나 있을 수 있다

* 디렉토리는 파일의 첫, 마지막 블럭을 가리킨다

* continuous allocation의 모든 문제 해결! no fragmentation! files can grow! 

* Potential problems

+ good for only sequential access files, not direct access

+ 공간 낭비(모든 블럭에는 다음 블럭을 가리키는 포인터가 추가로 저장되어야 하므로) - cluster. 작게 나뉜 것들을 붙여서 internal fragmentation 높인다

+ Poor reliability : 포인터를 잃거나 손상되면 파일은 복구 불가하다.. double-linked list를 쓰면 되지만 overhead(처리시간 같은 것)가 늘어난다

* File-Allocation Table(FAT)

+ 디스크 시작점의 테이블은 각 디스크 블럭에 대한 entry가 있으며 블락#로 indexed

+ 블럭 #에 의해 인덱스된 테이블 entry는 파일에서의 다음 블럭 #를 갖고 있다

+ 디스크에 여러 포인터들이 흩어져 있는 문제점을 해결 (포인터 점핑이 훨씬 빠르다)

+ finding free block is simple -> to find the first 0 entry in the table

3 Indexed allocation

* index block에 모든 포인터를 가져온다 (인덱스 블락의 i번째 entry는 i번째 블락을 가리킨다)

* 디렉토리는 인덱스 블럭의 주소를 갖는다

* 페이징과 비슷

* Random access without external fragmentation, but overhead of index block : linked allocation의 포인터 오버헤드보다 인덱스 블럭의 포인터 오버헤드가 더 크다. 인덱스 블럭을 최대한 작게 만들어야 하지만 너무 작으면 큰 파일에 대한 포인터가 충분하지 않을 수 있다

* How  to organize index block?

1) Linked scheme

- link blocks of index table

- index block = header,block addresses, pointer to another index block

2) Multi-level scheme

- a first level index block to point to a set of second-level index blocks, which in turn point to the file blocks

- block size : 4096 bytes, pointer size : 4 bytes

- two level index scheme -> up to 4GB file size

3) Combined scheme

- for a small file it seems a waste to keep a large index

- for a medium-sized file it seems a waste to keep multi-level index

- How about keeping all options open?

few pointers to actual disk blocks(12 blocks)

a pointer to a single-level index

a pointer to a two-level index

a pointer t a three-level index

= small files don't even use an index

- Unix inode에 사용됨

* Unix inode

block size=512 bytes

Pointer = 4bytes (=32 bit)

Max file size = 12*512 + 128*512 + 128^2*512 + 128^3*512 bytes

= 12 block pointer + singly + doubly + triply (128=512/4bytes)

Free space management

How do we keep track of free blocks?

1 Bit Vector

- 한 비트 당 디스크 블럭 하나를 나타내는 비트 배열. 1=free 0=not free(allocated)

- 장점: 간단하고 free block 찾기가 쉽다

- 단점: bitmap이 커질 수 있어 메모리에 fully cacheable되지 못할 수 있다

2 Linked List

- Maintain a chain  of free blocks, keeping a pointer to the first block

- Traversing the list could take tie, but it rarely happens

- FAT deals with free blocks in the data structure that keeps the "linked list" of non-free blocks

3 Grouping

- stores addresses on n free blocks in the first free block

- the first n-1 of these blocks are actually free. last block contains the addresses of another n free block

4 Counting

- Based on the fact that several contiguous blocks may be allocated and freed simultaneously

- keeps the address of the first free block and the number of free contiguous blocks that follow the first block

Efficiency and Performance

Consistent Checking

Recovery