File System Implementation

<Allocation of File data in Disk>

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

<Contiguous Allocation>

하나의 파일이 디스크에 연속해서 저장되는 것을 말한다. directory는 파일의 메타데이터를 가지고 있다. 

* 단점

- external fragmentation

- file grow가 어렵다.

 -> 파일 생성 시 얼마나 큰 hole을 배당할 것인가?

 -> grow 가능 (파일이 커질 걸 생각해서 미리 자리 배당하기) vs 낭비 (internal fragmentation)

 

* 장점

 - fast i/o

  -> 한번의 seek/rotation으로 많은 바이트 transfer

  -> realtime file 용으로, 또는 이미 run 중이던 process의 swapping 용 swap area -> 어차피 프로세스 종료되면 사라지니까 공간 효율성보다는 빠른(속도 효율성이 중요하다.)

- direct access(= random access) 가능

  -> ex) tr 프로세스 접근하려면 14 + 3 하면 된다. 14,15,16이 tr이구나 알 수 있음

 

<Linked Allocation>

파일의 데이터를 연속적으로 저장하는 것이 아니라 빈 위치면 막 넣는다. 파일의 시작과 끝만 가지고 있음

* 장점

 - external fragmentation(외부 조각) 발생하지 않는다.

 

* 단점

 - No random access (직접 접근 x) -> 순차 접근만 가능하다(만약에 4번째 블록(중간 위치) 것 보고 싶어도 1-2-3 이렇게 지나가면서 봐야 함 지나치는거 안되고 순서대로만!) -> 디스크 헤드의 이동이 많다 -> 시간이 오래 걸린다.

 - Reliability 문제: 한 sector가 고장나면 pointer 유실된다 -> 많은 부분을 잃음

 - pointer을 위한 공간이 block의 일부가 되어 공간 효율성을 떨어트린다. 한 섹터당 512 바이트인데 포인터는 4 바이트여야 하므로 실제 데이터 저장 공간은 512-4 바이트임

 

* 변형

 - File - allocation table (FAT) 파일 시스템: 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제를 해결한다.

 

<Indexed Allocation>

index block은 파일이 어디에 저장되어 있음을 열거하는 블록이다. 이 파일의 앞에서부터 네번째 블럭 보고시파하면 10번째 블록 보면 된다.

* 장점

 - external fragmentation 발생하지 않는다.

 - direct Access 가능하다

 

 * 단점

 - small file의 경우 공간이 낭비된다 (실제로 많은 file들이 작음)

 - too large file의 경우 하나의 block으로 index를 저장하기 부족할 수 있다. -> linked scheme / multi-level index

linked scheme: 죽 인덱스 플록에 파일들 위치 적다가 다 못적으면 마지막에 또 다른 인덱스 블록 위치 적어둔다. 일종의 직렬 연결이라고 보면 됨

multi-level index: 인덱스가 데이터의 위치를 바로 가리키는 것이 아니라 또다른 인덱스를 가리킨다.

 

 

<UNIX 파일 시스템의 구조>

어떤 파일 시스템이건 boot block이 제일 먼저 부팅할 때 0번 블럭 메모리에 올리는게 그게 바로 boot block이다. Index allocation 변형 시스템

* 유닉스 파일 시스템의 중요 개념

 - Boot block: 부팅에 필요한 정보(bootstrap loader) 0번 블록

 - super block: 파일 시스템에 관한 총체적인 정보를 담고 있다.

 - Inode(Index-node): 파일 이름을 제외한 파일의 모든 메타데이터를 저장한다.

 - Datablock: 파일의 실제 내용을 보관한다. 파일 이름은 디렉토리가 갖고 있다.

파일의 메타데이터가 그 파일을 가지고 있는 디렉토리에 저장되어 있다고 배웠지만 unix에서는 파일의 메타데이터 일부만 디렉토리가 갖고 있고 나머지는 Inode가 갖고 있다. file의 메타데이터 중 이름만 디렉토리가 갖고 있고 나머지는 Inode가 가지고 있음

유닉스 파일 시스템은 위치 정보를 index allocation 변형으로 저장하는데 direct, single, double, triple 4 가지로 나눈다. 작은 데이터(파일 크기가 작다) -> 다이렉트 인덱스만 갖고 저장 가능하다. 매우 큰 데이터 -> single indirect / double triple 등... 파일 크기는 사실 작으므로 아이노드만 메모리에 올라오면 바로 찾을 수 있다. 가끔 있는 일이지만 큰 데이터가 들어오면 datablock 들렸다가 찾으면 된다. 

 

<FAT File System>

directory 217 보고 fat 217 보면 618,fat 618 보면 339 fat 339 보면 eof

실제 블록 접근하지 않는다. fat만 확인해보면 된다. 직접 접근이 가능하며 fat는 작은 테이블이고 메모리에 올려놨기 때문에 곧바로 파악이 가능하기 때문이다. 디스크 헤더가 움직일 필요가 없음 fat는 중요 정보라 2 카피 이상 가지고 있기에  bad sector 나도 괜찮다.

 

<Free Space Management>

그렇다면 빈 공간은 어떻게 관리할까?

* bIt map or bit sector

데이터 블록은 n개 있다

bit map 은 부가적인 공간을 필요로 한다. 

연속적인 n개의 free block을 찾는데 효과적이다. 

* Linked List

모든 free block들을 링크로 연결한다 (free size)

연속적인 가용 공간을 찾는 것은 쉽지 않다.

 공간의 낭비가 없다.

 

* Grouping

- Linked list 방법의 변형

- 첫번째 free block이 n개의 Pointer를 가짐

  n - 1 pointer는 free data block를 가리킨다.

  마지막 pointer가 가리키는 block을 또 다시 n pointer를 가진다.

 

* Counting

- 프로그램들이 종종 여러개의 연속적인 블록을 할당하고 반납한다는 성질에 착안함

- first Free block, # of Contiguous free blocks를 유지한다. 빈 블럭을 가리키고 그 이후 n개가 비어있다는 것 저장한다.

 

<Directory Implementation>

* Linear List

- file name, file의 metadata의 list

- 구현이 간단하다. (크기가 고정되어 있음)

- 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요하다.(time consuming/ 다 검색해봐야 함)

 

* Hash Table

- linear list + hashing

- hash table은 파일 이름을 이 파일의 linear list의 위치로 바꾸어준다.

- search time을 없앤다.

- collision 발생 가능 -> 다른 파일이름인데 같은 값이 나올 수도 있다.

 

<VFS and NFS>

VFS (Virtual File System)

- 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해준다.

 

NFS (Network File System)

- 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다. 

- NFS는 분산 환경에서의 대표적인 파일 공유 방법이다. 

 

<Page Cache and Buffer Cache>

* Page cache

- virtual memeory의 paging system에서 사용하는 page frame을 caching의 관점에서 사용하는 용어

- memory mapped I/O을 쓰는 경우 file의 I/O에서도 paging cache 사용한다.

 

* Memory Mapped I/O

- 파일의 일부를 virtual memory에 mapping 시킨다.

- Copying 할 필요가 없음 -> 속도 효율성면에서 좋음 그러나 다른 process가 share할 수 있다는 점에서 일관성 깨질 가능성이 있으므로 주의할 필요가 있음

- 매핑 시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 한다. 

얘는 파일의 일정 부분을 그 프로세스의 메모리에 매핑하고 쓴다. 원래 파일 오픈 한 후 read 시스템콜이나 write 시스템 콜 해야하는데 얘는 그런 시스템 콜을 하지 않고 메모리에 읽고 ㅆ느는데 그게 파일에 읽고 쓰는 것과 같은 효과가 난다.

 

* Buffered Cache

 - 파일 시스템을 통한 I/O연산은 메모리의 특정 영역인 buffer cache 사용한다.

 - file 사용의 locality 활용: 한번 읽어온 block에 대한 후속 요청 시 buffer cache에서 즉시 전달

 - 모든 프로세스가 공용으로 사용한다. 

 - replacement algorithm 필요로 한다. (LRU, LFU 등)

파일 데이터를 사용자가 요청했을 떄 디스크한테 읽어서 사용자한테만 주고 끝나는게 아니라 OS가 자기 자신 어딘가에 저장해두고 다른 얘나 같은 얘가 요청 다시 하면 buffere cahce에서 읽어온다. 

 

* Unified Buffer Cache 

 - 최근의 OS에서는 기존의 buffer cache가 page cache에 통합된다.