File-System-Implementation

• toc {:toc}

File System Structure

• Disk 는 덮어쓰기, 랜덤 접근을 제공한다.
  • I/O 전송은 하나 이상의 sector 로 이루어진 block 단위로 이루어진다. (512bytes or 4KB)
  • 일반적으로 4KB
• File system → secondary storage 에 위치한다.
• Mapping Logical to physical
• Logical file system 은 metadata 정보를 다룬다.
• Metadata : 구조 유지를 위한 정보. 실제 데이터가 아닌 파일 시스템 구조를 포함한다.
• File Control Block (FCB) 는 파일에 대한 정보를 포함한다.
• File organization module → logical block 과 파일에 대한 정보를 가지고 있다.
  • 각 파일의 logical block ⇒ 0~N 으로 번호 매겨진다.
  • Free-space manager 를 통해 할당되지 않은 block 을 추적한다.
• Basic file system
  • logical block 주소들에 대해 드라이브에 명령을 내린다.
  • 메모리 버퍼와 캐쉬를 관리한다.
  • Block I/O subsystem 이라 불린다.
• Device driver
  • I/O device 를 다룬다.
  • 메인 메모리와 디스크 사이 정보를 전송한다.
  • High level 명령이 주어지고 low level instruction 을 출력한다.

Disk Structure

• Partition : 디스크의 논리적 분할을 뜻한다. ⇒ 디스크를 분할한 것을 말함.
  • Raw(w/o file system), Formatted(w/ file system) 으로 사용될 수 있다.
• Volumn : 하나의 file system 의 logical area
  • Device directory 또는 volume table of contents 를 이용해 file system 정보를 기록한다.

File System Operation

• Boot control block (per volumn) : OS 를 boot 하기 위한 정보를 포함한다.
  • OS 를 포함한 volumn 의 경우 주로 volumn 의 첫 block 을 boot control block 이 차지한다.
• Volumn control block (per volumn) : volumn 의 세부 정보를 포함한다.
  • 총 block 수, free block 수, 크기, 등
• Directory structure (per file system) : file 을 관리한다.
• File control block (per file) : file 의 세부 정보를 포함한다.
• Mount table : file system mount, mount point 등을 저장한다.
• Directory structure cache : 최근 접근한 directory 정보를 저장한다.
• System-wide open-file table : 시스템 전체의 열린 file 의 정보를 포함한다.
• Per-process open-file table : system-wide open-file table 에서 프로세스가 연 pointer 를 포함한다.

• 파일 open 과정

1. Open
2. 디스크에서 디렉토리 구조를 가져온다.
3. 디렉토리 구조에서 파일을 선택한다.
4. FCB 를 메모리에 올린다.
5. 처음 올리는 경우 system-wide open-file table 에 entry 를 추가한다.
6. Per-process open-file table 에 해당 파일의 system-wide open-file table entry 를 가리키는 pointer 를 추가한다.

Directory Implementation

• Linear List : Data block 에 대해 (file name / pointer) 저장
  • 프로그래밍 하기 쉽다.
  • 시간 소요가 있다. (선형 복잡도)
  • linked list 또는 B+ tree 이용해 알파벳순으로 정렬 가능
• Hash Table : hash 데이터 구조를 가진 linear list
  • Search time 을 감소시킨다.
  • Collision : 해쉬 함수에 의해 변환됐을 때 같은 위치에 2 개의 파일이 위치하는 상황
    • 해결하기 위해 하나의 file 만 저장할 수 있도록 구현 → Collision 발생 X
    • 같은 값을 가지면 linked list 로 파일 연결

Contiguous Allocation Method

• 각 file 이 contiguous block 의 집합으로 점유한다.
• 간단하다.
• (file, Start, Length) 구조
• 문제점
  • 비어있는 공간을 찾는 과정 (Free frame 찾는 것과 비슷하다. Free disk block 찾기)
  • 동적 저장소 할당
  • External fragmentation
• ⇒ 변형
• 처음에는 contiguous 하게 저장
• Hole 이 생겼을 때 contiguous 하게 저장한 후 저장하지 못했을 때 다음 hole 에서 contiguous 하게 저장

Linked Allocation Method

• 각 file 이 block 의 linked list 로 구성되어 있다.
• Block 안에 다음 block 의 번호가 포함된다.
• (file, Start, End) 구조
• 압축, External fragmentation 없다.
• 문제점
  • 신뢰성이 낮다. ---⇒ 중간 정보가 유실되면 다음 block 은 전부 접근 불가
  • Block 의 중간 위치를 알기 위해서는 disk seek 시간이 오래 걸린다.
• File Allocation Table (FAT)
  • File 들이 연결된 번호들을 저장하고 있는 table 이다.
  • Table 이 각 block 에 대해 연결된 block number 로 인덱싱된 하나의 entry 만 갖는다.
  • MS Dos 에서 사용됐다.

Indexed Allocation Method

• 각 block 의 pointer 를 저장하고 있는 index block 를 지닌다.
• (file, index block)

Performance of Allocation Methods

• File access type 에 따라 좋은 방법 다르다.
  • Contiguous → sequential / random
  • Linked → sequential / not random
• 만들 때 contiguous or linked 를 선택한다.
• Indexed 가 더 복잡하다.
  • 하나의 block 을 읽으려해도 index block 을 읽어야 하므로 추가 연산 발생
  • ⇒ 여러 개 연속된 묶음으로 할당한다. ⇒ throughput 향상, CPU overhead 감소
• NVM → disk head 없기 때문에 다른 알고리즘 필요

Free-Space Management

• 이용 가능한 block, cluster 를 추적하는 free-space list 를 사용한다.
• Bit vector or bit map (n blocks)
• block free : 1
• block occupied : 0
• word ⇒ bit 를 일정한 크기로 나눈 것
• (0 으로 구성된 word) X (word 안의 bit 의 수) + (1 이 나올 때 까지의 bit 수) ⇒ free block
• Contiguous file 을 얻기 쉽다.
• Linked List (Free List) : free block 이 linked list 로 연결되어 있다.
• Grouping : n 개의 free block 의 주소를 저장하도록 linked list 구성
• Counting : (start addr, length) 로 counting 해 저장 [(0, 2), (6, 2), (14, 3) …]
• Space Maps

Efficiency and Performance

• Efficiency
  • Fragmentation 발생하면 효율 감소
  • Metadata 증가 ⇒ 실제 데이터 저장공간 감소 ⇒ 효율 감소
  • Metadata 필요시 추가 ⇒ 빈공간 찾는 overhead ⇒ 효율 감소
  • FCB 공간 미리 할당 ⇒ 안 쓰면 효율 감소
• Performance
  • data 와 metadata 가 같이 위치하도록 유지해 disk 가 덜 움직이게 한다.
  • Buffer cache : 자주 사용되는 block 에 대한 메인 메모리 구역을 분리한다.
  • Synchronous : 바로 disk 에 작성
  • Asynchronous : buffer 에 놔두고 나중에 disk 에 작성 (더 흔한 방식)
    • 모았다가 작성해서 더 빠르다. 계속 접근할 시간을 줄이기 때문.
  • Free-behind / read-ahead : sequential access 에 최적화
  • Read 가 주로 write 보다 느리다.
    • read → 데이터를 가져와서 읽어야 한다.
    • write → 데이터 buffer 에 저장해뒀다가 덮어씌우면 된다.

Page Cache

• Virtual memory, address 를 이동해 page 를 저장한다.
• 디스크로의 접근보다 cache 접근이 더 빠르기 때문에 사용한다.
• 한 번 읽은 파일의 내용을 page cache 영역에 저장시켜 놓고 사용하는 방식 ⇒ 디스크 접근 감소
• Memory-mapped I/O 이 page cache 이용
• File system 의 routine I/O 는 buffer cache 이용

Unified Buffer Cache

• 대부분의 block 은 데이터를 저장하고 있는 block 이다.
• → 파일의 내용이 buffer cache 에 존재
• → 따라서 buffer cache 에도 존재하고 page cache 에도 존재하는 이중 cache 문제 발생
• → 해결하기 위해 같은 page cache 를 사용한다.

Recovery

• Consistency checking : 디렉토리 구조에서 데이터가 동일한지 확인 / 동일하지 않으면 복구
• Back up 해 놓고 복구한다.

Log Structured File Systems

• Log structured(or journaling) : 파일의 메타데이터 업데이트를 기록한다.
• 모든 거래는 순차적으로 log 에 써진다.
• 거래가 가끔 device 나 disk section 에 써지는 경우 있다.
• log 는 asynchronous 하게 파일 시스템 구조에 반영된다.
  • log 기록만 되고 disk 에 반영되지 않는 경우가 생길 수 있다.
• 파일 시스템이 충돌이 나면 log 에서 남아있는 모든 거래는 처리되어야 한다.