CS 정리 | OS | 9. 파일시스템 (2) | File system implementation | kocw 반효경 교수님

Allocation of File Data in Disk

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

Contiguous Allocation

• 단점
  • 외부조각 발생 가능성이 있음
  • file grow가 어려움
    • file은 write로 인해 크기가 바뀔 가능성이 있는데, 자유자재로 크기를 변경하기가 어려움
    • 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
  • realiability 문제
    • 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
    • pointer를 위한 공간이 block의 입루가 되어 공간 효율성을 떨어뜨림
• 변형
  • File-allocation table(FAT) 파일 시스템
    • 포인터를 별도 위치에 보관하여 reliability와 공간 효율성 문제를 해결

Indexed Allocation

• 장점
  • 외부조각이 발생하지 않음
  • direct access 가능
• 단점
  • small file의 경우 공간 낭비(실제로 많은 file들이 samll)
  • too large file의 경우 하나의 block으로 index를 저장하기에 부족
    • 해결 방안
      • linked scheme
      • multi-level index

UNIX 파일시스템의 구조

• 크게 4가지로 분류됨
  • Boot block
    - 부팅에 필요한 정보 (bootstrap loader)
  • super block
    • 파일 시스템에 관한 총체적인 정보를 담고 있다
  • Inode
    • 파일 이름을 제외한 파일의 '모든' 메타데이터를 저장
    • 고정된 크기 즉, 유한함
    • 참고로 디렉토리는 파일 이름과 inode 번호를 갖고 있음
    • 즉, 디렉토리는 파일의 모든 데마테이터를 갖고 있진 않는다 !
      
  • Data block
    • 파일의 실제 내용을 보관

FAT File System

• 중간에 파일포인터가 유실되더라도, fat에 모든 정보가 있으므로 realiability 문제를 해결할 수 있음
• 다음 파일 포인터를 알 수 있다는 아주 중요한 정보가 담겨 있으므로 fat은 2 copy 를 함 -> 신뢰성 확보

Free Space

비어 있는 블록은 어떻게 관리할 것인가?

• Bit map or bit vector
  

  • 사용중인 block인지 아닌지 bit로 표시 (unix의 경우 super block에 표시됨)
  • Bit map은 부가적인 공간을 필요로 함
  • 연속적인 n개의 free block을 찾는데 효과적

• Linked list

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

• Grouping

  • linked list 방법의 변형
  • 첫번째 free block이 n개의 pointer를 가짐
    • n-1 pointer는 free data block을 가짐
    • 마지막 Pointer가 가리키는 block은 또 다시 n pointer를 가짐
  • 비어 있는 블록을 (일부) 한꺼번에 찾을 수 있다는 점은 linked list보다 효과적이지만, 연속적인 빈 block을 찾기엔 여전히 쉽지 않음

• Counting

  • 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안
  • first free block, # of contiguous free blocks 를 유지
    • 빈 블록을 가리킬 뿐만 아니라, 연속 빈 블럭 개수까지 쌍으로 관리하겠다는 의미

  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 발생 가능 (hash 자료구조의 고질적인 문제)

• File의 metadata의 보관 위치

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

• 파일 이름이 너무 길면 어떻게 저장할까 🤔 ? (long file name의 지원)
  

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

VFS and NFS

파일 시스템 종류별로 서로 다른 시스템 콜을 호출해야한다면 사용자(프로세스) 입장에서 굉장히 혼란스러울 것이다. 그래서 보통 파일 시스템 종류와 상관없이 VFS나 NFS 인터페이스에 먼저 접근하게 된다.

• Virtual File

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

• Network File System

  • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
  • NFS는 분산 환경에서의 대표적인 파일 공유 방법임
    
    client 컴퓨터와 server 컴퓨터 두 대가 존재. 서로를 접근하기 위해선 NFS를 사용. 각 컴퓨터 내에서 파일시스템을 접근하기 위해선 VFS 사용!

Page Cache and Buffer Cache

• Page Cache
  • virtual memory의 page system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
  • memory-mapped I/O를 쓰는 경우 file의 I/O에서도 page cache를 사용
• memory-mapped I/O
  • file의 일부를 virtual memory에 mapping시킴
  • 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행 하게 함
  • 한 번 mapping을 하면 자신의 메모리 내에서 write, read를 할 수 있음
  • 그러나 여러 프로그램이 memory-mapped를 사용할 땐 데이터의 일관성 문제가 생길 수 있음
• Buffer Cache
  • 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
  • File 사용의 locality 활용
    • 한 번 읽어온 block에 대한 후속 요청 시 vuffer cache에서 즉시 전달
  • 모든 프로세스가 공용으로 사용
  • Replacemene algorithm 필요 (LRU, LFU 등)
• Unified Buffer Cache
  
  • 최근의 OS(ex. linux)에서는 기존의 buffer cache가 page cache에 통합되기도 함

프로그램의 실행

• 프로그램이 데이터 파일을 사용하는 방법 두 가지

  • read/write system call 호출
    

  • memory mapped IO (mmap() 호출)