파일, 파일시스템이란?

파일이란 보조 기억 장치에 저장된 연관된 연관된 정보들의 집합이다. 물리적으로는 바이트들의 집합이라 할 수 있다. 내용에 따라서는 프로그램 파일(소스 프로그램, 오브젝트 프로그램, 실행 파일 등)과 데이터 파일로 나눌 수 있다. 형태에 따라 텍스트 파일과 이진파일로 나눌 수 있다.

파일 시스템이란 사용자들이 사용하는 파일들을 관리하는 운영체제의 한 부분이다. 파일시스템은 파일, 디렉토리 구조, 파티션으로 이루어진다. 디렉토리 구조는 시스템 내 파일들의 정보를 구성하고 제공한다. 파티션은 디렉토리들의 집합을 논리적으로 구분한다.

디렉토리는 파일들을 분류, 보관하기 위한 개념이다. 디렉토리를 통해 파일 검색, 파일 생성, 파일 삭제, 디렉토리 나열, 파일 이름 변경, 파일 시스템 순회 등의 동작을 수행 할 수 있다. 디렉토리도 하나의 파일이다. 파일의 메타데이터 중 일부를 보관한다.

보통 디스크를 파티션으로 구성한 뒤 각각의 파티션에 파일 시스템을 깔거나 VM을 보조하는 Swapping 용도로 사용한다.

디렉토리 구조

디렉토리 구조는 단일 디렉토리 구조부터 일반 그래프 디렉토리 구조까지 필요에 의해 변형되어 왔다. 각각의 구조마다 어떤 이슈가 있고 어떻게 해결해왔는지 살펴보려 한다.

1. Flat(single-level) directory structure

   파일 시스템 내에 하나의 디렉토리만 존재하는 구조이다.(ex. MP3) 디렉토리가 한개이기 때문에 구현은 쉽지만 관리가 어렵다. 파일 이름이 동일하면 안된다. 그리고 디렉토리가 하나이기 때문에 특정 파일을 따로 관리 할 수가 없기 때문에 보호 문제가 발생한다. 그리고 다중 사용자 환경에서 문제가 더 심각해 진다.

   

2. 2-level directory structure

   이전 Flat directory 구조는 다중 사용자 환경에서 파일 이름 중복 등 문제가 많이 발생하였다. 그래서 사용자 별로 별도의 디렉토리를 갖는 2-level 구조를 만들었다. 2-level 구조에는 2가지 디렉토리가 있다. 모든 디렉토리의 상위 디렉토리인 마스터 파일 디렉토리(Master File Directory)와 각 유저마다 할당 받는 유저 파일 디렉토리(User File Directory)가 있다. 하지만 이런 2단계 구조도 한계점이 있다. 우선 하위 디렉토리를 만들 수 없어 파일 이름 문제는 여전하다. 그리고 사용자간 파일 공유가 불가능하다.

   

3. Hierarchical(tree-structure) directory structure

   앞의 두 디렉토리 구조들은 계층이 없는 구조였다. 계층 구조를 가지면서 관리가 더욱 수월하다. 그리고 사용자가 하부 디렉토리를 생성할 수 있어 파일 이름 문제에서 자유로워진다. 하지만 디렉토리를 관리하기 위한 시스템 콜들이 제공되어야 한다. 오늘날 대부분의 OS들이 해당 디렉토리 구조를 사용한다.

   

4. Acyclic graph directory structure

   앞서 보았던 계층형 구조를 변형시킨 것이다. 디렉토리 안에 공유 디렉토리, 파일을 담을 수 있다. 이를 위해 Symbolic link를 이용한다. 마치 컴퓨터의 바로가기와 같다. 다만 현 구조는 루프가 생기는 것을 허용하지 않는다.

   

5. General graph directory structure

   General graph 구조는 위의 Acyclic graph 구조에서 원형 링크를 허용한 구조이다. 원형 링크가 존재할 경우 탐색시 무한루프에 빠질 수 있는 문제가 있다.

   

파일 보호

다중 사용자 시스템에서는 사용자마다 파일 접근 권한이 달라야 한다. 아무나 파일을 열고 읽고 실행시키면 보안 뿐만 아니라 시스템 관리가 되지 않는다. R(읽기)W(쓰기)X(실행)A(추가)에 대한 권리를 운영체제가 관리해야한다. 파일 보호를 위한 방법은 크게 두가지가 있다. 첫번째로 각 파일마다 비밀번호를 부여하는 것이다. 하지만 이 방법은 파일마다 비밀번호를 외울 수 없으며 접근권한 별로 다른 비밀번호를 부여해야 하기 때문에 현재 운영체제에 맞지 않다.

두번째로 Access Matrix 기법이 있다. 사용자와 파일 사이의 접근권한을 표시한 표를 만드는 것이다. Access Matrix의 예시는 아래와 같다.

위의 표를 보면 domain 과 object라는 용어가 나온다. 도메인이란 접근 권한의 집합으로 같은 권한을 가지는 그룹을 의미한다. 예를들어 사용자, 프로세스가 이에 해당된다. 그리고 오브젝트는 접근 대상으로 파일, device 등 도메인이 접근할 수 있는 대상이다. 마지막으로 Access right는 오브젝트 이름과 권리들의 집합을 튜플 형식으로 나타낸 것이다. 이러한 Access Matrix 를 구현하는 방법은 크게 4가지가 있다. 각각의 구현 방식은 특징이 서로 다르다. 나의 사용환경에 맞는 구현 방법을 선택하여 사용하는 것이 바람직하다.

1. Global Table

   시스템 전체 파일들에 대한 권한을 테이블로 유지하는 것이다. 따라서 구현하는 것이 매우 간단하다. 한 파일마다 모든 도메인의 권한을 저장해야 하며 권한이 없는 도메인들에 대해서도 내용을 저장해 주어야 하기 때문에 테이블 사이즈가 너무 크다.

   

2. Access list

   

   위 그림과 같이 Access Matrix의 열을 리스트로 표현한 것이다. 각 오브젝트에 대한 권한을 나열한다. 오브젝트를 만들 때 각 도메인에 대한 권한을 부여한다. 따라서 오브젝트 별 권한 관리가 용이하다. 오브젝트 접근 시 권한을 검사한다. 이는 오브젝트에 접근 할 때마다 검사를 해야한다는 뜻이다. 실제 Unix에서 사용하는 방식이다.

3. Capability list

   

   Capability list는 Access Matrix의 행을 리스트로 표현한 것이다. capability를 가짐이 권한을 가짐을 의미한다. 이와 같은 특징 때문에 list에 포함된 오브젝트들에 대한 접근이 유리하다.

   프로세스가 권한을 제시하면 운영체제가 검증을 승인하는 구조이다. 따라서 capbility list는 일반 데이터와 다르게 운영체제가 직접 관리해야한다. 따라서 capability list는 커널 영역에 저장되어 있다. 커널 영역 안에 도메인 별 리스트를 전부 저장해야하며 이는 커널의 Overhead로 작용한다. 또한 한 오브젝트의 권한이 변경되면 모든 리스트를 순회하며 해당 오브젝트에 대한 권한을 수정해주어야 한다.

   Access list와 capability list를 혼합시킨 것이 Lock key mechanism이다.

4. Lock key mechanism

   오브젝트는 락을, 도메인은 키를 갖는다. 도메인 내의 프로세스가 오브젝트에 접근 할 때, 자신의 키와 오브젝트의 락이 맞아 떨어져야 한다. 많은 OS가 Access list 와 Capability list 개념을 함께 사용한다. 오브젝트에 대해 처음 접근할 때 access list를 탐색하여 권한이 있는 도메인 인지 확인한다. 만약 권한이 있다면 프로세스에 capability를 생성하여 전달한다. 이 경우 다시 접근 시 access 리스트를 탐색하지 않아도 된다. 모든 작업이 끝나면 capability를 삭제한다. 이는 회사에 방문했을 때 출입증을 받는것과 유사하다.

   

할당 정책

파일을 저장하면 디스크의 빈 공간을 할당해 주어야 한다. 컴퓨터는 사람이 아니기 때문에 일정한 규칙(정책)을 정해주어야 한다. 할당 정책에 따라 디스크의 공간 활용도나 디스크 내의 블럭에 접근하는 속도가 다를 것이다. 할당 정책은 크게 3가지가 있다.

1. Continuous allocation

   한 파일을 디스크의 연속된 블럭에 저장한다. 파일의 데이터가 디스크의 가까운 영역에 있으므로 접근이 쉽다. 하지만 새로운 파일을 저장하기 위한 공간을 확보하는 것이 쉽지않다. 그리고 외부 단편화의 문제가 발생한다. 아래 그림에서 만약 7개블럭이 필요한 파일을 저장하려 한다면 연속할당 정책으로는 저장 할 수 없다. 전체 가용 블럭은 15개 이지만 저장할 수 없는 상황이 발생 한다. 또한 파일 크기가 커지는 경우 빈 블럭을 미리 할당해 주어야 한다. 이는 곧 공간 낭비이다.

   하지만 접근이 쉬우므로 적은 작업으로 많은 데이터를 전달 할 수 있다. 연속 할당은 swapping과 같은 Realtime 용으로 사용된다.

   

2. Linked allocation

   위의 연속 할당과 달리 파일이 저장된 블럭들을 링크드 리스트로 연결한 형태이다. 디렉토리에는 각 파일의 시작 블럭 포인터가 기입되어 있으며 각 블럭에는 다음 블럭의 포인터가 저장된다. 구현이 간단하며 위에서 설명한 연속할당과 달리 외부 단편화가 발생하지 않는다.

   하지만 원하는 블럭에 접근하려면 시작 블럭부터 순차적으로 접근해야한다. 그리고 블럭안에 포인터를 저장해야 하므로 추가 공간이 필요해 공간이 낭비된다. 또한 crash나 사용자가 실수로 포인터를 건들면 뒤의 블럭에는 접근할 수 없는 문제가 발생한다. 아래는 Linked allocation의 모식도이다.

   

   linked 할당 정책에서 문제가 되는 것은 블럭 내에 포인터를 저장해야 한다는 것이었다. 이를 해결하기 위해 블럭 시작부분에 포인터가 아닌 다음 블럭의 번호를 기입하는 방법을 적용하였다. 이를 FAT(File Allocation Table)라 부르면 MS-DOS와 윈도우 운영체제에서 사용된다.

   

3. Indexed allocation

   Indexed allocation은 파일이 저장된 블럭의 포인터를 Index 블럭에 모아둔다. 임의의 블럭에 접근하고자 한다면 인덱스 블럭에서 해당 블럭의 포인터를 조회하면 된다. 따라서 직접 접근에 효율적이다. 하지만 파일의 블럭들을 순차적으로 접근하고자 한다면 인덱스 블럭을 계속 접근해야 하기 때문에 비효율 적이다.

   또한 파일마다 인덱스 블럭이 있어야 하기 때문에 공간 낭비가 발생하며 인덱스 블럭의 크기에 따라 파일 크기의 제한이 생긴다. 이를 해결하기 위해 블럭 맨 마지막에 다음 인덱스 블럭 주소를 입력하거나 pml4 처럼 다단계 인덱스 블럭 구조를 만든다.

   

비할당 영역 관리

위에서는 비할당 영역을 할당하기 위한 정책들을 살펴보았다. 그렇다면 비할당 영역들은 어떻게 관리할까? 비할당 영역을 관리에는 4가지 방법이 사용된다.

1. Bit Vector

   시스템 내 모든 블럭들에 대한 사용여부를 비트맵을 통해 표시한다. 구현이 쉽고 관리가 간단하다. 하지만 비트 벡터 전체를 메모리에 보관해야 하기 때문에 대형 시스템에는 부적합하다.

   

2. Linked list

   익숙한 링크드 리스트이다. 빈 블럭을 링크드 리스트로 연결하는 것이다. 구현은 쉽지만 접근하는 것이 비효율적이다.

   

3. Grouping

   그룹핑은 위의 링크드 리스트를 개선한 방식이다. n개의 빈 블럭을 그룹으로 묶고 그룹 단위로 링크드 리스트를 연결한다. 이 경우 연속된 빈 블럭을 쉽게 찾을 수 있다.

   

4. Counting

Directory 구현

Page Cache & Buffer Cache

프로그램 실행

open 시스템 콜