KOCW - 운영체제(이화여대 반효경 교수)
10장 파일 시스템

파일 시스템

파일?

A named collection of related information

• 일반적으로 비휘발성의 보조기억장치에 저장

• 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해줌

• 파일 관련 연산

  	* create, read, write, reposition, delete, open, close 등 (이 모든건 I/O 시스템 콜)

  File attribute(혹은 파일의 메타데이터)

• 파일을 관리하기 위한 각종 정보들

  * 파일 이름, 유형, 저장된 위치, 파일 사이즈

  • 접근 권한(읽기/쓰기/실행), 시간(생성/변경/사용), 소유자 등

  File system

• 디렉토리 제공

• 파일의 저장 방법

• 파일의 보호

  Directory and Logical Disk

  Directory

• 디렉토리 또한 파일이다

  	* 디렉토리 파일 밑에 있는 메타데이터를 내용으로 하는 파일

• 디렉토리 관련 연산

  	* search for a file, create a file, delete a file

  • list a directory, rename a file, traverse the file system

• Partition(=Logical Disk)

  	* 하나의 디스크 안에 여러 파티션을 두는게 일반적

  • 디스크를 파티션으로 구성한 뒤 각각의 파티션에 파일 시스템을 깔거나 스와핑 등 다른 용도로 사용할 수 있음

open()

• file을 open()할 경우 그 file의 metadata가 메모리로 올라오게 된다.

open("/a/b") 과정

1. 사용자 프로세스에서 open()으로 시스템 콜

2. CPU가 운영체제로 넘어가고 파일 root 디렉토리의 메타데이터(파일 content의 위치 정보가 있음를 읽고 content 위치로 이동)

3. 파일 a의 metadata가 있음 -> a의 metadata 안에는 a의 content에 대한 metadata(위치 정보)가 있음

4. 파일 a의 content 안에는 파일 b의 metadata가 있음 -> b의 metadata안에는 b의 위치가 있음

5. 그 후 사용자 프로세스가 read(fd..) 요청 -> b의 content 내용을 읽고 복사한 다음 사용자 프로세스에게 넘겨준다.

• 운영체제의 종류에 따라서 위와 같은 테이블이 여러개일 수도 있고 각기 다를 수 있음

File Protection

파일의 접근 권한

• 파일의 접근 권한은 두 가지

  	* 접근 권한이 누구에게 있는가?

  • 어떤 접근이 가능한가?

Access Control 방법

• Access control Matrix : 위의 그림과 같은 방법, 모든 파일과 모든 유저에 대해 가지고 있는 권한을 행렬로 나타내는 방법, 하지만 모든 파일, 유저에 대해 적는 것은 매우 낭비이기 때문에 linked list를 사용하는 방법을 고려해볼 수 있음

• Access control list : 파일별로 권한이 있는 사용자를 linked list로 묶어놓는 방식

• capability : 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시, 각 사용자 별로 접근 권한이 있는 파일들의 목록을 linked list로 연결 해놓은 것

• Grouping(위 방법들은 부가적인 overhead가 크다, 일반적인 운영체제에서 사용하는 방법) : 각각의 파일에 대해서 그룹을 세개로 나눈다. 9개의 비트만 있으면 모두 표현 가능

위 그림처럼, 세 그룹에 대해서 파일에 대한 접근 권한을 각각 다르게 관리할 수 있음

• Password : 파일마다 password를 두는 방법, 모든 접근 권한에 대해 하나의 password를 둔다 -> password가 많아지면 기억 문제 등이 발생할 수 있음

파일 접근 방법(Access Methods)

순차 접근(sequential access)

• 카세트 테이프를 사용하는 방식처럼 접근(되감기)

직접 접근(direct access)

• LP 레코드 판, 하드디스크와 같은 방식

Allocation of File Data in Disk

Contiguous Allocation

• 하나의 파일이 연속된 블록에 저장됨(만약 블록의 크기가 6이라면, 6개 블록에 연속으로 할당)

장단점

• 장점 : 빠른 I/O(HEAD 이동 시간이 대부분의 I/O 시간, 한 번의 HEAD seek로 많은 정보), 직접 접근 가능

• 단점 : 블록의 크기가 일정하지 않기 때문에 외부조각이 발생할 수 있음, File이 수정됨에 따라 크기가 커질 수 있는데 뒤에 빈 블록이 없을 경우 파일 크기를 키우는데 제약이 생김(미리 더 할당해놓는 방법도 있으나 그 이상 커지면 또 문제 발생, 심지어 내부조각임)

Linked Allocation

• file의 데이터를 연속적으로 배치하지 않고, 빈 블록에 할당하는 방법, 각 블록마다 다음 블록을 가리키는 정보가 들어있음

• 파일의 시작 위치만 directory가 가지고 있음

장단점

• 장점 : External fragmentation(외부 조각) 발생 안함

• 단점

  	* No random access -> 인덱스 접근이 불가능함(linked list의 전형적인 문제, 직접 접근이 아닌 순차접근만 가능함)

  • 다음 위치를 가리키는 pointer가 유실되면 데이터의 상당부분 상실
  • pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림

• 변형

  • File-allocation table(FAT) 시스템

Indexed Allocation

• 파일의 직접 접근을 위한 방법

• 인덱스 블록 안에 각 블록의 인덱스를 적어놓는다.

장단점

• 단점

  	* 아무리 작은 파일이라도 인덱스 블록이 필요 -> 공간 낭비

  • 매우 큰 파일의 경우에는 인덱스 블록 하나로 모든 인덱스를 저장하기에 부족하다. -> 만약 다른 인덱스 블록을 사용해야 할 경우 기존 인덱스 블록의 가장 마지막 인덱스는 다음 인덱스 블록의 위치가 됨

UNIX 파일 시스템의 구조

Boot block

• 부팅에 필요한 정보

Super block

• 파일 시스템에 관한 총체적인 정보를 담고 있다.

Inode list

• 파일의 메타데이터를 가지고 있음

• 파일당 크기가 고정되어있음

• 위치 정보를 가지고 있는 포인터의 개수도 유한함

• direct, single, double indirect에 파일의 인덱스들이 있음(direct -> single -> double -> triple)순으로 크기가 큰 파일의 접근(파일의 위치 찾기)에 사용됨

Data block

• 파일의 실제 내용을 보관

FAT File System

• FAT에 위치 정보를 저장

• 나머지 메타데이터는 Data block에 저장

• FAT의 배열 - Data block에서 관리하는 데이터의 개수(N)만큼 블록이 있음(크기 N), 이 배열에는 한 칸당 한 개의 숫자를 담을 수 있는데 그 블록의 다음 블록 번호를 저장함(Linked allocation 활용) -> 배열에 계속해서 파일의 다음 위치가 담겨있는 구조임

• linked allocation을 활용한 방식이지만 직접 접근이 가능한 파일 시스템이다(FAT 자체가 배열로 되어있기 때문에 인덱싱이 가능함)

Free-Space Management

비어있는 블록의 관리 방법

Bit map or bit vector

• Bit map은 부가적인 공간을 필요로 함

• 연속적인 n개의 freeblock을 찾는데 효과적

• 각 블록 별로 0, 1값을 매긴 배열, 0일 경우 free block, 1일 경우 occupied block

Linked list

• 모든 free block들을 링크로 연결

• 비어있는 첫번째 블록(HEAD)부터 순차적으로 연결해서 관리

• 연속적인 가용공간을 찾기가 쉽지 않다.

• 빈 공간만 따로 연결하기 때문에(Bit map과 같은 방식에 비해) 공간적인 낭비가 없다

Grouping

• linked list방법의 변형

• 첫번째 블록(HEAD)이 여러 개의(포인터 여러개) free block을 가리킴, 그 뒤에 있는 블록들도 마찬가지

• linked list와 마찬가지로 연속적인 공간을 찾기는 어려움

Counting

• 프로그램 뒤에 종종 여러 개의 빈 블록이 있다는 성질을 이용하여 프로그램 + 뒤에 오는 빈 블록 개수를 쌍으로 관리하는 방식

Directory Implementation

Linear list

• file name, file의 metadata를 저장한 리스트

• 특정 파일을 찾는 연산을 할 때 linear search -> 시간이 오래 걸림

Hash Table

• file name을 hash 함수로 적용

Hash 함수?

• 어떤 값을 입력하면 입력값에 상관없이 일정 범위 값으로 출력됨

• ex) filename : cccc -> (hash 함수 적용) -> hash table 상 filename : 3 이런 식

File의 metadata의 보관 위치

• 디렉토리 내에 직접 보관

• 디렉토리에는 포인터를 두고 다른 곳에 보관

Long file name의 지원

file name을 일정 길이로 일단 제한, 길이가 제한을 넘을 경우 다음 이름을 다른 디렉토리 파일에 일괄적으로 저장, 포인터를 file name의 가장 끝에 저장해놓고 다음 이름을 가리키는 방시

VFS and NFS

Virtual File System(VFS) 계층

• 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 layer

Network File System(NFS)

• 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음

• 서버와 클라이언트 측에서 NFS를 위한 보조가 필요함

Page Cache and Buffer Cache

• Virtual Memory 관점 : Page Cache

• file system 관점 : Buffer Cache(커널 영역에서 관리되는 캐시)

  	* 버퍼캐시는 시스템콜이 들어왔을 때 파일 시스템에서 읽어온 정보를 버퍼캐시에 놓고, 이 내용을 복사해서 사용자 메모리에 보내준다. 이 정보는 버리지 않고 다음에 비슷한 요청이 들어올때 재활용한다.

  • 버퍼캐시의 경우에는 LRU와 같은 알고리즘이 사용 가능하다

• Unified Buffer Cache : 두 캐시가 통합된 캐시, page 캐시가 프로세스의 주소 공간을 담는 용도로도 쓰이지만 또 다른 일부분은 버퍼캐시처럼 사용이 된다.

• Memory-Mapped I/O : File의 일부를 메모리에 매핑, system call 필요 없이 메모리에서 읽고 쓰는 방식.

  	* Memory-mapped I/O를 사용하더라도 기존 방식은 buffer cache를 통과해야함

  • 하지만 Unified Buffer Cache의 경우에는 파일을 바로 Page cache와 매핑 할 수 있다.

프로그램의 실행

• 파일 시스템에 있는 파일을 프로세스의 주소 공간에 mapping 시켜놓는다.

• 그렇기 때문에 메모리에 필요한 코드가 없을 경우 파일 시스템을 뒤지는 것이 아니라, 가상 메모리에 매핑 되어있는 코드를 찾는 것이다.

• 데이터 파일 Memory-mapped I/O : 프로세스에서 데이터 파일을 사용하겠다는 system call -> 주소 공간 일부를 데이터 파일과 mapping -> 이 프로세스의 주소공간이 물리 메모리의 어딘가와 매핑이 되어있을 것임 -> 물리적인 메모리의 그 부분은 파일과 매핑이 되어있음

• read와 같은 I/O : 물리적인 메모리에 있는 read 요청을 받은 파일을 운영체제가 읽어온 다음 copy해서 해당 프로세스의 가상 공간에 복사해줌