File System

이화여자대학교 반효경 교수님의 2014년 Operating System 강의를 시청한 후 정리한 내용이다.

 

http://kocw.net/home/cview.do?cid=3646706b4347ef09

운영체제

 

 

File

이름을 통하여 접근하는 정보의 단위로, HDD와 같은 비활성 보조기억장치에 저장한다. OS에서는 문서 형태의 파일 뿐만 아니라 장치 또한 파일로 관리하고 있으며, 이를 special file이라 한다. 파일 연산에는 create/delete, read/write, reposition(lseek), open/close가 있다.

File Attribute (Metadata)

파일의 name, type, size, location 등의 관련 정보들을 File Attribute(Metadata)라 하고, 파일의 접근 권한이나 생성/변경/사용 시간, 소유자 등의 정보도 저장한다.

File System

OS에서 파일을 관리하는 소프트웨어로, 파일과 디렉토리, 메타데이터를 관리하며, 이들을 저장하고 관리하는 방법을 결정한다. 또한 파일의 위/변조 등의 악의적인 동작을 막기 위한 파일 보호도 담당한다.

Directory

그 아래에 저장된 파일들의 메타데이터들의 일부를 내용으로 담고 있는 파일이다. 디렉토리의 연산에는 file searching, create/delete file, list, rename file, traverse가 있다.

Partition (Logical Disk)

운영체제가 보는 논리적인 disk로, 물리 disk와는 다르다. 일반적으로 하나의 물리 disk에 여러 개의 파티션을 두며, 각 파티션을 file system이나 swapping 등 원하는 용도에 맞게 사용할 수 있다.

open() operation

파일의 메타데이터를 커널 메모리에 올려, 커널 영역의 open file table에 파일의 메타데이터를 등록함으로써, 해당 메타데이터로 파일 내용에 접근할 수 있도록 한다. 예를 들어, open("/a/b/c")를 실행하면 다음 과정을 거친다.

1. OS는 root 디렉토리의 위치를 알고 있으므로, 커널 영역의 open file table에 root 디렉토리 메타데이터를 저장한다. 그리고 root dir을 읽어 a의 위치를 알아낸다.
2. a의 메타데이터를 open file table에 저장하고, b의 위치를 알아낸다.
3. b의 메타데이터를 open file table에 저장하고, c의 위치를 알아낸다.
4. c의 메타데이터를 open file table에 저장하고, 그 메타데이터를 가리키는 포인터를 per-process file descripter table에 두어, 결국 open()이 해당 table의 index를 file descriptor로 하여 반환한다.

*System-Wide Open File Table: 커널 메모리 영역에 있는, 시스템에서 열려 있는 파일들의 메타데이터를 전역적으로 관리하는 table이다.

*Per-Process File Descriptor Table: 프로세스가 open한 파일의 메타데이터를 가리키는 포인터를 저장하는 table로, PCB에 저장되어 있다. 그리고 이 table의 index가 File Descriptor로 동작한다.

open 연산에서 path를 따라 디렉토리와 파일을 searching하는 것은 많은 시간을 소모하므로, read/write 연산과 별도로 두는 것이다. 그리고 open 연산을 한 번 하면, 파일의 메타데이터를 바로 접근할 수 있는 file descriptor를 받으므로, 다시 open하는 일 없이 read/write 연산이 가능하다.

read() operation

read() 연산은 읽을 파일의 파일 디스크립터를 인자로 받아 동작한다. 예를 들어, read(fd)를 실행하며 다음 과정을 거친다.

• 인자로 받은 fd를 index로 하여, per-process file descriptor table에서 fd에 해당하는 메타데이터 포인터를 찾는다.
• 메타데이터 포인터로 메타데이터에 접근한다.
• 메타데이터에 저장되어 있는 파일의 위치를 이용하여 파일의 내용에 접근한다.
• offset부터 인자로 받은 크기만큼 내용을 읽어들인다.
• 읽은 내용을 커널 메모리 영역의 buffer cache에 저장한다.
• buffer cache에 저장된 내용을 사용자 메모리 영역에 복사한다.

*Buffer Cache: 이전 chapter에서 설명한 caching 기법 중 하나로, 한번 더 동일한 offset에서 같은 파일의 내용을 읽을 경우, 파일에 접근하지 않고 바로 buffer cache에 저장된 내용을 제공받는다. buffer cache에 읽은 내용을 저장하거나, 읽을 내용이 해당 cache 안에 있는지 검사하는 주체는 OS이므로, LRU나 LFU 등의 알고리즘이 적용 가능하다.

File Protection

사용자에 따라 파일에 접근하는 권한을 설정하고 관리하기 위해 여러가지의 방법을 사용하는데, 대표적으로 아래 3가지가 있다.

• Access Control Matrix: 행을 사용자, 열을 파일로 하여, 각 파일에 대한 사용자의 권한(read, write, execute)을 해당하는 칸에 저장한 2차원 배열이다. 그러나 특정 파일의 열에 해당 파일에 접근하지 않는 사용자에 대한 칸을 할당하는 것은 공간상 비효율적으로, linked list를 이용하여 관리하는 방법도 있다. 파일이 기준인 AccessControl List(ACL)은 해당 파일에 권한을 갖는 사용자들을 linked list로 관리한다. 그러나 사용자가 기준인 Capability는 해당 사용자가 권한을 갖는 파일들을 linked list로 관리한다.
• Grouping: 실제 시스템에서 채택하는 방식으로, 사용자들을 owner, group, others(public)으로 그룹을 나누어 관리하는 방법이다. 각 그룹에 3비트를 할당하여, 비트를 이용하여 그룹이 갖는 접근 권한을 설정한다.

Linux File Permissions and Ownership Explained with Examples, Linux Handbook

• Password: 각 파일의 접근 권한에 password를 설정하는 방법이다. 같은 파일이라도 다른 권한에 대하여 password를 관리해야 하므로, 기억해야 하는 비밀번호가 많아 관리 측면에서 비효율적이다.

Mounting of File System

하나의 파일 시스템에 있는 디렉토리를 다른 파일 시스템의 root 디렉토리와 연결하여, 두 파일 시스템을 연결하는 것을 Mounting이라 한다.

Abraham Silberschatz, Operating System Concepts 10th ed.

Abraham Silberschatz, Operating System Concepts 10th ed.

Access Mehods

시스템이 제공하는 파일의 접근 방식은 2가지가 존재한다.

• Sequential Access(순차 접근): 어느 위치의 데이터에 접근하기 위해, 앞선 데이터를 먼저 접근하여 offset이 자동으로 증가하는 방식으로, 카세트 테이프와 유사하다.
• Random Access(Direct Access, 직접 접근): 특정 위치의 데이터를 임의의 순서로 접근할 수 있다.

Disk Allocation of File Data

디스크는 연속된 block(sector)로 구성되어 있고, 파일의 정보를 여러 개의 block으로 디스크에 저장한다. 따라서 파일을 저장하기 위해 block을 할당할 필요가 있는데, 크게 Contiguous/Linked/Indexed 3가지가 있다. 이 할당 방법에 따라서 디스크와 같은 장치도 direct access가 불가능하다.

Allocation Method #1: Contiguous Allocation

Abraham Silberschatz, Operating System Concepts 10th ed.

Contiguous Allocation은 block을 연속적으로 할당하는 방법이다. 따라서 디렉토리에 하위 파일의 할당 시작 위치와 길이를 파악하여 디스크에 접근할 수 있다. 이 방법은 아래와 같은 특징을 지닌다.

• 시작 위치와 offset 정보가 디렉토리에 있으므로, 디스크에 Direct Access가 가능하다.
• 한 위치부터 연속적으로 block을 할당받으므로, disk head를 한 번만 seek하면 한 번에 많은 데이터를 I/O할 수 있다. 즉, Fast I/O가 가능하다. 이러한 장점으로, swap area와 같은 real-time용에 사용되기도 한다.
• 연속 할당된 block사이에 External Fragmentation이 발생한다. 따라서 남는 block을 효율적으로 사용하지 못한다.

Allocation Method #2: Linked Allocation

Abraham Silberschatz, Operating System Concepts 10th ed.

Linked Allocation은 block을 각각 다른 위치에서 할당받아 이들을 포인터로 연결하는 방법이다. 디렉토리에는 파일의 시작 block, 끝 block위치를 갖고 있으며, 각 block에는 다음 block의 위치를 갖고 있다. 위 그림을 예로 들면, 9번 block에서는 16번 block위치 정보를 갖고 있으며, 10번 block는 25번 block의 위치 정보를 갖고 있다. 하지만 25번 block는 end block이므로, 다음 block의 위치 정보를 갖고 있지 않다. 이 할당 방법은 다음과 같은 특징을 지닌다.

• 흩어진 위치의 block들을 할당받을 수 있으므로, External Fragmentation이 발생하지 않는다.
• 특정 block의 위치는 이전 block이 갖고 있으므로, 해당 block에 접근하려면 시작 block부터 순차적으로 접근해야 한다. 즉, Indirect Access이며, 각 block을 seek해야 하기 때문에 I/O시간이 오래 걸린다.
• 각 block에는 다음 block에 대한 포인터 정보를 갖고 있으므로, block의 공간 효율성이 떨어진다.
• 일부 block이 bad block일 경우, 다음 block에 대한 포인터 정보가 유실되어, bad sector부터 나머지 데이터들에 접근할 수 없으므로, reliability가 떨어진다.

실제로 사용하는 파일 시스템 중 FAT(File Allocation Table)은 Linked Allocation을 변형한 것이다.

Allocation Method #3: Indexed Allocation

Abraham Silberschatz, Operating System Concepts 10th ed.

Indexed Allocation은 하나의 block에 나머지 데이터를 저장하기 위해 할당된 block들의 위치 정보를 저장한다. 이러한 정보를 저장하는 block을 index block이라 하고, 위 그림에서는 19번 block에 해당된다. 이 할당 방법은 다음과 같은 특징을 지닌다.

• 흩어진 block들을 할당받을 수 있으므로, External Fragmentation이 발생하지 않는다.
• index block에서 원하는 block의 위치를 바로 알 수 있으므로, Direct Access가 가능하다.
• 아무리 작은 파일이라도, 하나의 block을 데이터 저장이 아닌 다른 block들의 위치 저장을 목적으로 사용하므로, 적어도 2개의 block이 필요하다.
• 큰 파일일 경우, 수많은 할당 block에 대한 위치 정보를 저장하기 위해 여러 개의 index block을 사용해야 할 수 있다. 이 문제는 index block을 multi-level^[각주:1] 혹은 linked scheme^[각주:2]으로 구성하여 해결할 수 있다.

Unix File System Structure

Internal Structure of UNIX File system, Javatpoint

• Boot Block: bootstrap loader가 있는 block으로, 시스템 부팅을 담당한다.
• Super Block: 파일 시스템의 크기나 free block의 수 등 파일 시스템의 전체적인 정보를 저장한다.
• Inode Blocks: inode를 list로 관리하는 block이다.
• Data Blocks: 파일의 내용이 저장되는 block이다.

UNIX inode

Abraham Silberschatz, Operating System Concepts 10th ed.

inode는 이름을 제외한 파일의 모든 정보를 저장하는 구조체로, 파일의 메타데이터^[각주:3] 뿐만 아니라 data block의 위치 정보도 갖고 있다. 만약 파일의 크기가 작을 경우 direct block으로 한번에 block을 가리키지만, 파일의 크기가 더욱 커질수록, single/double/triple indirect block을 사용한다. 또한 디렉토리에서는 내용을 {"파일 이름": "inode 번호"}로 구성하고 있으며, inode list에서는 inode를 list로 관리하므로, 해당 list에서 index가 inode의 번호가 된다.

FAT File System

Design of the FAT file system, wikipedia

FAT File System은 하나의 block을 FAT을 두어 관리하는 파일 시스템이다. Unix FS와 마찬가지로 첫 번째 block인 reserved sector에 boot sector가 들어간다. 그리고 FAT block이 별도로 있으며, 이 block과 data block 사이에 root block이 존재한다. 또한 FAT FS에서는 디렉토리가 각 파일마다 {"파일 이름", "접근 권한 등 일부 메타데이터", "시작 data block 위치"}를 저장하고 있다.

Abraham Silberschatz, Operating System Concepts 10th ed.

FAT(File Allocation Table)은 저장된 파일들의 메타데이터들과 이들이 할당받은 data block의 위치를 저장하는 table로, linked allocation의 단점을 해결한 방식이다. 위 예시에서, test 파일의 시작 data block은 217번으로, data region에서 217번 data block이 test 파일의 첫 번째 블록이다. 그럼 이 다음 data block의 위치를 파악해야 하는데, 이는 FAT에서 확인할 수 있다. FAT의 217을 index로 하는 entry에는 다음 data block의 위치가 저장되어 있고, 이 값은 618이 된다. 따라서 618번 data block에 접근해서 파일을 계속 읽을 수 있고, 그 다음 data block 또한 table의 618번째 entry에 있는 339번 data block임을 파악할 수 있다. 즉, FAT의 index는 data block의 위치로 동작하고 있으며, table의 entry 수는 data region의 block 수와 동일함을 알 수 있다.

이 방식은 linked allocation에서 불가능했던 Direct Access를 할 수 있도록 한다. 특정 block의 위치를 알기 위해 이전 block에 접근할 일 없이, 파일의 시작 block의 위치만 안다면 table에서 원하는 위치를 바로 파악할 수 있기 때문이다. 또한 Reliability 문제도 해결하는데, 어느 data block이 bad sector여도, 이 다음 data block의 위치는 table을 통해 알 수 있다.

Root Region(Blocks)은 root 디렉토리에 위치한 파일과 디렉토리 정보를 담고 있는데, 이 block이 생성될 때의 크기가 고정되므로, root 디렉토리의 크기의 최대치 또한 고정된다. 이는 FAT12, FAT16에서의 구현 사항이고, FAT32에서는 root 디렉토리의 정보를 data region에 저장하여, root 디렉토리의 크기 제한 문제를 해결한다. 즉, Root Region의 시작 위치는 FAT32에 있어 Data Region의 시작 위치와 같다.

Free Space Management

디스크 block 할당 시 중간에 남아 있는 free block들을 효율적으로 사용해야 하는데, 이들을 관리하는 방법은 4가지가 있다.

Free Space Management #1: Bit map/vector

각 data block에 해당하는 bit들을 index로 나열하여, 해당하는 block이 free일 경우 0으로 표시하고, 그렇지 않으면 1로 둔다. 이 방법은 vector을 두기 위한 부가적인 공간이 필요하나, 각 entry가 bit이므로 큰 공간을 차지하지 않는다. 또한 이 vector에서 2개 이상의 연속적인 free block을 비교적 쉽게 찾을 수 있다^[각주:4].

Free Space Management #2: Linked List

Abraham Silberschatz, Operating System Concepts 10th ed.

첫 번째 free block을 head pointer로두어, 모든 free block들을 linked list로 관리하는 방법이다. head pointer 정보만 알면 free-block에 접근할 수 있으므로, map/vector와 같은 배열을 별도로 저장하기 위해 공간을 소비할 필요가 없다. 그러나 연속적인 free block을 찾기 위해 직접 header가 seek해야 하므로 효율적이지 않다.

Free Space Management #3: Grouping

https://www.slideshare.net/myrajendra/free-space-managment46

linked list의 변형으로, 첫 번째 free block에 다른 free block들의 위치 정보를 저장하고, 첫 번째 free block이 가리키는 free block들 중, 마지막 free block이 또 다른 free block들의 위치를 저장하는 index block의 역할을 한다. 즉, 첫 번째 free block이 n개의 free block을 가리키면, n번째 free block은 또 다른 m개의 free block들을 가리키는 방식이다. 이 방법 또한 연속적인 free block을 찾기에 좋은 방법이 아니다.

Free Space Management #4: Counting

이 방법은 연속적인 n개의 free block을 효율적으로 찾을 수 있는 방법으로, free-space list에 {"1개 이상의 free block 집합 중 첫 번째 free block의 위치":"연속적으로 free인 block의 수"}를 저장한다. 파일들이 보통 연속적인 block을 할당하고 반납한다는 성질을 이용하여 고안한 방법이다.

Directory Implementation

디렉토리는 하위 파일들의 파일 이름과 메타데이터를 갖고 있다. 이들의 정보를 이용하여 원하는 파일을 찾아야 하는데, 구현 방식에 따라 찾는 속도가 다르다.

• Linear List: <파일 이름, 파일 메타데이터> 정보를 리스트로 관리하는 방법이다. 구현이 간단하지만, 원하는 파일의 정보를 얻기 위해서 linear search를 해야 하므로 탐색 과정에서 시간이 걸린다.
• Hash Table: Hash 자료구조를 이용하여 파일 이름을 list에서 해당하는 entry의 위치로 바꾸어준다. 따라서 파일의 정보를 찾는 데 시간을 거의 소비하지 않지만, 해시 충돌이 발생할 수 있다.

한편 파일 메타데이터를 보관하는 위치는  파일 시스템에 따라 달라지는데, 디렉토리에 직접 보관하거나, FAT이나 inode에 메타데이터를 저장하여 이들의 포인터를 디렉토리에 보관하기도 한다.

또한 디렉토리에 하위 파일의 이름을 저장할 때, 파일 이름이 긴 파일이 있지만, 파일 이름이 저장되는 entry의 크기는 고정되어 있다. 이 경우 파일 이름 entry의 마지막 부분에, 이름 중 다 들어가지 못한 나머지의 시작점을 가리키는 포인터를 두어 해결할 수 있다.

VFS and NFS

• VFS (Virtual File System): 다양한 파일 시스템에 대해 동일한 시스템 API로 접근할 수 있도록 하는 OS의 Layer

• NFS (Network File System): 분산 시스템에서 네트워크로 파일을 공유할 때 사용하는 프로토콜

Abraham Silberschatz, Operating System Concepts 10th ed.

Page Cache and Buffer Cache

• Page Cache: virtual memory에서의 page frame을 caching의 관점에서 설명한 것이다.
  
  • Memory-Mapped I/O: 파일의 일부를 virtual memory에 mapping하여, 메모리 접근을 통해 파일의 I/O를 수행하는 방법으로, file I/O 시 page cache를 사용한다.
• Buffer Cache: 파일 시스템에서 I/O연산을 할 때 데이터를 커널 영역의 버퍼에 저장하고, 동일한 데이터를 요청했을 때 버퍼의 데이터를 바로 제공하는 목적으로 사용하는 cache이다. 모든 프로세스가 공용으로 사용하며, 커널에서 관리하므로 LRU, LFU 알고리즘을 사용할 수 있다.
  
  • Unified Buffer Cache: buffer cache가 page cache에 통합된 cache로, 최근의 시스템에서 채택하는 방식이다.

Abraham Silberschatz, Operating System Concepts 10th ed.

위 그림은 buffer cache와 page cache가 분리돼 있을 경우 file I/O를 나타낸 것이다. system call을 통한 I/O를 하면, CPU가 kernel mode로 동작하고, buffer cache에 요구하는 데이터가 있는지 확인한다. 만약 있으면 buffer cache의 내용을 제공하고, 없으면 disk I/O를 통해 데이터를 읽어, 이를 buffer cache에 두며 사용자 메모리 공간으로 복사한다. memory mapped file I/O의 경우, 먼저 파일의 내용을 읽어 buffer cache에 두고, 이를 사용자 메모리 공간에 mapping한다. 그 후 kernel의 간섭 없이 직접 사용자 메모리 공간에서 파일을 읽고 쓸 수 있다^[각주:5]. 그러나 해당 파일 내용이 메모리에 없다면 page fault가 발생한 것이므로, 이 경우에는 kernel의 도움을 받는다.

Unified Buffer Cache

Abraham Silberschatz, Operating System Concepts 10th ed.

Unified Buffer Cache는 buffer cache가 page cache에 통합된 cache로, buffer cache의 크기가 하나의 sector(512Byte)에서 page의 크기인 4KB로 확장된다. system call을 통한 I/O는 CPU가 kernel mode에서 동작한다는 사실은 다름없지만, memory-mapped I/O에서는 buffer cache가 곧 page cache이므로, page cache에 I/O를 수행한다.

Memory-Mapped I/O in Program Execution

Memory-mapped files, Microsoft Learn

프로세스의 segment 중 code 영역은 memory-mapped file과 유사하게 동작하는데, 디스크에 저장되었던 프로그램의 코드가 할당된 주소 영역에 mapping된다. 그러나 code 영역은 read-only이므로, page fault에 의해 swap out될 때 swap area에 두지 않고 물리 메모리에서 없앤다. 그리고 다시 code 영역의 요청이 들어오면 해당 code를 disk에서 mapping한다.

그러나 데이터가 저장된 파일의 경우, 이는 read, write가 모두 가능하므로, page fault 발생 시 swap out된다. 그러나 swap area에 있는 것이 아닌, disk에 저장된 원본 파일에 변경 내용을 저장하고 물리 메모리에서 삭제된다. 그리고 code와 마찬가지로 file 메모리 영역을 요청했을 경우 page fault가 발생하며 다시 disk로부터 file을 읽어 mapping한다.

 

 

참고한 자료

>> book

Abraham Silberschatz, Operating System Concepts 10th edition

>> FAT File System

https://en.wikipedia.org/wiki/File_Allocation_Table

 

 

 

1. multi level page와 유사한 방법 [본문으로]
2. index block의 마지막 부분에 다른 index block의 포인터를 두어 확장하는 방법 [본문으로]
3. 파일의 형식, 소유자, 권한, 크기 등의 정보 [본문으로]
4. 가능한 연속적인 block에 할당하고자 하는 이유는, disk header가 seek하는 시간을 줄이고, 한 번의 seek로 많은 양을 I/O하기 위함이다. [본문으로]
5. 다만 mapping하는 과정에서 mmap() system call을 사용하므로 CPU가 kernel mode에서 동작한다. [본문으로]