22. File System Implementations 1 & 2

이화여자대학교 반효경 교수님의 운영체제 강의 25강을 듣고 정리한 내용이다.

 

✏️ Allocation of File Data in Disk

✔️ Contiguous Allocation (연속 할당)

Contiguous Allocation

• 하나의 파일이 디스크 상에 연속해서 저장되는 기법
• 파일의 크기가 균일하지 않기 때문에 중간중간 hole이 생기는 문제 발생
• 페이징 기법과 유사
• 장점
  • Fast I/O
    • 많은 양의 데이터를 빠르게 가져올 수 있음 
    • 한번의 seek/rotation으로 많은 바이트 transfer
    • Realtime file 용으로, 또는 이미 run 중이던 process의 swapping 용
  • Direct access(=random access) 가능

• 단점
  • external fragmentation
  • File grow가 어려움
    • 파일 생성 시 얼마나 큰 hole을 배당할 것인가?
    • grow 가능 vs. 낭비 (internal fragmentation)

 

 

---

 

✔️ Linked Allocation (연결 할당)

• 장점 - External fragmentation 발생 안 함
• 단점  
  • No random access
  • Reliability 문제 - 한 sector가 고장나 포인터가 유실되면 많은 부분을 잃음
  • Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림 - 512 bytes/sector, 4 bytes/pointer
• 변형 - File-allocation table (FAT) 파일 시스템
  • 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

---

✔️ Indexed Allocation (인덱스 할당)

• 장점 - External fragmentation이 발생하지 않음 / Direct access 가능
• 단점
  • Small file의 경우 공간 낭비 - 실제로 많은 파일들이 small
  • Too large file의 경우 하나의 block으로 인덱스를 저장하기에 부족
    • 해결방안 - linked scheme / multi-level index

---

✏️ UNIX 파일시스템의 구조

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

• Boot block - 부팅에 필요한 정보(bootstrap loader)
• Superblock - 파일 시스템에 관한 총체적인 정보를 담고 있음
• Inode - 파일 이름을 제외한 파일의 모든 메타 데이터를 저장
• Data block - 파일의 실제 내용을 보관

---

✏️ FAT File System

---

✏️ Free-Space Management

✔️ Bit map or bit vector

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

✔️ Linked list

• 모든 free block들을 링크로 연결(free list)
• 연속적인 가용공간을 찾는 것은 쉽지 않음
• 공간의 낭비가 없음

 

✔️ Grouping

• linked list 방법의 변형
• 첫번째 free block이 n개의 pointer를 가짐
  • n-1 pointer는 free data block을 가리킴
  • 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐

 

✔️ Counting

• 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안
• (first free block, # of contiguous free blocks)을 유지

---

✏️ Directory Implementation

✔️ Linear List

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

 

✔️ Hash Table

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

✔️ File의 metadata의 보관 위치

• 디렉토리 내에 직접 보관
• 디렉토리에는 포인터를 두고 다른 곳에 보관 - inode, FAT 등

 

✔️  Long file name의 지원

• <file name, file metadata>의 각 리스트에서 각 엔트리는 일반적으로 고정 크기
• file name이 고정 크기의 엔트리 길이보다 길어지는 경우 엔트리의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
• 이름의 나머지 부분은 동일한 디렉토리 파일의 일부에 존재

---

✏️ VFS and NFS

✔️ Virtual File System(VFS)

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

 

✔️ Network File System(NFS)

• 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
• NFS는 분산 환경에서의 대표적인 파일 공유 방법

---

✏️ Page Cache and Buffer Cache

✔️ Page Cache

• Virtual memory의 paging system에서 사용하는 page frame을 caching 관점에서 설명하는 용어
• Memory-Mapped I/O를 쓰는 경우 파일의 I/O에서도 page cache 사용

 

✔️ Memory-Mapped I/O

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

 

✔️ Buffer Cache

• 파일시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
• 파일 사용의 locality 활용 - 한번 읽어온 블록에 대한 후속 요청시 buffer cache에서 즉시 전달
• 모든 프로세스가 공용으로 사용
• Replacement algorithm 필요 (LRU, LFU 등)

 

✔️ Unified Buffer Cache

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