파일 시스템은 데이터와 프로그램을 포함하여 파일 내용의 온라인 접근과 온라인 저장을 위한 기법을 제공하며, 보조저장장치에 영구적으로 상주한다. (13장 참고)

이번 14장에서는 하드 디스크 드라이브와 비휘발성 메모리 장치상의 파일 저장과 접근을 둘러싸고 있는 이슈들을 주로 다룬다.

14.1 File-System Structure

파일 시스템을 유지하기 위한 보조저장장치로 디스크가 대부분 사용된다. 아래 2가지 특성 때문이다.
1. 디스크는 추가 장소를 사용하지 않고 재기록이 가능하다.
2. 디스크에 있는 임의의 블록의 정보를 직접 접근할 수 있다. 따라서 임의의 파일을 순차적 또는 무작위 방법으로 쉽게 접근할 수 있다.

비휘발성 메모리(NVM) 장치는 파일 저장 및 파일 시스템의 장소로 점점 더 많이 사용되고 있다. 하드디스크와는 달리 재기록이 불가능하며 성능 특성이 다르기 때문이다.

✅ 파일시스템

• 쉽게 데이터를 저장하고, 찾고 또한 인출할 수 있게 함으로써 저장장치를 더욱 효율적이고 편리하게 사용할 수 있게 한다.
• 여러 층으로 이루어져 있으며, 각 층은 낮은 층의 기능을 사용하여 새로운 기능을 만들어 상위층에게 제공한다.

📌 I/O control (입출력 제어 층)

• 장치 드라이버 루틴들과 인터럽트 핸들러로 이루어져 있어서 메모리와 디스크 시스템 간의 정보 전송을 담당한다.
  (장치 드라이버는 번역기라고 생각할 수 있다. 입출력 제어기 메모리의 특별한 위치에 특정 비트를 설정하여 제어기에 어느 장치에 어떤 일을 수행할 지를 알린다.)

📌 basic file system (기본 파일 시스템)

• 적절한 장치 드라이버에게 저장장치상의 블록을 읽고 쓰도록 일반적인 명령을 내린다.
• I/O 요청 스케줄링을 고려한다.
• 다양한 파일 시스템, 디렉터리 및 데이터 블록을 저장하는 메모리 버퍼와 캐시를 관리한다.

📌 file-organization module (파일-구성 모듈)

• 파일 구성 모듈은 파일과 상응하는 논리 블록을 알고 있고, 어느 디스크 공간이 비어 있는지를 파악하는 가용 공간 관리자도 포함하고 있어서 이 모듈이 요구할 때 이들 블록을 제공한다.

📌 logical file system (논리 파일 시스템)

• 메타데이터 정보를 관리한다.
  (메타 데어터는 파일의 내용 자체인 데이터를 제외한 모든 파일 시스템 구조를 말한다.)

📌 file control block, FCB (파일 제어 블록)

• 소유, 허가 그리고 파일 내용의 위치를 포함하여 파일에 관한 정보를 가지고 있다.

14.2 File-System Implementation

파일 시스템 연산을 구현하는데 사용되는 구조와 연산에 대해 깊이 살펴보자.

14.2.1 Overview

파일 시스템은 저장장치에 저장된 운영체제를 어떻게 부트시키는지, 그리고 블록의 총수, 가용 블록의 수와 위치, 디렉터리 구조 그리고 개별 파일에 대한 정보를 디스크 상에 가지고 있다.

✅ 디스크 상의 구조

• 부트 제어 블록 : 시스템이 그 파티션으로부터 운영체제를 부트시키는데 필요한 정보를 가지고 있다. (운영체제를 가지고 있지 않다면 부트 제어 블록은 비어있음)
• 볼륨 제어 블록 : 볼륨의 블록의 수, 블록의 크기, 가용 블록의 수와 포인터, 그리고 가용 FCB 수와 포인터와 같은 볼륨 정보를 포함한다.
• 디렉터리 구조는 파일을 조직화 하는데 사용한다.
• 파일별 FCB는 자세한 파일 정보를 가지고 있다.

메모리 내의 정보는 파일 시스템 관리와 캐싱을 통한 성능 향상을 위해 사용된다. 이 정보들은 마운트 시점에 적재되고, 파일 시스템 동작 중에 갱신되며, 마운트 해제 시에 제거된다.

✅ 메모리 내의 정보

• 메모리 내 파티션 테이블은 마운트된 모든 파티션 정보를 포함한다.
• 메모리 내 디렉터리 구조는 최근 접근된 디렉터리의 디렉터리 정보를 가진다.
• system wide open file table(범 시스템 오픈 파일 테이블)은 다른 정보와 더불어 오픈된 각 파일의 FCB의 복사본을 가지고 있다.
• per-process open file table(프로세스별 오픈 파일 테이블)은 프로세스가 연 모든 파일에 대해 다른 정보 뿐만 아니라 범 시스템 오픈 파일 테이블 내의 해당 항목에 대한 포인터를 포함한다.
• 버퍼는 파일 시스템이 파일 시스템으로부터 읽히거나 써질 때 파일 시스템 블록을 저장한다.

정리하자면
➡ 새로운 파일을 생성하기 위해,,
1. 프로세스는 논리 파일 시스템을 호출한다.
2. 파일 시스템은 새로운 FCB를 할당하고, 해당 디렉토리를 메모리로 읽어, 새로운 파일 이름과 FCB로 디렉토리를 갱신하여, 파일 시스템에 다시 쓴다.
3. 그리고 파일 시스템은 디렉터리 입출력을 저장장치 블록 위치로 매핑하기 위해 파일 구성 모듈을 호출하고
4. 이것은 기본적인 파일 시스템과 입출력 제어 시스템에서 처리된다.

14.2.2 Usage

✅ open() system call & read() system call

• open() 시스템 콜은 논리적 파일 시스템에 파일 이름을 넘겨준다.
• open() 시스템 콜은 파일이 이미 다른 프로세스에 의해 사용 중인지 확인하기 위해 범 시스템 오픈 파일 테이블을 검색한다.
  • 사용중이라면)
    기존 범 시스템 오픈 파일 테이블을 가리키는 프로세스별 오픈 파일 테이블 항목이 생성된다.
  • 파일이 오픈되지 않았다면)
    주어진 파일 이름을 디렉터리 구조에서 찾는다. 디렉터리 연산의 속도를 향상시키기 위해 디렉터리 구조의 일부를 메모리에 캐싱한다.
    파일이 발견되면 FCB가 메모리 내의 범 시스템 오픈 파일 테이블에 복사된다.
• 범 시스템 오픈 파일 테이블의 항목에 대한 포인터와 몇 개의 다른 필드를 갖는 새로운 항목이 프로세스별 오픈 파일 테이블 안에 만들어진다.
  • 이 필드들은 파일 안의 현재 위치(read()나 write() 연산이 시작되는 위치)를 가리키는 포인터와 파일이 오픈된 접근 모드 등을 포함한다.
• open() 시스템 콜은 프로세스별 파일 시스템 테이블 내의 해당 항목에 대한 포인터를 찾아 돌려준다. 그 후 모든 파일 연산은 이 포인터를 통해 실행된다.
• 프로세스가 파일을 닫을 때, 프로세스별 테이블 항이 삭제되며 범 시스템 항목의 오픈 계수는 감소한다.

14.3 Directory Implementation

디렉토리 공간을 어떻게 할당하고 관리하는가는 파일 시스템의 효율, 성능과 신뢰성에 큰 영향을 미친다.

14.3.1 Linear List

디렉터리를 구현하는 가장 간단한 방법.
파일 이름과 데이터 블록에 대한 포인터들의 선형 리스트를 디렉터리에 사용한다.

이 방법은 프로그램이 쉽지만 실행 시간이 길다. (파일을 찾기 위해 선형 탐색을 해야 하므로)

✔ 파일 생성
: 먼저 디렉터리를 탐색하여 같은 이름을 가진 파일이 존재하지 않는다는 것을 확인한 후, 디렉터리의 끝 부분에 새로운 항목을 첨가한다.

✔ 파일 삭제
: 디렉터리에서 이름을 찾아 그 파일에 할당된 공간을 방출한다.

✔ 파일 재사용
: 항목을 미사용으로 표시하거나 가용 디렉터리 항목 리스트에 추가한다.

14.3.2 Hash Table

파일 이름을 제시하면 해시로부터 값을 얻어서 그것을 포인터로 활용하여 이 리스트를 직접 접근할 수 있다. ➡ 디렉터리 탐색 시간을 상당히 개선할 수 있다.

✔ 해시 테이블의 심각한 문제점

• 해시 테이블이 고정된 크기를 갖는다는 점

• 해시 테이블의 크기에 따라 해시 기능도 제한을 받는다는 점

  (예) 64개의 항목을 갖는 선형 탐사 해시 테이블을 만든다고 가정했을 때, 해시 함수는 64로 나눈 나머지 값을 이용하여 파일이름을 0부터 63까지의 정수로 변환한다. 나중에 65번째 파일을 생성하려면 디렉터리 해시 테이블을 (이를테면 128 항목이 들어가도록) 반드시 키워야 하고, 기존 디렉터리를 새로운 해시 값에 맞게 새로 조직해야 한다.

✔ 대안으로, 체인 오버플로우 해시 테이블을 사용할 수 있다.
: 각 해시 항목은 하나의 값이 아니라 연결 리스트가 되고, 새로운 항목을 연결 리스트에 추가함으로써 충돌을 해결한다.

14.4 Allocation Methods

파일을 어떻게 저장장치 공간에 배치해야 디스크 공간을 효율적으로 사용할 수 있고, 파일들을 빨리 접근할 수 있을까?

14.4.1 Contiguous Allocation

Contiguous Allocation (연속할당)

• 각 파일이 저장장치 내에서 연속적인 공간을 차지하도록 요구한다.
• 한 파일의 연속 할당은 첫 번째 블록 주소와 (블록 단위의) 길이로 정의된다.
  (파일 길이가 n 블록이고 블록 b에서 시작한다면, 이 파일은 블록 b, b+1, b+2, ,,, , b+n-1을 차지한다)

✔ 장점

• 순차 접근, 직접 접근 두 가지를 모두 지원할 수 있다.
  ➡ 순차접근: 파일 시스템은 가장 최근에 참조된 주소를 기억하고 있다가 필요할 때 다음 블록을 읽어들이면 된다.
  ➡ 직접접근: 블록 b에서 시작하는 파일의 'i번째 블록'을 직접 접근하기 위해서는 블록 b+i를 즉시 접근하면 된다.

✔ 단점

• 파일의 가용 공간을 찾기가 어렵다.
  (조금 있다가 설명할 가용 공간 관리 시스템의 구현이 이 문제를 해결)

• 파일을 위해서 얼마나 많은 공간을 주어야 할지 결정하는 것이 어렵다.
  ➡ 너무 작은 공간을 예약했을 경우

  1. 확장이 안 될 경우 사용자에게 오류 메시지를 출력하고 프로그램을 종료시키는 방법
     : 사용자가 더 많은 공간을 요구하며 프로그램을 다시 실행시켜야 하고,, 이러한 반복 수행은 비용이 많이 들며, 이를 방지하기 위해 사용자는 통상 필요한 공간을 지나치게 크게 추정하여 공간의 낭비가 발생한다.
  2. 보다 큰 조각을 찾아 그곳으로 파일을 복사하고 이전의 공간을 비우는 방법
     : 시간이 걸리긴 하지만 공간이 존재하는 한 반복될 수 있다. 따라서 사용자에게는 알리지 않지만 시스템이 점점 느려질 것이다.

운영체제는 이러한 단점을 최소화하기 위해 어느 정도의 연속된 공간만 초기에 할당하고 그 양이 충분히 크지 않을 때는 추후 n개의 연속된 공간을 단위로 할당한다.

14.4.2 Linked Allocation

Linked Allocation (연결할당)

• 파일은 저장장치 블록의 연결 리스트 형태로 저장되고, 이 블록들은 장치 내에 흩어져 저장될 수 있다.
• 디렉터리는 파일의 첫번째와 마지막 블록에 대한 포인터를 가지고 있다.
• 각 블록은 다음 블록을 가리키는 포인터를 포함한다.
  (포인터가 차지하는 영역은 사용자가 사용할 수 없다. 따라서 블록 크기에서 포인터의 크기를 뺀 만큼 데이터를 저장할 수 있다.)

✔ 장점

• 연결 할당의 경우 external fragmentation이 없고, 모든 블록의 크기가 같기 때문에 가용 공간 리스트의 어떠한 가용 블록들을 이용해도 무방하다.
• 파일 생성 시 생성할 파일의 크기가 미리 고정될 필요가 없다.
• 파일은 계속해서 커질 수 있으며 디스크 공간을 주기적으로 밀집화할 필요가 없다.

✔ 단점

• 순차적 접근 파일에만 효과적으로 사용될 수 있고, 직접 접근 방식에는 매우 비효율적이다.
• 포인터들을 위한 공간이 필요하다.
• 각 블록이 전체 장치에 흩어져 연결되기 때문에 오류나 하드웨어 고장으로 인하여 하나의 포인터를 잃어버리거나 잘못된 포인터 값을 가지면 모든 데이터를 잃게 되어, 신뢰성 문제가 있다.

➕ FAT (file allocation table)

• 연결할당 변형 방식
• 파일 할당 테이블은 각 블록마다 한 개의 항목을 가지고 있고, 이 항목은 디스크 블록 번호를 인덱스로 갖는다.
• 디렉터리 항목은 각 파일의 첫 번째 블록 번호를 가리키고, 그 블록 번호를 가지고 FAT 테이블로 가면 그 항목은 다음 블록의 블록 번호를 가리킨다.
• 마지막 블록의 테이블 항은 파일의 끝을 나타내는 특수한 값을 가진다.

14.4.3 Indexed Allocation

Indexed Allocation (색인할당)

• 모든 포인터들을 하나의 장소 즉, 색인 블록으로 관리한다.
• 각 파일은 저장장치 블록 주소를 모아놓은 배열인 색인(index) 블록을 가지며, 색인 블록의 i번째 항목은 파일의 i번째 블록을 가리킨다.
• 파일이 생성될 때 인덱스 블록의 모든 포인터는 null로 설정된다.

✔ 장점

• external fragmentation 없이 직접 접근을 지원한다.

✔ 단점

• 공간 낭비 문제가 있다.
  • 색인 블록의 포인터 오버헤드는 일반 연결 할당의 포인터 오버헤드보다 크다.
  • 색인 할당을 사용하면 하나 또는 두 개의 포인터만 null이 아니어도 전체 색인 블록을 할당해야 한다.

그렇다고 색인 블록을 작게 만들자니,, 큰 파일에 대한 충분한 포인터를 보유할 수 없으니까 문제!
이를 해결할 3가지 기법을 소개한다.

1. 연결 기법 (linked scheme)
   : 파일의 크기가 크면 여러 개의 색인 블록을 연결한다.
2. 다중 수준 색인 (multilevel index)
   : 연결 기법의 변형. 여러 개의 두 번째 수준 색인 블록들의 집합을 가리키기 위해 첫 번째 수준의 색인 블록을 사용하고, 파일 크기에 따라 계속된다.

3. 결합 기법 (combined scheme)
   : inode에 색인 블록의 15개 포인터를 유지한다.
   이 포인터들의 처음 12개는 직접 블록(direct block)을 가리키는데, 이 포인터들은 파일의 데이터를 저장하고 있는 블록들의 주소를 저장한다.
   그 다음의 3개의 포인터는 간접 블록(indirect block)을 가리킨다.
   그 중 첫 번째 포인터는 단일 간접 블록(single indirect block)을 가리키는데, 이 블록은 데이터가 아니라 데이터를 저장하고 있는 블록의 주소를 저장한다.
   두 번째 포인터는 이중 간접 블록(double indirect block)을 가리키는데, 이 블록은 실제 데이터 블록을 가리키는 포인터를 저장하는 블록의 주소를 저장한다.
   마지막 포인터는 삼중 간접 블록(triple indirect block)의 주소를 저장한다.

14.5 Free-Space Management

새로운 파일을 만들려면 가용 공간 리스트를 탐색하여 새로운 파일을 위한 공간을 할당받아야 한다.

14.5.1 Bit Vector

가용 공간 리스트는 흔히 비트맵, 또는 비트 벡터로서 구현된다.
각 블록은 1비트로 표현된다.
만약 블록이 비어 있으면 그 비트는 1이 되고 할당 되어 있으면 0이 된다.

14.5.2 Linked List

모든 가용 블록을 함께 연결한다.
첫 번째 가용 블록에 대한 포인터는 별도의 장소에 보관하고, 각 블록은 다음 가용 블록을 가리키는 포인터를 가진다.

14.5.3 Grouping

가용 리스트 방식의 변형으로, 첫 번째 가용 블록 내에 n개의 블록 주소를 저장하는 방법이다.
이 중 처음 n-1개는 실제로 비어있는 블록의 주소이고, 마지막 1개는 자신과 마찬가지로 n-1개의 빈 블록 주소를 가지고 있는 가용 블록을 가리킨다.

14.5.4 Counting

모든 블록을 일일이 추적할 필요 없이 연속된 가용 블록의 첫 번째 블록의 주소와 연속된 블록의 개수(count)만 유지하는 방식이다.
가용 공간 리스트의 각 항은 하나의 장치 주소와 블록의 개수로 구성된다.