10. File Systems

File Systems

File and File System

• File
  • A named collection of related information
  • 일반적으로 비휘발성의 보조기억장치에 저장
  • 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 보여줌
  • Operation
    • create, read, write, delete, open, close 등
• Metadata
  • 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보
  • ex) 파일 이름, 유형, 저장 위치, 파일 크기
  • ex) 접근 권한, 시간(생성/변경/사용), 소유자 등
• File System
  • 운영체제에서 파일을 관리하는 부분
  • 파일 및 파일의 Metadata, 디렉토리 정보 등 관리
  • 파일의 저장 방법 결정
  • 파일 보호 등

Directory and Logical Disk

• Directory
  • 파일의 Metadata 중 일부를 보관하고 있는 특별한 파일
  • 디렉토리에 속한 파일 이름 및 파일의 metadata 등 보관
  • Operation
    • search for a file, create a file, delete a file
    • list a directory, rename a file, traverse the file system
• Partition(=Logical Disk)
  • 하나의 디스크 안에 여러 Partition을 두는게 일반적
  • 여러 개의 물리적 디스크를 하나의 Partition으로 구성하기도 함
  • 디스크를 Partition으로 구성한 뒤 각각의 Partition에 file system을 깔거다 swapping 등 다른 용도로 사용 가능

open()

• File의 Metadata를 메인 메모리에 올리는 행위
• Directory path search 하는 데 너무 많은 시간 소요
  • read/write와 open을 따로 두는 이유!

• 운영체제에서 파일을 복사한 후, 전달하는 것이 Buffer Cache
  • 운영체제가 cache한 정보를 다 가지고 있으므로 LRU, LFU 등의 알고리즘 사용 가능

File Protection

• 각 파일에 대해 누구에게 어떤 유형의 접근을 허락할 것인가?
• Access Control 방법

• Access control Matrix는 모든 사용자에 대한 접근 권한 항목을 만들어야 하기 때문에 메모리 낭비가 큼
  • 주체에 따라 Linked List를 이용해 만드는 방법을 생각해볼 수 있음
  • 그러나, 이 역시 Overhead가 큼
• 일반적으로 Grouping 기법 사용

File System의 Mounting

Access Methods

• 순차 접근(sequential access)
  • 카세트 테이프를 사용하는 방식처럼 접근
  • 읽거나 쓰면 offset은 자동으로 증가
• 직접 접근(direct access, random access)
  • LP 레코드 판과 같이 접근
  • 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있음

Allocation of File Data in Disk

Contiguous Allocation

• 하나의 파일이 Disk 상에 연속해서 저장되도록 하는 것
• 장점
  • Fast I/O
    • 한 번의 seek / roation으로 많은 Byte transfer
    • Realtime file용으로, 또는 이미 run 중이던 프로세스의 swapping용
  • Direct access(=random access) 가능
• 단점
  • External Fragmentation
  • File grow가 어려움
    • File 생성 시 얼마나 큰 hole을 배당할 것인가?
    • grow 가능케 넉넉히 배당할 수도 있지만, grow 하지 않는다면 그 공간은 낭비(Internal Fragmentation)

Linked Allocation

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

Indexed Allocation

• Indexed 블럭에 파일의 위치를 저장하여 보여줌
• 장점
  • External Fragmentation 발생하지 않음
  • Direct access 가능
• 단점
  • Small file의 경우 공간 낭비
    • 실제로 많은 파일들이 small
  • Large File의 경우 하나의 block으로 index를 저장하기에 부족
    • 해결 방안
    • Linked Scheme: 또 다른 indexed block을 찾아가게 함
    • Multi-level index: like Two-level page

UNIX File System의 구조

• Boot block
  • 부팅에 필요한 정보 저장(Bootstrap Loader)
• Super block
  • 파일 시스템에 관한 총체적 정보를 담고 있음
• Inode list
  • 파일 이름을 제외한 파일의 모든 Metadata 저장
  • 디렉토리는 특정 파일의 Metadata만 가지고 있지만, Inode list는 모든 파일의 Metadata를 가지고 있음
• Data block
  • 파일의 실제 내용 보관
• Indexed allocation을 사용하는 UNIX File System
  • 파일 크기에 따라 direct blocks만 사용할지,
  • single, double, triple indirect를 사용할지 결정
  • 한정된 크기의 inode로 모든 크기의 파일 관리 가능

FAT File System

• 파일의 Metadata 중 일부(ex.위치 정보)를 FAT에 저장
  • 블럭의 다음 블럭을 저장하는 형식
  • 이미 Memory에 올라와 있는 FAT만 보면 되기 때문에, Direct access 가능해짐
  • 포인터 하나가 유실되더라도 FAT에 정보가 있기 때문에 Reliability 문제 해결
• 나머지 Metadata는 Data block이 가지고 있음
• FAT은 중요한 정보이기 때문에 보통 Disk에 2 copy 이상 저장

Free-Space Management

Bit map or bit vector

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

Linked List

• 모든 Free block들을 링크로 연결
• 부가적 공간 낭비가 없음
• 연속적 가용공간을 찾는 것이 쉽지 않음

Grouping

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

Counting

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

Directory Implementation

• Linear List
  • <file name, file의 metadata>의 list
  • 구현이 간단
  • 디렉토리 내에 파일이 있는지 찾기 위해서는 Linear search가 필요
• Hash Table
  • Linear list + hashing
  • Hash Table은 File name을 이 파일의 linear list의 위치로 바꾸어줌
  • Search time을 없애나, Collision 발생 가능
• File metadata의 보관 위치
  • 디렉토리 내에 직접 보관하거나,
  • 디렉토리에는 포인터를 두고 다른 곳(ex. FAT, inode)에 보관

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

VFS and NFS

• Virtual File System(VFS)
  • 서로 다른 다양한 file system에 대해 동일한 System call interface(API)를 통해 접근할 수 있게 해주는 운영체제의 layer
• Network File System(NFS)
  • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
  • NFS는 분산 환경에서의 대표적 파일 공유 방법

Page Cache and Buffer Cache

• 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 시킴
  • Mapping 시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
  • 이미 메모리에 올라온 File은 마치 내 File 처럼 사용할 수 있는 장점!

• Buffer Cache
  • 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 Buffer cache 사용
  • File 사용의 locality 활용
    • 한 번 읽어온 block에 대한 후속 요청 시, buffer cache에서 즉시 전달
  • 모든 프로세스가 공용으로 사용
  • Replacement Algorithm 필요

• Unified Buffer Cache
  • 최근 운영체제에서는 기존의 Buffer cache가 Page cache에 통합
  • 따라서 File block들도 Page 크기 단위(4KB)로 읽어옴