파일 시스템 구현, Implementing File-Systems

파일 시스템 구조, File-System Structure

• 파일시스템은 쉽게 데이터를 저장하고, 찾고 인출할 수 있게 함으로써 저장장치를 더욱 효율적이고 편리하게 사용
• 고려해야 할 것
  • 사용자에게 어떻게 보여야 할지
  • 파일은 무엇인지, 그 속성
  • 디렉터리 구조
  • 파일에 허용되는 연산
• 각 층은 낮은 층의 기능을 사용하여 새로운 기능을 만들어 상위층에게 제공한다.
• 입/출력 제어 층은 장치 드라이버 루틴들과 인터럽트 핸들러로 이루어져 있어서 메모리와 디스크 시스템 간의 정보 전송을 담당한다.
• 기본 파일 시스템 층은 적절한 장치 드라이버에게 저장장치상의 블록을 읽고 쓰도록 일반적인 명령을 내리는 층이다.
• 파일-구성 모듈 층은 파일과 상응하는 논리 블록을 알고 있다.
• 논리 파일 시스템 층은 메타데이터 정보를 관리한다.
  • 파일 내용 자체인 데이터를 제외한 모든 파일 시스템 구조를 말한다.
  • 파일 이름을 심볼릭하게 줄 경우 처리하여 하위층인 파일 구성 모듈에 필요한 정보를 넘겨주기 위해 디렉터리 구조를 관리한다.
  • 파일 구조는 파일 제어 블록을 통해 유지된다.
• 파일 제어 블록(file control block, FCB) 는 소유, 허가 그리고 파일 내용의 위치를 포함하여 파일에 관한 정보를 가지고있다.
  • inode로 구현된다.

 

파일 시스템 구현, Implementing File-Systems

• 부트 제어 블록은 시스템이 그 파티션으로부터 운영체제를 부트시키는 데 필요한 정보를 가지고 있다.
  • 일반적으로 첫 번째 블록이다.
  • 부트 블록 또는 파티션 부트 섹터라 불린다.
• 볼륨 제어 블록은 볼륨의 블록의 수, 블록의 크기, 가용 블록의 수와 포인터, 가용 FCB 수와 포인터 같은 볼륨 정보를 포함한다.
  • 슈퍼블록, 마스터 파일 테이블 이라 불린다.
• 디렉터리 구조는 파일을 조직화하는 데 사용된다.
  • UFS에서는 디렉터리 구조에 파일 이름 및 해당 inode 번호가 저장된다.
  • NTFS에서는 마스터 파일 테이블에 이러한 정보가 저장된다.

• open을 통해 파일을 열면, 다른 프로세스에 의해 사용 중인지 확인하기 위해 범 시스템 오픈 파일 테이블을 검색한다.
• 사용 중이면, 기존 범 시스템 오픈 파일 테이블을 가리키는 프로세스별 오픈 파일 테이블 항목이 생성된다.
• 만일 파일이 오픈되지 않았다면, 주어진 파일 이름을 디렉터리 구조에서 찾는다.

• 파일이 발견되면 FCB가 메모리내의 범 시스템 오픈 파일 테이블에 복사된다.
  • 이 테이블은 FCB를 저장할 뿐만 아니라, 파일을 오픈한 프로세스의 수도 저장한다.
• 범 시스템 오픈 파일 테이블의 항목에 대한 포인터와 몇 개의 다른 필드를 갖는 새로운 항목이 프로세스별 오픈 파일 테이블 안에 만들어진다.
• 이 필드들은 파일 안의 현재 위치를 가리키는 포인터와 파일이 오픈된 접근 모드 등을 포함한다.
• open은 프로세스별 파일 시스템 테이블 내의 파일에 대한 포인터를 찾아 돌려준다.
• 같은 파일에 대한 다중 오픈 연산을 빠르게 하기 위하여 파일에 대한 포인터를 캐싱한다.
• 이것을 파일 디스크립터 또는 파일 핸들이라고 부른다.

 

디렉터리 구현, Directory Implementation

• 선형 리스트
  • 프로그래밍은 쉽지만, 선형탐색을 해야하므로 실행 시간이 길다.
• 해시 테이블
  • 파일 이름을 제시하면 해시로부터 값을 얻어 그것을 포인터로 활용하여 직접 접근할 수 있다.
  • 성능이 크게 개선된다.
  • 단점은 고정된 크기를 갖는다는 점과 해시 테이블의 크기에 따라 해시 기능도 제한을 받는다는 점이다.

 

할당 방법, Allocation Methods

• 어떻게 저장장치 공간에 배치해야 디스크 공간을 효율적으로 사용하고, 파일에 빨리 접근할 수 있는가.
• 연속 할당
  • 연속적인 공간에 차지하도록 한다.
  • 탐색 횟수를 최소화하며 시간 또한 최소화 된다.
  • 구현하기 쉽지만 한계로 최신 파일 시스템에서는 사용되지 앟는다.
  • 새로운 파일을 위한 가용 공간을 찾으며 외부 단편화 문제의 어려움이 발생한다.
• 연결 할당
  • 연결 리스트 형태로 저장한다.
  • 장치 내에 흩어져 저장될 수 있다.
  • 각 블록이 다음 블록을 가리키는 포인터를 포함한다.
  • 외부 단편화가 없다.
  • 파일은 계속해서 얼마든지 커질 수 있다.
  • 직접 접근 방식에는 매우 비효율적이다.
  • 포인터들을 위한 공간이 추가로 필요하다.
    • 해결책은 블록을 모아 클러스터라고 하는 단위로 만들고 블록이 아닌 클러스터를 할당하는 것이다.
  • 파일 할당 테이블 (FAT, MS-DOS에서만 사용된다.) 
    • 각 파티션의 시작 부분이 FAT로 사용된다.
    • FAT 테이블은 각 블록마다 한 개의 항목을 가지고 있고 이 항목은 디스크 블록 번호를 인덱스로 찾는다.
    • 디렉터리 항목은 각 파일의 첫 번째 블록 번호를 가리킨다.
    • 그 블록 번호를 가지고 FAT 테이블로 가면 그 항목은 다음 블록의 블록 번호를 가리킨다.
    • 마지막 블록은 파일의 끝을 나타내는 특수한 값을 가지고 있다.
  • 색인 할당
    • 색인 할당은 모든 포인터들을 하나의 장소, 색인 블록으로 관리함으로써 외부 단편화 문제와 파일 크기 선언 문제를 해결한다.
    • 블록이 처음 쓰이면 가용 블록 관리자로부터 한 블록을 받아 그 주소를 인덱스 블록의 i 번째 항에 기록한다.
    • 연결 기법 : 블록의 크기가 크면 여러 개의 색인 블록으로 연결한다.
    • 다중 수준 색인 : 여러 개의 두 번째 수준 색인 블록(실제 파일)들의 집합을 가리키기 위하여 첫 번째 수준의 색인 블록을 사용한다.
    • 결합 기법 : inode에 색인 포인터 15개를 유지하여 12개에는 직접 블록을 저장한다. 작은 파일의 경우 추가 색인 블록이 필요 없다. 나머지 3개는 간접 블록을 가리키는 포인터이다. 첫 번째는 단일 간접 블록(데이터를 저장하고 있는 주소를 저장) 두 번째는 이중 간접 블록 (실제 데이터 블록을 가리키는 포인터를 저장하는 블록) 마지막은 삼중 간접 블록의 주소를 저장한다.

 

가용 공간의 관리, Free-Space Management

• 시스템은 가용 공간을 리스트로 유지하고 관리한다.
• 새로운 파일을 만들려면 가용 공간 리스트를 탐색하여 할당 받는다.
• 가용 공간 리스트는 비트 벡터 혹은 비트맵 으로 구현된다.
  • 블록이 비어있다면 1, 할당되어 있다면 0이다.
• 연결 리스트
  • 모든 가용 블록들을 함께 연결한다.
• 그룹핑
  • 첫 번째 가용 블록 내에 n개의 블록 주소를 저장하는 방법이다.
• 계수
  • 연속된 가용 블록의 첫 번째 블록의 주소와 연속된 블록의 개수만 유지한다.