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이다.
-
Boot block : 부팅에 필요한 정보
-
Super block : 파일 시스템에 관한 총체적인 정보가 있음
어디가 빈 공간이고 사용 중인지, 어디까지가 inode이고 data 인지 관리
-
Inode : 파일 이름을 제외한 모든 메타 데이터 저장
- 실제로는 Directory에 정보가 많지 않다.
- 파일 하나 당 한 inode가 할당 된다.
- index allocation을 사용한다.
direct blocks, single indirect, double indirect, tripke indirect 순으로 하단에 정보가 있는데, 따라가면 index block이 있다. 크기가 부족할 수록 내려간다.
➡️ 효율적인 이유 : 파일 위치도 바로 알 수 있고, indirect로 큰 파일도 커버 가능하다.
- Data block : 파일의 실제 내용 보관
file name | inode
번호 로 구성돼있다.
FAT File system
메타데이터 중 위치정보만 FAT에 저장한다.
-
Boot block
-
FAT : Data block의 개수만큼 entry가 있고, 해당 block번째 entry에는 다음 block의 위치가 담겨 있다.
- FAT는 중요한 정보라 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)
: 해당 쌍을 관리.
메타 데이터 보관 방법
- 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의 효율성을 높인다.