[OS 기초] File System

# Files and Directories

# File System

# File Structures

# Disk Space Management

# Unix File System

# Disk Scheduling

# Conclusion

# File 

: 이름을 가지는 디스크에 저장되는 바이트의 집합

> Views 

- OS가 보는 File : Block Sequence. Disk는 Block Storage 이므로 Block 단위로 저장 (내부)

- User가 보는 File : Bytes Sequence  (외부)

=> OS의 File System은 User가 보는Bytes 단위를 시스템 OS가 보는 Block 단위로 mapping 해야 함

* Naming 

: Disk 상에 존재하는 File은 addressing할 수 있어야 하는 이유로 인해 외부적으로는 Text Name을 가져야 함. 내부적으로는 File Identify를 가져야 함.

(*OS는 Naming을 File 뿐만아니라 I/O Devices 에도 적용시킴)

* File Descriptors 

: 파일의 내용에 접근하기 위해 필요한 메타데이터들을 저장하는 자료구조. 

* Operations on Files

- create and delete files

- open files for reading and writing 

- seek within a file

- read from and write to a file

- close files 

- create directories to hold groups of files

- List the contents of a directory

- Removes files from a directory

# File Descriptors

- unix에서는 index node라고도 부름

- 파일의 메타데이터를 저장하는 자료구조

- 파일의 크기, 소유자, 소유 그룹, 액세스 타임, 접근 권한, ...

- inode : unix의 file system에서 파일에 대한 메타데이터를 저장하는 자료구조

- i-node의 index :  i-number, file descriptor의 ID. 

> FIle Descriptors의  저장

과거: array의 형태로 만들어 disk에 특정 block을 할당하여 저장.    

=> 과거 disk는 bad block이 많고 취약했기 때문에, single copy로는 데이터 보호를 제대로 할 수 없음

=> File Descriptor들을 디스크의 특정 영역에 모아두면 성능저하가 발생

: 디스크 스토리지 상에서 File Contents와 File Descriptors를 나누면 물리적인 거리가 멀기때문에 Seek Time이 커짐

현재 : data contents 근처로 file descriptors를 가까이 두어 분산시키거나, data recovery를 위해 data의 copies를 여러개로 만듬

-  in memory cache : 성능의 향상을 위해 File Descriptor의 복사본을 Main memory에 유지

=> 부작용이 생길 수 있음. File Desciptor의 값을 수정할 때, Disk와 Main Memory에저장된 File Descriptor의 값이 달라질 수 있음

- 과거, Main Memory의 Cache에 복사한 file descriptor의 값을 안전하게 Disk에 옮기지 않고 시스템을 종료하면,
    시스템 재부팅 시에 OS는 해당 내용을 Disk의 file descriptor의 내용을 재구성해야함.

but,  현재는 디스크의 용량이 굉장히 커져 복구하기가 어렵고, 재부팅이 시스템을 정상화 하게 하는 경우가 많아짐(스마트 폰...)

=> log structured file system으로 진화

# Directories

- bytes sequence

- File 및 sub directories를 가지고있는 entity

- 내부적으로 File과 동일하게 관리

- File과는 다르게 data content로 contains(text file name, descriptor index) 값을 가짐. 

=> file의 text name을 file id로 mapping하기 위한 기본 데이터

> Unix File System의 구조

- tree 구조

- root directory, 하위 디렉토리는 각 leaf가 root로 부터 unique

- root directory의 inode number : 2

* why? http://stackoverflow.com/questions/12768371/why-root-directory-is-always-stored-in-inode-number-two

- name parsing 

# 부가사항

> Working Directory : 현재 위치한 디렉터리

> Link : 선택적으로 필요에따라 back-door path를 지정하는 기능

* inode의 i-number 값은 system wide하게, unique 하게 부여하는 것이 아니라, 볼륨 단위로 부여를 함

- Symbolic Link : 링크시킬 파일의 full path 값을 새로 링크시켜줄 디렉터리에 복사

원본 파일 A에 대해 심볼릭 링크를 생성하면, A라는 가리키는 파일을 생성

( "symbolic_link_file_B -> original_file_A" )

원본파일 A를 삭제하면 A를 가리키던 심볼릭링크파일도 삭제 됨됨(수정도 마찬가지)

- Hard Link : 링크시킬 파일의 contains pair 값을 새로 링크시켜줄 디렉토리에 그대로 복사. 

원본 파일 A에 대해 하드링크를 생성하면, A라는 파일을 가리키는 "이름"을 하나 더 만듬.

즉, 둘 중 하나의 파일을 삭제하더라도 이름 뿐인 녀석을 삭제하였으므로 내용은 그래도 남게 됨. 한 녀석은 그대로 존재하게 됨

=> symbolic link가 더 유연함. i-node의 number는 볼륨 단위로만 unique 하므로 Hard Link에 사용하는 contains pair값은 system wide하게 unique하지 않음.

즉, Hard Link는 같은 볼륨내에서만 사용이 가능

=> symbolic Link는 full path를 가지고 구현하기 때문에 모든 link는 system wide하게 unique 함

즉, 다른 볼륨간에도 사용할 수 있음

# Big Picture

> File System 기능

1. logical file name(logical resource name)을 physical address로 변환하기 위해 naming 기능을 제공

2. 사용자의 데이터를 저장장치로부터 read/write 하는 기능을 제공

> Views on Files

- User

file name + byte offset

: file pointer로 offset을 움직이며 파일 읽기

* file 단위의 sequence of bytes

* 주요 file access 패턴

- sequention access : file pointer를 한 칸씩(bytes) 움직이면서 파일의 내용을 읽기

- random access : file pointer를 임의로 이동하면서 파일의 내용을 읽기

- Kernel 

ino + logical block number

* file안에 존재하는 sequence of block

* bytes단위가 아닌 block 단위로 내용을 읽기

* kernel의 file system은 밑에 device driver와 interface 해야 함

* file descriptor, = index node

- Device Driver

Physical block number

* disk volume 단위로 관리, sector들의 linear sequence

* volume : 단일 file system으로 관리되는 저장 장치 상의 영역

* sector들의 number

- Device

cylinder number

head number

sector number

* drive number 이미 minor number로 사용 중

> File System in the Kernel (linux case)

user space            : file I/O    (system call : create, read, write, open, I/O contol)

--------------------------------------------------------------------------------

kernel space         : Virtual File System (VFS)  -> individual한 파일 시스템을 유니폼하게 사용자에게 제공하기 위해 필요

Individual Filesystems(EXT3, EXT4, JFFS2, VFAT, ...)

Buffer Cache(Page Cache) -> 최근 접근한 file의 Data Block의 내용을 Main Memory에 저장해 두는 공간으로 

디스크로 부터 한번 읽어온 파일의 내용에 다시 접근할 때, 빠른 속도를 제공함

(buffer cache도 swapping함. LRU같은 Policy를 적용)

I/O Schedulers

*Request Queue / Response Queue

Block Drivers   ,     Block Driver(FTL)

--------------------------------------------------------------------------------

Storage Media     : Disk ...... Flash

# File Structures

- Sequential access. ex. 방대한 코드를 컴파일 할 때,

- Random access.  ex. 데이터베이스에서 특정 데이터를 읽을 때, demanding paging에서 특정 page를 읽을 때, 

- keyed access. ex. 특정 key로 데이터를 읽을 때, (OS에서는 처리하지 않음)

* 과거 디스크는 fragmentation의 문제가 있음

=>  비연속적인 block단위로 allcation을 수행하여 fragmentation의 문제를 해결

1. Linked File 구조

: 해당 파일 디스크리터에 기록된 파일의 첫번째 블록의 주소를 통하여 파일에 접근

: fragmentation의 문제는 해결

: sequential access는 문제가 없으나, random access의 경우에는 seek time이 굉장히 오래 걸리게 됨

: 1970년대..

2. Indexed File 구조

: Unix의 기본 file 구조

: file descriptor에 파일이 가지고있는 block들에 대한 포인터를 index array로 저장

: sequential access, random access 둘다 용이함

: data block들은 file system의 sector array 중 임의의 block을 할당. 각 file의 file descriptor들이 해당 block들을 가리키는 구조

: file descriptor는 일정한 크기를 갖는 descriptor들의 array로 구성. 

=> 그안에 넣을수 있는 index의 갯수가 제한. 한 파일의 크기는 index의 갯수만큼 제한된다는 단점!

=> double indirect block 구조를 사용하여 큰 사이즈의 파일도 수용할 수 있음

 (but, 이중으로 처리하는 이러한 구조는 기존에 비해 데이터를 더 액세스해야하므로 seek time이 증가)

# Related Mechanisms

1. Block buffer cache

2. bit map operation  : 디스크 블락을 할당할 때, 꼭 sequential한 위치에 할당하지 않아도 되지만, seek time을 줄이기 위해 같은 실린더안에 있는 block을 할당하거나 하는 등의 인접한 위치의 block을 할당하는 방법

=>  OS의 File System에선 비어있는 연속된 block의 위치를 bit map을 통해서 알 수 있음

=> block들에게 1bit씩을 할당하여 1이면 이미 할당됨을, 0이면 할당되지 않고 비어있음을 나타내게 함함

=> 소프트웨어적으로도 구현이 가능하나 대부분의 마이크로 프로세서가 해당 기능을 제공

* Bit Map을 사용한 디스크의 free block 관리

: 각 bit가 디스크의 block이 사용 중인지 아닌지를 나타내는 Array. 

 HW/SW String Search 기법을 사용해 연속적인 사용 가능한 block을 쉽게 찾을 수 있음

> File의 구조를 결정하는 요소

: sequention access, random access를 효율적으로 지원해야함

작은 file, 큰 file 모두 효율적으로 지원해야 함

> must have items

1. Naming

2. Protection

3. Reliability

4. Disk Space Management 

# Disk Space Management

: File이 생성되거나 확장될 때, 어떻게 disk sector들을 file에 할당해 줄것인가를 결정

- 오버헤드가 적게

- 파일에 빠른 액세스가 가능하게 등등

- 파일의 각 block들

- matadata : user에게는 보이지는 않지만 커널이 각 파일별로 관리. 

in-memory cache를 유지하고, system이 shutdown될 때는 consistency를 잘 유지해야 함

- crash policies

> Disk space allocation policies

1. contiguous allocation

2. Block-based allocation

3. Extent-based allocation : block들을 그룹으로 묶고 각 그룹에 semantics를 부여함으로써 최적화를 달성하는 정책

=> block 단위로 allocation을 하면 sequential read를 할 때 seek가 많이 발생하므로 큰 단위로 할당해야하는 필요가 있음

# Unix File Systems

- System V file system : s5fs

: 완전 기본적 전통적인 파일시스템

- Berkeley fast file system (FFS) - often called UFS, 1980 년대 s5fs를 개선

- Sun's network file system (NFS) - 분산 operation과 file system을 접목

- Sun's virtual file system (VFS) - 다양한 파일시스템을 지원하기 위한

- Log-structured file system (LFS)