[OS] File System

파일 시스템

파일 시스템이란 컴퓨터에서 파일이나 자료를 쉽게 발견 및 접근할 수 있도록 보관 또는 조직하는 체계이다.

그 중 VSFS (Very Simple File System)의 구현에 대해 알아본다.

 

Block

파일 하나가 필요로 하는 디스크의 최소 공간을 클러스터 또는 블록이라고 한다.

대개 블록 하나의 크기는 4KB이며 각 블록은 아래의 4가지로 분류된다.

 

• Super block
  - 파일 시스템의 전체 정보를 담는 블록으로 하나의 파일 시스템에 1개만 존재
  
  
• Allocation structure block
  - inode 및 데이터에 대한 두 개의 비트맵 (free 0, used 1)
  
  
• Key meta data block
  - inode struct의 테이블이 저장됨
  
  
• User data block
  - 실제 데이터들이 저장됨
  
  

---

Inode Struct

inode struct에는 파일에 대한 메타 데이터가 저장되며 각 파일마다 하나의 inode struct가 부여된다.

파일의 메타 데이터에는 파일의 크기, 모드, 권한, 소유자, 각종 시간 등이 저장되어 있다. unix의 ls 명령어로 출력되는 정보들  또는 stat 구조체에 담긴 정보들은 모두 inode struct에서 가져온 것이다.

 

파일의 크기가 블록 사이즈보다 큰 경우에는 여러 개의 블록을 사용해야하기 때문에 inode struct에는 블록들을 가리키는 여러 포인터 변수들이 존재하게 된다. 

 

inode struct의 포인터 변수들은 크게 직접 포인터 (direct pointer), 간접 포인터 (indirect pointer) 두 가지로 나눌 수 있는데, 직접 포인터는 데이터 블록을 직접 가리키는 포인터이고, 간접 포인터는 데이터 블록을 가리키는 포인터들이 저장된 블록을 가리키는 방법으로 단일 간접 포인터, 이중 간접 포인터, 삼중 간접 포인터로 나뉜다.

 

직접 포인터만 쓰는 경우 한 파일이 가질 수 있는 최대 크기에 제약이 크기 때문에 간접 포인터들을 같이 사용한다.

다음은 한 파일이 가질 수 있는 최대 크기를 계산하는 예제이다.

 

※ 12개의 직접 포인터, 1개의 간접 포인터, 1개의 이중 간접 포인터, 1개의 삼중 간접 포인터를 가지는 inode struct가 있고, 한 블록의 크기가 4KB일때, 이 시스템에서 가질 수 있는 파일의 최대 크기는? (포인터의 크기는 4byte)

• 12개의 직접 포인터 - 12 * 4KB = 48KB
• 1개의 간접 포인터 - 1 * 1024 * 4KB = 4MB
• 1개의 이중 간접 포인터 - 1 * 1024 * 1024 * 4KB = 4GB
• 1개의 삼중 간접 포인터 - 1 * 1024 * 1024 * 1024 * 4KB = 4TB
• = 48KB + 4MB + 4GB + 4TB

---

Directory

디렉토리는 특수한 형태를 가지는 파일의 한 종류로 하나의 inode struct와 데이터 블록들을 가진다. inode struct는 일반 파일의 inode struct와 동일한 구조이며 데이터 블록들은 디렉토리 하위 항목들에 대한 linked list를 가진다. linked list의 각 node는 inode number와 name을 구성 요소로 갖는다. 디렉토리마다 단순 선형 linked list를 운용하는 경우 깊은 계층 구조의 디렉토리에서 성능이 많이 하락하기 때문에 B-tree와 같은 자료구조를 사용해 성능을 향상시키기도 한다.

 

※ 빈 공간의 관리

파일 시스템은 새로운 파일이나 디렉토리를 할당할 공간을 찾기 위해 inode와 데이터 블록의 사용 여부를 관리해야한다. VSFS에서는 inode bitmap과 data bitmap을 사용하여 이를 관리한다.

---

디스크에서 파일 읽기

super block만이 메모리에 올라와 있고 다른 모든 것(inode, 디렉토리)들은 디스크에 존재하는 상황에서 /foo/bar를 열고, 읽고, 읽은 후에 닫는 상황의 예제이다.

open 과정

open("/foo/bar", O_RDONLY) 시스템 콜이 발생하면 파일 시스템은 먼저 파일 bar에 대한 inode를 찾아서 기본적인 정보를 획득해야 한다. 파일 경로를 따라가는 것은 항상 루트 디렉토리부터 탐색하므로 루트 디렉토리의 inode를 읽어야 한다. inode를 읽기 위해서는 i-number를 알아야한다. 일반적으로 어떤 파일의 i-number는 부모 디렉토리에서 찾을 수 있는데 루트 디렉토리는 부모 디렉토리가 존재하지 않는다. 따라서 루트 디렉토리의 i-number는 2번으로 정해져있다. 

 

파일시스템은 i-number 2번을 포함하는 블록을 읽어서 루트 디렉토리의 inode를 읽고, 루트 디렉토리의 데이터 블록들을 읽어 foo에 대한 항목을 찾고 i-number를 얻는다. 

 

파일시스템은 foo의 i-number를 포함하는 블록을 읽어서 foo의 inode를 읽고, foo의 데이터 블록들을 읽어 bar에 대한 항목을 찾고 i-number를 얻는다.

 

open 시스템 콜은 bar의 inode를 메모리로 읽어 들이고 최종적으로 해당 파일에 대한 접근 권한을 확인한 뒤 이 프로세스의 file table에서 파일 디스크립터를 할당받아 사용자에게 리턴한다.

 

read 과정

open 이후에는 read 시스템 콜을 통해 파일을 읽는다. bar의 inode에서 데이터 블록에 대한 포인터를 획득하고, 해당 블록에 접근하여 읽은 뒤 파일을 마지막으로 읽은 시간을 inode에 기록한다.

---

디스크에 파일 쓰기

읽기 예제에서와 같은 상황에서 /foo/bar를 생성하여 디스크에 쓰는 예제이다.

create 과정

위의 예제의 과정을 통해 foo의 데이터 블록까지 읽어 foo의 하위 항목들에 대한 linked list를 획득한다. 그리고 create를 위해 inode bitmap을 읽어 현재 사용 중인 i-number들을 확인한다. 미사용 중인 i-number를 선택하고 사용 중으로 변경한다. 

 

선택한 i-number와 "bar" 명칭을 foo의 데이터 블록의 linked list에 추가한다. 그리고 bar의 inode를 초기화하기 위해 read, write를 한 번씩하고 foo의 inode에 access time을 갱신한다.

 

write 과정

write 가능한 데이터 블록을 확인하기위해 bar의 inode를 읽고 data bitmap을 읽는다. 미사용 중인 데이터 블록 number를 선택하고 사용 중으로 변경한다. bar의 데이터 블록에 write 한 뒤 inode에 access time을 갱신한다.

---

FFS (Fast File System)

FFS는 기존의 Unix 파일 시스템에서 성능을 향상시킨 파일 시스템이다. 기존의 Unix 파일 시스템은 디스크 전체에 super block, inode bitmap, data bitmap이 오직 한 개씩만 존재했다. 또한 inode 역시 디스크의 한 영역에 몰려있어 실제 데이터 블록들과 물리적으로 멀리 떨어져 있어 비효율적인 문제점이 있었다. FFS는 이러한 문제점을 다음과 같이 해결했다.

 

 

• 디스크를 여러 그룹으로 나누고 그룹마다 super block, inode bitmap, data bitmap을 배치
  - inode와 데이터 블록 사이의 물리적 거리가 줄어들어 seek time이 감소
  
  
• 디렉토리와 그 하위 파일들을 디스크 내에서 같은 그룹안에 배치 (Name-based Locality)
  - 동일한 디렉토리에 있는 파일에 접근할 확률이 높다는 통계에 기반하여 seek time이 감소
  
  
• 디스크 레이아웃 최적화
  - 로테이션 속도가 상승하며 연속된 섹터를 읽어들이는 것이 어려워짐
  - 1칸씩 띄워서 섹터를 배치하여 해결
  
  
• 블록 크기를 줄여 내부 단편화 현상 감소시킴
  
  

---