[OS] 파일 시스템 구현

장선규·2023년 10월 31일
File SystemOSOSTEPpersistence영속성운영체제파일 시스템
0

[OS] OSTEP Study

목록 보기
28/28

파일 시스템 구현

이번 장에서는 Unix 파일 시스템을 단순화한 vsfs(Very Simple File System)라는 간단한 파일 시스템 구현에 대해 소개하겠다.

파일 시스템은 순수한 소프트웨어다. 이점이 이책의 앞부분에서 다룬 CPU 가상화, 메모리 가상화 부분과 다른점이다.
(여기서는 성능 개선을 위한 하드웨어를 추가하지 않을 것이다.)

핵심 질문: 어떻게 간단한 파일 시스템을 만들 것인가

  • 간단한 파일 시스템을 어떻게 만들 수 있을까?
  • 디스크 위에는 어떤 자료 구조가 필요할까?
  • 그러한 자료 구조는 어떤 정보를 추적해야 하는가?
  • 그 자료 구조들은 어떻게 접근되어야 하는가?

1. 생각하는 방법

파일 시스템에 대해 학습할 때, 두 가지 측면에서 접근할 것을 권장한다. 그 두 측면을 다 이해하게 되면 파일 시스템이 기본적으로 어떻게 동작하는지 이해하게 될 것이다.

  1. 자료 구조
    • 관점: 파일 시스템이 자신의 데이터와 메타데이터를 관리하기 위해 디스크 상에는 어떤 종류의 자료구조가 있어야 하겠는가?
    • 이번 장에서는 주로 배열과 같은 간단한 자료구조로 구성되어 있다.
      (SGI의 SFX와 같은 파일 시스템들은 좀 더 복잡한 트리 기반의 자료구조를 사용한다).
  2. 접근 방법(access method)
    • 관점
      • 프로세스가 호출하는 open(), read(), write() 등의 명령들은 파일 시스템의 자료 구조와 어떤 관련이 있는가?
      • 특정 시스템 콜을 실행할 때에 어떤 자료 구조들이 읽히는가?
      • 어떤 것들이 쓰일까?
      • 이 모든 과정이 얼마나 효율적으로 동작하는가?

2. 전체 구성

이제 vsfs 파일 시스템의 자료 구조에 대해 디스크 상의 전체적인 구성을 개발해 보자.

  1. 디스크를 블럭(block)들로 나누기
    • 간단한 파일 시스템은 단일 블럭 크기만 사용하기 때문에 여기서도 그렇게 할 것이다.
      • 블럭의 크기: 4KB (일반적으로 사용되는 크기)
      • N 개의 4KB 블럭의 크기를 갖는 파티션에서 블럭은 0부터 N−1 까지의 주소를 갖고 있다.
        (여기서는 블럭이 64개 있는 작은 디스크를 가정하자.)
  1. 디스크 블럭들에 대해서 메타데이터를 위한 영역과 사용자 데이터를 위한 영역으로 분리
    • 데이터 영역(data region): 사용자 데이터가 있는 디스크 공간
      (사실 파일 시스템의 대부분의 공간은 사용자 데이터로 이루어져 있다.)
    • 메타데이터(metadata): 각 파일(데이터)에 대한 정보
      • 여기서는 0~7번 주소에 저장
      • 파일 시스템은 이 정보를 보통 아이노드(inode) 라고 부르는 자료 구조에 저장한다.
  1. 아이노드들의 저장을 위한 디스크 공간 확보
    • 이 영역을 아이노드 테이블(inode table)이라 한다.
      • 아이노드 테이블에는 아이노드들이 배열형태로 저장된다.
      • 전체 64개의 블럭 중 5개의 블럭이 아이노드를 저장하기 위해 할당된 것으로 가정하자.
      • 아이노드의 크기는 256 byte로 가정 (일반적인 크기)
  1. 할당 구조(allocation structure) 추가
    • 할당 구조: 각 블럭이 현재 사용 중인지 아닌지를 표현하는 구조
      • 아이노드나 데이터 블럭의 사용 여부를 알려준다.
      • 블럭이 사용 중인지 아닌지를 나타내는 정보는 어느 파일 시스템이든 꼭 있어야 한다.
    • 할당구조 표현 방식
      • 프리 리스트(free list) 방식: 미사용 블럭들을 링크드 리스트 형태로 관리
        • 아이노드는 첫 번째 프리 블럭의 위치만 기억하면 된다.
        • 다음 프리 블럭의 위치는 각 프리 블럭에서 정해진 위치에 기록한다.
        • 이 예제에선 이 방식을 안 쓸 것이다.
      • 비트맵(bitmap) 방식
        • 데이터 비트맵(data bitmap): 데이터 영역에 있는 블럭들의 사용 여부 표현
        • 아이노드 비트맵(inode bitmap): 아이노드 테이블에 있는 아이노드들의 사용 여부 표현
      • i는 아이노드 비트맵, d는 데이터 비트맵을 의미
      • 0이면 미사용, 1이면 사용 중
  1. 슈퍼블럭(superblock) 추가
    • 슈퍼블럭(superblock): 이 파일 시스템 전체에 대한 정보를 담고 있는 블럭
      • 아이노드 80개, 데이터 블럭 56개, 아이노드 테이블 시작위치는 3번블럭 등...
    • 파일 시스템을 마운트할 때, 운영체제는 우선 슈퍼블럭을 읽어들여서 파일 시스템의 여러가지 요소들을 초기화한다.
    • 그 후에 각 파티션을 파일 시스템 트리에 붙히는 작업을 진행한다.

3. 파일 구성: 아이노드

파일 시스템의 디스크 자료 구조 중 가장 중요한 것은 아이노드(inode) 이다.

아이노드(inode)

  • 파일 크기, 접근권한 그리고 파일 블럭들의 위치 정보를 가지고 있다.
  • 인덱스 노드(index node)의 약어로서, 디스크 상의 아이노드의 배열의 인덱스로 아이노드 번호를 사용하던 것에서 기인한다.
  • 각 아이노드는 아이넘버(inumber)라는 숫자로 표현된다.
    (앞 장에서는 이것을 파일의 저수준 이름(low-level name) 이라고 불렀었다.)
    • vsfs(그리고 다른 간단한 파일 시스템)에서는 아이넘버를 사용하여 해당 아이노드가 디스크 상에 어디에 있는지를 직접적으로 계산할 수 있다.
      • 크기가 20KB이고 (4KB 블럭 5개) 80개의 아이노드로 이루어져 있다.
        (각 아이노드는 256bytes라고 가정)
      • 예) 특정 아이노드 읽기
        • 32번 아이노드를 읽기 위해서는 파일 시스템은 아이노드 영역(12~32KB)에서의 오프셋을 계산한다.
          -> 32 * sizeof(inode) = 32 * 256 = 8192 (= 8KB)
        • 그 후 아이노드 테이블의 시작 위치를 더하면, 원하는 아이노드 블럭의 정확한 바이트 주소를 구할 수 있다.
          -> 12KB + 8KB = 20KB
        • 근데 디스크는 바이트 단위로 접근이 불가해서 섹터주소로 접근해야 한다. 섹터주소 sector는 다음과 같이 계산될 수 있다.
          // 참고로 섹터 크기는 대체로 512 byte
blk = (inumber * sizeof(inode_t)) / blockSize;
sector = ((blk * blockSize) + inodeStartAddr) / sectorSize;
  • 아이노드에는 파일에 필요한 정보가 다 들어있다. (메타데이터)
    • 위 표는 간략화한 Ext2의 아이노드이다.

아이노드 설계 방식 1 - 직접 포인터(direct pointer) 활용

  • 아이노드 내에 여러 개의 직접 포인터(direct pointer, 디스크 주소) 를 두는 방식이다.
  • 각 포인터는 파일의 디스크 블럭 하나를 가리킨다.
  • 이 방법은 파일 크기가 (포인터의 개수) * (블럭 크기) 로 제한된다.

더 좋은 방법이 없을까?

멀티 레벨 인덱스

큰 파일을 지원하기 위해서 파일 시스템 개발자들은 아이노드 내에 다른 자료 구조를 추가해야 했다.

아이노드 설계 방식 2 - 간접 포인터(indirect pointer) 활용

  • 간접 포인터는 데이터 블럭을 직접 가리키지 않고, 데이터 블럭을 가리키는 "포인터"들이 저장된다.
  • 직접 포인터와 간접 포인터를 결합하여 사용
    • 아이노드에는 정해진 수의 직접 포인터 (예, 12개), 그리고 하나의 간접 포인터가 있다.
    • 큰 파일에 대해서는 디스크의 데이터 블럭 영역에서 간접 블럭이 할당이 된다.
      • 아이노드의 간접 포인터는 이 간접 블럭을 가리킨다.
    • 블럭이 4KB이고 디스크 주소가 4 바이트라고 하면 1024개의 포인터들을 추가할 수 있게 된다.
      -> 최대 파일 크기는 (12 + 1024) * 4K (= 4144 KB)가 된다.
  • 더 큰 파일을 저장하고 싶으면 이중 간접 포인터(double indirect pointer) 사용
    • 이중 간접 포인터가 가르키는 블럭에는 간접 포인터들이 저장되어 있다.
    • 각 간접 블럭은 데이터 블럭을 가리키는 포인터들을 가리키고 있다.
    • 이중 간접 블럭을 사용하면 파일은 4KB * 1024 * 1024, 약 백만개의 4KB 블럭을 가질수 있다.
    • 즉, 4 GB가 넘는 크기의 파일을 지원할 수 있게 된다.
      (이보다 큰 파일을 저장하고 싶으면 삼중 간접 포인터(triple indirect pointer) 사용)

이제까지 설명한 것을 종합하면, 디스크 블럭들은 일종의 트리 형태로 구성되어 하나의 파일을 이룬다. 약간 한쪽으로 치우쳐진 형태의 트리다. 이러한 구성방식을 멀티 레벨 인덱스 기법이라 한다.

  • 예시 1) 12개의 직접 포인터 + 간접 블럭 + 이중 간접 블럭
    • 블럭 크기: 4KB
    • 포인터 크기 4바이트
    • 총 크기 = (12+1024+10242^2) * 4KB) = 약 100만 * 4KB = 약 400만 KB = 4GB
  • 예시 2) 12개의 직접 포인터 + 간접 블럭 + 이중 간접 블럭 + 삼중 간접 블럭
    • 총 크기 = (12+1024+10242^2+10243^3) * 4KB) = 약 10억 * 4KB = 약 40억 KB = 4TB
  • 리눅스의 ext2, ext3 등 많은 파일 시스템이 멀티 레벨 인덱스를 사용한다.
  • SGI의 XFS와 Linux 의 ext4와 같은 파일 시스템들은 간단한 포인터를 사용하는 대신 익스텐트(extent)를 사용한다.
  • 트리의 형태가 매우 편항적인데 (ex. 파일 시작 부분의 블럭들은 금방 접근), 이는 대부분의 파일들의 크기가 작기 때문이다.

4. 디렉터리 구조

vsfs의 디렉터리는 (다른 많은 파일 시스템에서 그러하듯이) 간단하다.

디렉터리 구조

  • 디렉터리는 (항목의 이름, 아이노드 번호) 쌍의 배열로 구성되어 있다.
  • 디렉터리의 데이터 블럭에는 문자열과 숫자가 쌍으로 존재하며 문자열 길이에 대한 정보도 있다 (가변 길이의 이름을 가정).
    • dir 이라는 디렉터리 안의 모습
    • 각 항목들은 아이노드, 레코드 길이, 문자열 길이, 항목 이름을 갖고 있다.
      • 항목의 길이를 명시하는 이유 중에 하나가 중간에 빈 공간이 생기기 때문이다.
      • 새로운 디렉터리 항목을 생성할 때, 기존 항목이 삭제되어 생긴 빈 공간에 새로이 생성된 항목을 위치시킬 수도 있기 때문이다.
    • foo, bar, foobar의 아이노드는 각각 12, 13, 24이다.
  • 디렉토리의 저장 위치
    • 디렉토리는 특수한 종류의 파일이다.
    • 자신의 아이노드를 가지며, 이 아이노드는 아이노드 테이블에 존재한다.
    • 디렉토리는 자신의 데이터 블럭을 갖고 있으며, 이 데이터 블럭들은 데이터 블럭 영역에 존재한다.
      (이들 블럭의 위치는 일반 파일과 마찬가지로 아이노드에 명시되어 있다.)
  • 이 vsfs 예제에서 디렉터리는 가변 크기 레코드로 구성된 배열이지만, 이 외에도 많은 방식이 존재할 수 있다.
    • 잘 돌아가기만 한다면 어떤 자료구조도 상관 없다.
    • XFS는 디렉터리를 B-tree 형식으로 구성하여 검색시간이 빠르고 파일 생성을 빨리 할 수 있다. 대신에 동일한 이름의 파일이 있는지 먼저 검사해야 한다.

5. 빈 공간의 관리

파일 시스템은 아이노드와 데이터 블럭 사용 여부를 관리해야 한다. 그래야 새로운 파일이나 디렉터리를 할당할 공간을 찾을 수 있다.

빈 공간 관리(free space management)

  • vsfs에서는 두 개의 비트맵을 사용할 것이다.
  • 파일 생성 시 아이노드 할당
    • 파일 시스템은 아이노드 비트맵을 탐색하여 비어 있는 아이노드를 찾아 파일에 할당한다.
    • 파일 시스템은 해당 아이노드를 사용 중으로 표기하고 (1로 표기) 디스크 비트맵도 적절히 갱신한다.
    • 이와 유사한 동작이 데이터 블럭을 할당할 때에도 일어난다.
  • 선할당(pre-allocation) 정책: 데이터 블럭 할당 시 가능하면 여러 개의 블럭들이 연속적으로 비어 있는 공간을 찾아서 할당
    • ext2, ext3 파일 시스템의 경우, 추후에 할당요청이 발생하는 것에 대비하여 가능하면 여러 블럭들을 연속적으로 할당한다.
    • 연속적으로 여러 개의 블럭들이 비어있는 공간을 할당함으로써 해당 파일에 대한 입출력 성능을 개선한다.

6. 실행 흐름: 읽기와 쓰기

이제까지 파일과 디렉터리를 디스크에 저장하는 방법에 대해 학습했다. 이제 파일을 읽고 쓰는 실행 과정(access path)을 이해해보자.

가정

  • 파일 시스템은 마운트되었고, 슈퍼블럭은 메모리 상에 위치
  • 다른 모든 것(예, 아이노드, 디렉터리)들은 디스크에 존재
  • 메모리는 아직 미 탑재

디스크에서 파일 읽기

간단한 예제로 단순히 파일을 열고(예, /foo/bar), 읽고, 읽은 후에 닫는 상황을 가정해보자.

  • 파일은4KB의 크기(1개의 블럭)를 갖고 있다고 가정

  1. open("/foo/bar", O_RDONLY) 시스템 콜 호출

    • 파일 bar에 대한 아이노드를 찾아서 파일에 대한 기본적인 정보를 획득해야 한다.
      (권한 정보,파일의 크기 등)
    • 파일에 대한 전체 경로명을 갖고 있으므로, 파일 시스템은 경로명을 따라가서(traverse) 원하는 아이노드를 찾아야한다.

  2. 경로명 순회(traverse)
    2-1. 순회는 항상 루트 디렉토리(root directory)에서 시작한다.

    • 먼저 루트 디렉토리의 아이노드를 읽는다.
      • 아이노드를 찾기 위해선 inumber를 알아야 하는데, 일반적으로 루트 디렉토리의 inumber는 2 이다.
      • 보통 다른 디렉토리는 inumber를 부모로부터 알아낸다.
    • 읽어들인 아이노드에서 데이터 블럭의 포인터를 추출한다.
      • 포인터가 가리키는 블럭에는 루트 디렉터리의 내용이 들어 있다.
        (/ 의 data)
      • 루트 디렉터리 안에서 foo라는 항목을 찾는다.
      • foo의 아이노드를 찾아낸다.

    2-2. foo의 아이노드를 읽고, foo의 데이터 블럭의 포인터를 추출한다.

    • 포인터가 가리키는 블럭에는 foo 디렉터리의 내용이 들어 있다.
      (/foo 의 data)
    • foo 디렉터리 안에서 bar라는 항목을 찾는다.
    • bar의 아이노드를 찾아낸다.

    2-3. bar의 아이노드를 읽고, 접근 권한을 확인하고, open() 한다.

    • 아이노드로 해당 블럭의 디스크상 위치를 파악하고 블럭을 읽는다.
    • bar의 첫 번째 데이터 읽기
      (/foo/bar 의 data[0])
    • 파일을 읽은 후 마지막으로 읽은 시간을 아이노드에 기록한다. (write)
      ...
      ...반복...
      ...
    • 아이노드로 해당 블럭의 디스크상 위치를 파악하고 블럭을 읽는다.
    • bar의 N 번째 데이터 읽기
      (/foo/bar 의 data[N-1])
    • 파일을 읽은 후 마지막으로 읽은 시간을 아이노드에 기록한다. (write)

  3. 파일을 다 읽었으면 할당된 파일 디스크립터를 해제하여 파일을 닫는다.

    • 디스크 I/O는 발생하지 않는다.
  • 참고로 I/O 발생 횟수는 경로의 길이에 비례한다.
  • 디렉터리가 크다면 원하는 항목을 찾기 위해서 많은 데이터 블럭을 읽어야 할 것이다.

디스크에 쓰기

디스크 쓰기도 비슷한 과정을 밟는다.

  1. 먼저 파일을 연다 (읽기에서 했던 것과 같이).
  2. 그 후에 응용 프로그램은 write()를 호출하여 새로운 내용으로 파일을 갱신한다.
  3. 최종적으로 파일을 닫는다.

단, 읽기와 다르게 파일 쓰기는 블럭 할당을 필요로 할 수 있다.

  • 새로운 파일에 쓸 때에는 각 write()는 데이터를 디스크에 기록해야 할 뿐만 아니라 파일에 어느 블럭을 할당할지를 결정해야 한다.
  • 그에 따라 디스크에 데이터 비트맵이나 아이노드와 같은 다른 자료 구조들을 갱신해야 한다.
    • 파일에 대한 쓰기 요청은 논리적으로 5번의 I/O를 생성한다.
      1. 데이터 비트맵 읽기 (이후 새로 할당된 블럭의 상태를 사용중으로 표시하기 위해)
      2. 비트맵을 쓰기 (디스크에 새로운 상태 반영을 위해)
      3. 아이노드 읽기
      4. 아이노드 쓰기 (새로운 블럭의 위치 반영을 위해)
      5. 실제 블럭 기록
  • 예시) 파일 생성 과정
    • /foo/bar를 생성하고 그 안에 세 개의 블럭을 쓰는 예
    • 파일 생성까지 10번의 I/O 발생
    • 각 write()는 5번의 I/O 발생

핵심 질문 : 파일 시스템의 I/O 비용을 어떻게 줄일까
파일 열기, 읽기 또는 쓰기와 같은 단순한 동작이 디스크 위 여기저기에 엄청나게 많은 I/O를 발생시킨다.

  • 파일 시스템은 이렇게 많은 I/O에 대한 엄청난 비용을 줄이기 위해서 무엇을 할 수 있을까?

7. 캐싱과 버퍼링

앞의 예제에서 볼 수 있듯이 파일을 읽고 쓰는 잃은 많은 I/O를 발생시킨다. 컴퓨터의 전체 성능에 중요한 영향을 미친다. 성능개선을 위해 대부분의 파일 시스템들은 자주 사용되는 블럭들을 메모리 (DRAM) 에 캐싱한다.

블럭 캐싱

  • 초기 파일 시스템에는 자주 사용되는 블럭들을 저장하기 위해 캐시를 도입하였다.
  • 캐싱을 하지 않는다면 파일을 여는 동작은 디렉터리 레벨마다 최소한 두 번의 읽기가 필요하다.
    (디렉터리 아이노드 읽기와 디렉터리 데이터 읽기)
    • /1/2/3/.../100/file.txt 과 같은 파일은 수백번의 읽기 수행
  • 정적 기법
    • 고정 크기의 캐시 사용
    • LRU와 기타 다른 캐시 교체 정책들이 캐시에 어떤 블럭들을 남길지 결정해야 한다.
    • 부팅 시에 할당이 되며 전체 메모리의 약 10% 를 차지하는 낭비가 존재
  • 동적 파티션 방식
    • 일원화된 페이지 캐시(unified page cache): 가상 메모리 페이지들과 파일 시스템 페이지들을 통합한 캐시
      • 어느 한 시점에 어느 부분에 더 많은 메모리가 필요하냐에 따라 파일 시스템과 가상 메모리에 좀 더 융통성 있게 메모리를 할당할 수 있다.
  • 캐싱을 하는 경우에 파일 열기
    • 첫 번째 열기는 디렉터리 아이노드와 데이터로 인해서 많은 읽기 I/O를 발생시키겠지만,
    • 그 뒤를 따르는 같은 파일(또는 같은 디렉터리의 파일들)에 대한 파일 열기의 경우 캐시에서 히트가 되기 때문에 추가 I/O가 필요 없다.
  • 캐싱을 하는 경우에 파일 쓰기
    • 캐시가 충분히 크면 대부분의 읽기 I/O를 제거할 수 있다.
    • 쓰기 버퍼링(write buffering): 쓰기의 경우에는 캐시가 읽기에서와 같은 필터 역할을 할 수가 없고, 캐시는 쓰기 시점을 연기하는 역할을 한다.
      • 장점 1) 쓰기 요청을 지연시켜 다수의 쓰기 작업들을 적은 수의 I/O로 일괄처리(batch) 할 수도 있다.
        • "비트맵 1 갱신 후 비트맵 2 갱신"보단 두개 한번에 처리하는게 더 좋음
      • 장점 2) 여러 개의 쓰기요청들을 모아둠으로써 다수의 I/O들을 스케줄하여 성능을 개선할 수 있다.
      • 장점 3) 지연시키는 것을 통해 쓰기 자체를 피할 수도 있다.
        • "임시파일 생성 후 삭제"보단 메모리에 아예 안 쓰고 게으른 것이 더 좋음
profile
장선규
코딩연습
이전 포스트

[OS] 파일과 디렉터리

0개의 댓글