12. File System

OS의 역할은 크게 3가지로 나눌 수 있다.

1. 프로세스 관리 2. 메모리 관리 3. 파일과 I/O

 

File

파일을 한 마디로 정의하면, 데이터나 프로그램을 담는 그릇이라 생각할 수 있다.
그리고 그 그릇들을 관리하는 시스템이 파일 시스템이다.

파일에 데이터나 프로그램을 담는데, 파일의 제일 앞 부분을 0번지라 생각하고 offset이 커지면서 연속적으로 담기게 된다.

즉, 파일 하나는 그 자체로 하나의 logical한 address space이다. 그 주소공간 안에 데이터를 연속적으로 저장한다.

 

File Structure

파일의 구조는 3가지가 있다.

1. None: 구조가 없는 파일로 바이트 sequence로 데이터를 저장한다.

2. Simple record structure: 파일에서 한 줄이 하나의 의미 단위를 갖는다.

3. Complex Structures: hwp, word, ppt 처럼 자체적으로 내부적인 형식을 가지고 있는 파일

이러한 파일의 구조는 누가 결정하느냐

OS가 결정하는 파일도 있고, 프로그램이 결정하는 파일도 있다.

 

File Attributes ( File Metadata )

파일을 관리하기 위한 정보(메타 데이터)에는 파일의 이름, 확장자, 위치, 크기, 권한 등이 있다.

파일의 메타 데이터는 일반적으로 directory 또는 Folder에 저장된다. 그 폴더 안에 담긴 파일들에 대한 정보가 폴더에 저장되기 때문에, 파일에 접근하려면 폴더에 먼저 접근해야 한다.

 

Directories

디렉토리가 존재하는 이유는 파일을 너저분하게 하드 디스크에 흩어 놓으면 어디에 어느 파일이 있는지 관리하기가 어렵다. 또는 비슷한 파일들은 그루핑을 하고 싶은데, 흩어져 있으면 그것도 안 된다.

=> 사용자 입장에서 파일을 체계적으로 관리하기 위해서 디렉토리가 필요하고,
=> 파일을 관리하는 파일 시스템 입장에서는 디렉토리가 어떤 파일의 유일한 이름을 결정할 수 있는 편리한 방법을 제공한다.

파일의 이름은 사용자가 정하는 건데, 하드 디스크 안에 들어 있는 모든 파일의 이름을 다 다르게 지정하기가 어렵다.
그런데 디렉토리 안에 파일을 넣으면 디렉토리 이름까지 포함해서 파일의 이름이 결정되게 된다.
파일의 이름은 root부터 시작해서 파일까지의 경로가 파일 이름이 된다고 생각하면 된다.

=> 파일의 이름이 같아도, 들어 있는 디렉토리가 다르면 서로 다른 이름을 갖는다고 생각하면 된다.

 

파일 시스템은 파일들을 편리하게 관리하기 위해 디렉토리라는 구조를 사용하고 있다.

 

A Directory Entry

파일의 메타 데이터가 디렉토리에 저장된다고 했다. 어떤 식으로 저장되는지 보자.

 

어떤 디렉토리는 내부에 여러 개의 파일을 갖고 있다.
그러면 그 디렉토리에 속한 파일 각각에 대한 메타 데이터가 저장되는 장소가 파일의 수만큼 존재할 것이다.

파일의 메타 데이터를 저장하기 위해  메타 데이터를 저장하기에 적합한 자료구조가 필요하고 그것을 Directory entry라고 한다.
=> 파일의 개수만큼 Directory entry가 존재한다.

디렉토리에는 parent directory를 가리키는 포인터와, child directory를 가리키는 포인터가 존재한다.

일반적으로 UNIX 계열의 OS들은 디렉토리도 하나의 파일로 취급한다.
파일인데 파일의 contents가 그 디렉토리 안의 파일들에 대한 정보를 담고 있는 파일이다.

하나의 디렉토리는 해당 디렉토리 내의 파일에 대한 정보 뿐 아니라, 하위 디렉토리들의 메타 데이터도 같이 가지고 있다는 것이다.

 

파일의 위치는 메타 데이터에 저장된다.
그러면 메타 데이터의 위치는 어디에 저장이 되어야 할까?
이것 역시 디렉토리에 저장이 되면, 디렉토리만 찾으면 파일의 메타 데이터 위치를 알 수 있고, 메타 데이터를 통해 파일의 위치를 알 수 있다.

그럼 디렉토리의 위치는 어떻게 알까? 디렉토리는 파일로 취급되기 때문에 상위 디렉토리가 하위 디렉토리의 위치를 알고 있다.

이렇게 루트로부터 원하는 디렉토리가 있는 위치까지 찾아갈 수 있다.

 

그렇게 첫 번째 데이터 블럭의 위치를 찾아낸 다음에 첫 번째 바이트를 읽었다고 하자.
그런 다음에 두 번째 데이터를 읽고 싶으면 똑같은 행위를 반복하게 된다.
디렉토리 엔트리로 접근해서 데이터 블럭의 위치를 찾아내고, 데이터에 접근한다.

데이터에 접근할 때마다 그 데이터의 위치를 파악하기 위한 과정을 반복하게 된다.
파일은 모두 하드디스크에 저장되기 때문에 데이터의 위치를 파악하기 위해 디스크에 접근하는 일이 반복된다.
=> 데이터 하나에 접근하기 위해 여러 번의 I/O 발생하게 되는 셈이다.

파일을 오픈한다는 행위는 오픈하는 파일의 메타 데이터를 메모리에 올려놓는 행위를 한다.
이렇게 하면 데이터의 위치를 찾기 위해 매번 데이터에 접근할 때마다 디스크에 접근하는 일을 하지 않아도 된다.
=> I/O를 줄이기 위해 파일을 오픈하는 것이 필요하다.

 

특히 메타 데이터가 처음 메모리에 올라오기 전까지, 메타 데이터를 메모리에 올리는 과정에서 I/O가 많이 발생한다. 루트부터 접근해서 찾아나가야 하기 때문에

그래서 한 번이라도 파일이 접근이 되어 메모리에 메타데이터가 올라오면 파일을 close해서 다 사용했다고 하더라도, 그 파일의 메타 데이터를 그냥 지워버리면 다음에 그 파일에 또 다시 접근했을 때 같은 과정을 반복해야 한다.
=> 디렉토리 엔트리 캐시를 사용한다.
한 번 메모리에 올라온 파일 메타 데이터는 close되어도 버리지 않고 캐시에 남겨둔다.

 

파일이 변경되게 되면, 파일의 메타 데이터도 변경되게 되는데 그러면 먼저 메모리에 올라온 메타 데이터가 업데이트가 될 것이다.
그런데 메모리에 있는 업데이트 된 메타 데이터가 하드 디스크에 있는 원본 메타 데이터에도 반영이 되어야 한다.

최신의 메타 데이터 정보가 하드 디스크의 메타 데이터 정보와 일치하도록 해야 한다.
=> 이 역시 I/O가 발생한다.

성능을 위해 메모리에 계속 반영하다가 최종적으로 한 번 디스크에 써주는 방식을 사용할 수 있다.
이렇게 되면 메모리에 있는 메타 데이터와 하드 디스크에 있는 메타 데이터 간의 차이가 발생한다.
이러한 차이도 파일 시스템에서 관리를 해야 할 것이다.

디렉토리 엔트리를 하나의 집합으로 그루핑해서 연속적으로 저장해놓고 관리를 할 필요가 있는데, 디렉토리 엔트리 하나 하나의 사이즈가 크면 묶어서 관리해야 할 정보의 양이 많아진다.
=> 유닉스는 디렉토리 엔트리를 분할한다.

 

유닉스는 디렉토리 엔트리에서 File name과 나머지 메타 데이터들을 분리시킨다.

나머지 메타 데이터들을 별도로 모아서 inode라는 이름으로 관리한다.

이렇게 하면 디렉토리가 관리하는 디렉토리 엔트리들은 파일 네임과 inode를 가리키는 포인터만 갖고 있기 때문에 엔트리들이 가벼워진다.
가벼운 디렉토리 엔트리들을 모아서 연속적으로 관리하면 사이즈가 작아진다.
=> Search를 할 때 빨라지고, 추가적인 여러 장점들이 생긴다.

inode들은 포인터를 통해서 접근하기 때문에 물리적으로 모아서 관리할 필요가 없다.

 

Directory Implementation

디렉토리 엔트리들을 Linear 하게 쭉 써두는 방법을 사용할 수 있다.
=> 구현하기가 쉽지만, 디렉토리 안의 특정 정보를 찾기 위해서는 linear list를 linear search를 해야 한다.
=> 오버헤드가 크다.

search 시간을 줄이기 위해서 디렉토리 엔트리는 linear list로 구현을 하되, 별도로 해시 테이블을 만들자.
file name을 input으로 해시 함수에 넣어서, output은 linear list의 특정 위치를 가리키는 포인터가 되도록 해시 함수를 만든다.

 

Single-Level Directory

하나의 디렉토리 내에는 같은 이름의 파일이 여러 개 존재할 수 없기 때문에 모두 다 다른 이름을 가져야 한다.
물론 255개의 문자를 사용해서 naming을 할 수 있기 때문에 만들 수 있는 이름의 수는 충분하지만 사용자가 같은 이름의 파일을 여러 개 생성하게 되면, 충돌이 발생한다. 모든 사용자가 파일의 이름을 안 겹치게 지어야 하므로 사실상 불가능하다.

또한 연관있는 파일들끼리 그루핑을 할 수가 없다.

=> 사실 이론만 존재하고 사용되지 않는다.

 

Two-Level Directory

서로 다른 사용자 사이에는 같은 이름의 파일이 존재할 수 있지만, 역시나 한 사용자의 입장에서 보면, 같은 이름의 파일을 여러 개 만들 수가 없다.
또한 그루핑 역시 할 수 없다.

 

Tree-Structured Directories ( Multi-Level Directory )

Tree-Structured Directories는 서브 디렉토리를 무한히 만들 수 있는 구조이다.

현재 디렉토리를 기준으로 하는 Relative path와 루트를 기준으로 하는 Absolute path가 있다.

트리 구조를 사용하면 하나의 파일을 찾기 위해서 모든 트리를 돌아야 한다는 문제가 있다.
=> Search path를 등록한다.

Search path는 어떤 파일 네임이 주어졌을 때, 그 파일을 찾기 위한 위치를 나열해둔 것.

 

어떤 디렉토리를 삭제하게 되면, 해당 디렉토리를 포함해서 하위 디렉토리까지 모두 삭제해버리는 게 맞을까?

그렇게 하면 너무 위험할 수 있다. 그래서 하위 디렉토리가 없을 때만 삭제할 수 있게 하면 안전하다.

그런데 이렇게 하면, 실제로 모든 디렉토리를 지워야 하는 상황에는 최하위 디렉토리부터 시작해서 위로 올라가면서 하나씩 삭제해야 한다.
=> 편의성이 떨어진다.

편의성과 안전성 사이에 결정을 해야 한다.

 

Acyclic-Graph Directories

트리 구조에서는 하나의 노드는 하나의 부모만 가져야 하기 때문에, 하나의 파일은 하나의 디렉토리에만 포함될 수 있다.

Graph 구조를 사용해서 하나의 파일이 여러 개의 디렉토리에 포함될 수 있도록 하자.

예시에서 count라는 파일은 두 개의 디렉토리에 포함되어 있다. count라는 파일을 여러 디렉토리가 공유할 수 있게 된다.

 

하나의 파일이 여러 디렉토리에 들어 있다고 했을 때 2가지의 문제가 발생한다.

1. 파일을 traverse 할 때, 하나의 노드가 두 번 방문되게 된다.

2. 삭제할 때도 문제가 발생한다.

처음에 Kang이 X라는 하위 디렉토리를 만들었다.
그 상황에서 Jung이 X라는 디렉토리를 공유하고 싶다면, Link라는 명령을 사용한다.
link의 방식에는 2가지가 존재한다.

Symbolic Link
: 디렉토리 안에 실제로 디렉토리 엔트리를 만드는 것이 아니라, 디렉토리를 찾아가는 pathname만 등록을 해둔다.
메타 데이터는 하나만 존재한다.
이때 Kang이 자기가 만든 X라는 디렉토리를 삭제하면 디렉토리 엔트리도 삭제되고, Jung 입장에서는 삭제한 적이 없기 때문에 X를 찾아가려고 시도할 것이다. Jung은 디렉토리 엔트리를 가지고 있지 않기 때문에 pathname을 통해 접근하게 된다. 그런데 루트부터 시작해서 Kang까지는 갈 수 있는데 Kang이 X에 대한 디렉토리 엔트리를 삭제했기 때문에 X를 찾아갈 수가 없다.
=> illegal directory access 발생

Hard Link
: 디렉토리 엔트리를 카피해서 만들어준다.
Jung은 독립적으로 X에 대한 디렉토리 엔트리를 갖게 된다.
Kang이 X를 삭제한다고 해도, Jung은 독립적인 디렉토리 엔트리를 갖고 있기 때문에 X를 찾아갈 수 있다.
그런데 Kang이 X를 업데이트하게 되면, 업데이트된 정보를 디렉토리 엔트리에 반영을 해야 하기 때문에 Kang은 자기가 가진 디렉토리 엔트리에 반영을 할 것이다.
=> 그런데 Jung은 이 사실을 모르기 때문에 Consistency 문제가 발생할 수 있다.

또 다른 문제는 Kang이 X 디렉토리 자체를 삭제해버리려 했는데 Jung이 디렉토리 엔트리를 가지고 있기 때문에 함부로 삭제할 수가 없다.
OS는 특정 디렉토리에 대해 해당 디렉토리를 관리하고 있는 상위 디렉토리에 대한 정보를 모두 가지고 있어야 한다.
=> 아무도 관리하고 있지 않을 때만 실제로 삭제할 수 있다.

파일에 대한 메타 데이터를 갖고 있는 디렉토리가 몇 개인지를 세는 Reference count라는 값을 유지한다.

Refrence count가 0이 되면, 디렉토리를 삭제할 수 있다.

 

General Graph Directory

General Graph Directory는 사이클을 허용하는 Graph directory 구조로, 하위 디렉토리가 자신의 상위 디렉토리를 하위 디렉토리로 가질 수 있는 것을 허용하기 때문에 매우 복잡해진다.

예시에서 X에 대한 디렉토리 엔트리를 Kang도 가지고 있고, Y도 갖고 있게 된다.
그렇기 때문에 X에 대한 Reference count는 2가 된다.
이때 Kang이 X를 지우려고 시도하면, Reference count가 2->1로 바뀌고 0이 아니기 때문에 X는 삭제되지 않는다.

그런데, 루트에서 타고 내려와서 Kang에서 X로 갈 수 없기 때문에 X에는 접근을 할 수 없게 된다.
=> 삭제되지 않았지만 접근할 수가 없게 되는 것이다.

garbage collection을 통해 접근 불가능한 데이터를 지워주어야 한다.
=> 시간이 오래 걸린다.

 

사이클을 허용하게 되면 복잡해지기 때문에 보통 사이클을 허용하지 않는다.
그런데 사이클을 허용하지 않는 파일 시스템을 만들려면 사용자가 서브 디렉토리를 만들 때마다 사이클이 만들어지는지를 Detect 해야 한다.

 

Protection

파일에 대한 권한을 부여할 수 있는 주체는 파일의 소유자이다.

1. 사용자마다 파일에 대한 접근 권한을 명시하는 방법
=> 사용자가 100명이 있다고 하면, 하나의 파일에 대해서 100명의 접근 권한을 명시해야 한다.
=> 너무 커진다.

2. UNIX는 user, group, others 3가지로만 사용자를 구분한다.

user는 파일의 소유자
group은 user와 같은 group에 속한 사용자들 (변경할 수 있다)
others는 user와 다른 group에 속한 사용자들

총 9 bit로 모든 사용자에 대한 권한을 표시할 수 있다.

UNIX에서는 change mode(chmod) 명령을 통해 파일에 대한 권한을 설정한다.

chmod 761 game 이라고 명령을 하면, game이라는 파일에 대해서 owner는 R,W,E 모두 가능하고 owner와 같은 그룹에 속한 사용자들은 R,W가 가능하고 owner와 같은 그룹에 속하지 않은 사용자들은 E만 가능하다.

디폴트로 groups는 owner와 같은 그룹의 사용자들이지만, chgrp 명령을 통해 변경할 수 있다.

 

File-System Structure

파일 시스템이 파일과 디렉토리 관리를 위해 필요로 하는 모든 정보 역시 파일이기 때문에 디스크에 저장이 된다.

파일 시스템이라는 프로그램은 사실 커널의 코드이다.
그런데 그건 그냥 코드일 뿐이고 그 코드가 하드 디스크에 있는 정보들을 읽어서 파일 관리를 해주는 것이다.

앞에서 봤듯이 파일 시스템은 복잡한 계층 구조로 만들어진다.
파일에 한 번 접근하려면 그 계층 구조를 층층이 타고가서 접근해야 한다.
함수가 함수를 부르면서 계속 내려가서 결국 하드 디스크에 접근하게 되는 것이다.
=> 그 과정이 매우 무겁기 때문에 open systemcall이 필요하다.

층층이 거쳐서 내려가는 것을 하지 않기 위해 open system call이 필요하다.

open의 최종 목표는 접근하고자 하는 파일의 메타 데이터를 메모리에 올리는 것이다.

결국엔 그 메모리에 올라온 메타 데이터를 가지고 파일에 접근을 하겠다는 것.

 

Open file table 

=> Open된 파일에 대한 메타 데이터가 모두 저장되어 있다.

Open-file table에는 많은 메타 데이터들이 저장되어 있을 것인데, 그 사이에서 내가 찾는 메타 데이터를 또 찾아야 한다.
=> 이것을 쉽게 하기 위해서 테이블에 대한 인덱스를 제공하는데, 이것을 File descriptor라고 한다.
=> 이게 있으면, 테이블 내에서 내가 찾고자 하는 메타 데이터를 바로 찾아갈 수 있다.

파일을 open하기 위해서 fopen이라는 함수를 사용하는데,

fp = fopen()에서 fopen의 리턴값인 fp를 descriptor라 생각하면 된다.

 

/a/b/c/d/e.hwp

이러한 경로에 저장되어 있는 e.hwp라는 파일을 open하려고 한다 하자.

메타 데이터를 메모리에 올리기 위해서는 일단 파일의 위치를 찾아야 한다.
e.hwp라는 파일의 위치를 알아내기 위해서는 상위 디렉토리인 d를 찾아야 한다.
그런데 d의 위치를 알기 위해서는 c를 찾아야 하고, c를 찾기 위해서는 b를 찾아야 하고, b를 찾기 위해서는 a를 찾아야 하며, a를 찾기 위해서는 결국 Root에서 찾아야 한다.

Root에서 a를 찾아서 디렉토리 엔트리를 읽어서 b에 접근하고, b에서 c의 디렉토리 엔트리를 찾아서 c에 접근하고 쭉쭉 해서 결국 e.hwp의 메타 데이터를 찾아 메모리에 올리게 된다.

그런데 이걸 open을 통해 메모리에 올려놓지 않으면 파일에 접근할 때마다 이 과정을 거쳐야 한다.

 

Mounting File System

파일이 저장되는 저장 장치는 여러 개가 있을 수 있다. 디스크, CD, USB, ... 등

Windows에서는 다른 저장 장치에 있는 파일에 접근하기 위해서는 먼저 드라이브부터 바꿔야 한다.
드라이브를 바꾸고 그 드라이브를 루트로 파일을 찾아나간다.
=> UNIX에서는 마운트라는 명령을 제공한다.

 

USB의 루트 디렉토리를 하드 디스크가 관리하는 특정 디렉토리에 갖다 붙인다.
usr 디렉토리가 USB의 Root 디렉토리가 되는 것이다.
=> 이렇게 하면 드라이브를 바꾸지 않아도 된다.

---

Allocation of File Data in Disk

파일의 데이터를 저장하기 위해서 디스크 내에 Block을 어떻게 할당할 것인가.

 

하드 디스크는 기본적으로 Block device이다.

데이터를 Block 단위로 I/O를 하는 장치라는 뜻이다.
하드 디스크와 같은 2차 저장 장치는 느리기 때문에 한 번 접근할 때 많은 양의 데이터를 가져오거나 써서 접근을 최대한 줄인다.

Block의 크기는 누가 결정할까.
하드 디스크를 포맷할 때 Block의 크기를 지정할 수 있다. 지정하지 않으면 디폴트로 4KB로 설정된다.

 

Contiguous Allocation

Contiguous Allocation은 하드 디스크의 연속된 Block을 이 파일의 데이터를 저장하기 위해 할당하겠다는 방식이다.

파일의 사이즈가 16KB라고 하면 연속된 4KB Block 4개를 할당한다.

<장점>

이 방식의 장점은 파일 데이터를 찾을 때, 첫 번째 Block의 위치만 알면 나머지 데이터의 위치는 계산을 통해 알아낼 수 있다는 것이다.

그렇기 때문에 첫 번째 Block의 위치와 길이 정보만 저장하면 파일의 모든 데이터에 접근할 수 있다.

하드 디스크에서 가장 시간이 오래 걸리는 것이 head를 옮기는 시간이다.
그런데 연속된 block에 파일이 저장되어 있으면 한 번의 head 움직임으로 모든 데이터를 읽을 수 있다.

=> Contiguous Allocation을 사용하면 I/O 오버헤드를 최소화할 수 있다.

동영상과 같이 한 번 저장되면 커질 일이 없는 파일들을 사용하는 어플리케이션에 대해서는 Contiguous Allocation이 좋은 방법이 될 수도 있다.

 

<단점>

하지만 앞서 메모리 할당 방식에서 봤던 Contiguous Allocation의 문제점과 동일하게, External fragmentation이 발생한다는 문제가 있다. 즉, 비어있지만 사용되지 못 하는 공간들이 발생한다는 의미이다.

=> 하지만 하드 디스크의 용량이 워낙 크기 때문에 이건 큰 문제가 되지 않는다.

 

더 큰 문제는 파일의 크기를 처음 파일이 만들어졌을 때의 크기로 fix해버리면 파일이 커졌을 때는 어떻게 할까?
만약 다른 파일이 그 뒤에 연속되어 저장되어 있다면, 파일이 커질 수가 없다는 문제가 있다.

1. 현재 사이즈보다 더 많은 Block을 처음에 할당한다.
=> 파일이 커지지 않아서 사용하지 않으면 낭비되는 공간이 된다. (internal fragmentation)

2. 파일을 그 위치에서 덜어내서 더 큰 위치로 옮긴다.
=> I/O가 매우 많이 발생해서 성능이 떨어진다.

 

앞서 말했듯이 연속된 공간에 Block을 할당하면 첫 번째 블럭의 시작 주소만 알면 모든 데이터에 offset을 이용해서 접근할 수 있다는 것이다.

Contiguous Allocation의 장점은 이 정도의 정보만 가지고도 충분히 데이터를 찾아낼 수 있다는 것.

 

Linked Allocation

Linked Allocation은 각 파일의 Block들을 Linked list 형태로 저장하는 방식이다.

Contiguous Allocation과 달리 각 블럭은 다음 블럭의 포인터를 가지고 있기 때문에 실제로는 연속된 공간에 저장하지 않아도 된다.

Linked Allocation을 사용하면, Contiguous allocation의 문제였던 File Growth 문제를 걱정하지 않아도 된다.

파일이 커지면 새로운 블럭을 할당하고 포인터만 연해주면 된다.

<장점>

첫 번째 블럭의 주소만 갖고 있으면 되고, 파일의 크기를 키우고 줄이는 것이 자유롭다는 장점이 있다.

<단점>

그런데 장점만 있는 건 아니다. Random Access가 불가능하다는 단점이 있다.
예를 들어 세 번째 Block을 찾아가기 위해서는 첫 번째 Block 부터 시작해서 타고 타고 가야 한다.
=> Disk I/O의 Efficiency가 좋지 않다.

또한 한 섹터가 깨져버려서 포인터가 손실되면, 그 노드의 이후의 노드들도 찾을 수가 없게 된다는 문제도 있다.
=> 깨진 블럭부터 이후의 블럭들은 모두 잃게 된다.

포인터가 공간을 차지한다는 문제가 있긴 하지만 이건 큰 문제가 안 된다.

 

이러한 단점들로 인해 Windows에서는 이것을 베이스로 조금 변형시킨 FAT 방식을 사용한다.

 

File Allocation Table ( FAT )

다음 블럭에 대한 포인터를 블럭 내에 저장하는 것이 아닌 별도의 테이블로 관리하는 방식이다.

부팅 시에 이 테이블을 메모리에 올린다. 모든 파일에 대한 위치 정보가 이 FAT 안에 들어 있다.
모든 파일의 Block은 시작 블럭의 위치만 알고 있으면 메모리 접근을 통해 접근할 수 있다.

하드 디스크 내에서 파일의 포인터를 읽어서 다음 블럭에 접근하는 것이 아니라 메모리 내에서 다음 블럭을 접근하기 때문에 빠르다.
=> Faster random access 가능

 

문제는 FAT가 유실되면 파일 시스템이 다 날아가버린다는 단점이 있다.
=> 이 문제를 예방하기 위해서 FAT의 사본을 여러 개 저장해둔다.
=> 파일의 위치가 바뀌면 사본의 내용도 바꿔야 한다는 오버헤드가 있지만, 계속 메모리에 있는 FAT만 바꾸다가 마지막에 하드 디스크에 반영하기 때문에 그 오버헤드는 그렇게 크지 않다.

사본 중 하나가 깨지게 되면, 다른 사본을 이용해서 이를 복구해 항상 같은 수의 사본을 유지한다.

그렇기 때문에 FAT가 유실되어 파일 시스템이 날아가는 경우는 거의 없다고 볼 수 있다.

 

Indexed Allocation

각 파일은 파일의 데이터가 저장된 Block들의 위치를 가리키는 포인터들만 담고 있는 블럭인 index block을 가지고 있다.

디렉토리 엔트리는 인덱스 블럭의 위치만 저장하고, 인덱스 블럭 내의 포인터를 통해 모든 데이터가 들어 있는 블럭에 접근한다.

index block 자체가 하나의 디스크 블럭이다.
블럭의 크기가 4KB라고 한다면, 포인터를 1024개 저장할 수 있다. 그러면 1024개의 블럭만 사용할 수 있다는 뜻이 된다.
=> 4MB 까지만 저장할 수 있다는 의미이다 (4KB * 1024 = 4MB)
이보다 큰 파일은 저장할 수 없다는 단점이 있다.
인덱스 블럭을 확장하는 별도의 방법이 필요하다.

 

1. Linked Scheme

index block들을 링크드 리스트로 연결하는 방법

4KB짜리 index block에는 1024개의 포인터가 저장되는데, 1023개는 파일의 데이터가 들어 있는 디스크 블럭에 대한 포인터이고 나머지 하나는 다음 index block에 대한 포인터이다.

 

2. Two-level index

index block을 가리키는 포인터를 저장하는 index block을 별도로 만든다.
1024 * 1024개의 데이터 블럭을 만들 수 있게 된다.
=> 역시나 파일 사이즈의 제한이 생기긴 한다.

 

3. Combined Scheme

UNIX 계열 운영체제가 파일의 메타 데이터를 저장하는 자료구조가 inode이다.

inode안에는 데이터 블럭을 가리키는 포인터인 direct block과

index block을 가리키는 포인터인 single indirect, double indirect, triple indirect이 있다.

single indirect는 single level index block을 가리키고, double indirect는 two level index block을 가리키고, triple indirect는 three level index block을 가리킨다.

direct block 하나는 4KB의 블럭 하나를 커버할 수 있고, single indirect는 1024 * 4KB = 4MB의 파일을, double indirect는 1024 * 1024 * 4KB = 4GB의 파일을, triple indirect는 1024 * 1024 * 1024 * 4KB = 4TB의 파일을 커버할 수 있다.

 

Free-Space Management

빈 블럭들을 관리하는 방법

Bit map or bit vector

 블럭 수 만큼의 비트를 사용하는 Bit map을 만든다.

bit가 1이면 비어 있는 블럭임을 의미하고 bit가 0이면 사용 중인 블럭임을 의미한다.

이 방법을 사용하면 매번 bit vector를 1bit씩 돌면서 비어있는 블럭(1)을 찾으려면 시간이 오래 걸린다는 문제가 있다.
시간이 지날 수록 사용 중인 블럭(0)이 많아지기 때문에 더 오래 걸릴 것이다.

1bit씩 읽지 말고 워드 단위로 읽자. 32bit를 읽었는데 0이면 모두 차있다는 뜻이다.

Bit map을 사용했을 때의 장점은Bit map에서 연속된 1은 실제로 연속된 블럭이 비어있다는 것을 의미한다.

 

Linked list

빈 블럭들을 linked list로 관리한다.

연속적으로 비어 있는 공간을 찾기가 매우 힘들다는 문제가 있다.

 

Grouping

첫 번째 블럭은 비어있는 블럭들의 포인터를 가진다.
그리고 마지막 포인터는 다음 블럭에 대한 포인터를 가리킨다.
다음 블럭에는 또 비어 있는 블럭들의 포인터가 들어 있다.

 

Counting

첫 번째 비어 있는 블럭의 번호와, 그 블럭부터 몇 개의 블럭이 연속으로 비어 있는지에 대한 정보를 pair로 관리한다.
OS는 성능 문제 때문에 웬만하면 연속적으로 할당하기를 원한다.
그러다보니 하나의 파일이 삭제되면 그 파일이 사용하던 연속된 블럭이 삭제될 가능성이 높다. 그래서 몇 번 블럭부터 몇 개의 블럭이 연속적으로 비어있는지를 저장하는 것이 효율적일 수 있다.

 

Performance

디스크에 접근하는 것은 매우 느린 작업이기 때문에, 이것을 만회하기 위한 기술들이 많이 있다.

Disk Cache

메인 메모리의 특정 영역을 디스크에서 읽어온 데이터를 저장하는 캐시로 사용한다.
디스크에 접근하기 전에 디스크 캐시를 먼저 탐색한다.

디스크 접근 보다는 메모리 접근이 훨씬 빠르기 때문에 성능이 개선될 수 있다.

 

Free-behind and Read-ahead

Read-ahead:

한 번 디스크에 접근할 때, 필요한 블럭 외에 다음 블럭들도 미리 같이 읽어온다.

Free-behind:

어떤 데이터 블럭을 요청해서 메모리에 가져왔을 때, 이 블럭이 차지하고 있는 메모리 공간이 있을텐데 그 메모리 공간의 블럭을 다 읽었다고 하더라도 바로 비우지 말고, 다음 블럭을 읽으라는 요청이 들어와서 메모리에 올려야 할 때 그 때 비우자.
=> 디스크 캐시와 비슷하지만 다르다.

프로세스가 I/O를 하게 되면, 불러온 데이터는 프로세스의 address space에 저장되게 된다.
그게 다 사용이 되어도 바로 디스크 캐시로 보내거나 버리거나 하지말고, 다음 블럭을 읽어와서 address space에 저장해야 할 때, 디스크 캐시로 보내거나 비우자.
=> 최대한 늦게 버리자. 

 

Virtual disk ( RAM Disk )

메모리의 일정 영역을 디스크 처럼 사용하자. 즉, I/O가 메모리 상에서 일어나는 것임.

메인 메모리는 휘발성이기 때문에 주기적으로 하드 디스크에 백업하는 행위가 필요할 것이다.

 

Directory entry cache ( dentry cache )

자주 접근되는 파일에 대한 메타 데이터는 메모리의 dentry cache에 저장해둔다.

 

Recovery

느린 하드 디스크의 속도를 만회하기 위해서 메모리를 이용하는 기술들을 많이 사용한다는 것을 위에서 살펴봤다.
그렇기 때문에 메모리에 있는 데이터만 업데이트하게 되면 비일관성 문제가 발생한다.
그런데 메인 메모리는 비휘발성 메모리이기 때문에 디스크에 쓰지 않은 채로 종료가 되어 버리면 업데이트된 정보가 모두 날아가버린다.

어떤 부분이 어떻게 변경되었는지를 log를 남겨서 비정상적으로 종료된 경우 log를 통해 데이터나 메타 데이터를 fix한다.
=> 이걸로도 fix되지 않으면 어쩔 수 없이 일부 데이터를 손실할 수 밖에 없다.

 

비 정상적으로 종료가 경우에 어떻게 알고 날아간 내용들을 복구하려는 작업을 할까?

정상적으로 종료되면 체크를 한다.
부팅시에 체크되어 있지 않으면, 지난 번에 정상적으로 종료되지 않았다고 판단하고 파일 시스템을 점검한다.