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