[Operating System] File System

File

File concept

• file : data/program을 담는 그릇
• data의 type은 numeric, character, binary 등 다양하게 될 수 있다.

File Structure

None

• bytes나 words의 집합으로, 특별한 structure가 존재하지 않는 경우

Simple record structure

• lines
• fixed length : 고정된 길이의 line
• variable length : 가변 길이의 line

Complex structures

• formatted document : application에 의해 정의되는 경우(ex. hwp..)
• relocatable load file : OS에 의해 정의되는 경우(ex. dll)

File attribute

• Name : file의 이름
• Type : 확장자
• Location : disk에서 저장된 위치의 pointer
• Size : 크기
• Protection : 유저의 접근 권한
• Time, date, user identification : data for protection, security, and usage monitoring

File Operations

• create
• write
• read
• repositioning within file(file seek) : 접근 위치 변경
• delete
• truncate : content 삭제 / meta data만 유지
• open : file data를 memory에 적재
• close : file data를 memory에서 삭제

Directories

directory : file의 meta data가 저장된다.

• unix에서는 directory도 하나의 file로 취급

purposes

1. user 입장 : file의 분류를 위함
2. file system : unique file name을 인식

path

1. current directory : relative path
2. root directory : absolute path

Directory Entry

directory entry : file의 meta data를 directory에 효과적으로 저장시킬 수 있는 자료구조로 disk에 저장되어 있다.

• file 1개당 1개의 directory entry가 존재
• directory는 각 file의 meta data에서 disk 주소를 읽어와 실제 data를 읽어올 수 있게 된다.
• 각 directory에 접근할 때마다 IO가 발생하기 때문에 한 번 data를 읽으려 할 때마다 많은 IO가 발생할 수 있다.
  • 따라서 OS는 최근 접근한 directory entry를 memory에 caching

Directory Sturcture

각 directory에서 directory entries를 통해 file에 접근하는 것을 구조화한 것

 

UNIX에서는 directory entries의 크기를 줄이기 위해 inodes를 중간에 둔다.

directory entries에는 filename과 inodes pointer만을 저장하고, 실제 meta data는 inodes에 저장되어 있다.

Directory Implementation

Linear list

directory를 단순히 list로 관리하는 방식

• directory entries를 검색하는 것에 시간이 많이 든다.

Hahs table

filename을 hashing해 linear list의 index를 얻는 방식

• 빠른 searching이 가능하지만, hash table이 필요하고 collision 처리를 별도로 해줘야 한다.

Directory sturcture(detailed)

single-level directory

root 밑에 모든 file이 포함되어 있는 형태

• directory가 root 한 개만 존재
• 동일한 file name을 사용할 수 없게 된다.

Two-level directory

user 별로 다른 directory를 사용하는 형태

• 각 user는 동일한 이름의 파일을 2개 이상 가질 수 없다.

Tree-sturectured directory

• search path : 우선적으로 탐색할 path(ex. ls 명령어를 입력하는 경우)
• 비어 있지 않은 directory를 지울 수 있도록 허가해야 할지가 문제(편의성과 위험성의 trade-off)

Acyclic-graph directory

하나의 file이 2개 이상의 directory에 속할 수 있는 구조

• file을 쉽게 공유할 수 있다는 장점이 있다.
• cycle을 허락하지 않는 구조

 

acyclie-graph directory 구조에서 다음과 같은 문제점이 발생

1. traverse problem : 동일한 node가 두 번 이상 방문되는 문제
2. delete problem : shared file이 삭제되는 경우 문제가 발생할 수 있다.

link type

1. symbolic link : meta data는 없고, pointer만 사용해 file을 공유
2. hard link : directory entry 자체를 복사해 file을 공유

delete problem

1. symbolic link
   • 참조하고 있는 file을 다른 parent에서 삭제하게 되는 경우 illegal file error가 발생할 수 있다.
2. hard link
   • shared file이 update되었을 때 동기화가 필요
   • 특정 directory에서 file을 삭제했다고 해서 바로 삭제하면 안된다.
     • reference count를 둬 몇 개의 directory에서 해당 file을 참조하고 있는지를 검사해 reference count = 0인 경우에만 file 삭제

General graph directory

• cycle을 허용하는 directory 구조

다음과 같은 문제점이 발생

1. traverse : infinite loop를 피해야 한다.
2. delete : file이 삭제되었을 때, cycle이 있으면 reference code ≠ 0이기 때문에 삭제되지 않았지만 실제로는 접근할 수 없는 경우가 발생할 수 있다.(garbage data)

💡 cycle을 허용하지 않는 directory의 경우 사용자가 link를 생성할 때마다 cycle detection algorithm을 수행한 뒤 link 생성 cycle을 허용하는 경우 link algorithm의 복잡해진다.

 

Protection

file의 접근 권한을 설정

 

access control

모든 user와 모든 file의 matrix를 만들어 권한을 기입하는 방식

• user와 file이 커질수록 matrix의 크기도 커진다는 문제점이 발생

따라서 UNIX에서는 user/group/other 3가지 categories에 대해서만 file 권한을 관리

File-system structure

file-system은 일반적으로 disk에서 동작

open() system call

• Load : meta data를 disk에서 memory로 적재해 data 접근 시 I/O 발생을 최소화
• Open-file table : memory에서 현재 열려있는 file의 meta-data를 관리하는 table
  • 많은 open-data에서 현재 접근할 file data가 어떤 것인지 searching을 해야 한다는 문제점이 발생.
  • 따라서 file descriptor를 이용해 각 file data를 가리키는 pointer를 제공
• file descriptor : open-file table 내의 index로, 해당 index의 file data로 바로 접근할 수 있도록 해준다.

Mounting File-system

각 file-system은 각자만의 root file system이 존재한다.

windows에서는 각 disk 별로 이동하는 방식으로 탐색

UNIX에서는 하나의 disk의 directory에 다른 disk의 root directory를 붙이는(mount) 방식을 사용

Allocation of File data in Disk

특정 file의 data를 저장하기 위해 disk의 block을 어떻게 할당할 것인가에 대한 문제

• disk : block device로, block 단위로 데이터를 읽고 쓴다.

Contiguous allocation

각 file이 인접한 block에 할당되도록 하는 방식

• 따라서 각 file에 대해 시작 지점과 길이만 알고 있으면 접근이 가능

장점

• 연속된 위치에 저장되어 있기 때문에 file write/read 시 빠르게 읽기가 가능
• memory에서 swap-out을 빠르게 할 수 있다.

단점

• dynamic storage-allocation : external fragmentation이 많이 발생
• difficulty in file growth : file이 수정되면서 크기가 증감하는 것에 대해 대응이 어렵다.
  • 처음부터 넉넉히 할당하게 될 경우 disk 낭비가 커질 수 있다.(internal fragmentation)
  • 처음에 필요한 만큼만 할당하게 될 경우, file이 커지게 되면 문제가 발생할 수 있다.

💡 특정 application의 경우 contiguous allocation이 적절할 수 있다. 동영상 제공 서비스의 경우 영상은 한 번 저장되면 크기가 바뀌지 않고 read를 빠르게 해야하기 때문에 적절한 선택이 될 수 있다.

 

Linked Allocation

file의 block을 linked-list로 관리하는 방식

장점

1. 시작지점만 관리하면 된다.
2. 공간 낭비가 적다.

단점

1. random access가 불가 : 2번째 block에 접근하기 위해서는 반드시 1번 block을 거쳐야 한다.
2. disk I/O : disk 어느 곳에나 저장이 될 수 있기 때문에 I/O 속도는 상대적으로 느리다.
3. reliability : linked list의 중간이 유실되면 그 뒤의 데이터 모두 유실될 수 있다.

FAT(File-allocation Table)

file system의 모든 위치 정보가 저장되어 있는 FAT을 disk에 저장한 뒤 booting할 때 memory에 적재

directory entry에는 start block의 주소가 있는 FAT를 가리키는 pointer를 저장

장점

1. 기존 linked list에서 random access가 안돼 발생하는 속도 문제를 in-memory table을 사용해 해결
2. FAT를 copy해 3개를 관리함으로써 reliability 문제를 해결

Indexed Allocation

각 file마다 index table을 갖고, index table에는 disk block의 위치 정보가 저장되어 있는 형태

장점

1. random access가 가능 : 자신의 index table에서 필요한 block index를 바로 접근하면 되기 때문에

단점

1. index table도 결국 disk에서 1개의 block에 저장되어야 하기 때문에 크기 제한이 존재

linked scheme

index table을 linked list로 연결하는 방식

• size limit가 없다

two-level index

index table을 mapping하는 outer-index table을 추가로 배치

• size limit가 존재

combined(UNIX)

• direct blocks : data를 직접 가리키고 있는 부분
• single indirect block : single index block(index table)
• double indirect blcok : two-level index blcok
• triple indirect block : three-level index block

Free-space management

Bit-map or bit-vector

block map을 유지해 free space를 관리하는 방식

• block 단위로 bitmap을 읽어 free-space를 탐색하는 방식을 사용
  • 0~5 bit를 뽑았을 때 값이 0이 아닌 경우 이 중 free-list가 존재함을 알 수 있다.
• contiguous allocated file을 얻을 때나 할당할 때 용이한 방식

Linked-list

free list를 linked list로 관리하는 방식

• free list를 탐색하는 데에 많은 시간이 소요
• contiguous space를 찾기가 어렵다.

Grouping

linked list의 단점을 보완한 방식으로, free list n개로 이루어져 있는 free block을 사용

free block에는 n-1개의 free list가 존재하고, 마지막 포인터는 다음 free block을 가리키는 포인터

Counting

비어 있는 block, 해당 block으로부터 몇 번째 까지 연속적으로 비어있는지에 대한 수)**로 free list를 관리하는 방식

Performance

Disk cache

자주 사용하는 blocks을 memory 일부 공간에 caching하는 방식

free-behind and read-ahead

• read-ahead : 한 개의 file을 읽을 때 그 다음 file 몇 개를 같이 읽어가는 방식(locality 기반)
• free-behind : file을 다 읽었어도 바로 memory에서 지우지 않고 다른 file을 memory에 적재하기 전까지 대기하는 방법

virtual disk

memory 일부를 disk처럼 사용하는 방식

• 사용자가 주기적으로 disk로 다시 백업해야 한다.

directory entry cache

빈번하게 접근되는 directory entry를 memory에 caching

• directory entry : meta-data를 caching하는 것

Recovery

file data나 system이 memory에서 동작하는 경우가 많기 때문에 적절한 consistency checking 및 recovery가 필요

• log data를 이용
• backup 진행

Others

logical formatting : meta data만 모두 지우는 것

physical formatting : 실제 데이터까지 모두 지우는 것