파일 시스템 구현 (File System Implementation)

1. 파일 시스템 구현 (File System Implementation)

(1) 디스크 상의 파일 시스템 구조

• 부트 제어 블록 (Boot control block)
  • 시스템이 운영체제를 그 파티션으로부터 부트 시키는데 필요한 정보를 저장
• 볼륨 제어 블록 (Volume control block)
  • 볼륨(또는 파티션)의 블록 수, 블록의 크기, 가용 블록의 수와 포인터, 그리고 가용 FCB 수와 포인터와 같은 파티션 정보를 저장
• 디렉터리 구조는 파일을 조직화하는데 사용
• 파일별 FCB는 자세한 파일 정보를 저장

(2) File Control Block , FCB

• 응용 프로그램은 논리 파일 시스템을 통해 새로운 파일을 생성
  • 새로운 FCB를 할당하고, 해당 디렉터리를 메모리로 읽어, 새로운 파일 이름과 FCB로 디렉터리를 갱신하여, 디스크에 다시 쓴다.
• Linux에서 Inode의 역할

 

2. 할당 방법 (Allocation Method)

(1) 연속 할당 (Contiguous allocation)

• 각 파일이 저장장치 내에서 연속적인 공간을 차지한다.
• 외부 단편화(External Fragmentation) 문제 발생

(2) 연결 할당 (Linked Allocation)

• 파일은 저장장치 블록의 연결 리스트 형태로 저장되고, 이 블록들은 장치 내에 흩어져 저장될 수 있다.
• 디렉터리는 파일의 첫번째와 마지막 블록에 대한 포인터를 가지고 있다.
• 외부 단편화 문제 해결

(3) Linked Allocation의 변형 - FAT

• FAT (File Allocation Table)
  • 디스크 블록마다 한 개의 항목을 가지고 다음 디스크 블록을 가리킨다.
  • 디렉터리 항목은 파일의 첫 번째 블록 번호를 가리킨다.
  • 임의 접근 시간을 개선할 수 있다. 

• disk의 217 주소 읽기 + FAT의 618 주소 읽기

(4) 색인 할당 (Indexed Allocation)

• 모든 포인터들을 하나의 장소, 즉 색인 블록으로 관리한다.
• 직접 접근할 수 있다.

 

3. 가용 공간의 관리 (Free-Space Management)

(1) 비트 벡터 (Bit Vector)

• 비트맵 또는 비트 벡터로서 구현된다.
• 각 블록은 1비트로 표현된다.
• 만약 블록이 비어 있으면 비트는 1이 되고, 만약 블록이 할당되어 있다면 비트는 0이 된다.
• 비트맵이 차지하는 크기
  • Example
    • block size = 4KB  = 2^12 bytes
    • disk size = 2^40 bytes (1 tereabyte)
    • n = 2^(40-12) = 2 ^ 28 bits = 2 ^ 25 bytes = 32MB

(2) 연결 리스트 (Linked List)

• 모든 가용 블록들을 함께 연결
• 첫 번째 가용 블록은 다음 가용 블록을 가리키는 포인터를 가진다.
• 공간의 낭비가 없다.