File System Implementation

Allocation of File Data in Disk

기본적인 방법

Contiguous Allocation

연속적인 공간 할당
directory에 file | start | length 정보가 있다.

특징

• 장점
  • Fast I/O : seek할 필요가 없음
    realtime file 혹은 swap area로 이용하기 좋음
  • Direct access 가능
• 단점
  • 외부 조각 발생 : 파일의 크기가 균일하지 않아서 중간에 홀 발생
  • File grow가 어려움 : 뒤에 줄 자리가 없어 파일의 크기를 늘릴 수 없음
    미리 빈공간을 확보하여 대비할 수는 있지만 내부 조각이 발생할 수 있음

Linked Allocation

빈 위치에 아무 곳이나 할당하게 됨
연결 리스트 이용
directory에 file | start | end 정보가 있고, 각 공간에 다음 공간 위치 주소도 함께 저장돼있다.

특징

• 장점
  • 외부 조각은 발생하지 않는다
• 단점
  • no random access
  • reliability 문제가 있다
    한 sector가 고장나 pointer가 유실되면 많은 부분을 잃어버림 (뒷부분 몽땅)
  • 위치를 가리키기 위한 pointer에게 별도 공간을 주면 block 공간의 효율성을 떨어뜨림
    실 저장공간이 줄어듦. practical한 문제

변형 ➡️ FAT File-allcation table 파일 시스템, reliability와 공간 효율 문제를 해결

Indexed Allocation

index block을 이용하여 block의 한정된 공간 내에 위치 정보를 열거 해둠
directory에는 file | index block(위치) 정보가 있고, index block에 가보면 공간들의 위치들이 있다.

특징

• 장점
  • 외부 조각 발생하지 않음
  • direct access 가능
• 단점
  • 작은 파일이면 공간 낭비 (다수가 작은 파일임)
  • 큰 파일이면 위치 정보 저장 공간이 부족. index가 부족하여 다 표현할 수 없음
    해결 방안
    • linked scheme : 공간이 부족할 때, 마지막 index에 새로운 index block 위치를 표시
    • multi-level index : 각 index가 index block 위치를 가리킴. table처럼. 단점은 공간을 낭비함

실제 파일 시스템

UNIX 파일시스템의 구조

가장 기본적인 시스템. Fast File System 등 많은 파일 시스템으로 발전시킴
Boot block은 매번 논리 Disk의 최상단에 위치. bootstrao loader이다.

0. Boot block : 부팅에 필요한 정보

1. Super block : 파일 시스템에 관한 총체적인 정보가 있음
   어디가 빈 공간이고 사용 중인지, 어디까지가 inode이고 data 인지 관리

2. Inode : 파일 이름을 제외한 모든 메타 데이터 저장

• 실제로는 Directory에 정보가 많지 않다.
• 파일 하나 당 한 inode가 할당 된다.
• index allocation을 사용한다.
  direct blocks, single indirect, double indirect, tripke indirect 순으로 하단에 정보가 있는데, 따라가면 index block이 있다. 크기가 부족할 수록 내려간다.
  ➡️ 효율적인 이유 : 파일 위치도 바로 알 수 있고, indirect로 큰 파일도 커버 가능하다.

3. Data block : 파일의 실제 내용 보관
   file name | inode 번호 로 구성돼있다.

FAT File system

메타데이터 중 위치정보만 FAT에 저장한다.

0. Boot block

1. FAT : Data block의 개수만큼 entry가 있고, 해당 block번째 entry에는 다음 block의 위치가 담겨 있다.

• FAT는 중요한 정보라 2카피 이상 저장 돼있다
• 곧바로 위치 파악 가능하다

2. Data block
   file name | 다른 온갖 메타 데이터 정보 | 첫번째 block 위치로 구성돼있다.

Free-Space Management

Bit map or bit vector

• 부가적인 공간 필요(저장 공간)
• 연속적인 n개의 free block을 찾는데 효과적. 가능한 연속 공간을 찾는게 좋아서 효율

bit[i]

• 0 : block[i] free
• 1 : block[i] occupied

Linked list

• linked allocation 느낌
• 모든 free blockd이 링크로 연결 ➡️ free list
• seek 해야 하지만 공간의 낭비가 없다.

Grouping

• linked list 변형으로 free block을 관리한다.
• 첫번째 free block이 n개의 pointer을 갖고 있고, 그 위치를 가보면 free data block이 있다.
• 마지막 pointer은 또다른 block을 가리키고, 위 과정 반복
• 연속 공간 찾기에 비효율적임

Counting

• 종종 연속적인 block을 할당하고 반납한다는 성질에서 나옴
• (first free block, # of 연속 free blocks) : 해당 쌍을 관리.

Directory Implemetation

메타 데이터 보관 방법

• Linear list
  <file name, file metadata>의 list
  • 구현은 쉽지만 순차 탐색 필요
  • metadata의 크기가 고정 돼있어서 연산하기 편리함. 바로 접근 가능(?)
• Hash table
  linear list + hashing
  • file name을 해당 파일의 linear list에서 위치로 바꿔줌
  • 검색 시간 X, 하지만 mapping이 중복될 경우 collision 발생

긴 파일 이름 지원 방식

• File의 메타데이터의 보관 위치 (대부분 길이가 고정돼있음)
  • 디렉토리 내 직접 보관
  • 포인터를 두고 다른 곳에 보관 : inode, FAT 등
• Long file name의 지원
  file name, file metadata entry는 일반적으로 고정 크기
  • file name을 한정해 두지만 길이가 넘어가면 마지막 공간에 포인터를 두고, 디렉토리 끝 부분에 거꾸로

VFS and NFS

• Virtual File System
  서로 다른 다양한 파일 시스템이 있어도 사용자 입장에서 동일하게 사용할 수 있도록 한 인터페이스를 제공함.
  동일한 시스템 콜 인터페이스를 접근하도록 하는 OS의 레이어
• Network File Systme
  로컬 파일시스템 뿐 아니라 원격일수도..
  분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음

➡️ 로컬이어도 VFS를 통해 사용자는 동일한 인터페이스로 접근할 수 있음

Page Cache and Buffer Cache

• Page Cache : Virtual memory 관련
  OS에 제공되는 정보가 적음. 메모리여서 OS말고 직접 함. 그래서 Clock Algorithm을 사용하게 됨
• Buffer Cache : file 관련
  OS에 제공되는 정보가 많음. I/O시 시스템 콜로 OS가 항상 관여
• Memory-Mapped I/O
  file의 일부를 가상 메모리에 매핑시킴. 시스템콜을 하지 않고 메모리에서 파일 시스템을 적용함. 해당 부분의 접근 연산은 파일의 입출력이 된다.
• Unified Buffer Cache
  최근 기존 buffer cache가 page cache에 통합됨. 페이지 단위로 관리되는 파일
  ➡️ 속도 효율이 좋다.

Unified Cache

• 해당 cache를 사용하는 file i/o
  공간을 나눠두지 않고 한 cache를 사용하기에 경로가 더 단순하다.
  buffer cache에 바로 올려두고 OS 요청 필요 없이 직접 접근이 가능해진다.
  copy 단계가 필요없음
• 해당 cache를 사용하지 않는 file i/o
  buffer cache에 os가 읽어온 것을 page cache에 copy를 해야한다.

프로그램의 실행

.. 정리 못하겠어요,,

Disk Management and Scheduling

Disk Structure

• Logical Block : 디스크 외부 관점
  sector에 mapping 돼있음
  주소를 가진 1차원 배열처럼 취급
• Sector : disk 관리하는 최소 단위. 디스크 내부
  logical block이 물리적인 디스크에 매핑된 위치
  sector 0 : 어느 파일 시스템이든 booting에 관련된 정보들이 들어있음

Disk Management

• physical formatting (low-level formatting)
  컨트롤러가 디스크를 읽고 쓸 수 있도록 섹터를 나누는 과정
  각 섹터는 header + 실 data(512B) + trailer로 구성 512
  header, trailer > sector number, 오류를 잡아내기 위한 ECC(Error-Correcting Code) 등의 정보가 저장되고 controller가 직접 접근 및 운영
  -> meta-data
• Partitioning
  하나의 실린더 그룹으로 나누는 과정
  OS는 이것을 독립적 disk로 취급 as Logical Disk > swap area나 file system으로 만들 수 있음
• Logical formatting
  파일 시스템을 만드는 것
  FAT, inode, free space 등의 구조를 관리하게 됨
• Booting
  Rom : 메모리 영역 중 전원 off에도 남아있는 부분. 부팅 정보 소량 저장 돼있음
  sector0 == bootblock : OS의 커널을 메모리에 올려 실행해라. OS를 디스크에서 load하여 실행

Disk Scheduling

디스크는 항상 회전 중...

• Access time 구성 > 거의 seek time이 대부분을 차지 함
  • Seek time : 헤드를 track 찾아가는 시간
  • Rotational latency : 헤드가 원하는 섹터에 도달하기까지 걸리는 회전 지연 시간
  • Transfer time : 실제 데이터의 전송 시간 (굉장히 적은 시간)
• Disk Bandwidth : 디스크 성능 : 단위 시간 당 전송된 바이트 수
• Disk Scheduling
  seek time 줄여서 bandwidth 높이는 게 목표
  seek time은 seek distance와 비례함

Disk Scheduling Algorithm

FCFS

First Come First Service
들어온 순서대로

• 이동거리가 멀수록 비효율적

SSTF

Shortest Seek Time First
현재 Head에서 가장 가까운 요청부터 처리

• FCFS보다는 낫다
• 하지만 Starvation 발생 가능성 : 더 가까운게 queue에 들어오면 순서 밀림

SCAN

한쪽 끝에서 다른쪽 끝으로 이동하면서 길목에 있는 모든 요청 처리
다른 한쪽에 도달하면 역방향으로 이동하며 오는 길목 요청 처리함
가장 간단하고 획기적이다.

• 이동거리 짧고, starvation x
• 하지만 실린더 위치에 따라 대기 시간이 다름. 편차가 크다.

C-SCAN

헤드가 가는 길목에 있는 모든 요청 처리
다른 쪽 끝에 도착했으면 요청 처리하지 않고 곧바로 출발점으로 이동

• SCAN보다 균일한 대기 시간 제공
• 어느 한쪽으로 unbalance하지 않는다.

Other Algorithms

• N-SCAN
  SCAN의 변형 알고리즘
  지나가는 중에 들어오는 것은 처리 x고 다음에 처리
  • 대기 시간 편차 ⬇️
• LOOK and C-LOOK
  헤드가 진행 중에 그 방향에 더 이상 기다리는 요청이 없으면 이동방향 즉시 반대로 이동
  각각 SCAN과 C-SCAN을 변형함
  SCAN / C-SCAN은 헤드가 디스크 끝에서 끝으로 이동

Disk-Scheduling Algoritm

SCAN, C-SCAN, LOOK, C-LOOK 등이 일반적으로 효율적임
File 할당 방법은 성능에 영향을 준다.
디스크 스케줄링 알고리즘은 필요한 경우 다른 알고리즘으로 쉽게 교체하도록 모듈로!

• 파일에 따라 적절한 것이 다르기에 모듈을 이용한다.
• 또, 개별 요청 처리 보다 한꺼번에 하여 disk I/O의 효율성을 높인다.