해당 글은
경희대학교 조진성, 허선영 교수님의 강의 자료 및 내용을 정리한 글입니다
개인적으로 공부하며 작성된 글이라 잘못된 부분이 있을 수 있습니다!
오류가 있다면 알려주세요
File System Structure
memory와 mass stroage 사이의 I/O transfer는 Block 단위로 이루어진다.
각 Block은 하드디스크의 Sector 단위로 이루어져 있어요(주로 512, 4096 bytes)
File system
- NTFS, EXT4와 같은 File system은 meta data와 file data로 구성
- secondary storage(disks) 내에 존재
- User interface를 제공함. Logical -> physical로 mapping
- efficient하고 convenient access를 제공
Application에서 Device까지 I/O가 전달되는 과정
- Logical file system
File Control Block(FCB)가 각 File마다 존재하며,
실질적인 File data를 제외한 정보인 metadata information을 관리합니다.
- File organization module
files와 해당 files의 logical blocks(0~n)를 파악합니다.
해당 Block들이 비어있는지를 파악합니다.
- Basic file system
Logical block address를 기반으로 실제 읽어야하는 Block address를 device driver에게 전달합니다.
Memory buffer와 cache들을 관리하여, 자주 사용될 것으로 예상되는 것을 보관해둡니다.
Linux에서는 Block I/O subsystem이라고 함
- Device Driver
OS에 의해 관리되며, I/O controller에게 요청합니다.
~ block을 원한다는 내용의 high-level command를 I/O에 요청해야 하는 Low-level의 instruction으로 바꾸어주는 것쉼
Disk Structure
Partition
Disk의 Logical하게 여러 단위로 쪼갠 것이다.
Disk는 여러 Partition으로 구성될 수도 있고, File system이 raw(w/o), formatted(w)된 상태로 사용할 수도 있음
Volume
Single file system의 Logical area를 의미한다.
Device directory나 volume table에서 파일 시스템의 정보를 추적함
File System Operations
File system를 OS에서 운영하기 위해서
여러 on-disk(non-volatile) structures와 in-memory(volatile) structures를 필요로 한다.
먼저, On-disk Structures
- Boot control block: Boot를 하기 위한 필요한 정보와 코드. 주로 First block에 위치함
- Volume control block: volume 내에 있는 block의 사이즈, 수, free block의 수와 pointer등 (UFS-superblock, NTFS-master file table)
- Directory structure: File system마다, file의 구조를 저장합니다.
- File control block: File마다, inode number, permissions와 같은 관련 detail을 저장합니다
다음으로 In-memory Structures
- Mount Table: file system mounts, points, type 등을 저장한다.(mount이란 root 등의 Partition에 붙여서 System에서 접근 가능한 상태로 만드는 것을 것을 의미 )
- Directory Structure Cache: 최근에 접근한 directory에 대한 정보를 저장하여, File 검색 시 Disk에 접근하지 않아도 되도록 한다.
- System-wide open-file table: 시스템 전체에 하나 존재한다. 각 File의 FCB 복사본, 다른 정보를 저장해둔다.
- Per-process open-file table: PCB와 연결되며, system-wide open-file table로 향하는 entries pointer들을 저장한다.
(a) Open()
File의 이름을 통해 open()
→ kernel에 올라간 directory structure cache가 존재한다. 접근해서 File을 찾는다
→ directory structure에서 File control block을 가져온다.
→ open을 하면 FCB를 Disk에서 memory로 Cache함
(b) Read()
Open()을 하면, File을 구분할 수 있는 descripter인 fd가 return됨
→ 이는 System-wide open-file table에 FCB가 cache된 Index이다.
→ 이를 가리키고 있는 pointer가 per-process table에 추가된다.
→ 따라서 FCB를 여러번 가져올 필요 없이, pointer로 같은 file을 가리킬 수 있게 된다.
→ File control block이 해당 FCB를 보고 실제 데이터가 어디 있는지 파악하여 contents를 읽어올 수 있음
Allocation Method
File에 데이터를 저장하기 위해서는 Block이 필요한데, 어떻게 할당할 것인가?
▶Contiguous Allocation Method
각 File에게 연속된 Blocks를 할당해주는 것으로
대부분 상황에서 Best 성능을 낸다
BUT 👎
- File이 저장된 공간을 Finding할 때 문제
- Dynamic하게 변하는 storage allocation 문제
- External fragmentation
따라서 extent, 연속된 block의 묶음을 여러 개 할당하는 방식도 있슴
▶ Linked Allocation Method
각 File이 blocks의 Linked list로 구성됨
따라서 external fragmentation이 발생하지 않고
이를 방지하기 위해 blocks를 모아주는 compaction을 수행하지 않아도 된다.
BUT 👎
- Link가 끊어지면 File이 망가지므로 Reliability가 부족
- n번째 메모리를 찾기 위해서 너무 많은 I/O및 Disk seek를 요한다
- pointer 사이즈 만큼 메모리를 낭비한다.
MS-DOS와 같은 OS에서는
Link 정보를 따로 저장해두는 File Allocation Table(FAT)를 두기도 함
▶Indexed Allocation Method
각 File이 자신만의 Index block을 가진다.
Index block은 해당 file이 가진느 data blocks의 pointer를 모음
따라서 n번째 block을 찾고자 할 때 request 처리가 간결하다는 장점이 있음
BUT 👎
- index block을 따로 저장하는 것에서 오는 낭비
- 저장할 수 있는 Block 갯수의 한계 존재
따라서 index block를 Link해서 파일 사이즈가 block의 크기에 제한되지 않도록 하는 여러 방식이 있다고 하네요.
ex) Linked scheme, Multilevel index, Combined scheme
Performance of Allocation Methods
File access type에 따라서 Best method가 달라집니다.
Contiguous의 경우
sequential, random 접근 모두에서 좋은 성능을 내고,
Linked의 경우
sequential은 좋은 성능을 내지만, random에서는 은 좋은 성능을 내지 못합니다
Indexed의 경우
data block을 읽기 위해 index block 읽기가 선행되어야 하다보니 복잡
Clustering을 통해 throughput을 향상하고, CPU overhead 감소 가능
추가적으로 NVM(Non-volatile Memory)의 경우
Disk Head가 없고 Block erase overhead가 존재하기 때문에
다양한 알고리즘&최적화가 필요하다고 하네요
Free-Space Management
File system은 어떤 block/clusters가 비어있는 상태인지 트래킹하기 위해서 free-space list를 유지합니다.
이는 Bit vector / Bit map ($n$ blocks)로 표현함
Disk $n$개의 block 중에서 새로운 블록을 찾아 할당해주기 위해서
CPU에는 first bit를 찾아주는 instruction이 존재. 효율적이고 빠른 처리 가능
Free space를 관리하는 또 다른 방법에는 무엇이 있을까?
▶Linked List (Free list)
Free block들을 pointer로 서로 묶어준다.
빠르게 찾을 수 있다는 장점
▶Grouping
Linked List에서 free block을 묶어준다.
▶Counting
묶어준 것의 가장 첫번째 것만 point하고, 묶는 것의 크기를 저장해둔다.
이를 통해 contiguous한 할당시에 좀 더 빠른 처리가 가능합니다.
▶Others
Space maps - Oracle's ZFS
TRIMing
Efficiency and Performance
Efficiency는 space, Performance는 I/O request의 처리 속도와 같다고 볼 수 있음
▶Efficiency
Disk의 space를 얼마나 잘 활용하는가?
- Disk allocation 및 Directory algorithm에 영향을 받음
- Pre-allocation / As-needed: 파일이 커질 정도를 예상하고, 미리 할당? 또는 필요할 때 확장?
- Fixed-size / Varying-size data structure: Data structure 공간을 미리 고정으로 할당? 또는 유동적?
▶Performance
- Data와 metadata를 Disk의 가까운 곳에 위치시켜 Overhead 줄이기
- Buffer cache: File의 내용을 미리 Main memory에 올려두어, 자주 사용되는 파일을 빠르게 접근 가능
- Synchronous: 바로 Disk로 변경 사항을 Update. 안전성을 보장해야 하는 경우.
- Asynchronous: cache에 변경 내용을 반영하고, 이후에 한번에 Disk에 write()
- Free-behind / Read-ahead: Block을 계속해서 읽을 때 앞에 읽었던 내용은 cache하지 않거나, 뒤에 내용까지 한번에 cache에 올려버리거나
- Read는 Asynchronous Write보다 대부분 느리다. Request가 요청하고, 이를 Data로 받아올 때까지 아무런 작업도 할 수 없기 때문.
Page Cache
파일을 메모리에 Cache해두는 것
File system에서 Disk block들을 buffer cache가 되고,
해당 cache는 I/O나 Memeory-mapped I/O를 할 때 사용될 수 있음.
이때 똑같은 파일이 여러 개의 cache가 될 수 있다는 문제가 발생한다.
▶Unified Buffer Cache
In Linux
중간에 page cache를 한번 더 사용하면 Double caching이 발생할 수 있기 때문에 동일한 cache를 사용하게 함
Recovery
Disk가 고장났을 때는 어떻게 회복할 것인가?
Consistency Checking
Disk를 mount할 때 Meta data와 실제 data를 비교하여, Disk의 Data가 잘 보관이 되고 있는지 확인한다.
그러나 굉장히 느리겠죠 ..
Back up
another storage device에 저장해두기
Log Structured File Systems
Log structured(Journaling): meta data의 수정이 발생하는 내용을 전부 transaction(operation의 단위)으로 기록
해당 log안의 transaction은 Asynchronously하게 실제 Disk에 written 된다.
이를 통해 Crash가 나게 되더라도 Log에 기록이 되어 있기 때문에, 이전 상태로 Fast recovery가 가능함
끄 읕
'STUDY > 운영체제' 카테고리의 다른 글
| [OS] Chap15. File-System Internals (0) | 2023.12.16 |
|---|---|
| [OS] Chap13. File-System Interface (0) | 2023.12.13 |
| [OS] Chap12. I/O Systems (0) | 2023.12.08 |
| [OS] Chap11. Mass Storage Structure (0) | 2023.12.05 |
| [OS] Chap10. Virtual Memory (1) | 2023.12.03 |
