운영체제 강의노트 정리 - 파일 시스템 구현
파일 시스템 구현
파일 시스템 구조
디스크는 다시 쓰기 가능하고, 직접 접근을 제공한다.
디스크 입출력은 보통 블록 단위로 이루어진다.
논리적 파일 시스템을 물리적 보조 저장 장치에 어떻게 저장할 것인지가 문제가 된다.
파일 시스템은 여러 단계로 구성되어 있다.
- 장치 드라이버와 인터럽트 처리기 : 고수준 명령어를 하드웨어 컨트롤러가 이해할 수 있는 명령어로 바꾸어 전달한다.
- 기본 파일 시스템 : 일반 명령을 장치 드라이버에 전달한다. 일반 명령에는 블록 읽기와 블록 쓰기가 있다.
- 파일 조직 모듈 : 파일의 내용을 제외한 메타데이터를 관리한다.
대부분의 운영체제는 하나 이상의 파일 시스템을 지원한다.
파일 시스템 구현
개요
운영체제는 파일 시스템을 구현하기 위해 디스크와 메모리에 여러 정보를 유지한다.
다음은 디스크에 유지되는 정보다.
- 부트 제어 블록boot control block : 파티션으로부터 운영체제를 부팅하기 위한 정보를 유지한다. 파티션의 첫 번째 블록에 위치한다.
- 파티션 제어 블록partition control block : 파티션 크기(블록 수), 블록 크기, 빈 블록 수 등 파티션의 정보를 관리한다.
- 디렉토리 구조
- FCB : 보통 파티션 제어 블록과 별도로 저장된다.
유닉스 파일 시스템에서, FCB는 i-node와 같다.
다음은 주기억 장치에 유지되는 정보다.
- 파티션 테이블 : 마운트된 각 파티션에 대한 정보를 유지
- 최근에 접근된 디렉토리 구조 : 디렉토리에 대한 소프트웨어 캐시
- 시스템 전체 연 파일 테이블SWOFT : System-Wide Open-File Table : 연 파일의 FCB의 복사본 유지
- 프로세스 별 연 파일 테이블PPOFT : Per Process Open-File Table : 시스템 전체 연 파일 테이블의 항을 가리키는 포인터 유지
다음은 파일 생성과 관련된 내용이다.
- 새로운 FCB를 할당하고 해당 디렉토리를 주기억 장치로부터 읽어 갱신한 다음 이 디렉토리를 디스크에 쓰는 것으로 파일이 생성된다.
- 유닉스는 디렉토리와 파일을 동일하게 취급하고, 윈도우즈는 별도의 시스템 호출을 사용한다.
다음은 파일 열기와 관련된 내용이다.
- 파일 이름을 이용하여 디렉토리를 검사, 파일에 해당하는 항을 찾아 그 파일의 FCB를 SWOFT에 복사하며, 이후 PPOFT에 새로운 항을 추가한다.
- SWOFT는 각 파일마다 그것을 연 프로세스의 수를 나타내는 열기 계수open count를 관리한다.
- PPOFT는 SWOFT가 관리하고 있는 FCB에 대한 포인터와 파일 포인트 등을 관리한다.
- 열기 시스템 호출은 PPOFT에 새롭게 추가한 항에 대한 포인터를 반환해 주며, 이후의 파일 조작은 이 포인터를 이용하여 이루어진다.
- PPOFT의 항을 유닉스에서는 파일 설명자file descriptor라고 하며, 윈도우즈에서는 파일 핸들file handle이라고 한다.
다음은 파일 닫기와 관련된 내용이다.
- PPOFT의 해당 항을 삭제한다.
- SWOFT의 열기 계수를 하나 감소시킨다.
- 파일을 연 모든 프로세스가 파일을 닫으면, 갱신된 파일 정보를 디스크에 쓰고 SWOFT의 항을 제거한다.
파티션과 마운팅
각 파티션은 파일 시스템을 포함할 수cooked도 있고, 포함하지 않을 수raw도 있다.
원시 디스크raw disk를 그대로 사용하는 경우도 있다. 예를 들어 유닉스의 스왑 공간을 제공하거나, 어떠한 데이터베이스의 자체적인 형식을 사용하기 위해 이러한 방식을 취할 수 있다.
부트 정보를 별도 파티션에 저장하는 경우도 있다.
보통 부팅할 때는 파일 시스템 장치 드라이버가 실행되기 전이므로 자체 형식을 사용한다.
다중 부팅을 하기려면 부트 파티션에 여러 파일 시스템을 이해하는 부트 적재기boot loader가 있어야 한다.
운영체제 커널을 포함하는 루트 파티션은 시스템이 부팅될 때 자동으로 마운트된다. 다른 파티션은 부팅 때 자동으로 마운트되거나 나중에 수동으로 마운트된다.
운영체제는 주기억 장치에 마운트 테이블을 유지한다.
디렉토리 구현
선형 리스트
파일 이름과 데이터 블록에 대한 포인터로 구성된 선형 리스트를 유지할 수 있다.
파일의 검색이나 생성시 선형 검색을 통해 파일을 찾거나 중복 파일을 찾아야 한다는 문제가 있다.
선형 리스트의 단점을 극복하기 위해 사용된 항은 소프트웨어적으로 캐시된다.
디렉토리의 항을 재사용하기 위해 삭제돈 항은 빈 상태로 유지될 수 있으며, 탐색 비용을 줄이기 위해 마지막 항을 빈 항에 옮길 수 있다.
정렬된 리스트를 유지하면 이진 탐색을 할 수 있지만, 정렬을 유지하는 추가 비용이 소요된다.
해시 테이블
검색 시간이 빠르고, 삽입 및 삭제도 용이하다. 해시 충돌 문제를 해결해야 한다.
할당 방법
연속 할당
각 파일을 연속된 공간에 할당한다.
빈 공간을 찾기 위해 홀들을 유지해야 하고, 주기억 장치 관리와 마찬가지로 최초 적합 / 최적 적합 / 최악 적합 방법으로 모두 사용할 수 있다.
외부 단편화 문제가 발생할 수 있다.
파일을 생성할 때, 그 크기를 알 수 없는 경우가 많다.
- 예측을 통해 최적 적합 방식을 사용하면 공간이 부족해질 수 있다. 공간이 부족해질 때 더 큰 공간으로 이동하면 되지만 시간이 많이 소모된다.
- 복사된 파일의 경우에도 시간이 지남에 따라 그 크기가 변화할 수 있으며, 이를 대비해 실제 크기보다 많은 공간을 미리 확보해주면 내부 단편화 문제가 발생하게 된다.
- 몇 공간을 연결 리스트 형태로 유지하여 공간을 할당하는 것으로 위의 문제를 극복할 수 있다.
파일 접근 시간이 빠르고, 직접 접근과 순차 탐색을 모두 지원한다.
디렉토리의 항은 시작 위치와 크기만 유지하면 된다.
연결 할당
파일을 디스크 블록의 연결 리스트 형태로 할당하며, 디렉토리 항에는 첫 번째 블록과 마지막 블록에 대한 포인터만 유지한다.
각 블록은 다음 블록을 가리키는 포인터를 유지한다.
외부 단편화가 발생하지 않으며, 내부 단편화는 발생할 수 있으나 무시할 수 있다.
파일의 생성 및 삭제가 쉽다.
파일의 크기 변화에 쉽게 대처할 수 있다.
파일에 대한 순차 탐색만 지원한다. 직접 접근은 연결 리스트를 따라 찾아가는 방법밖에 없다.
많은 공간이 포인터 값을 저장하기 위해 낭비된다. 이를 극복하기 위해 블록을 묶어 클러스터 단위로 사용할 수 있다.
포인터 값이 하나만 손상되어도 파일 자체가 손상되므로 신뢰성이 떨어진다. 이중 연결 리스트를 사용하여 극복할 수 있으나 포인터를 저장하기 위한 오버헤드가 더 커진다.
FAT은 MS-DOS에서 사용한 연결 할당 방뻐이다.
색인 할당
디스크의 한 블록에 파일의 나머지 블록에 대한 포인터를 유지하는 방법이다.
연결 할당 방법의 장점을 모두 가지고 있으며, 추가로 빠른 직접 접근을 지원한다.
색인 블록 유지를 위한 공간 오버헤드가 존재한다.
다음과 같은 방식을 취하여 구현할 수 있다.
- 연결 방식 : 처음에는 디스크의 한 블록만 색인 블록으로 할당하고, 이 이상 필요하면 연결 리스트 형태로 색인 블록을 유지한다.
- 다단계 색인 방식 : 다단계의 색인 블록을 유지한다.
- 결합 방식 : 색인 블록의 15개 정도의 포인터를 i-node에 유지하며, 대부분 항은 직접 색인을 유지하고, 나머지는 다단계 색인 방식을 사용한다.
성능
디스크 공간 할당 방법의 성능은 저장 공간 효율과 접근 속도의 측면에서 고려된다.
연속 할당의 경우 접근 속도 측면에서 가장 우수한, 파일의 변화에 대처하기 어렵고 디스크 공간 할당이 어렵다.
여러 방법을 함께 사용하여 성능을 최대화한다.
빈 공간 관리
비트 벡터
Bit Vector.
각 블록마다 1비트를 사용하여 블록의 할당 여부를 나타낸다. 1이면 블록이 빈 상태이고, 0이면 블록이 할당되어 있음을 나타낸다.
첫 번째 빈 블록을 찾기가 단순하며 효율적이다.
비트 벡터를 모두 주기억 장치에 유지할 경우에만 효율적으로 사용할 수 있다.
연결 리스트
빈 블록을 연결 리스트 형태로 유지하고, 첫 빈 블록에 대한 포인터를 운영체제가 주기억 장치에 유지한다.
목록 순회가 효율적이지 못하며, 주어진 크기의 빈 공간을 찾기 어렵다.
항상 첫 번째 빈 블록을 할당에 사용하는 FAT와 같은 할당 방식에서만 사용할 수 있다.
그룹핑
n개의 빈 블록 주소를 첫 빈 블록에 저장하고, n개 중 마지막 주소는 그 다음 n-1개의 빈 블록 주소를 포함하고 있는 블록을 가리키도록 하는 방식이다.
카운팅
빈 공간을 연결 리스트로 관리한다.
빈 공간마다 첫 번째 블록 주소와 총 블록 수를 유지한다.
연속 할당에서 사용할 수 있다.