[운영체제] File system implementation

File System Structure

 

I/O는 block 단위로 전달되고 block은 하나 이상의 sector(512 or 4096 bytes)로 이루어져 있다.

일반적으로 block size는 4096 bytes이고 이건 일반적으로 사용하는 page size와도 일치한다.

 

 

 

File system

-  File system은 데이터를 disk에 어떻게 저장할지를 결정함

-  사용자가 storage에 접근할 수 있는 interface를 제공, logical structure을 physical device에 어떻게 저장할지 결정

-  사용자가 데이터에 효율적이고 편하게 접근할 수 있게 함

 

 

위 그림은 파일 접근 과정을 나타내는 계층적 구조를 표현한 것이다. 

Logical file system

컴퓨터 시스템에서 파일과 디렉토리를 조직화하고 관리하기 위한 추상화된 계층이다. 이는 사용자 및 응용 프로그램이 파일 시스템과 상호작용하는 인터페이스 역할을 한다.

-  Metadata 정보를 관리한다.

(Metadata는 데이터에 대한 설명, 구조, 특성 등을 기술하는 데이터이다. 즉 데이터를 설명하는 데이터로, 파일의 실제 데이터를 제외한 모든 파일 시스템 구조를 포함한다.)

-  File Control Block(FCB)는 파일에 대한 정보를 가지고 있다.

 

File organization module

파일과 디렉토리를 저장 및 관리하는 방식을 결정한다. 이 모듈은 파일의 논리적 구조를 관리하고 파일의 물리적인 배치를 결정한다.

 

-  파일들과 파일에 속하는 logical block들의 정보를 가지고 있는 모듈

-  각 파일의 logical block은 0부터 N까지 숫자가 매겨진다.

-  Free space manager을 포함하며 이를 통해 디스크의 어떤 부분이 사용가능한지 추적한다.

 

Basic file system

파일 및 디렉토리의 저장, 검색, 조작 등의 기본적인 파일 시스템 기능을 제공한다.

 

-  주어진 IO request를 device driver가 이해할 수 있는 command로 변경

-  Logical address 기반으로 되어 있는 command를 device driver에게 전달

-  Memory buffer와 cache 관리

-  리눅스에서는 ‘block I/O subsystem’이라 부름

 

Device driver

파일 시스템과 주변장치 간의 데이터 전송을 관리한다.

 

-  실제 IO device와 communication

-  메인메모리와 디스크 사이에서 데이터 이동을 관리

-  High level command를 받으면 디스크가 이해할 수 있는 low level instruction으로 변경하여 보냄

 

 

 

Disk structure

Partition

disk를 논리적으로 나눠 놓은 것

disk나 partition은 file system이 없는 ‘raw’ 상태로 사용될 수도 있고 file system이 ‘formatted’된 상태로 사용될 수 있다.

 

Volume

logical 영역이 하나의 file system을 포함하고 있는 경우 -> file system으로 포맷된 디스크의 저장 영역

file system의 정보를 device directory나 volume table을 통해 추적

 

 

 

 

File system operations

 

file system operation을 지원하기 위해 file system에서 다양한 data structure을 지원한다. 이러한 data structure들은 disk에 올라가 있을 수도(on-disk), 메모리 내에 위치해 있을 수도(in-memory) 있다.

 

On-disk structure

disk 위에 저장되는 data structure

1. Boot control block

OS를 boot하기 위한 정보를 담고 있는 block, 볼륨마다 있음

볼륨이 OS를 포함하고 있을 때만 필요

 

2. Volume control block

volume에 대한 정보를 포함하는 block (volume에 포함되어 있는 block의 개수, 비어있는 block의 개수, block의 크기 등), 볼륨마다 있음

 

3. Directory structure

파일의 구조를 저장하고 있음, 파일 시스템마다 존재

Names, inode numbers(unix에서 사용하는 file identifier), master file table 등을 가짐

 

4. File control block

file에 대한 자세한 정보를 가짐, 파일마다 존재

inode number, permissions, size, data 등을 가짐

 

 

 

In-memory structure

커널이 runtime에 메모리에 올려서 사용하는 data structure

 

1. Mount table

mount 되어있는 file system의 정보를 가지고 있는 table (mount = 접근가능한 상태로 만들어 주는 것)

file system이 어디에 mount 되어 있는지, file system의 type은 무엇인지 등

 

2. Directory structure cache

최근에 접근한 directory에 대한 정보를 가지고 있는 data structure

 

3. System-wide open-file table

system 전체에서 open된 파일들을 관리하는 table

open된 파일들의 FCB를 디스크로부터 복사해와서 메인메모리 위에 올려 둠

 

4. Per-process open-file table

각 프로세스가 연 파일들의 리스트를 관리하는 table

직접 FCB에 접근하는 것이 아니라 system-wide open file table의 entry를 가르키고 있음

 

 

 

 

Directory Implementation

Linear list

directory에 포함되는 file들을 list 형태로 가지고 있는 방식

file을 찾을 때 리스트의 시작부터 순서대로 찾아야 하므로 시간이 오래 걸릴 수 있음

 

Hash table

해시 함수에 파일 이름을 대입해 나온 값으로 file에 대한 정보를 얻어오는 방식

파일을 찾아오는 것이 빨라지나, 서로 다른 file이 같은 해시 값을 가져서 collision이 발생할수도 있음

 

 

 

 

Allocated Method

파일은 기본적으로 데이터를 담고 있고, 데이터를 담을 disk block들이 필요하다. 그렇다면 파일에 disk block들을 어떻게 할당할까?

 

1.  Contiguous allocation method

각 파일에 물리적으로 연속되어있는 data block을 할당

장점

-  seek time이 짧기 때문에 performance가 좋다.

-  파일의 첫 block 위치(starting location)와 몇 개의 block이 할당되었는지(number of block)만 알면 file을 관리할 수 있다.

 

단점

-  파일을 생성할 때 할당할 disk 공간을 찾기 까다롭다

-  잉여 block들이 disk 전체에 분산되어 있어서 block이 충분해도 file을 할당하지 못할 수 있다.

-  file이 더 커지면 다른 file들과 충돌이 일어날 수 있다.

   -> 처음에는 contiguous하게 disk block을 할당하고 file이 더 커지면 다른 부분의 연속된 block을 할당

 

 

 

2. Linked allocation method

block을 linked list 형태로 묶어서 할당함

각 block이 다음 block을 가르키는 포인터를 가지고 있음

 

장점

-  contiguous하게 할당했을 때의 문제점이 해소된다.

 

단점

-  하나의 block이 잘못되면 file 전체가 망가진다.

-  특정 block에 접근하려고 하면 첫번째 block부터 순차적으로 따라가서 접근해야 한다.

   -> 이러한 문제를 해결하기 위해 file allocation table(FAT)를 사용해 접근 시간을 줄일 수 있다.

 

 

 

3.  Indexed allocation block

각 파일이 자신만의 index block을 따로 가지고 있음

 

 

 

 

Free-Space Management

file에 block을 할당하기 위해서는 어떤 block이 비어있는지 알아야한다. file system은 free-space list를 갖고 있으면서 어떤 block이 사용가능한지 파악하고 있어야한다.

 

Bit vector(Bit map)

-  비어있는 block은 1, 채워져있는 block은 0

-  첫 free block을 쉽게 찾을 수 있다. 

-  block을 contiguous하게 할당하기 쉽다.

 

Linked list

free block들을 linked list 형태로 묶어 관리

 

 

Grouping

free block들을 grouping 한 것을 linked list 형태로 묶어 관리

 

Counting

free block의 시작 위치와 연속된 길이를 묶은 형태로 관리

위 그림을 예로 들면 (2, 4), (8, 6), (17, 2) ......

 

 

Buffer Cache의 경우 기본적으로 파일의 내용을 일부 메모리에 올려놓을 때 사용하고, 

Page Cache의 경우 Memory-Mapped I/O를 이용하면 파일이 페이지 단위로 관리되게 되는데, 이때 파일의 내용에 해당하는 페이지를 메모리에 올려놓을 때 사용한다.

 

 

unified buffer cache

- memory-mapped IO와 read(), write()이 같은 buffer cache를 사용함으로써 메모리에 중복된 내용이 올라가지 않게 함

 

 

 

Disk Recovery

Consistency checking

metadata에 저장되있는 data랑 실제 data block과 비교했을 때 다른게 있는지 파악하고 고치는 방식

disk를 많이 읽기 때문에 느릴 수 있음

 

Back up

시스템 프로그램을 사용해 disk에 있는 data를 다른 저장소에 복사해놓는 방식

 

Log structured file systems

matadata의 업데이트를 log에 기록하는 file system

-  업데이트가 log에 기록됐다면 'commit' 됐다고 함

-  log는 다른 장치나 disk의 section을 따로 둬서 기록함