Allocation of File Data in Disk: 파일을 디스크에 저장하는 방법
1) Contiguous Allocation(연속 할당)
▷ 단점
- External fragmentation(외부조각)
- File grow가 어려움 (file을 위해 미리 hole을 배당해 둔다면, internal fragmentation(내부조각) 문제가 발생한다.)
▷ 장점
- Fast I/O: 데이터가 연속할당 되어 있기 때문에, 한 번의 seek/rotation으로 많은 바이트 transfer
- --> realtime file, process swapping용으로 쓰인다.
- Direct access(= random access)(직접접근) 가능하다.
2) Linked Allocation
▷ 장점
- External fragmentation(외부조각)이 발생하지 않는다.
▷ 단점
- Random access(직접접근)이 불가능하고, 순차접근만 가능하다.
- Reliability 문제: 한 sector가 고장나서 pointer가 유실되면, 많은 부분을 잃는다.
- 공간 효율성 문제: pointer를 위한 공간이 block의 일부가 된다. (512 bytes/sector, 4 bytes/sector)
▶ File-Allocation Table: FAT
: 포인터를 별도의 위치에 보관하여, reliability 문제, 공간 효율성 문제 해결
3) Indexed Allocation
▷ 장점
- External fragmentation(외부조각)이 발생하지 않는다.
- Direct access(직접접근)이 가능하다.
▷ 단점
- small file의 경우, 공간 낭비: index를 위한 block, 실제 데이터 저장을 위한 block 이렇게 두 개가 항상 필요하다.
- too large frile의 경우, 하나의 block으로 index를 저장하기에 부족
--> 해결방안:
- linked scheme: 마지막 위치에서 또 다른 index block을 가리키도록 한다. --> 큰 파일 커버 가능
- multi-level index
실제 파일 시스템에서의 할당 방법
1) UNIX: Inode list
▶ Boot block: 부팅에 필요한 정보 (모든 파일 시스템의 가장 앞에 나오는 정보)
▶ Superblock: 파일 시스템에 관한 총체적인 정보
▶ Inode list: 파일 이름을 제외한 파일의 모든 메타정보
- 디렉토리: 파일의 모든 메타정보를 저장하는 것은 아니다. (파일 이름을 갖고 있음)
▶ Data block: 파일의 실제 내용
2) MS-DOS: FAT
▷ FAT file system: Linked allocation의 단점들을 전부 극복한 file system 방식
- random access(직접접근) 가능
- 공간 효율성 문제 해결: 포인터를 별도의 위치에 보관한다: FAT
- Reliability 문제 해결: 포인터가 유실되더라도, FAT에 data의 위치 정보가 담겨 있기 때문에 모든 정보가 손실되지 않는다.
Free-Space Management: 비어있는 block 관리 방법
▶ Bit map(Bit vector)
- Bit map에서 1/0 표시를 통해, block이 사용중인지(1), 아닌지(0) 표시한다.
- 단점: Bit map을 위한 부가적인 공간이 필요하다: block 1개 = 1 bit
- 장점: 연속적인 n개의 free block을 찾는데 효과적이다: 연속적으로 bit map = 0인 것
▶ Linked list
- 모든 free block들을 링크로 연결한다: free link
- 단점: 연속적인 가용공간을 찾는 것이 쉽지 않다.
- 장점: 공간 낭비가 없다.
▶ Grouping
- Linked list 방법의 변형(Linked list: 하나씩 가리킴 // Grouping: n개씩 가리킴)
- 첫 번째 free block이 n개의 포인터를 가진다: (n-1) 포인터는 free data block을 가리키고, 마지막 포인터가 가리키는 block은 또다시 n개의 포인터를 가진다.
▶ Counting
- (first free block, #(number) of contiguous free blocks)
- 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안한 방법 --> 연속적인 free block을 찾는데 효과적이다.
Directory(디렉토리) Implementation
▶ Linear list
- <file name, file의 metadata>
- 단점: 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search가 필요하다.
▶ Hash table
- <file name(Hash function), file의 metadata>
- Hash table은 file name을 이 파일의 linear list 위치로 바꿔준다.
- 장점: search time이 없다.
- 단점: collision이 발생할 수 있다.
File의 metadata 보관 위치
▶ 디렉토리 내에 직접 보관
▶ 디렉토리에는 포인터를 두고, 다른 곳에 보관: inode, FAT
- UNIX - inode: 파일 이름을 제외한 파일의 모든 메타정보를 저장한다.
- MS-DOS - FAT: 데이터의 위치정보를 저장해서, 포인터를 대체할 수 있게 한다.
Long file name의 지원
- <file name, file의 metadata>의 list에서 각 엔트리는 일반적으로 고정 크기이다. 따라서 long file name의 경우 file name에 다 들어가지 않을 수 있다.
- 따라서 file name이 고정 크기 엔트리 길이보다 길어지는 경우, 엔트리의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 둔다.
VFS & NFS
▶ VFS(Virtual File System)
: 서로 다른 다양한 file system에 대해, 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 운영체제 layer
▶ NFS(Network File System)
: 분산 환경에서 네트워크를 통한 파일 공유 방법
Page cache & Buffer cache
▶ Page cache
: virtual memory paging system에서 사용하는 page frame의 caching 관점에서 설명하는 용어
▶ Buffer cache
: 파일시스템을 통한 I/O연산은 메모리의 특정 영역인 buffer cache를 사용한다.
- file 사용의 locality 활용: 한번 읽어온 block에 대한 후속 요청 시, buffer cache에서 즉시 전달한다.
▶ Unified Buffer cache
: buffer cache가 page cache에 통합된다: buffer cache도 page 단위로 관리한다.
▷ Memory-Mapped I/O
: file의 일부를 virtual memory mapping시킨다.
'운영체제' 카테고리의 다른 글
| [운영체제] KOCW 12.3 - Ch11: File System Implementation (0) | 2023.06.10 |
|---|---|
| [운영체제] KOCW 12.1 - Ch10: File System (0) | 2023.06.10 |
| [운영체제] KOCW 11.2 - Ch9: Virtual Memory (0) | 2023.06.10 |
| [운영체제] KOCW 11.1 - Ch9: Virtual Memory (0) | 2023.06.10 |
| [운영체제] KOCW 10 - Ch8: Memory Management (0) | 2023.06.10 |
