[운영체제 정리] 파일 & 파일시스템

파일 시스템 정리

---

개요

오랜 기간 동안 저장되어야하는 정보의 저장에는 몇가지 조건이 있다.

• 프로세스가 종료된 후에도 정보가 유지되는 비휘발성

• 많은 정보를 저장할 수 있는 큰 용량

• 다수의 프로세스가 동시에 접근 가능한 접근성

  오랜 기간동안 큰 정보를 저장하는 장치 중 하나인 Disk는 고정된 크기의 block들로 구성되어있는데, 다음과 같은 질문들을 불러일으킬 수 있다.

1. Disk에 저장한 정보를 어떻게 찾을 것인가?

   정보의 양이 방대해서 정보를 찾기가 쉽지 않다.

2. 빈 공간을 어떻게 관리할 것인가?

   새로운 정보를 저장할 때 빈 공간을 찾아서 사용해야한다.

3. 사용자 별 권한을 어떻게 관리할 것인가?

   데이터를 보호해야한다.

이 해답은 파일 과 파일시스템 에서 찾을 수 있다.

파일

파일은 저장 장치에 정보를 저장하는 기본 단위이다. byte 정보들의 연속으로 이루어져있으며, 사용자는 하나의 단위로 파일을 사용한다. 파일은 unique한 path name이 있으며, 이는 파일의 이름은 같을 수 있으나 저장된 디렉토리까지 같을 수는 없다는 의미이다. 또한 파일은 사용자별로 r,w,x 권한을 제어할 수 있다.

이러한 파일의 특징으로 봤을 때, 큰 저장장치에서 저장단위로 파일을 이용할 수 있다.

파일 시스템

파일 시스템은 파일 사용과 관련된 서비스를 제공해주는 시스템 소프트웨어의 set이다.

---

파일

이름 짓기

파일이름.확장자 로 이름이 구성되어있으며 확장자는 3개까지 인식하지만 여러 글자를 적어도 상관없다. 전통적으로 몇몇 파일을 정의하는 확장자가 있으니 웬만하면 지키는 것이 좋다.

파일 구조

파일은 앞에서 설명했듯이 byte들의 연속이므로 어떤 데이터가 들어가는지, 어떤 구조로 들어가는지에 대한 제한이 없다. 데이터와 구조는 파일을 사용하는 응용프로그램이 결정한다. 예를 들어 '한글과 컴퓨터' 응용프로그램에서는 'hwp'의 형태로 파일을 구성하는 것이다.

하지만 실행파일만큼은 어떤 형태의 데이터가 필요한 지를 OS에서 정의하고 있다. 아카이브 파일 (라이브러리 파일) 또한 그렇다.

파일은 root 디렉토리부터 sub 디렉토리로 이어지는 트리구조를 가지고 있다.

파일 속성

파일은 이름 + 속성 + 데이터 로 구성되어있다. 그 중 속성에는 Protection, Password, Creator, Owner 등의 정보가 저장되어있다. 쉽게 말해서 이름과 데이터를 제외한 파일의 모든 정보가 속성에 들어있다. 파일 시스템마다 사용하는 파일의 속성이 다르다.

파일 접근

파일을 접근하는 방법은 두 가지가 있다.

• Sequential access

  Tape의 파일은 순차적으로 접근해야한다.

• Random access

  Disk의 파일은 Random하게 접근할 수 있다.

  임의 접근에는 또 두가지 방식이 있다.

  1. read(id, &buf, from, rwbytes)

     이와 같은 형태의 명령어는 from 위치를 받아서 해당 위치에서 부터 데이터를 접근한다. 즉, offset의 위치를 매개변수로 받는다.

  2. read(id, &buf, rwbytes)

     이와 같은 형태의 명령어는 눈에 보이지 않는 offset이 파일마다 존재해서 해당 offset부터 데이터를 접근한다. 데이터를 접근하면서 offset는 자동 증가한다. offset의 위치를 바꾸려면 lseek와 같은 명령어를 사용해야한다.

많은 프로세스들이 파일을 순차적으로 접근하니까 2번 방법이 많이 사용된다. 하지만 다중 스레드 프로그래밍에서 스레드가 병렬로 동작하는 경우에는 1번 방법을 사용한다.

파일 공유

파일을 다수의 프로그램이 동시에 읽고 쓸 수 있을까?

가능하다. 그렇다면 한 프로그램이 수정한 파일의 내용을 다른 프로그램들은 언제부터 수정된 내용으로 읽을 수 있을까?

대부분의 OS에서는 파일의 내용을 수정하자마자 다른 프로그램들이 볼 수 있다. 예전 분산 파일시스템(Andrew file system)에서는 원격 서버에 파일을 저장해야했기 때문에 수정해도 다른 프로그램이 바로 볼 수 없었고, 수정이라는 단어의 semantic을 file을 close하는 것까지 포함해서 정의하였다.

파일 연산

파일과 관련된 연산들은 프로세스가 OS에게 시스템 콜을 요청해서 사용할 수 있다. 연산에는 create, delete, open, close, read, write, append, seek, get attribute, set attribute, rename 등이 있다.

디렉토리 (폴더)

유닉스에서는 디렉토리, 윈도우에서는 폴더라고 부르는 자료의 단위이다. 단순히 데이터를 저장해두는 파일과 형태는 똑같지만 안에 든 내용은 다르다. 디렉토리 파일은 테이블의 형태로 담고있는 파일과 서브 디렉토리의 내용이 들어가 있다. 디렉토리의 목적은 _파일의 이름을 속성과 데이터 같은 정보로 mapping 해주는 것_이다.

파일은 이름 + 속성 + 데이터로 구성되어 있다고 이전에 언급한 바 있는데, 파일은 이름으로 저장되어 해당 파일의 실제 정보를 얻기 위해서는 이름으로 정보를 찾아야한다. 이러한 역할을 디렉토리가 해주는 것이다.

계층 디렉토리 시스템

트리 구조로 Root 디렉토리부터 Sub 디렉토리가 이어져있는 것이 일반적이다. 원래는 Single 디렉토리만 있어서 모두가 Root 디렉토리이고 한 파일만을 의미하는 것이라 '디렉토리'라는 용어도 존재하지 않았다. 하지만 이후 파일들을 찾기 힘들어지자 디렉토리라는 트리 구조로 파일을 묶기 시작한 것이다.

Path name (경로 이름)

파일의 path name은 unique하다고 했다. 리눅스의 파일 구조를 보면 다음과 같다.

이렇게 root 디렉토리부터 해당 파일까지의 경로를 path name이라고 하고 위 그림의 '/usr/jim'이 예시이다. 이러한 path name은 unique해야하며 이름이 같아도 디렉토리만 다르다면 path name이 다르다.

절대 path

root 디렉토리로부터의 path를 의미한다.

ex_) C:\Document (윈도우즈) \usr (유닉스)

상대 path

현재 작업 디렉토리(Current Working Directory)로부터의 path를 의미한다.

ex_) ./Work 에서 '.'는 현재 디렉토리를 의미한다. '..'는 부모 디렉토리를 의미한다.

디렉토리 연산

create, delete, opendir, closedir, readdir, rename, link, unlink 등의 연산이 존재한다. link 연산은 파일이나 디렉토리의 이름을 하나 더 부여하는 연산으로, 파일의 정보는 하나인데 이름을 여러 개 생성하는 경우이다. Unlink 연산은 반대로 이름을 하나씩 지우는 연산이다. Unlink 연산 시 파일의 마지막 이름이 unlink되면 파일의 정보 자체가 사라진다.

---

레이아웃

하드디스크는 원판을 트랙단위로 쪼개서 관리한다. 그림에서 A로 표시된 부분이 트랙이다. 트랙은 바깥쪽부터 안쪽으로 들어가면서 사용되고 트랙 자체는 512byte의 섹터단위로 이루어져있다. 그림에서 C로 표시된 부분이 섹터이다. 파일시스템은 이 섹터를 여러 개 모아서 블록이라는 단위로 사용한다.

하드디스크의 트랙을 이루는 단위가 섹터이고 파일시스템은 여러 개의 섹터로 된 블록을 사용한다.

원형 모양의 하드디스크를 일자로 펼쳐보면 다음과 같은 형태가 나온다.

나뉘어진 단위를 섹터라고 보면, 첫번째 섹터에는 MBR(master boot record)이라는 코드가 있고, 부트 섹터라고 불린다. 컴퓨터에 전원을 켜면 ROM BIOS (OS 중 가장 기본적인 컴퓨터의 IO를 처리하는 Software) 가 초기화하고, 하드디스크 첫번째 섹터에 있는 MBR 코드를 메모리에 적재한 후 실행한다. MBR 코드(부트 코드)는 파티션 테이블에서 부트 파티션을 찾아서 OS의 부트 블록 코드를 메모리에 적재할 수 있도록 한다. 이후 OS의 부트 코드가 실행된다.

즉, 처음에는 MBR 코드로 부팅을 하고 디스크의 파티션 중 OS 부트 파티션을 찾아서 OS 부팅을 한다.
MBR에는 파티션의 갯수와 시작 위치, 사이즈 등이 기록되어있다.

파티션 테이블에는 최대 4개의 엔트리가 존재할 수 있고, 이는 하드디스크를 최대 4등분하여 사용할 수 있다는 말이다. 이 중 하나는 OS의 부트 파티션이여야한다. 파티션마다 새로운 파일시스템과 운영체제가 사용될 수 있다.

위에 표시된 그림 상의 파티션 구조는 유닉스 파일시스템의 경우이다.

---

파일 시스템 설계

파일 시스템을 설계할 때 고려해야할 사항들은 앞의 개요에서 다뤘었다. 그 중 두 개를 가져와보자.

1. 파일에 대한 데이터블록의 할당 / 관리 (정보 찾기)

   하드디스크의 512byte 섹터는 너무 작아서 파일시스템은 섹터를 모아 블록단위로 사용한다.

   유닉스 : block, 윈도우즈 : cluster

2. 빈 공간 관리

파일 할당 방법

• Contiguous allocation

  연속적으로 블록을 할당하는 방법이다.

  해당 파일이 어떤 블록에 있는 지 쉽게 찾을 수 있게 하기 위해 디렉토리 테이블을 사용하자. 이 테이블의 엔트리는 (파일이름, 시작 블록위치, 사이즈)로 구성되어있다. 시작 블록위치부터 연속적으로 사이즈만큼 읽으면 해당 파일이라는 정보가 된다.

  이러한 연속적 블록 할당 방식의 장점은 읽고 쓰기 좋다는 것이다. 단점은 external fragmentation 문제를 야기하여 저장공간 효율이 낮아질 수 있다는 것이다. 이 방법은 하드디스크에서는 사용하기 어렵고, 한 번 구우면 수정이 불가능한 CD-ROM과 같은 저장매체에서 주로 사용된다.

• Chained allocation (=LinkedList allocation)

  연속적이지 않고, 동적인 할당 방법이다.

  디렉토리 테이블의 엔트리는 (파일이름, 시작 블록위치, 사이즈)로 Contiguous allocation과 같다. 하지만 실제 블록에 담겨있는 정보에 차이가 있다. Contiguous allocation에서는 블록에 file data만이 존재했다면, Chained allocation에서는 블록에 file data와 meta data가 함께 존재한다.

  따라서 해당 파일이 저장매체의 어디에 저장되어있는지를 확인할 때, 시작 블록위치에 있는 블록에서 file data를 읽고, 다음 블록의 정보를 meta data에서 읽어서 블록을 사이즈만큼 따라가면서 읽는다.

  이러한 방식은 external fragmentation 문제를 해결해주겠지만, 한 블록에 file data와 meta data를 함께 기록하는 것은 좋지 않다. 파일 손상 시 meta data가 손상되어 이후 블록들이 모두 손상될 수 있기 때문이다. 또한 linked-list 방식으로 구현하여 순차접근만이 가능하다는 것도 단점이다.

• FAT (File Allocation Table)

  그렇다면 Chained allocation 방식에서 meta data만 다른 곳에 모아보자. meta data(해당 블록 다음에는 어떤 블록이 오는지)만 모아둔 자료구조가 있고, file data는 따로 있다면 하나의 단점은 커버할 수 있다.

  실제로 MS사의 FAT 파일 시스템은 이러한 방식을 이용하여 개발되었다. 처음에는 Master Boot Block으로 부팅하고 파티션 중 Partition Boot Block의 코드를 실행하면 OS 부팅이 된다. 여기에 특징적으로 FAT Block table이 있는데, 이 테이블은 모든 물리적 블록들이 대응되어 'FF=-1'은 다음 블록이 없음을 '숫자'는 다음 블록의 번호를 '0'은 비어있는 프리 블록을 의미한다. meta data를 모아두는 Fat block table을 따로 만든 것이다.

  FAT 파일시스템은 유닉스 파일시스템과 달리 루트디렉토리가 .와 ..을 가지지 않는다. 또 유닉스 파일시스템과 구분되는 점은 모든 파일의 정보(이름, 속성, 데이터)를 파일 엔트리에 기록한다는 것이다.

  FAT 파일시스템은 예전에 MS에서 소용량 플러피 디스크 / 하드디스크 용으로 사용한 파일시스템이다. 호환성이 좋아서 USB 드라이브 용도로도 사용되지만 성능은 그다지 좋지 않다.

저장용량이 커지면 FAT block table의 크기도 커져서 메모리 낭비
파일의 크기가 커지면 linked-list 형식의 순차탐색 방법이 시간 낭비

• Indexed allocation

  디렉토리 테이블의 엔트리는 (파일이름, 인덱스 블록)으로만 이루어져있다. 인덱스 블록은 파일 정보가 기록되어있는 블록으로 array 구조로 나열되어있지만, 용량이 부족하면 linked-list나 tree 형태로 만들어지기도 한다. 데이터가 기록되는 데이터 블록은 연속되게 배치할 필요는 없지만 하드디스크의 특성을 고려한다면 가능한 연속적으로 배치하는 것이 좋다.

  하드디스크의 헤드 이동 시간이 많이 들기 때문

  => 유닉스 V7 FS 보기

  • inode

    inode가 가지고 있는 정보는 파일의 이름과 데이터를 제외한 속성이며, 이름과 데이터는 데이터블록에 저장되어있다.

이러한 indexed 방식은 효율적으로 동작하며 임의 접근을 할 수 있어서 성능도 좋다. 하지만 데이터블록의 갯수가 많은 경우에는 indirect block이 만들어져 순차접근을 해야하는 경우도 있다.

• 유닉스 파일시스템에서 indexed allocation 방식을 약간 변형해서 사용하였는데, 여기서는 인덱스 블록을 inode라고 부른다.

파일 공유

이렇게 여러 개의 디렉토리에서 공유하는 파일이 있을 수 있을까? 가능하다. Unix 파일시스템에서 이는 link라는 기능으로 구현된다. 디렉토리는 어차피 파일이름을 inode로 변환하는 목적으로 만들어진 것이므로 알맞은 inode로 변환해주기만 한다면 문제 없다.

따라서 파일의 데이터와 속성은 하나인데, 이름이 두 개의 디렉토리에 있을 수 있다. Unix 파일시스템에서는 이러한 이름을 link라고 하며 이름의 갯수를 link-count라는 형태로 유지한다. link-count가 0이되면 실제 저장하고 있는 파일의 정보(inode)가 사라진다.

이렇게 여러 개의 이름이 있는 것이 통계프로그램에서의 중복가능성, 삭제가 안되는 경우, 2번 백업되는 경우, 디렉토리 링크 때문에 무한루프를 도는 경우 등의 문제를 야기할 수 있지만 이는 바로가기 파일(Symbolic link)으로 해결할 수 있다. 바로가기 파일은 원본과 다른 별도의 파일로써 원본 파일의 path name을 저장하는 파일이다. 바로가기 파일을 열고자할 때, 해당 path name으로 가서 다시 원본 파일을 열어야하지만 이정도 overhead는 괜찮다고 본다.

Log-structured 파일시스템 (LFS)

몇몇 연구자들이 하드디스크에 write 시 seek time을 줄여 속도를 높이기 위한 방안으로 데이터블록들의 위치를 가변으로 하는 방식을 연구했다. 위에서 배운 FAT, UNIX 파일시스템의 경우 한번 파일 데이터블록들의 위치가 등록되면 변화하지 않는다.

기본적인 아이디어는 log 형식으로 disk에 계속 적어나가는 것이다. 하드디스크 공간의 현재 writing할 point에서 segment 단위로 log를 기록할 것이다. 데이터를 기록할 때 이전 파일시스템들은 해당 파일의 데이터블록을 찾아가서 수정하는 방식으로 진행했는데, LFS의 경우 현재 writing point에서 순차적으로 전체 데이터를 write한다. 그리고 해당 위치에 변경된 inode까지 작성한다. 그러는 와중 LFS라고 불리는 GC는 cleaning point를 증가시키면서 변경되지 않은 데이터만 copy하는 방식으로 빈공간(segment)을 만들어준다.

이전 Unix 파일시스템에서는 inode의 위치가 고정되어있어 inode 번호만 알면 데이터블록을 찾을 수 있었는데, LFS에서는 inode도 새로 기록하므로(가변 위치이므로) inode의 위치도 기록해두어야한다. 이 때 파일을 바꾸고, inode를 바꾸고, 수퍼 블록을 바꾸는 순으로 log를 기록하기 때문에 read시에는 반대로 헤드를 움직이며 읽어주어야한다는 점에서 성능이 약간 저하된다. 일정주기마다 순차적으로 기록하면서 하드디스크의 고정된 위치에 있는 inode map에 inode들의 위치를 기록하는 식으로 진행한다.

이 일정주기를 check point라고 하며 check pointing을 하여 마지막 체크포인트 위치에서부터 변경된 파일들을 모두 inode map에 기록한다.

=> write 측면에는 약간의 이득이 있지만 GC도 사용하고 inode도 map을 이용하기 때문에 성능이 썩 좋지 않다. 하지만 SSD와 같은 플래시 메모리는 큰 단위로 지우고 사용하는 특성이 있기 때문에 LFS 구조와 잘 맞아서 LFS는 플래시 메모리 저장장치에 많이 쓰인다.

삼성의 F2FS도 LFS를 응용해서 만든 파일시스템이다.

Journaling 파일시스템

FFS에서는 파일을 만들고자하면 inode를 할당하고 파일의 속성을 기록하고 데이터블록을 할당하고 데이터블록에 데이터를 기록하고 디렉토리에 이름과 inode를 기록하고 비트맵을 세팅해주어야한다.

이 때 여러 개의 블록을 거치는데 파일시스템은 해당 블록들의 일관성이 완벽하게 해결된 상태에서만 동작해야한다. 일관성을 맞추는 것에 시간이 너무 오래걸리자 Journaling 기법이 나왔다.

Journaling기법은 파일시스템의 구조를 변경할 때 Log Area에 log를 만들고 동작을 한다. 해당 동작이 완료되면 log를 삭제하지만 완료되지 않은 상태에서 리부팅 시 log를 보고 roll back이나 roll forward해서 일관성을 회복한다. 전체 파일시스템을 맞춰보면서 일관성을 체크하는 것보다 log 기록만 보면 되니까 속도가 굉장히 빨라진다.

가상 파일시스템 (VFS)

예전에는 OS마다 하나의 파일시스템만 지원했었다. 현재는 다양한 파일시스템을 지원하고 있다. Unix Sun Micro Systems라는 회사에서 Unix OS에서 여러 파일시스템을 사용하기 위해 VFSlayer를 개발했다. VFSlayer는 사용하는 파일시스템의 공통된 부분을 VFSlayer로 만들고, 각각의 FS마다 다른 부분들만 아래에 붙여서 구현한 구조이다. 현재도 많은 컴퓨터 시스템에서 해당 구조를 사용하고 있다.

Linux의 VFS을 거쳐서 각 FS의 메소드를 불러서 동작시킨다. 따라서 OS 안에서 여러 개의 FS를 구동하면서 각 FS에 특화된 메소드를 동작시킬 수 있다.

블록 사이즈 결정

• Large 블록 사이즈 (8KB 블록 => 16개의 섹터)

  성능면에서는 좋지만 공간 효율면에서는 좋지 않다. 블록을 관리하는 table의 엔트리가 적으므로 관리하기 좋다.

  FAT에서는 FAT table 엔트리가 적고, FFS에서는 inode에 기록되는 데이터블록 갯수가 적다.

• Small 블록 사이즈 (1KB 블록 => 2개의 섹터)

  공간 효율면에서는 좋지만 큰 파일의 경우 블록이 흩어져있을 수 있기 때문에 성능면에서는 좋지 않다. 블록 엔트리 개수가 많아지므로 관리하기 어렵다.

시간이 지날 수록 점점 크기가 큰 파일이 생겨나지만 여전히 작은 파일들이 대부분이다. 그래프의 오른쪽으로 가수록 공간활용도는 증가하지만 성능은 저하한다. 위에서 분석했듯이 성능과 공간 효율은 반비례하는데 그래프가 크로스하는 지점이 아닌 2,4KB 정도에서 블록사이즈를 결정한다. 여기서 성능이 중요하면 8KB를 사용하기도 하며 아주 특이한 경우 64KB를 사용하는 경우도 있다.

공간 관리

하드디스크 등 거대한 저장장치의 공간은 어떻게 관리할까? 사용하고 있지 않은 블록을 할당해주기 위해 이를 표시하고 있어야한다. 방법에는 3가지가 있다.

1. Bit map ( bit vector )

   디스크에 있는 블록이 bit map의 한 bit에 대응하여 사용중인지 아닌지를 0과 1로 표현하는 방법이다. bit로 표현하므로 메모리 차지가 적으며 연속적으로 빈 블록을 찾기가 좋다. 따라서 많은 파일시스템이 free block 관리 시 이 방법을 사용하고 있다.

   예를 들어 블록사이즈가 2^12byte이고 디스크사이즈가 2^30byte(1GB)라고 한다면 블록은 2^18개 만큼 존재한다. 따라서 한 블록을 한 bit로 표현하므로 2^18bit인 32Kbyte가 필요하다.

2. Linked List

   한 free block이 다음 free block을 가리키도록 하여 chain으로 엮는다. 하나의 free block이 새로 생겼을 때 linked list 형태로 붙여주어야하고 free block을 할당할 때 순차적으로 접근하며 읽어야하기 때문에 overhead가 크다.

3. Grouping(Indexing)

   여러 개의 free block을 인덱스 블록 하나로 묶어서 사용하는 방법이다. 인덱스 블록 마지막에는 다음 인덱스 블록을 가리키는 포인터가 기록되어있다. 따라서 인덱스 블록 자체는 linked-list 형태로 구성되어있다. Linked List 방법보다 overhead는 줄어들었지만 여전히 존재하고 하드디스크가 Aging 된 후에는 파일들이 불연속적으로 할당되므로 효율성이 감소한다.

   원래는 free block이 생겼을 때 메인 메모리에서 모아가면서 인덱스 블록을 준비하고 인덱스 블록이 가득 차면 디스크에 기록하는 식으로 구현했는데, 이런 방식은 free block이 필요할 때 계속 한 인덱스 블록을 읽고 쓰는 작업이 반복되므로 성능이 하락할 수 있다. 따라서 인덱스 블록을 반만 채우고 디스크에 기록하자는 의견도 나왔으나 어차피 현재는 많은 파일시스템이 bitmap을 사용하고 있다

Disk Quotas

예전에는 컴퓨터를 여러 명이 함께 사용하므로 각 사용자마다 정해진 자원의 제약이 있었다. 이를 Quota라고 하는데, Quota table에 제약들을 기록해둠으로써 사용자가 할당된 용량을 넘어서 사용하면 처음에는 Soft Block Limit에서 경고가 오고 Hard Block Limit에서는 더이상 하드디스크 공간을 사용할 수 없었다.

파일 시스템 백업

파일 시스템은 주기적으로 정해진 규칙에 따라 백업해야하며, 백업 시 보통 가격이 저렴한 tape 저장매체에 하는 편이다.

<tape 백업 방법>

1. Physical dump : 순차적 백업
2. Logical Dump : 파일시스템 구조대로 백업
   1. Complete Dump : 파일시스템 구조자체부터 모든 파일을 백업 (주기적으로)
   2. Incremental Dump : 마지막 변경 이후 파일만 백업 (주기 사이에)

Incremental Dump

파일 백업 이전에 디렉토리 트리 구조를 먼저 백업한다. 이 때, 바뀐 파일에 관련된 구조만 백업하면 된다.디렉토리의 뼈대를 만든 후에 파일의 위치에 따라 백업한다.

<dump 절차>

1. 모든 파일 / 디렉토리 마다 1 bit 씩 대응되는 bitmap을 만든다.
2. 디렉토리는 모두 1로 세팅하여 우선 dump할 것이라고 표시한다.
3. 파일은 변경된 파일만 1로 세팅하여 dump할 것이라고 표시한다.
4. 변경된 파일이 존재하지 않는 디렉토리를 0으로 clear하여 dump하지 않을 것이라고 표시한다.
5. 무엇을 dump해야하는 지 결정되었으므로 디렉토리를 먼저보면서 bitmap 상 1로 표시된 디렉토리를 dump한다.
6. 변경된 파일들을 dump한다.

다른 고려사항

1. 백업으로부터의 회복

   백업 시 complete dump => incremental dump 하므로 complete dump를 회복한 후 incremental dump를 적용한다.

2. logical dump 문제

   파일이 link되어있어 이름이 2개 존재하는 경우에는 inode의 link-count를 보고 결정해야하므로 dump가 어려워진다.

   FFS의 파일에서 중간에는 기록이 없고 앞 뒤부분만 기록되어있는 큰 파일을 Hole이라고 한다. 이 파일은 백업 시 많은 용량을 차지하므로 따로 처리해주어야한다.

기록되어있지 않은 부분은 OS에서 대부분 0으로 채워서 전달하기 때문이다.
중간에 기록이 없는 경우는 seek로 r/w offset을 이동하였거나 sparse matrix인 경우이다.

3. dev 디렉토리 아래에 있는 디바이스 파일이나 파이프 파일은 dump하면 안된다.

파일 시스템 일관성

앞에 언급한 Journaling 파일시스템처럼 파일 시스템은 일관성을 유지하고 있어야한다. 파일이나 디렉토리를 수정하게 되면 그 정보를 저장하고 있는 여러 개의 블록(inode, 데이터 블록, bitmap, 디렉토리 엔트리 등)이 모두 수정되어야하는데 그렇지 않다면 일관성이 깨진 상태(inconsistent state)가 된다. 이런 일관성이 깨진 상태는 시스템이 갑자기 다운될 때 많이 발생한다.

일관성을 유지하기 위해 파일시스템에는 회복하는 프로그램이 있는데 UNIX 파일시스템의 경우 fsck, 윈도우 파일시스템의 경우 scandisk가 해당한다. 많은 파일시스템이 회복에 걸리는 시간을 줄이기 위해 journaling 기법을 사용한다.

사용하고 있는 블록을 기록해두는 bit map과 인덱스 블록 안에 기록되어있는 free block 번호들을 매치시켜서 일관적인지 확인한다. 가끔 일관적이지 않은 경우가 발생한다.

1. 파일 생성 시 free block을 할당해서 inode에 등록해야하는데, 할당 직전에 문제가 생긴 경우

   이 경우에는 free block을 다시 할당해주기만 하면 된다.

2. 파일 삭제 시 생긴 free block을 기록하려했는데 문제가 생겨서 다시 등록되는 경우

   free block이 2로 되어있으므로 1로 변경시켜주기만 하면 된다. 일관성을 회복하지 않으면 같은 블록에 2번 파일이 할당되어 큰 문제가 생긴다.

3. 데이터 블록이 2개의 파일에 할당되어있는 경우

   심각한 문제를 초래한다.

따라서 파일시스템은 반드시 일관성이 회복된 상태에서 동작해야한다.

 

파일 시스템 성능 향상

파일 시스템 성능의 병목점은 하드디스크와 같은 물리적 장치이다. 따라서 성능을 향상 시키려면 물리적 장치의 기능을 개선할 필요가 있다.

• Caching

  하드디스크에서 data를 읽어오는 횟수를 줄이자. 캐시는 disk캐시, buffer캐시, block캐시라고 불린다. 이는 CPU와 DRAM 사이의 캐시와는 다르다. 데이터를 읽어올 때 하드디스크 접근 전 DRAM에 있는 해당 캐시를 먼저 살펴본다. 이러한 디스크캐시에도 용량 제한이 있으므로 교체정책이 필요한데 역시나 LRU가 가장 적절하므로 약간의 수정을 통해 사용한다.

디스크 블록들을 double linked-list 형식으로 저장한 후 front는 LRU이고 rear는 MRU가 되도록 유지한다. 이 때 각 요소들을 임의로 찾기 위해 해시테이블을 이용해서 찾는 시간을 줄여준다. 해시 값이 같은 데이터 블록들은 double linked-list와 별개로 연결되어있으므로 빠르게 해당 블록을 찾을 수 있다.

블록들을 LRU위치에 넣어둘 것인지 MRU위치에 넣어둘 것인지는 해당 블록의 특성(순차적인지 아닌지)에 따라 결정될 수 있다. 또한 일관성과 관련된 블록은 빠르게 write-through해주는 것이 좋다.

• meta data 같은 중요한 정보의 경우 수정 즉시 하드디스크에 적어주는 Write-Through 방식을 사용하고 나머지 정보는 MS-DOS에서는 Write-Through 방식으로 Unix에서는 Write-back 방식으로 기록한다. 많은 파일시스템이 성능때문에 Write-back 방식을 사용하는 대신 일정주기(Unix의 경우 30초)에 한번씩 sync하는 방식으로 일관성을 유지한다.

• Read-ahead

  실제 리눅스에서도 사용되는 방식으로 파일 하나를 읽을 때, 뒷부분도 미리 읽어서 disk캐시에 넣어두는 방식이다. 캐시에 넣어둔 부분이 필요없는 부분이면 손해이기 때문에 점점 read-ahead 간격을 늘려가는 식으로 동작해야한다. 순차적으로 파일을 접근할 때만 성능이 좋다.

• 디스크 암 움직임 축소

  하드 디스크는 헤드가 원판 위에서 움직이면서 읽는데, 움직이는 시간 때문에 성능이 나빠진다. 따라서 파일 시스템의 구조를 바꾼다.

  기존에는 하드디스크를 일렬화해보았을 때 super block => block bitmap => inode bitmap => inode list => data block 순으로 기재되어있기 때문에 이 순으로 바깥쪽 헤드부터 안쪽 헤드로 들어가면서 디스크를 사용하였다. 한 파일을 읽으려면 inodelist와 data block을 계속 번갈아가면서 왔다갔다 해야하므로 헤드의 움직임이 많아서 파일시스템의 성능이 나빴다. 또한 트랙의 바깥 부분에 중요한 정보가 저장되어있기 때문에 하드디스크의 신뢰성이 낮았다.

따라서 Unix 파일시스템에서는 FastFileSystem이라는 FFS방식을 도입하였다. 이는 실린더 그룹이라는 개념을 사용한 기법인데, 실린더란 여러 개의 원판에 동일한 트랙들을 모은 것이고 이러한 실린더를 모은 것이 실린더 그룹이다. 이렇게 구성하게 되면 파일시스템은 전체공간을 몇 개의 실린더 그룹으로 나누는 새로운 분할방식을 사용하게 되며, 실린더 그룹의 특성 상 헤드가 한 번 자리 잡으면 거의 움직이지 않고 데이터를 다룰 수 있다.

FFS에서 디렉토리에 파일을 만들면 동일한 실린더 그룹에 파일을 할당하지만, 한 실린더 그룹에서의 파일이 너무 커서 용량이 부족하다면 인접 실린더 그룹의 데이터블록을 소모하도록 유도하는 등의 정교한 패턴 정책을 가지고 있다.

디스크가 여러 개의 실린더 그룹으로 나뉘므로 실린더 그룹마다 파일시스템 구조를 다르게 만들 수도 있다. 따라서 파일시스템은 이러한 정보도 유지해야하므로 Group descriptor를 도입하여 Super block에는 파일 시스템 전체 구조에 대한 형상정보를, Group descriptor에는 실린더 그룹 내의 형상정보를 기록한다.

Linux의 ext 파일시스템도 실린더 그룹 단위로 파일시스템을 따로 만든다.

• 이렇게 실린더를 이용한 기법은 구조가 훼손되더라도 한 그룹만 피해를 보는 안정성, 헤드를 거의 움직이지 않고 데이터에 접근할 수 있는 성능 측면에서의 장점을 보인다.

• 디스크 단편화 축소

  윈도우즈에서 제공하는 디스크 조각모음 (defrag)이라는 기능이 한 예이다. 디스크의 단편화를 축소하기 위해 빈공간을 통합하고 한 파일의 데이터 블록들을 순차적으로 바꾸어준다. 하지만 최근 이것이 뛰어난 성능향상을 가져다주지 못한다고 밝혀졌다.

 

The ISO 9660 파일 시스템

CD-ROM에서 사용하는 파일시스템이다. 엔트리가 MS-DOS의 FAT 파일시스템의 엔트리와 유사하다.

CD-ROM은 한 번 찍어내면 변경되지 않으므로 연속할당기법을 사용하는 것이 좋다고 Contiguous allocation 방식에서 언급하였다. 엔트리에는 (시작위치, 사이즈, ...)가 기록되며 데이터를 변경할 때는 미 사용 영역에 해당 데이터를 새로 쓴다.

파일의 이름은 8.3밖에 안되며 Symbolic link가 없고 디바이스 파일을 기록하는 Major, minor 번호가 없으며 디렉토리 depth가 짧다는 단점이 있다. 이러한 단점을 커버하기 위해 Unix 커뮤니티에서 확장판인 _'Rock Ridge Extension'_와 _'Joliet Extension'_을 구현하였다.

 

파일 접근 제어

파일시스템에는 여러 사용자의 파일이 있으므로 접근 제어 기법을 통해 보안성을 갖추어야한다.

• Access Control matrix

  행이 파일을, 열이 사용자를 나타내는 matrix를 사용하여 사용자와 파일사이의 관계를 RWED 접근제어 bit로 기록하는 방식이다. 이 방식은 matrix가 너무 큰 단점이 있다.

• Access Control List

  파일을 기준으로 사용자마다 무엇을 할 수 있는지를 기록한다. 아무것도 할 수 없는 사용자를 기타 사용자라고 기록하여 관리한다. Unix는 이를 약간 변형한 형태로 사용하여 사용자를 '소유자, 그룹소유자, 기타사용자' 3분류로 나눈다.

• Capability List

  사용자를 기준으로 파일마다 어떤 작업을 할 수 있는지를 기록한다. 즉, 사용자의 능력을 기록한다. 많은 OS가 사용하고 있는 방법이기는 하지만 파일이 아닌 시스템관리나 네트워크 통신 측면에서 해당 방법을 사용한다.

---

파일 시스템 구조

하드디스크 공간은 회전하는 원판이며 트랙 단위로 나눌 수 있다. 트랙은 섹터 단위로 쪼개어져있고 이를 일렬화하여 표현하면 다음과 같다.

대부분의 디스크는 위와 같은 구조로 되어있다. 가장 앞에는 MBR(Master Boot Record)이 위치하며 뒤에는 Partition table이 위치하여 파티션의 갯수, boot 파티션의 위치를 저장한다. 각 파티션에는 boot block, super block등의 구조가 있다. 파티션마다 다른 파일 시스템 및 운영체제가 동작할 수도 있다.

PC에 전원을 넣으면 ROM-BIOS가 MBR의 부트코드를 적재하고 실행한다. 그 후 boot partition을 찾아 OS의 부트 코드를 적재하고 실행하면 OS가 부팅된다.

 

MS-DOS FAT 파일시스템

MS 사에서 PC용으로 만든 파일시스템이다. 현재는 USB 드라이브용으로 사용하고 대용량 하드디스크에는 NTFS를 사용한다. FAT 파일시스템의 구조는 다음과 같다.

FAT block을 사용하는 것이 특징이며 FAT block table의 요소 하나하나는 실제 데이터블록과 대응된다. FAT block table은 데이터블록의 다음 데이터블록을 나타내는데에 사용되기도 하고 비어있는 free block을 나타내는 역할도 한다. 이는 이전에 설명했듯이 contiguos allocation 방식과 linked-list 방식을 지나 meta data를 FAT block table이라는 자료구조에 모아둠으로써 만들어진 구조이다.

현재 디렉토리는 데이터 블록의 주소로 기억하며 디렉토리를 만들면 테이블이 만들어지고 root 디렉토리를 제외한 디렉토리에서는 .과 ..이 기본으로 생성된다. 데이터 블록의 사이즈는 기록 시 byte 단위로 기록되지만 그림에는 편의상 block의 갯수로 표시해두었다. 데이터 블록의 위치는 FAT block table에서 관리하고 있기 때문에 연속적으로 할당되어있지 않을 수도 있다.

파일을 찾고자 할 때는 파일시스템이 알고있는 루트 디렉토리를 기준으로 찾아나가면 된다.

데이터 블록 엔트리에서 이름은 8글자 + 확장자 3글자로 구성되고 속성은 '디렉토리','파일','시스템파일'을 구분하기 위해 1bit를 사용하여 나타냈었다. 현재 reserved 영역은 없어졌으며 파일 이름을 확장할 수 있도록 가변길이 엔트리를 사용하고 있다.

데이터 블록 엔트리의 크기를 기준으로 FAT-12(12bit), FAT-16, FAT-32 순으로 발전하다가 현재는 NTFS를 사용한다.

 

UNIX V7 FS

초기의 유닉스 파일시스템이다. inode를 사용한 것이 특징이고 Super block에는 전체 파일시스템의 형상구조가 담겨있다. 실제로는 Super block과 inode 사이에 inode bitmap과 block bitmap이 존재한다.

inode의 크기는 버전마다 다르고 ext-4 파일시스템에서는 256byte이다. inode는 위치가 정해져있어 번호만 알면 바로 접근할 수 있는 것이 특징이다. 0,1번 inode는 전통적으로 사용하지 않고 2번 inode block부터 root 디렉토리를 기록하면서 사용된다. inode에는 이름을 제외한 파일의 모든 정보가 담겨있다. inode에 있는 데이터블록은 총 13개이며 10개의 directed 데이터블록과 3개의 indirected 데이터블록으로 구성되어있다. indirected 데이터블록은 싱글, 더블, 트리플로 구성되어있으며 포인터를 통해 index block에 접근한다.

모든 디렉토리 엔트리에는 .과 ..이 있으며 루트 디렉토리에서만 두 개의 inode가 같다. 디렉토리는 table 형태로 되어있으며 이름과 inode를 매핑해주는 역할을 한다. 현재 작업 디렉토리(CWD)도 inode 번호로 기억한다. 현재는 이름의 길이를 길게 할 수 있도록 가변 엔트리를 사용한다.

파일 접근 제어에서 다뤘듯이 Unix FS는 파일의 권한을 Access Control List(각 파일에 따른 사용자의 권한을 나타내는 list)로 표현한다. 사용자는 소유자, 그룹사용자, 기타사용자로 나누어지며 각 bit는 inode에 속성으로 저장되어있다. 이렇게 각 사용자의 권한에 대해 나타낸 bit는 inode 상에 저장되어있다. 해당 파일에 대한 접근은 파일을 열 때 검사하게 된다. 따라서 파일을 연 후 다른 사용자가 접근 권한을 바꿔도 파일을 열고있는 동안은 이전 권한이 유지된다.

<유닉스 파일시스템>

블록의 처음에는 역시 Boot 블록이 존재하고 Super 블록이라는 전체 파일시스템에 대한 형상정보를 담아두고 있는 블록도 있다. i-node 블록의 위치, 데이터 블록의 위치, 비트맵의 위치 등이 담겨있다.

그 후 나오는 i-node list는 리눅스에서 256byte정도로 구성되어있으며, 고정된 위치에 있기 때문에 임의접근하여 읽을 수 있다. 전통적으로 0번과 1번 inode는 사용하지 않고 2번 inode를 root 디렉토리용으로 사용한다. 2번 inode부터 root 디렉토리의 정보를 기록하고 서브 디렉토리와 디렉토리 내의 파일 정보를 데이터블록에 기록한다. 파일의 데이터 블록 정보는 inode에 기록하여 정해진 위치에 있는 inode에 접근하면 해당 파일의 데이터블록을 찾을 수 있도록 한다.

따라서 동작은 간단히 '파일이름'으로 사용자가 접근하고자 하면 데이터 블록(디렉토리)에서 해당 이름을 inode 번호로 매핑해주고, 해당 inode로 이동하여 파일의 정보가 저장된 데이터 블록 위치를 읽는다.

디렉토리는 이름과 파일의 정보(inode)를 연결해주는 역할을 한다.

inode 블록에는 데이터블록을 13개밖에 기록하지 못하는데, 이를 개선하기 위해 index블록을 가리키는 포인터를 추가해서 tree 형태로 사용한다. 따라서 10개이 데이터블록은 direct block이고 나머지 3개는 순차적으로 single indirect block, double indirect block, triple indirect block이다. 실제로 웬만한 크기는 double에서 커버 가능하다.

 

FAT vs UNIX

위에서 설명한 FAT 방식과 Indexed allocation 방식의 차이점을 보기 위해 FAT과 Unix 파일시스템을 비교해보자

OS	FAT	UNIX
파일 이름	데이터 블록	데이터 블록
파일 속성	데이터 블록	inode
파일 데이터	데이터 블록	데이터 블록

두 파일시스템 모두 이름을 데이터블록에 저장하는데, 처음에는 고정길이를 사용하다가 이름이 길어짐에 따라서 가변 엔트리를 사용하기 시작했다.

가변 엔트리 구조

a와 같이 엔트리마다 파일이름을 더 확장할 수 있는 가변길이 엔트리를 사용하기도 하고, b와 같이 heap에 파일이름을 모아두고 해당 위치를 포인터가 가리키게 하기도 한다. b 방법은 거의 사용하고 있지 않으며 FAT과 UNIX 파일시스템 모두 a와 같은 방법을 사용하고 있다.

FAT 파일시스템 엔트리

FAT 파일시스템의 데이터블록 엔트리인데, 앞에서 언급한대로 파일의 모든 정보가 들어있다. 사이에 Reserved 부분은 처음에 빈공간으로 나누었지만 현재는 이 영역을 모두 사용하고 엔트리도 가변으로 해서 파일 이름을 길게 저장할 수 있게끔 만들었다.

 

FFS (Fast File System)

FFS는 UNIX 파일 시스템의 현재 버전이다. 이전에 설명했듯이 FFS는 실린더 그룹을 만들어 헤드 arm의 움직임을 최소화하여 rotational delay(=seek time)을 줄이고자 고안한 파일시스템이다. 실린더 그룹은 헤드가 정착하면 더 이상 움직이지 않고 데이터에 접근할 수 있으며 인접 실린더 그룹으로 가기에 용이하다.

 

Linux EXT 2,3,4 FS

http://esos.hanyang.ac.kr/tc/2015gradproject8/i/entry/3

• Ext 2

  디스크 공간을 실린더 그룹 단위로 쪼갠 파일시스템

  Journaling은 사용하지 않는다.

• Ext 3

  Ext 2에서 Journaling 방식을 이용한 fsck 프로그램을 도입해서 회복시간을 줄인 파일시스템

• Ext 4

  Ext2, Ext3가 indirected 포인터 매핑 방법을 사용하는 것과 달리 Ext4는 extent라는 새로운 자료구조를 만들어서 사용한다. indirected 방식이 결국에는 모든 블록에 대한 포인터가 필요했지만, extent 방식은 여러 개의 블록을 연속적으로 묶어둠으로써 meta data의 크기를 줄였다.

  블록을 연속적으로 기록, 할당할 수 있으므로 더 효율적으로 관리할 수 있다.