[운영체제] 11 File Systems Implementation

gramm·2021년 2월 16일

운영체제

목록 보기

12/14

내용 출처

KOCW 반효경 교수님 <운영체제> 강의

반효경 교수님의 <운영체제> 강의 내용을 기반으로 정리했으며,

이 포스팅의 모든 이미지는 <운영체제> 강의에서 가져왔습니다.

디스크에 파일 데이터를 저장하는 방식은 크게 Contiguous Allcocation, Linked Allocation, Indexed Allocation으로 나눌 수 있다.

연속 할당

Contiguous Allcocation : 하나의 파일이 디스크 상에 연속해서 저장되는 방식

디렉토리 파일은 디렉토리 하의 파일들의 메타 데이터를 내용으로 한다. 위 그림에서는 디렉토리 하에 5개의 파일이 있고, 그 파일의 메타 데이터(이름, 위치 정보 등)이 담겨 있다.

단점
- 외부 조각이 발생한다.
- 파일의 크기를 키우는 데 제약이 있다. 파일을 수정하면서 파일의 크기가 커질 수 있는데, 그것에 제약이 있다는 것이다. 그래서 미리 여유 공간을 할당할 수는 있지만, 이 경우 내부 조각이 발생할 수 있다.
장점
- 빠른 입출력이 가능하다.
  - 한번의 seek/rotation으로 많은 바이트를 전송할 수 있다.
  - realtime file용으로, 또는 이미 run 중이던 프로세스의 swapping용으로 사용 가능하다.
- 직접 접근(임의 접근)이 가능하다.

연결 할당

Linked Allocation : 파일의 데이터를 디스크에 연속적으로 배치하는 대신, 빈 위치 아무데나 들어갈 수 있게 배치하는 방식

장점
- 외부 조각이 발생하지 않는다.
단점
- 직접 접근(임의 접근)이 불가능하다.
- reliability 문제
  - 하나의 sector가 bad sector가 되어 pointer가 유실되면 이후 부분을 모두 잃어버리게 된다.
- 포인터를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨린다.
  - 디스크에서 하나의 sector는 512byte를 차지하는데, 포인터가 4byte를 차지하므로 비효율적이다.
변형
- File-allocation table (FAT) 파일 시스템
  - 포인터를 별도의 위치에 보관하여 reliability와 공간 효율성의 문제를 해결한다. (아래에서 자세히 다룸)

인덱스 할당

Indexed Allocation

블록 하나에 위치 정보를 저장하는데, 이 블록을 인덱스 블록이라고 한다. 디렉토리는 파일의 위치 정보 대신 인덱스 블록 값을 저장한다.

장점
- 외부 조각이 발생하지 않는다.
- 직접 접근(임의 접근)이 가능하다.
  (연속 할당 / 연결 할당의 단점을 모두 극복)
단점
- 작은 파일인 경우 공간이 낭비된다. (실제로 많은 파일들의 크기가 작다.)
- 너무 큰 파일인 경우 하나의 블록으로 인덱스를 모두 저장할 수 없다.
  - 해결 방안
    - 1. linked scheme
        인덱스 블록의 마지막 위치가 또 다른 인덱스 블록을 가리키게 한다.
    - 1. multi-level index
        인덱스 블록 내의 값들이 각각 인덱스 블록을 가리킨다.
        (2단계 페이징 테이블과 유사)

UNIX 파일 시스템

파티션(논리적 디스크)에 UNIX 파일 시스템을 설치했다.

Boot block
- 부팅에 필요한 정보 (bootstrap loader)
- UNIX 시스템뿐 아니라, 어떤 파일 시스템이라도 가장 먼저 나온다.
Super block
- 파일 시스템에 관한 총체적인 정보를 담고 있다.
- 어디까지 빈 블록이고 어디부터 실제 사용 중인 블록인지, 혹은 어디까지 inode list가 있고 어디부터 data block이 있는지 등을 관리한다.
Inode list
- 파일 하나당 inode가 하나씩 할당된다. 이 inode에 파일 이름을 제외한 파일의 모든 메타 데이터가 저장된다.
- direct blocks부터 triple indirect까지 파일의 위치 정보를 저장한다. 크기가 작은 파일의 경우 direct blocks만으로 파일의 위치 정보를 저장하고, 크기가 커질수록 더 많은 indirect 블록들을 함께 사용한다.
Data block
- 파일의 실제 내용을 보관한다.
- UNIX 파일 시스템에서 data block 내의 디렉토리는 메타 데이터 중 하나인 파일의 이름, 그리고 inode 번호만을 가지고 있다.

FAT 파일 시스템

파일의 메타 데이터 중 위치 정보만을 FAT에 보관한다.

UNIX 파일 시스템과는 대조적으로, 디렉토리 파일이 파일의 메타 데이터 중 위치 정보를 제외한 모든 정보를 가지고 있다. 파일의 첫 번째 위치 정보도 저장하고 있다.

FAT 파일 시스템에서는 하나의 데이터 블록의 다음 블록에 대한 정보를 FAT이라는 별도의 배열에 담고 있다. FAT의 배열의 크기는 디스크가 관리하는 블럭의 크기와 같다.

이는 연결 할당 방식을 활용한 것이지만, 직접 접근이 가능하다. 또한 bad sector가 발생하더라도 FAT의 정보는 남아 있다. FAT의 정보는 중요하므로 보통 디스크에 여러 카피를 저장한다. 따라서 reliability의 문제가 개선된다. 또한 포인터가 저장 공간의 일부를 가져가지도 않는다. 이처럼 FAT 파일 시스템은 연결 할당의 문제점을 모두 개선한다.

Free-Space Management

Bit map / Bit vector
- 비어 있으면 0, 비어 있지 않으면 1로 표시한다.
- bit map은 부가적인 공간을 필요로 한다.
- 연속적인 n개의 free block을 찾는데 효과적이다.
Linked list
- 모든 free block들을 링크로 연결한다.
- 연속적인 가용공간을 찾는 것은 쉽지 않다. (실제로 쓰기는 어렵다.)
- 공간의 낭비가 없다.
Grouping
- linked list 방법의 변형
- 첫 번째 free block이 n개의 pointer를 가진다.
  - n-1 pointer는 free data block을 가리킨다.
  - 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가진다.
Counting
- 프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안한다.
- 빈 블록의 첫 번째 위치(first free block)와, 그 블록에서부터 몇 개의 블록이 비어있는지를 하나의 쌍으로 저장한다.
  (연속된 n개의 블록을 찾기에 적합하다.)

디렉토리의 구현

Linear List
- <파일 이름, 파일의 메타 데이터>의 리스트
- 구현이 간단하다.
- 디렉토리 내에 파일이 있는지 찾기 위해서는 선형 탐색이 필요하므로, 시간이 많이 걸린다.
Hash Table
- linear list + hashing
- 해시 테이블은 파일 이름을 이 파일의 linear list의 위치로 바꾸어준다.
- 탐색 시간을 없앤다.
- 충돌이 발생할 수 있다. (자료구조 내용 참고)
파일의 메타 데이터의 보관 위치
- 1) 디렉토리 내에 직접 보관
- 2) 디렉토리에는 포인터를 두고 다른 곳에 보관
  - UNIX 파일 시스템의 inode, FAT 파일 시스템의 FAT 등

긴 파일 이름의 지원
- <파일 이름, 파일의 메타 데이터>의 리스트에서 각 entry는 일반적으로 고정 크기다.
- 파일 이름이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 둔다. (그림 참고)
- 이름의 나머지 부분은 동일한 디렉터리 파일의 일부에 존재한다.

VFS and NFS

Virtual File System (VFS)
- 서로 다른 다양한 파일 시스템에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 계층
Network File System (NFS)
- 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다.
- NFS는 분산 환경에서의 대표적인 파일 공유 방법이다.

페이지 캐시와 버퍼 캐시

Page Cache
- 가상 메모리의 페이징 시스템에서 사용하는 page frame을 캐싱의 관점에서 설명하는 용어
- Memory-Mapped I/O를 쓰는 경우 파일의 I/O에서도 페이지 캐시를 사용한다.
Memory-Mapped I/O
- 파일의 일부를 가상 메모리에 mapping시킨다.
- 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 한다. 따라서 파일을 접근할 때 read/write 콜을 하는 대신 메모리 영역에 맵핑시킨 영역을 참고하면 된다.
Buffer Cache
- 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 버퍼 캐시를 사용한다.
- 파일 사용의 locality를 활용한다.
  - 파일의 데이터를 사용자가 요청했을 때, 운영체제가 읽어온 내용을 자기 영역의 일부에 저장해 놓는다. 그 내용에 대한 요청이 다시 들어왔을 때 디스크까지 가지 않고 버퍼 캐시에서 바로 읽어다준다.
- 모든 프로세스가 공용으로 사용한다.
- Replacement 알고리즘이 필요하다. (LRU, LFU 등)
Unified Buffer Cache
- 최근의 OS에서는 기존의 버퍼 캐시가 페이지 캐시에 통합되었다.

페이지 캐시 - 프로세스의 주소 공간을 구성하는 페이지가 swap area에 내려가 있는가, 혹은 페이지 캐시에 올라가 있는가?

버퍼 캐시 - 파일 데이터가 파일 시스템 스토리지에 저장되어 있는가, 혹은 버퍼 캐시에 올라가 있는가?

페이지 캐시의 단위는 보통 페이지의 크기인 4KB다.

버퍼 캐시의 단위는 보통 논리적 디스크에서 sector 단위를 의미한다. 이것이 예전에는 512byte였으나, 최근에는 버퍼 캐시가 페이지 캐시와 통합되어 (Unified Buffer Cache) 버퍼 캐시에서도 페이지 단위인 4KB를 쓴다.

파일 입출력

1. Unified Buffer Cache를 이용하지 않는 파일 입출력

2가지 인터페이스가 존재한다.

1) 파일을 open한 뒤, read/write 시스템 콜을 한다.
- 운영체제는 해당하는 파일 내용이 버퍼 캐시에 있는지 확인한다. 있으면 바로 전달해주고, 없으면 디스크 파일 시스템에서 읽어와서 버퍼 캐시에 저장한 뒤 전달해준다.
2) Memory-Mapped I/O
- 처음 memory-mapped I/O를 쓰겠다는 mmap() 시스템 콜을 한다. 그러면 자신의 주소 공간 중 일부를 파일에 매핑한다. 디스크에서 버퍼 캐시로 내용을 읽어온 뒤, 그 내용을 페이지 캐시에 카피한다. 그러면 그 이후에는 운영체제의 간섭없이 내 메모리의 영역에 메모리를 읽고 쓰는 방식으로 파일 입출력을 할 수 있다. 매핑은 했지만 아직 메모리로 읽어오지 않았다면 page fault가 발생한다.

1번 방식의 경우, 그 내용이 버퍼 캐시에 있든 없든 항상 운영체제에 요청해서 받아와야 한다. 반면 2번 방식의 경우, 일단 페이지 캐시에 올라온 내용은 운영체제의 도움을 받지 않고 사용자 프로세스가 직접, 자기 메모리에 접근하듯이 접근할 수 있다. 이것이 memory-mapped I/O를 사용하는 이유다.

하지만 둘 중 어떤 방식을 쓰더라도 파일 입출력 시 버퍼 캐시를 통해야 한다.

2. Unified Buffer Cache를 이용하는 파일 입출력

1) 파일을 open한 뒤, read/write 시스템 콜을 한다.
- 위와 동일하다.
2) Memory-Mapped I/O
- 처음 운영체제에 자신의 주소 영역의 일부를 파일에 매핑하는 단계를 거치고 나면, 그때부터는 사용자 프로그램의 주소 영역에 페이지 캐시가 매핑된다. 그래서 Unified Buffer Cache를 이용하지 않을 때처럼 버퍼 캐시의 내용을 카피하는 것이 아니라, 페이지 캐시 자체가 사용자 프로세스의 논리적 주소 영역에 매핑되었으므로, 페이지 캐시에 직접 읽고 쓸 수 있게 된다.

프로그램의 실행

이미 배운 내용 : 프로그램이 파일 시스템에 실행파일 형태로 저장되어 있고, 이를 실행시키면 프로세스가 된다. 그러면 그 프로세스만의 독자적인 주소 공간인 Virtual Memory가 만들어진다. 이는 code, data, stack으로 구성된다. 그리고 주소변환을 해주는 하드웨어에 의해서 당장 필요한 부분은 물리적 메모리에 올라가 있게 된다. 물리적 메모리는 공간이 한정되므로 쫓겨나는 내용들은 디스크의 swap area로 넘어간다.

위의 내용을 배울 때 code 부분을 간과했었다. code 부분은 메모리에 올라갔다가 쫓겨날 때 swap area로 내려가지 않는다. 코드는 파일 시스템에 실행 파일의 형태로 이미 저장되어 있기 때문이다.

그래서 만약 프로그램이 특정 코드에 접근하는 데 메모리에 올라와 있지 않다면, swap area가 아니라 파일 시스템의 실행 파일에 접근해야 한다. 이것이 파일을 프로그램의 주소 영역에 매핑해서 쓰는 대표적인 예다.