File System- Sturcture, Implementation

File System

File System Structure

- Disk에 효율적이고 편리한 접근을 제공한다.

- User에게 보여질 File system을 정의하고 Logical file system을 관리하기 위한 자료구조, 알고리즘을 결정한다.

Features

1) File structure

- Logical storage unit : 관련된 정보들의 집합

- File control block(FCB) : File에 대한 정보를 가지고 있는 storage structure(File에 대한 metadata를 가짐)

2) File System은 보조기억장치에 존재한다.

3) Block 단위로 Disk operation을 수행한다.

4) File system은 일반적으로 계층구조를 가지고 있다.

File System Implementation

1) Information on disk

① Boot control block

 -  Volume으로 부터 OS를 boot하기 위한 시스템 정보들을 포함하고 있다.

 - 일반적으로 Volume의 첫번째 block이 Boot control block이다.

 - UNIX 계열에서는 bootblock이라 부르고, NTFS에서는 partition boot block이라 부른다.

② Volume control block

 - File-system 자체의 정보를 가지고 있다.

  -> Partition에 존재하는 block의 수

  -> 비어있는 block에 대한 Pointer

  -> FCB Pointer

 - UNIX 계열에서는 superblock이라 부른다.

 - NTFS에서는 master file table에 저장되어 있다.

③ Directory structure for a file system

 - 파일을 조직하는데 사용된다.

 - UNIX 계열에서는 File name, inode Mapping 정보 등 파일에 대한 metadata를 가지고 있다.

 - NTFS에서는 master file table에 저장되어 있다.

④ Per-file FCB

 - 파일에 대한 상세 정보가 들어있다.

 - UNIX 계열에서는 inode(index node)라고 불린다. File name과 inode number가 inode table에 mapping되어 있음.

 - NTFS에서는 master file table에 저장되어 있다.

2) Information in memory

① In-memory mount table

 - 각 Mount된 volume에 대한 정보와 Mount된 File system에 대한 정보를 가지고 있다.

② In-memory directory structure

 - 최근에 사용된 directory structure에 대한 정보를 가지고 있다.

③ System-wide open-file table

 - Open된 파일에 대한 정보와 Open된 파일의 FCB 복사본을 가지고 있다.

④ Per-process open-file table

 - 프로세스마다 존재하는 FCB로 System-wide open-file table의 entry에 대한 pointer와 file offset, protection을 가지고 있다.

3) Partitions

- Disk는 다수의 Partition으로 나뉠 수 있다.(Boot Partition, Root Partition)

- Raw disk : FIle system이 존재하지 않는 Partition <-> Cooked disk : File system이 존재하는 Partition

4) Virtual File System(VFS)

- File System의 객체 지향 방식을 제공한다.

- 같은 형태의 system call interface 로 다른 type의 file system을 제어할 수 있다. (하나의 interface로 여러 개의 file system 사용 가능)

- Virual Node(Vnode)

 -> Inode와 비슷한 형태로 In-memory에서 사용한다.

 -> File system을 Mapping 시킨다. 

위 사진과 같이 하나의 Interface를 통해 다른 type의 file system에 접근하고 제어할 수 있다.

- VFS object

 ① Inode object : 파일에 대한 Inode 정보를 가지고 있음.

 ② File object : Process에 의해 open된 파일의 정보를 가지고 있음.

 ③ Superblock object : 전체 파일 시스템에 대한 정보를 가지고 있음.

 ④ Dentry object : Directory entry에 대한 정보를 가지고 있음. Directory entry를 한번이라도 읽을 경우, dentry object에 전송됨.

5) Directory Implementation

① Directory entry를 Linear list로 구현하는 경우

 - File name의 data를 가지고 있음

 - 프로그래밍이 간단하지만 List이기 때문에 search에 시간 소모가 크다. 

② Directory entry를 Hash table로 구현하는 경우

 - List로 구현한 것에 비해 search에 걸리는 시간을 줄일 수 있다.

 - collsion이 발생할 수 있다. File name의 Hash값이 중복되는 경우