Implementing File System

운영체제에서 file system의 구현은 다음과 같이 두 가지의 형태이다.

 

1. On-disk structure

hard-disk 라고 불리는 secondary storage에 있는데 2차 저장장치에 구현된 구조이다.

 

2. In-memory structure

memory에 파일을 올려놓고 어떻게 쓸지에 관한 구현이다.

 

이 중에서 유닉스에서의 on-disk structure 구현만 살펴보도록 하자.

---

On-Disk Structure

master boot record는 부트로더가 저장되는 곳이다.

어찌되었든 운영체제 또한 sw이므로 메모리에 올라가야 실행이 된다. 따라서 이렇게 메모리에 운영체제 sw를 올려두는 것이 부트로더의 역할이다. 이 부트 로더가 저장되는 곳이 바로 master boot record이다.

다른 partition마다 다른 운영체제가 저장된다. master boot record에서 어떤 운영체제를 올릴 지 결정해서 partiton을 activate한다.

 

 

boot block

운영체제가 있는 영역이며 실행까지 담당한다.

 

super block

partiton의 파일 시스템에 대한 전반적인 정보를 저장한다.

예를 들어 FTA, NTFS 인지 등의 시스템 정보, 즉 파일 시스템에 대한 메타 데이터를 저장하며 block의 수와 type을 저장한다.

이때 하드디스크는 4kb 단위이다.

 

bitmaps

free space management

어떤 디스크 블록이 free인지 확인한다.

 

i-nodes

파일의 구조에 대한 메타 데이터를 저장한다.

예를 들어 파일 수정 정보, 권한 등 터미널에서 "ls -al" 을 실행했을 때 나오는 정보들이다.

 

root dir

root directory를 관리한다.

가장 상위단에 있기 때문에 파일 생성시 무조건 하나씩 있다.

 

files & directories

데이터 블록을 저장하며 파일 형태로 저장된다.

 

그렇다면 디스크에서 블록은 어떻게 배치할 수 있을까?

---

Continuous Allocation

디스크에서도 블록을 연속으로 배치한다.

 

다음과 같이 디스크가 있을 경우 파일마다 시작 블록과 몇개의 블록으로 이루어져 있는지 정보를 따로 가지고 있는다.

디스크에서도 이렇게 file이 연속적으로 배치된다.

 

PLUS

1. 저장해야 하는 정보가 줄어든다, 즉 기록이 쉽다.

길이만 알고 있으면 처음 시작 블록에서 이동하면 되므로 관리가 효율적이다.

 

2. 하드디스크는 하드웨어이므로 동일 블록에 없는 경우 탐구 시간이 증가한다. 따라서 이런 연속배치는 read-write 성능을 올려준다.

연속적으로 배치되어있기 떄문에 디스크 헤드가 움직이는 시간이 줄기 때문이다. 이는 데이터 베이스 시간에 디스크 구조에 대해서 배운 것과 동일하다.

 

MINUS

1. 외부 단편화가 발생한다.

연속적으로 저장할 수 밖에 없기 때문에 분명 디스크 블록이 남는데도 연속이 아니라서 배치할 수 없는 문제가 발생한다.

이는 utilization 측면에서 최악이다.

 

2. 파일의 크기가 커지면 문제가 발생한다.

만약 모든 파일을 연속으로 배치하여 디스크가 차있다고 하자. 이 경우 파일을 수정해서 크기가 커지는 경우 더 이상 연속적인 공간이 없으므로 배치가 불가능한 상황이 발생한다.

 

이러한 단점은 장점들을 다 먹어요(?)

그렇기 때문에 불연속적으로 배치하는 Linked Allocation을 사용한다.

 

---

Linked Allocation

디스크에서 블록을 불연속적으로 배치한다.

 

데이터는 블록마다 랜덤하게 두고 이를 모아두는 포인터 데이터, 즉 블록 포인터를 활용하여 이를 관리한다.

자료구조 시간에 배운 linked list로 관리하는 형태이다.

마지막 블록의 경우 -1을 표시하여 끝을 알린다.

 

PLUS

1. 데이터나 파일의 확장이 쉽다.

크기가 커져도 그냥 아무곳이나 던져 넣어두고 포인터로 연결만 하면 관리가 끝난다.

 

MINUS

1. 중간에 있는 파일들만 읽고 싶어도 처음부터 포인터를 따라가야 한다.

이는 순차 저장보다 성능이 떨어진다.

 

2. 신뢰도가 낮다.

디스크 자체의 문제로 하나의 bad sector 문제가 발생하였다면, 그 뒤에 연결된 모든 디스크 블록 또한 잃게 된다.

 

따라서 이를 해결하기 위한 것이 File Allocation Table, FAT이다.

즉 포인터들만 따로 모아서 저장하는 포인터 테이블을 만들고 이를 관리하여, 성능과 신뢰도를 모두 해결하는 것이다.

이 방법이 Indexed Allocation 이다.

---

Indexed Allocation

파일 위치 정보를 모아둔 인덱스 파일을 모아서 파일 컨트롤 블록에 저장한다.

이를 UNIX 용어로 i-node 라고 한다.

 

처음에는 direct blocks 를 사용하여 바로 데이터에 접근한다.

direct block을 초과하면 single indirect에서 추가로 생성하고 이를 계층적으로 연결하는 방식이다.

중간에 데이터가 끊겨도 나머지 정보를 다 가지고 있기 때문에 추적이 가능하여 신뢰도가 높다.

하지만 외부 단편화 문제를 해결하긴 했지만 index의 오버헤드가 크다는 단점은 존재한다.