파일 시스템

반효경교수님 운영체제-2017 강의를 참고하여 작성하였습니다.

File and File System

• File
  • 정보와 관련된 이름있는 컬렉션
  • 일반적으로 비휘발성의 보조기억장치에 저장
  • 운영체제는 다양한 저장장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해줌
  • Operation
    • Create, read, write, reposition(lseek), delete, open, close
• File attribute(혹은 metadata)
  • 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들
    • 파일 이름, 유형, 저장된 위치, 파일 사이즈
    • 접근 권한(읽기/쓰기/실행), 시간(생성/변경/사용). 소유자 등
• File system
  • 운영체제에서 파일을 관리하는 부분
  • 파일 및 파일의 메타데이터, 디렉토리 정보 등을 관리
  • 파일의 저장 방법 결정
  • 파일 보호 등

Directory and Logical disk

• Directory
  • 파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일
  • 그 디렉토리에 속한 파일 이름 및 파일 attribute들
  • operation
    • Search for a file, create a file, delete a file
    • list a directory, rename a file, traverse the file system
• Partition(=Logial Disk)
  • 하나의 물리적 디스크 안에 여러 파티션을 두는게 일반적
  • 여러 개의 물리적인 디스크를 하나의 파티션으로 구성하기도 함
  • 물리적 디스크를 파티션으로 구성한 뒤 각각의 파티션에 file system을 깔거나 swapping(swap area) 등 다른 용도로 사용할 수 있음

Open()

• Open("/a/b/c")
  • 디스크로부터 파일 c의 메타데이터를 메모리로 가지고 옴
  • 이를 위하여 directory path를 search
    • 루트 디렉토리 "/"를 open하고 그 안에서 파일 "a"의 위치를 획득
    • 파일 "a"를 open한 후 read하여 그 안에서 파일 "b"의 위치를 획득
    • 파일 "b"를 open한 후 read하여 그 안에서 파일 "c"의 위치를 획득
    • 파일 "c"를 open
  • directory path의 search에 너무 많은 시간 소요
  • Open을 read / write와 별도로 두는 이유임
  • 한 번 open한 파일은 read/write시 directory search 불필요
  • Open file table
    • 현재 open된 파일들의 메타데이터 보관소 (in memory)
    • 디스크의 메타데이터보다 몇 가지 정보가 추가된다.
      • open한 프로세스의 수
      • file offset : 파일의 어느 위치에 접근 중인지 표시 (별도의 테이블을 둔다)
    • Fiel descriptor(file handle, file control block)
      • Open file table에 대한 위치 정보 (프로세스 별)

File Protection

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

• Access Control 방법

  • Access control Matrix

    	file 1	file 2	file 3
    user 1	rw	rw	r
    user 2	rw	r	r
    user 3	r

    • Access Control list : 파일별로 누구에게 어떤 접근 권한이 있는지 표시 column
    • Capability : 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시 row

  • Grouping

    • 전체 user를 owner, group, public의 세 그룹으로 구분
    • 각 파일에 대해 세 그룹의 접근 권한을 3비트씩으로 표시

  • Password

    • 파일마다 password를 두는 방법 (디렉토리 파일에 두는 방법도 가능)
    • 모든 접근 권한에 대해 하나의 password: all-or-nothing
    • 접근 권한별 password: 암기 문제, 관리 문제

Access Methods

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

File system implementation

Allocation of File Data in Disk

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

Contiguos Allocation

• 단점
  • external fragmentation
  • File grow가 어려움
    • file 생성시 얼마나 큰 hole을 배당할 것인가?
    • grow 가능 vs 낭비 (internal fragmentation)
• 장점
  • Fast I/O
    • 한번의 seek/rotation으로 많은 바이트 transfer
    • Realtime file 용으로, 또는 이미 run 중이던 process의 swapping용
    • Direct access(=random access) 가능

Linked Allocation

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

Indexed Allocation

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

UNIX 파일시스템의 구조

중요 개념

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

FAT File System

• 메타데이터를 directory가 다 가지고 있음
• FAT의 배열에 다음 block의 정보를 가지고 있음
• Linked Allocation을 활용했지만, Direct access가 가능하다.
• Reliablilty 문제를 해결

Free-space management

Bit map or bit vector

• Bit[i]
  • 0 : block[i] = free
  • 1 : block[i] = occupied
• Bit map은 부가적인 공간을 필요로 함
• 연속적인 n개의 free block을 찾는데 효과적

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, # of contiguous free blocks)을 유지

Directory Implementation

• Linear list
  • <file name, filed의 metadata> 의 list
  • 구현이 간단
  • 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요 (time-consuming)
• Hash Table
  • Linear list + hashing
  • Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
  • search time을 없앰
  • Collsion 발생 가능
• File의 metadata의 보관 위치
  • 디렉토리 내에 직접 보관
  • 디렉토리에는 포인터를 두고 다른 곳에 보관
  • Inode, FAT 등
• Long file name의 지원
  • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정 크기
  • File name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
  • 이름의 나머지 부분은 동일한 directory file의 일부에 존재

VFS and NFS

• Virtual File System (VFS)
  • 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스를 통해 접근할 수 있게 해주는 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를 쓰는 경우 file의 I/O에서도 page cache 사용

Memory-Mapped I/O

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

Buffer Cache

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

Unified Buffer Cache

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

Virtual memory에서 프로세스의 주소영역에서 Code 영역은 memory-mapped I/O를 활용