11.1 파일 시스템 구조(File-System Structure)

▶ 파일 시스템: 자료와 프로그램의 온라인 저장과 접근에 대한 관리 기법을 제공

→ 보조기억장치에 상주: “디스크”

11.1 파일 시스템 구조(File-System Structure)

▶ 디스크: 보조기억장치의 유지 → 기억장치와 디스크간의 입출력은 블록 단위로 실행

- 재기록 가능

- 직접 접근 가능

→ 디스크 구조: 13장

11.1.1 파일 시스템 조직(File-System Organization)

▶ 파일 시스템 설계의 고려 사항

1) 사용자를 위한 파일 시스템의 표현

① 파일의 정의와 속성

② 파일 구성을 위한 디렉토리 구조

③ 파일에 대한 조작

2) 물리적 보조기억장치와 논리적 파일 시스템을 사상하는 알고리즘과 자료 구조

[그림 11.1] 계층적 파일 시스템

① 논리적 파일 시스템(logical file system): 파일명으로 디렉토리를 참조하여 파일 구성 모듈에게 파일 속성 제공

→ 보호 문제(10장), 보안 문제(19장) 담당

② 파일 구성 모듈(file-organization module): 파일과 디스크 블록에 대한 정보 유지

→ 특정 블록의 주소 산출 담당: ex) 구동기 1, 실린더 73, 표면 2, 섹터 10

③ 기본적 파일 시스템(basic file system): 디스크에 있는 물리적 블록을 읽거나 쓰는 기본 명령어를 발생

④ 입출력 제어(I/O control): 장치 구동기와 정보 전송을 위한 인터럽트 처리기로 구성

→ 12장 참조

▶ 개방 파일 테이블: 디렉토리 구조 참조의 비효율성을 해결

[그림 11.2] 전형적인 개방 파일 테이블

① 파일의 열기(open)시 디렉토리의 해당 항목을 개방 파일 테이블의 항목으로 복사하고 그 항목의 색인(index)을 사용자 프로그램에 넘김

② 이후 파일의 참조 및 속성 수정은 인덱스에 의한 개방 파일 테이블을 통해 효율적으로 이루어짐

③ 파일의 폐쇄(close)시 변경된 내용이 디렉토리에 복사됨

* 색인(index)의 명칭: 

- UNIX의 파일 기술자(file descriptor)

- Windows NT의 파일 처리기(file handler)

- 파일 제어 블록(file control block)

11.1.2 파일 시스템 마운팅(File-System Mounting)

▶ 시스템 상에서 파일처리를 가능하게 하기 위해서 파일 시스템은 마운트되어야 함 

① 운영체제는 해당 파일 시스템에 대한 장치명과 부착시킬 파일구조내의 위치인 마운트 포인터(mount pointer)를 넘겨받음

ex) /home에 파일 시스템 이름 jane을 마운트 → /home/jane으로 참조

② 운영체제는 장치가 타당한 파일 시스템을 포함하는지를 점검

→ 장치 구동기에게 장치 디렉토리를 판독하게 하여 디렉토리가 기대한 형식을 갖는지를 입증함

③ 운영체제는 파일 시스템이 특정한 마운트 포인터에 마운트되어 있음을 디렉토리 구조에 나타냄

▶ 예: Macintosh 운영체제 → 17.6.2절 참조

- 시스템이 처음으로 디스크를 접하면(하드디스크: 부팅시, 플로피 디스크: 구동기에 넣은 순간), 장치에서 파일 시스템을 찾음

- 찾은 파일 시스템을 루트에 마운트하고, 파일 시스템 이름을 홀더 아이콘 형태로 화면에 나타냄

- 사용자는 아이콘을 눌러 사용

11.2 할당 방법(Allocation Methods)

▶ 목적: 디스크 공간의 효율적 사용 및 신속한 파일 접근

▶ 방법

- 연속 할당(contiguous allocation)

- 연결 할당(linked allocation)

- 색인 할당(indexed allocation)

11.2.1 연속 할당(Contiguous Allocation)

▶ 정의: 각 파일에 디스크의 연속적인 주소들의 집합을 할당하는 방법

▶ 디렉토리의 파일 항목: ‘시작 블록의 주소’(b) + ‘파일 길이(블록수)’(n)

→ 파일: 블록 로 구성

[그림 11.3] 디스크 공간에서의 연속 할당

▶ 장점: 접근 용이

- 순차 접근 가능: 블록 의 다음 블록 → 블록

- 직접 접근 가능: 블록 에서 시작하는 번째 블록 → 블록

▶ 단점

1) 파일에 할당할 가용 공간의 확보가 복잡

① 최초 적격(first-fit): 요구량보다 큰 첫 번째 가용 영역을 할당

② 최상 적격(best-fit): 요구량보다 큰 영역 중 가장 작은 것을 할당 

③ 최악 적격(worst-fit): 가장 큰 가용 영역을 할당

→ 모의 실험: 기억 공간 이용률 및 처리 시간 측면에서 ①과 ②가 보다 우수

2) 외부 단편화: 전체 가용 공간이 요구량보다 크지만 연속적인 공간이 아닌 경우에 발생

→ 압축(compaction): ①과 ②의 처리 시간이 오래 걸림

해당 디스크

다른 디스크

① 전체 복사

② 재배치

③ 새 파일 할당

3) 출력되는 파일에 요구되는 기억 장소의 크기 결정 문제

- 오류 메시지와 함께 생성 작업이 중단되면 사용자가 보다 큰 공간을 할당하고 재수행하는 방법

→ 시간 많이 소요, 넉넉하게 공간 할당을 할 경우 공간 낭비

- 생성 작업이 중단되면 파일 시스템이 보다 큰 사용 공간에 복사하고 계속 진행하는 방법

→ 여전히 시간 많이 소요

* 특히 장시간에 걸쳐서 서서히 증가하는 파일의 경우, 총 공간을 미리 할당하는 것은 비효율적

11.2.2 연결 할당(Linked Allocation)

▶ 정의: 파일에 디스크 블록의 연결 리스트(linked list)를 할당하는 방법

→ 각 블록은 다음 블록을 가리키는 포인터를 가져야 함

▶ 디렉토리의 파일 항목: ‘파일의 처음 섹터 포인터’ + ‘파일의 마지막 섹터 포인터’

[그림 11.4] 디스크 공간에서의 연결 할당

▶ 사용법

- 파일 생성: 디렉토리에 새 항목 추가 → 처음 블록 포인터를 로 초기화

- 쓰기: 첫 번째 사용 가능 블록에 쓰고 이전의 마지막 블록에 연결

- 읽기: 처음 블록부터 을 만날 때까지 포인터를 따라가면서 읽음

▶ 장점

- 외부 단편화 현상이 발생하지 않음 → 압축 필요 없음

- 생성되는 파일의 크기를 미리 선언할 필요 없음 → 사용 가능 공간이 존재하는 한 증가 가능

▶ 단점

- 직접 접근이 불가: 파일의 번째 블록 참조를 위해서는 처음부터 포인터를 따라가야 함

- 포인터가 차지하는 공간 소요

ex) 포인터: 4bytes, 블록: 512bytes → 0.78% 소모

- 신뢰성 결여: 운영체제의 결함, 하드웨어의 고장 등으로 포인터 손실시 파일의 상당한 훼손 초래

→ ‘이중 연결 리스트’로 보완 가능: 메모리 소요 증가

▶ 변형: 파일 할당 테이블(FAT) 사용 → MS-DOS, OS/2에서 사용

[그림 11.5] 파일 할당 테이블

- 위치: 각 단편(partition)의 처음 부분(0번 블록)

- 구성: 블록 번호를 인덱스로 하고 각 항목에는 다음 블록 번호를 기록하여 연결 리스트로 사용

(단, (-1): 파일의 끝, 0: 가용블록)

- 단점: 디스크 헤드의 이동이 빈번해짐

→ 요구되는 블록에 접근하기 위해서는 FAT(0번 블록)를 먼저 접근해야하기 때문

- 장점: 직접 접근 시간이 줌

→ FAT(0번 블록)내에서만 탐색하면 됨

11.2.3 색인 할당(Indexed Allocation)

▶ 정의: 각 파일의 색인 블록에 그 파일의 블록들을 가리키는 포인터들을 모아두는 방법

                      → 디스크 블록 주소의 배열

▶ 디렉토리의 파일 항목: ‘각 파일의 색인 블록에 대한 포인터’

[그림 11.6] 디스크 공간에서의 색인 할당

▶ 장점

- 직접 접근 가능: 번째 블록은 색인 블록의 항목에 있는 번째 포인터로 직접 접근

▶ 단점

- 블록수가 적은 파일의 경우: 색인 블록의 기억 장소가 낭비됨

- 블록수가 많은 파일의 경우: 하나의 색인 블록으로 충분한 포인터를 가질 수 없음

(해결 방법)

① 연결 기법(linked scheme): 색인 블록의 마지막까지 이 나오지 않으면 마지막의 주소가 다음 색인 블록의 포인터임

② 다중 수준 색인(multilevel index): 색인 블록의 색인 블록을 운영 - 2단, 3단, ...

→ 주로 매우 큰 파일들이 많은 경우 적합

ex) 1단: 256 포인터

    2단: 256×256=65,536 포인터

③ 결합 기법(combined scheme): BSD UNIX의 경우

[그림 11.7] UNIX의 inode

* 디렉토리의 항목이 inode를 가리킴

11.2.4 성능(Performance)

▶ 기준

- 기억 장소의 효율성

- 자료 블록의 접근 속도

▶ 연속 할당

- 직접 접근/순차 접근: 단 한번의 블록 접근 소요

- 외부 세그먼트 발생함

▶ 연결 할당

- 순차 접근: i번째 섹터에 접근하기 위해서는 디스크를 i번 읽어야 함 → 직접 접근 불가 

- 외부 세그먼트 발생 안함

▶ 연속 할당과 연결 할당의 병용

- 운영체제가 두 가지 방식을 지원해야 하고, 파일 선언시 접근 형태를 선언해야 함  

- 직접 접근 파일과 순차 접근 파일은 복사에 의해 상호 변환 가능

▶ 색인 할당

- 성능은 색인의 구조, 파일의 크기, 블록의 위치에 영향을 받음

▶ 연속 할당과 색인 할당의 병용

- 파일의 크기에 따라, 파일의 유형이 자동 결정 및 자동 변환됨

1) 小(3-4블록 이내): 연속 할당

2) 大: 색인 할당

- 대부분의 파일이 작기 때문에 평균 성능은 우수

11.3 가용 공간 관리(Free Space Management)

▶ 가용 공간 리스트(free space list): 비어 있는 모든 디스크의 블록들을 등록

- 제거: 파일 생성시

- 추가: 파일 삭제시

→ 구현: 11.3.1 - 11.3.4

11.3.1 비트 벡터(Bit Vector)

▶ 비트 ↔ 블록

- 0: 사용 가능

- 1: 사용중

ex) 사용 가능 섹터: 2, 3, 4, ... → 비트 벡터: 00111...

11.3.2 링크드 리스트(Linked List): 연결 할당 개념

▶ 가용 공간 리스트 헤드부터 시작하여 링크에 의해 다음 사용 가능 블록을 연결

[그림 11.8] 디스크 상의 연결된 가용 공간

→ 가용 공간 리스트 검사 시, 모든 가용 블록에 접근해야 함: 비효율적

11.3.3 그룹핑(Grouping): 색인 할당 개념

▶ 처음 가용 블록에 n개의 가용 블록의 주소를 기입하되, 마지막에는 다른 n개의 가용 블록의 주소를 기입하고 있는 블록의 디스크 주소가 위치함

  → 가용 공간 리스트 검사 시, 평균 1/n 블록만을 접근하면 됨: 신속한 검색 가능

11.3.4 계수(Counting): 연속 할당 개념

▶ 가용 공간 리스트의 항목: 연속된 가용 공간마다 첫 번째 블록의 주소와 블록 수를 기록

- 가용 공간 리스트의 축소

- 연속 할당에 유용

11.4 디렉토리 구현(Directory Implementation)

11.4.1 선형 리스트(Linear List)

▶ 선형 리스트(linear list): 선형 탐색

- 실행 시간이 오래 걸림

- 알고리즘 간단

▶ 정렬된 리스트(sorted list): 이진 탐색

- 평균 탐색 시간 감소

- 알고리즘 복잡

11.4.2 해시 테이블(Hash Table)

▶ N 항목의 경우: 파일명(key)     ↔     0 . . N-1

                       ‘해시 함수(hash function)’

(장점) 탐색 시간을 상당히 개선

(단점) 일반적으로 key > N이므로 충돌(collision) 발생 가능

- 다음 빈 공간에 저장: 선형 검색법(linear probing)으로 탐색

- 빈 공간이 없으면 실패: 과잉 상태(overflow) 

  → 고정된 N에서 초래됨: 해시 테이블의 확대 재구성 필요

11.5 효율성(Efficiency)과 성능(Performance)

▶ 시스템의 병목 현상 주원인: 보조기억장치

→ 디스크 공간의 효율성과 파일 시스템의 처리 성능을 향상시키기 위한 기법 논의

11.5.1 효율성(Efficiency)

▶ 디스크 공간의 효율적 사용: 디스크 할당 및 디렉토리 알고리즘과 밀접하게 관련됨

- 분할(partition) 상에 inode를 분배하여 할당: ex) UNIX

→ inode에 인접하여 해당 파일의 데이터를 위치시킴으로써 디스크의 탐색 시간을 줄임

- 파일 크기에 따른 클러스터링 기법: ex) BSD UNIX → 단편화의 최소화

1) 소용량 클러스터: 작은 파일, 파일의 마지막 클러스터

2) 대용량 클러스터: 채워지는 경우 사용

- 디렉토리 구조의 정보 형태

1) 최종 기록 날짜: 파일의 예비 저장(backup) 필요 여부를 결정

2) 최종 판독 날짜: 파일 접근이 빈번한 경우는 비효율적

3) 포인터의 크기: 클수록 파일의 최대 크기가 커지지만 가용 공간 관리를 위한 공간 소모도 커짐

- 파일 시스템의 크기: 고정 크기 ↔ 동적 할당

11.5.2 시스템 성능(Performance)

▶ 디스크 캐시(disk cache): [그림 11.9] 다양한 디스크 캐시 위치

1) 트랙 버퍼(track buffer): 디스크 제어기는 한번에 전체 트랙의 내용을 저장할 수 있는 캐시(on-board cash) 형태의 충분한 지역 기억공간을 가지고 있음

2) 블록 버퍼(block buffer): 사용되지 않는 기억장치 공간을 페이징 시스템과 디스크 블록 시스템에 의해 공유되는 버퍼 풀로 사용

3) 가상/램 디스크(virtual/RAM disk): 기억장치의 특정 부분을 가상/램 디스크로 사용

→ 주로 중간 컴파일된 파일과 같은 임시 파일의 저장에 사용

▶ 디스크 캐싱의 최적화: 파일의 접근 형태에 따라 서로 다른 교체 알고리즘을 사용

ex) 순차적 접근의 경우, LRU 교체는 부적합 → free-behind, read-ahead 기법이 적합

11.6 회복 기법(Recovery)

▶ 시스템 결함으로 인한 자료의 비일관성 또는 자료 손실이 초래되지 않도록 해야 함

11.6.1 일관성 검사(Consistency Checking)

▶ 일관성 검사자(consistency checker)

- 디렉토리 구조에 있는 정보와 디스크에 있는 데이터 블록을 비교하여 발견된 불일치 내용을 수정

- 접근 속도를 높이기 위해 주기억장치에 위치하는 디렉토리 정보의 일부(ex: 개방파일테이블)과 실제 디렉토리와의 불일치를 수정

11.6.2 예비 저장(Backup)과 재저장(Restore)

▶ 재저장: 시스템 프로그램의 저장을 위한 디스크로부터 플로피 디스크, 자기 테이프, 광 디스크와 같은 다른 저장 장치로의 복사

▶ 예비 저장: 개개의 파일 혹은 전체 디스크의 손실로부터 회복하기 위한 재저장 → (예) p.422 내용