09. 파일 시스템 구현 - 1

Allocation of File Data in Disk

Contiguous Allocation 연속 할당

하나의 파일이 디스크 상에 연속되어 저장되는 방식

 

ex) 블록의 크기가 6개인 파일이 있을 때
19번 블록이 시작점이라고 한다면 24번 블록까지 연속적으로 차지한다

단점

• 블록의 크기가 균일하지 않기 때문에 외부 조각이 발생할 수 있다
• file grow가 어렵다
  • file 생성 시 얼마나 큰 hole을 배당할 것인가?
  • grow 가능 vs 낭비 (내부 조각 발생)

장점

• i/o 작업이 빠르다
  • 하드디스크의 접근 시간은 대부분 헤드 이동의 오버헤드임
  • 한 번의 seek/rotation으로 많은 바이트를 전달할 수 있다
  • process의 swap area로도 사용 가능
• direct access(=random access)가 가능하다

Linked Allocation 연결 할당

연결 리스트 형태로 디스크 공간을 할당하는 방식

장점

• 외부 조각 문제가 발생하지 않는다

단점

• direct access가 불가능하다
  • 한 파일에 접근하고자 한다면 이전 파일을 전부 거쳐야만 그 위치를 알아낼 수 있다
• 의존성 문제
  • 포인터 하나가 오류가 나 유실되면 그 뒤에 있는 파일들은 접근이 불가능해진다
• 포인터를 위한 공간이 블록의 일부가 되어 공간 효율성을 떨어트린다
  • 512bytes/sector, 4bytes/pointer

변형

• File-allocation table(FAT)으로 효율적인 구현이 가능
  • 포인터를 별도의 위치에 보관하여 의존성과 공간 문제 해결

Indexed Allocation 인덱스 할당

디렉토리에 하위 파일들의 위치를 배열 형태로 저장해두는 방식

장점

• 외부 조각 발생 X
• direct access 가능

단점

• 작은 파일들의 경우 공간이 낭비된다 (인덱스를 위한 블록, 데이터를 실제로 저장하는 블록 이렇게 공간이 두 개 필요하기 때문)
• 너무 큰 파일의 경우 하나의 블록으로 인덱스 정보를 저장하기에 부족하다
  • 해결 방안
  1. linked scheme
  2. multi-level index

UNIX 파일시스템의 구조

Boot block

부팅에 필요한 정보가 담긴 block

컴퓨터를 부팅할 때 0번 블록을 가장 먼저 참조한다
어떤 시스템에서든 boot block이 가장 먼저 나온다

Superblock

파일시스템에 대한 총체적인 정보를 담고 있는 block

총체적인 정보 = 어떤 블록이 쓰이고 있고 어떤 블록이 빈 블록인지

Inode list (UNIX 파일시스템의 핵심)

파일 이름을 제외한 파일의 모든 메타데이터를 저장

파일의 이름은 디렉토리가 가지고 있다
파일 하나당 하나씩 할당됨

 

유닉스에서 파일의 위치정보를 저장하는 방식: indexed allocation을 살짝 변형해 사용하고 있다

 

큰 파일의 경우 single indirect를 따라가면 index block이 나오고 그 index block이 파일의 위치를 담고 있다
더 큰 파일의 경우 double indirect (index block이 한 단계 더 중첩됨), 그것보다 더 크면 triple indirect를 쓴다

Data block

파일의 실제 내용을 보관한다

FAT 파일 시스템

File-allocation table(FAT)

파일의 메타데이터 중 위치정보를 FAT이라는 곳에 보관한다
나머지 메타데이터는 디렉토리가 보관한다

 

FAT의 크기는 Data block의 크기에 따라 결정된다
Linked Allocation이 가지고 있던 문제는 한 포인터가 유실될 시 그 뒤에 있는 파일들에 접근할 수 없어진다는 점이다 (블록에 직접 접근하기 때문)
FAT 파일 시스템에서는 데이터의 위치 정보를 배열 형태로 저장해두어 블록에 직접 접근할 필요없이 FAT을 보고 그 위치로 바로 이동하면 된다. 따라서 직접 접근이 가능하다

Free space management

파일에 할당되지 않은 공간들은 어떻게 관리하는가?

Bit map or Bit vector

0이면 비어있음, 1이면 파일이 이미 할당됨

 

특징

• 디스크의 부가적인 공간을 필요로 한다
• 연속적인 n개의 free block을 찾는데 효과적이다

Linked List

비어있는 모든 블록을 linked list로 관리하는 방법

 

특징

• 연속적인 가용공간을 찾는 것이 어렵다
• 공간의 낭비가 없다

Grouping

linked list의 변형
첫 번째 free block이 n개의 pointer를 가진다
연속적인 빈 블록을 찾기에는 효과적이지 않다

Counting

빈 블록의 처음 위치와 그 이후 몇 개가 비어있음을 쌍으로 관리한다
연속적인 빈 블록을 찾기에 효과적이다

Directory Implementation

파일의 메타데이터를 담는 디렉토리를 어떻게 구현할 것인가?

Linear List

• <file name, file의 metadata>의 list
• 구현이 간단하다
• 디렉토리 내의 파일이 있는지 찾기 위해서는 선형 탐색을 해야 한다 (time-consuming)

Hash table

• linear list + hashing
• 파일의 이름에 해시 함수를 적용해 그 위치에 파일의 이름과 메타데이터를 저장한다
• 충돌 발생 가능
• 검색 시간 절약

메타데이터의 보관 위치

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

긴 파일 이름의 지원

• <file name, file의 metadata> list에서 entry는 일반적으로 고정되어 있다
• file name이 entry의 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방식

VFS and NFS

Virtual File System (VFS)

서로 다른 다양한 파일시스템에 대해 동일한 시스템 콜 인터페이스를 통해 접근할 수 있게 해주는 OS의 계층

Network File System (NFS)

분산 환경에서의 대표적인 파일 공유 방법
분산 시스템에서는 네트워크를 통한 파일 공유가 가능
서버와 클라이언트 둘 다 NFS를 지원해야 한다

Page Cache and Buffer Cache

Page cache

• 가상메모리 paging system에서 사용하는 page frame을 캐싱의 관점에서 설명한 용어
• memory-mapped i/o를 쓰는 경우 파일 입출력에서도 page cache를 사용한다

Memory-mapped i/o

• 파일 관련 연산 대신 사용하는 방법
• 파일의 일부를 가상 메모리에 mapping 시킴
• 메모리 접근 연산이 파일의 입출력 연산이 됨

Buffer cache

• 파일시스템의 i/o 연산 시 사용
• 한 번 읽어온 파일을 buffer cache에 저장해둔다
• file의 locality 활용
  • 한 번 읽어온 파일에 대해 후속 요청이 있을 시 buffer cache에서 바로 전달한다
• 모든 프로세스가 공용으로 사용
• 교체 알고리즘 필요 (LRU, LFU 등)

Unified Buffer cache

• 최근의 OS에서는 기존의 buffer cache와 page cache를 통합해 같이 관리한다
• buffer cache도 page 단위로 관리한다고 보면 됨