1.FS Implementation

Disk에 파일을 저장하는 3가지 방법

1.Contiguous Allocation

하나의 파일이 연속적으로 저장되는 방법

단점 : 중간중간 빈 블럭이 생길 수 있음(external fragmentation) -낭비

/파일 크기 키우는데 재약이 있음(File grow)

장점 : 빠른 I/O가 가능함(DISK 헤드가 이동하는 시간이 대부분)

/한번의 SEEK/rotation로 많은 바이트 transfer

Realtime file 용으로, 또는 이미 run 중이던 process의 swapping 용으로 좋음

Direct access(=random access) 가능(주소 참조할 필요없이 +offset으로 접근)

 

Linked Allocation

블럭마다 연결되어 있음

장점 : External fragment가 발생하지 않음

단점 : 중간위치를 보려면 앞의 블록을 모두 접근해봐야함 (No random access)

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

Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림

• 512 bytes/sector, 4bytes/pointer

변형

File-allocation table (FAT) 파일 시스템

• 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

Indexed Allocation

index블록이 저장된 block의 위치정보를 하나의 블록에 모두 갖고 있음

인덱스 블록만 보고 바로 접근 가능

장점 : 외부조각이 생기지 않으면서 직접접근 가능

단점 : 작은 파일의 경우 공간 낭비

/큰 파일의 경우, 해결 방안 : linked schema, multi-level index

운영체제 커널을 찾아 메모리에 올리며 부팅이됨 - Boot block

Super block이 빈 블럭 및 inode와 data를 구별하여 다 알고있음

file하나당 - inode하나(그 파일의 metadata정보)

double indirect, triple indirect : multi level index 접근 방식

대부분의 작은 파일은 바로 접근 하며 가끔 큰파일은 indirect를 통해 접근

 

FAT File System

bad sector가 나면 없어지는 문제등을 해결

FAT이라는 별도의 table에 저장 - 그 블럭의 다음 블럭 위치를 저장(FAT에서 다음블럭 위치를 찾음)

장점 : 직접 접근이 가능하다. 포인터 하나가 유실되더라도 FAT에 데이터가 있다.

/FAT은 중요한 정보라 디스크에 두 개 이상 있음

 

Free space Management

Bit-map : 각 블록별 번호에 bit로 사용중인지 0/1로 구별

/bit map은 부가적인 공간을 필요로 함, 연속적인 n개의 free block을 찾는데 효과적

Linked list - 모든 free bloc을 링크로 연결, 연속적 가용공간 찾기 어려움, 공간낭비가 없다.

Grouping ?

 

Directory Implementation

Linear list - <file name, file metadata>의 list / 구현이 간단 / 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요 (time-consuming)

Hash Table - linear list +hasing / Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌 / search time을 없앰 / Collision 발생 가능

 

File의 metadata의 보관 위치

• 디렉토리 내에 직접 보관

• 디렉토리에는 포인터를 두고 다른 곳에 보관

  • inode, FAT 등

Long file name의 지원

• <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정크기

• file name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법

Virtual File System (VFS)

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

 

Network File System (NFS)

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

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

Page Cache

Virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어

Memory-Mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용

 

Memory-Mapped I/O

File의 일부를 virtual memory에 mapping시킴

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

 

Buffere Cache

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

file 사용의 locality 활용

• 한번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전달

모든 프로세스가 공용으로 사용

Replacement algorithm 필요 LRU, LFU등

Unified Buffer Cache

• 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨

Page Cache와 Buffer Cache의 차이점