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

파일 시스템 구현

사용자(user) 관점의 파일 시스템

• 파일 시스템 인터페이스
• 파일 시스템을 사용자에게 보여주는 방법은 무엇인가?
• 파일, 디렉토리, 속성(attribute), 작업(operation)
• 트리 구조

스토리지 관리(storage management) 관점의 파일 시스템

• 파일 시스템 구현
• 논리 파일 시스템을 저장장치에 매핑하는 방법은 무엇인가?
• 레이아웃, 데이터 구조, 알고리즘
• 스토리지 내부를 이해해야 한다.

파일 시스템은 저장 장치를 일련의 블록(sequence of blocks)으로 간주

• 데이터는 디스크와 메모리 간에 블록 단위로 전송
• 각 블록에는 일반적으로 512바이트인 섹터가 하나 이상 존재

파일 시스템 구현

• 각 파일에 대해 속성 및 파일 데이터를 모두 저장
• 속성 - 크기, 권한, 소유자, 시간 등

• 속성과 파일 데이터에 저장장치를 할당하는 방법?

유닉스 파일 시스템

• 아이노드
  
  • 파일 데이터 속성 + 인덱스
• 아이노드 영역과 파일 데이터 영역이 분리

• 아이노드의 크기는 같지만 파일 데이터의 크기는 다르다.
  
  • i-number를 통해 아이노드에 액세스
• 파일 데이터에 스토리지를 할당하는 방법?
  
  • 연속(contiguous) / 연결(linked) / 인덱스 할당(indexed allocation)

---

연속 할당(Contiguous Allocation)

각 파일은 디스크의 연속 블록 집합을 차지

• 시작 위치와 길이만 필요

• 파일에 순차적으로/임의로 액세스하는 것은 간단함
• 새 파일을 위한 공간을 찾는 것은 어려움

---

연결된 할당(Linked Allocation)

각 파일은 디스크 블록의 연결된 리스트

• 예: MS-DOS 파일 시스템(FAT 파일 시스템)
• 블록은 디스크 어디에나 흩어져 있을 수 있다. → 공간 낭비 없음
• 순차적 접근에만 적용
• 포인터가 손실되거나 손상된 경우?

MS-DOS의 FAT 파일 시스템

---

인덱스 할당(Indexed Allocation)

모든 포인터를 인덱스 블록으로 가져온다.

• 임의 접근 가능
• 연속된 블록을 찾을 필요가 없다.
• 파일당 하나의 인덱스 블록이 필요
• 인덱스 블록의 크기가 큰 파일에 대한 포인터를 보관하기에 여전히 작은 경우?

다중 레벨 인덱스(Multilevel index)(예: UNIX 파일 시스템)

• 15개의 포인터 필드가 유닉스 파일 시스템의 아이노드에 있다.
  
  • 직접 블록용 포인터 필드 12개
  • 간접 블록에 대한 포인터 필드 3개
  • 싱글, 더블, 트리플

---

빈 공간 관리(Free Space Management)

비트맵(=비트 벡터)

• 블록[i]가 할당된 경우 : 비트 = 1, 할당되지 않은 경우 : 비트 = 0

• 연속된 빈 블록을 쉽게 얻을 수 있다.
• 비트맵에는 추가 공간이 필요
  
  • 예: 블록 크기 = 212바이트(= 4KB)
  • 디스크 크기 = 240바이트(= 1TB)
  • n = 240/4000 = 228비트(= 32MB)

링크 리스트(Linked list)

• 오버헤드 공간이 없다.
• 사용 가능한 연속 블록을 쉽게 얻을 수 없다.

그룹화

• 링크된 목록 접근 방식의 수정
• 첫 번째 n-1 빈 블록은 실제로 비어있다.
• 마지막 블록에는 다른 n개의 빈 블록의 주소가 포함

---

디렉터리 구현

선형 리스트

• (파일 이름, 파일 포인터)
• 구현이 간단
• 파일을 검색에 시간이 많이 걸린다.
• B-트리를 사용할 수 있다.

해시 테이블

• 해시 데이터 구조를 가진 선형 리스트
• 해시 함수는 "파일 이름"을 "파일의 선형 리스트에 대한 포인터"로 변환
• 디렉토리 검색 시간을 줄인다.
• 충돌은 해결되어야 한다.

---

성능 및 복구

효율성(Efficiency)

• 파일의 데이터 블록을 해당 파일의 아이노드 블록 근처에 보관하여 검색 시간을 줄인다.
• 아이노드의 "마지막 접근 시간" 정보에는 블록 읽기 및 쓰기가 필요
• 데이터에 접근하는 데 사용되는 포인터의 크기? 16비트 또는 32비트

성능(Performance)

• 버퍼 캐시 : 자주 사용되는 블록에 대한 주 메모리의 별도 섹션
• 미리 읽기(read-ahead) : 순차 액세스를 최적화하는 기술

버퍼 캐시

• 파일에 액세스할 때마다 디스크에서 파일 데이터를 가져와야 한다.
• 그러나 디스크 접근으로 인해 I/O 오버헤드가 크게 발생
• 파일 접근 패턴에서 한 번 액세스한 데이터는 곧 다시 사용(시간적 지역성 temporal locality)
• 버퍼 캐시는 디스크 액세스를 줄이기 위해 곧 다시 사용될 블록을 유지

불일치가 발생 가능

• 파일 시스템의 일부는 속도 향상을 위해 메모리에 저장
• 시스템이 손상되면? 일부 데이터는 디스크에 저장할 수 없다.
• 디렉터리 또는 메타데이터(아이노드)가 손실된 경우?

일관성을 위한 솔루션

• 일관성 검사기(예: UNIX의 fsck)
• 디렉터리 구조의 데이터를 디스크의 데이터 블록과 비교하여 불일치를 해결
• 중요 메타데이터에 대한 동기식 쓰기(Synchronous write)
• 저널링(Journaling)

시스템 프로그램을 사용하여 데이터 백업

• 디스크에서 다른 저장 장치로
  백업에서 데이터를 복원하여 손실된 파일 또는 디스크 복구

---

요약

• 파일 시스템 : 저장 장치를 일련의 블록으로 간주
• 파일 시스템 구현 : 각 파일에 대해 속성 및 파일 데이터를 모두 저장해야 함
• 디스크의 파일 할당 방법 : 연속 할당(contiguous), 연결 할당(linked), 인덱스 할당(indexed)
• 파일 시스템 구현을 위해서도 사용 가능한 공간 관리 체계가 필요
• 버퍼 캐시 : 파일 시스템 성능을 향상시키기 위해 사용, 데이터 불일치가 발생 가능