File Systems Implementation - 파일 시스템의 구현

Allocation of File Data in Disk

• Contiguous Allocation
• Linked Allocation
• Indexed Allocation

 

Contiguous Allocation

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

 

Linked Allocation

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

 

Indexed Allocation

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

 

UNIX 파일시스템의 구조

• 유닉스 파일 시스템의 중요 개념
  • Boot block
    • 부팅에 필요한 정보 (bootstrap loader)
  • Superblock
    • 파일 시스템에 관한 총체적인 정보를 담고 있다.
  • Inode
    • 파일 이름을 제외한 파일의 모든 메타 데이터를 저장
  • Data block
    • 파일의 실제 내용을 보관( Data block → directory file구조 : file이름 - inode 번호 )

 

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)을 유지

 

Linked Free Space List on Disk

 

Directory Implementation

• Linear list
  • <file name, file의 metadata>의 list
  • 구현이 간단
  • 디렉터리 내에 파일이 있는지 찾기 위해서는 linear search 필요 (time-consuming)
• Hash Table
  • linear list + hashing
  • Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
  • search time을 없앰
  • Collision 발생 가능
  

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

 

VFS ans NFS

• Virtual File System (VFS)
  • 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스 (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를 쓰는 경우 file의 I/O에서도 page cache 사용
• Memory-Mapped I/O
  • File의 일부를 virtual memory에 mapping시킴
  • 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함
• Buffer Cache
  • 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
  • File 사용의 locality 활용
    • 한번 읽어온 block에 대한 후속 요청 시 buffer cache에서 즉시 전달
  • 모든 프로세스가 공용으로 사용
  • Replacement algorithm 필요 (LRU, LFU 등)
• Unified Buffer Cache
  • 최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨
  

 

프로그램 실행

1. 프로그램이 파일 시스템의 실행파일 형태로 저장되어 있다가 실행시키면 프로세스가 된다.
2. 프로세스가 되면 그 프로세스만의 독자적인 주소공간인 Virtual Memory라는 것이 만들어진다.
3. 주소변환을 해주는 하드웨어에 의해서 당장 필요한 부분은 물리적 메모리에 올라가게 된다.
4. 물리적 메모리는 공간이 한정되어 있으므로 쫓겨나는 것들은 Disk의 Swap Area로 넘어간다.

cf)

1. Memory Mapped I/O를 쓰는 대표적인 방법이 실행파일에 해당하는 Code 부분이다.Code 영역 부분은 별도의 Swap Area 영역을 가지고 있지 않고 파일 시스템에 파일로 존재하는 내용이 그대로 프로세스 주소 영역에 매핑이 되어있다. 만약, 이 프로그램이 특정 Code에 접근하는데 메모리에 안 올라와 있다면 Swap Area에서 올리는 것이 아니라 파일에서 올려 써야 한다.(Code 영억 부분은 메모리에 올라간 다음 쫓겨날 때 Swap Area로 내려가지 않는다. read only라서 File System에 저장되어 있기 때문이다.)
2. 실행파일도 파일시스템에 저장되어 있지만 데이터 파일도 저장되어있다. 프로그램이 실행되다가 자신의 메모리 접근만 하는 것이 아니라 파일의 내용을 읽어오라는 read 시스템 콜을 할 수 있고, Memory Mapped I/O를 쓸 수 도 있다.

 

Memory Mapped I/O 이용

1. 운영체제가 데이터 파일의 일부를 Virtual Memory 주소공간 일부에다가 매핑을 해준다.
2. 프로그램이 실행되면서 이 메모리 위치를 접근했을 때 메모리에 안올라와있으면 Page Fault를 일으킨다.
3. 그러면 운영체제가 Page Fault가 일어난 Page를 물리적 메모리에 올려준다.
4. 그 이후는 가상 메모리 Page가 물리적 메모리의 Page와 Mapping이 되어 접근할 때는 운영체제 도움을 받지 않아도 된다.( 운영체제 도움 없이 물리적 메모리에 읽거나 쓰거나 하게 됨 )
5. 메모리에 쫓겨날 때는 Swap Area에 쫓겨나는 게 아니라 File System에 수정된 내용을 써주고 메모리에서 쫓아낸다.

• 단점 : 여러 프로세스가 같이 공유하게 되면 일관성을 주의 해야한다.

 

Read/Write 시스템 콜 이용 시

1. read 시스템 콜로 파일 요청
2. 운영체제는 자신의 Buffer Cache에 내용을 읽어온다.
3. Unified Buffer Cache는 요청한 데이터 파일의 내용이 이미 Buffer Cache에 올라와 있다면 그 내용을 카피해서 사용자 프로세스에게 전달한다.

 

 

출처

KOCW :  이화여대 반효경 교수님 <운영체제, 2014>