1. Project Introduction

파일 시스템이란 파일의 실제 데이터와 메타데이터(파일의 위치, 크기, 소유자, 허가권 등, ls -al로 볼 수 있는 파일정보)를 유지/저장하는 체계로써 파일에 이름을 붙이고, 저장이나 검색을 위해 논리적으로 그것들이 어디에 위치시켜야 하는지 등을 나타내는 방법이다.

윈도우, OS/2, 매킨토시 및 유닉스 기반의 운영체계들은 모두 파일들이 어딘가에 계층적인 구조로 위치하는 파일 시스템을 가지고 있다. 파일은 계층구조 내의 올바른 디렉토리 또는 서브디렉토리 내에 놓여진다.

2. Project Goals

앞서 설명한 구조의 파일시스템을 구현하는 것으로, 모든 구현이 완료된 후에 disk.img 파일을 읽어와 마운트 시킨 후, 랜덤으로 10개의 파일 이름을 할당 받은 후 올바른 구조에 따라 해당 파일 이름의 데이터를 출력하는 것이다. 따라서 Mount 완료한 super block의 정보를 모두 출력하고, inode table에 들어있는 모든 정보를 파악하여 원하는 파일을 올바르게 읽어오는지 확인하고 출력하는 것이 이번 프로젝트의 목표이다. 뿐만 아니라 write기능을 추가하여 해당 파일의 데이터를 사용자가 원하는 데이터로 수정될 수 있도록 구현하는 것도 이번 프로젝트에서 해야 할 목표이다.

본 프로젝트를 구현함에 있어 파일시스템의 개념에 대해 이해하고, 구조, 특징 역할등을 파악하여 파일시스템이 필요한 이유에 대해서 생각하며, 각종 파일시스템의 종류를 알아보고 차이점을 찾아 파일시스템에 대한 이론을 숙지하는 것이 이번 프로젝트의 목적이다.

파일시스템의 이론을 확립하여 실제 파일시스템에서 작동하는 open, read, write를 구현하며, 추가 directory생성, 다수 사용자의 공유 파일사용 등 여러 명령을 어떻게 가능하도록 할지에 대해서 알아보도록한다.

3. Concepts used in CPU simulation

1) 파일시스템(File System)

1-1) 파일시스템이란?

컴퓨터에서 파일이나 자료를 쉽게 발견 및 접근할 수 있도록 보관 또는 조직하는 체제를 가리키는 말이다. 저장 매체의 크기가 증가 할수록 보관하는 파일의 수 또한 점점 증가하게 되어 별도의 관리 시스템이 필요하다. 따라서 개발된 것이 파일시스템이다. 파일시스템 종류에는 UFS, FAT16, FAT32, NTFS, ext2, ext3, ext4, HFS+ 등이 있다.

1-2) 파일이란?

파일은 프로그램 또는 데이터 등과 같은 정보들의 집합을 말한다. 이러한 정보를 저장할 수 있는 기억장소 공간은 디스크에 할당되어 있으며 디스크에 존재하는 여러 파일들은 각자 고유한 이름을 가짐으로서 구별된다.

1-3) 파일시스템 구조

파일시스템은 파일에 대한 메타데이터 즉, 파일 데이터의 데이터가 저장된 영역과 실제 데이터가 기록된 영역 2가지로 구분된다.

메타 영역(Meta Area) : 데이터 영역에 기록된 파일의 이름, 위치, 크기, 시간정보, 삭제유무 등 파일의 정보
데이터 영역(Data Area) : 파일의 데이터

1-4) 파일시스템 특징

⦁ 계층적(Hierarchical) 디렉터리 구조를 가진다.
⦁ 디스크 파티션 별로 하나씩 둘 수 있다.

1-5) 파일시스템 역할

⦁ 파일관리 : 파일 저장, 참조, 공유
⦁ 보조 저장소 관리 : 저장 공간 할당
⦁ 파일 무결성 메커니즘 : 파일이 의도한 정보만 포함하고 있음을 의미
⦁ 접근 방법 : 저장된 데이터에 접근할 수 있는 방법 제공

1-6) 파일시스템 목적

⦁ HDD와 메인 메모리 속도차 줄이기
⦁ 파일 관리 용이
⦁ HDD의 막대한 용량을 효율적으로 이용

1-7) 파일시스템은 왜 필요한가?

파일은 정보를 저장할 수 있는 기억장소공간이 디스크에 할당되어 있으며 디스크에 존재하는 다른 파일들과 구별할 수 있는 고유의 이름이 존재한다. 여기서 디스크란 소멸하지 않는 기억장치이다. 다시 말해 디스크에 저장된 데이터나 프로그램, 즉 파일은 프로세스가 수행을 완료하고 사라진 후에라도 여전히 남아있게 된다. 디스크는 고정된 블록단위로 데이터를 저장하게 된다. 모든 디스크의 입력과 출력은 섹터(물리적 레코드)단위로 이뤄진다. 연속적인 바이트로 구성된 파일이 일정 바이트로 나뉘어져 디스크 곳곳에 저장된다. 이때, 한 가지 문제점은 사용자는 블록에 관한 정보를 아무것도 모른다는 점이다. 메모리는 바이트 단위로 읽어 들일 수 있지만 디스크는 바이트 단위로 읽어 들일 수 없는 구조로 되어 있다. 그렇기에 파일 시스템이 파일과 디스크 블록 간에 밀접한 연결 작업을 해주어야 한다.

2) 파일시스템 마운팅

파일이 사용되기 전에 수행하는 작업으로 파일 시스템은 프로세스들에 의해 사용되기 전에 mount 되어야 한다.

즉, 운영체제(OS)에게 장치의 이름과 파일 위치가 주어진다. 일반적으로 마운트 포인트는 장착되는 파일 시스템이 부착될 비어있는 디렉토리이다. 운영체제(OS)는 장치가 유효한 파일 시스템을 포함하는지 확인한다. 그 과정은 장치 드라이버가 장치 디렉토리를 읽고 디렉토리가 유효한 포맷을 가지고 있는지 확인하도록 요청함으로써 이루어진다. 운영체제는 파일 시스템이 지정된 마운트 포인트에 장착되었음을 디렉토리 구조에 기록한다. 이 기법은 운영체제가 디렉토리 구조를 순회하고 파일 시스템을 적절히 교체할 수 있게 한다.

3) 파일시스템(File System) 모델

3-1) 슈퍼블록(Super Block)

UFS(Unix File System)에서 슈퍼블록은 수많은 정보들을 포함하고 있다. 이러한 값들로 파일시스템에 레이아웃을 정의 할 수 있는 것이다.
super block에 있는 filesystem 상태를 기술하는 여러 field를 보면,

• filesystem의 크기
• filesystem 내의 free block 수
• inode의 list 크기
• filesystem 내의 free inode 수
• filesystem 내의 free inode의 list
• free inode list의 다음 free inode의 index
• free block list와 free inode list를 위한 lock field들이 있다.

3-2) inode(Index node)

process가 disk의 file을 access하기 위한 도구로 'inode table = inode list'를 이용한다.
어느 한 file이나 directory가 만들어질 경우 그에 해당되는 하나의 inode가 만들어 지고 그 inode가 inode list에 등록되는데, 이 때 등록된 번호를 'inode number'라 한다.
inode 하나는 64 byte의 크기이고, 어떤 file이나 directory에 대한 모든 정보가 해당 inode에 담겨져 있어 file을 대표한다.

하나의 inode에 담겨진 내용을 보면 다음과 같다.
- file type, access mode
- link된 갯수
- file의 크기(byte수)
- file이 마지막으로 access, write되고 inode가 change된 시간
- 'direct'로 data block을 가리키는 12 pointer의 array
- 'indirect' pointer
- file에 의해 사용된 physical block의 수

※ file의 크기와 'inode의 data block pointer'의 관계

• file의 최대 크기 : ① + ② + ③ 하면 된다.
  ① 'direct' pointer 12 개 : 8192 x 12 / 1024 = 96 Kbyte
  ② 'single indirect' pointer 1 개 : 8192 x 2048 / 1024 = 16 Mbyte
  ③ 'double indirect' pointer 1 개 : 8192 x 2048 x 2048 /1024 = 32 Gbyte

3-3) Data block

데이터블록은 inode 에 포함된다. inode 는 몇 개의 data block 을 포함하고 있으며, 각 데이터 블록은 파일들의 데이터를 실제로 저장하고 있다.

3-4) Indirection block

간접 블록은 추가적인 데이터 블록을 사용하기 위한 포인터들이 할당되는 공간이다. 실제로 inode 는 적은 수의 데이터블록을 갖고 있으며 더 많은 데이터블록이 필요할 경우 이를 동적으로 가리킬 포인터가 저장된다.

3-5) directory file

• directory는 file 이름들의 저장 창고와 같다.

• directory는 각 file의 이름과 그 file 자체를 서로 연결시켜 주는 역할을 하므로 file 시스템의 전체적 구조를 결정지어 준다.

• directory는 많은 file들을 포함하며 또한 마찬가지로 여러 file들을 갖는 sub directory를 가질 수 있다.

• directory는 ordinary file과 구별되는 개념이지만 읽힐 때는 ordinary file과 똑같이 행동한다.

• 모든 directory는 적어도 '.'와 '..'라는 file을 가지고 있어야 하는데, '.'은 directory file 자체를 지시하고 '..'은 그 directory의 상위 directory를 나타낸다. 이들 file들을 이용하여 전체 file 시스템을 루트에서부터 차례로 내려오면서 모든 file을 탐색할 수 있다.

• pathname(경로명)
  모든 file은 자신이 속해 있는 directory가 있으므로 어느 한 file을 지정하기 위해서는 그 file명은 물론 그 File이 속해 있는 directory name도 지정해야 한다. 따라서 file을 지정하기 위해서는 관련 directory name과 file명 그리고 '/'로 이루어지는 pathname(경로명)이 필요하다.
  - 절대 path
  - 상대 path

3-6.1) 디렉토리 구조(Directory Structure)

 1단계 디렉토리 (Single Level Directory)

모든 파일이 한 개의 디렉토리 밑에 있는 개념으로 같은 디렉토리에 모든 파일이 존재 하므로 각 파일은 유일한 이름을 가져야 한다. 따라서 다수의 사용자에게 제약이 크다.

 2단계 디렉토리(Two Level Derictory)

각 사용자는 자신만의 사용자 파일 디렉토리(User File Directory, UFD)를 가지고 있으며 UFD는 비슷한 구조를 가지고 있지만 각 디렉토리에는 오직 한 사람의 파일 만을 저장한다.

사용자의 작업이 시작되거나 시스템에 사용자가 로그인을 통해 접속하면 시스템은 마스터 파일 디렉토리(Master File Directory, MFD)를 먼저 탐색한다. MFD는 사용자 이름이나 계정 번호로 색인되어 있으며 각 항목은 그 사용자의 UFD를 가리키고 있다.

2단계 디렉토리 구조에서 파일 이름이 충돌하는 문제는 어느 정도 해결하였으나 한 사용자의 UFD를 다른 사용자가 접근을 할 수 없기 때문에 파일을 공유해서 사용하는 경우는 공유가 불가능하다. 따라서 접근을 허용하려면 한 사용자가 다른 사용자의 디렉토리에 있는 파일을 지칭 할 수 있어야 한다.

 트리 구조 디렉토리(Tree Structure Directory)

여러 단계로 확장하는 일반적인 방법의 임의의 높이를 갖는 트리 구조이다. 일반 사용자들에게 자신의 서브디렉토리(subdirectory)를 얼마든지 만들 수 있게 해준다. 트리는 가장 일반적인 디렉토리 구조이다.

 비순환 그래프 디렉토리(Acyclic Graph Directory)

트리 구조는 파일 또는 디렉토리의 공유를 허용하지 않는다. 비순환 그래프는 디렉토리들이 서브디렉토리들과 파일 들을 공유할 수 있도록 허용하는 구조로 똑같은 파일이나 서브디렉토리가 서로 다른 서브디렉토리에 있을 수 있다. 비순환 그래프는 트리 구조 디렉토리 방식을 일반화한 것이다.

파일을 공유하는 방법으로는 링크(link)라 불리는 새로운 디렉토리 항목을 만드는 것과 디렉토리들이 동일한 항목 내용을 복사해서 가지고 있는 방법이 있다. 후자의 경우에는 일관성에 문제가 발생한다. 링크의 경우는 다른 파일이나 서브디렉토리를 가리키는 포인터를 가지고 참조한다. 디렉토리를 검색할 때 디렉토리 항목이 링크로 표시되어 있다면 실제 파일 이름을 링크 정보에 포함되어 있다. 실제 파일에 대한 경로 이름을 사용함으로써 링크를 해석(resolve) 한다.

 일반 그래프 디렉토리(General Graph Directory)

비순환 그래프 트리 구조에 있어서 중요한 문제점은 순환이 발생하지 않도록 어떻게 보장하느냐는 것이다. 2단계 디렉토리부터 시작해서 사용자가 서브디렉토리를 생성하면 트리 구조가 형성된다. 단순히 새로운 파일이나 디렉토리를 기존의 트리 구조 디렉토리에 추가하는 것은 트리 구조의 성질을 유지 하지만 기존의 트리에 새로운 링크를 추가하면 트리 구조는 파괴되고 일반적인 그래프 구조가 될 수 있다.

비순환 그래프의 장점은 파일을 검색하고 파일에 대한 참조의 존재 여부를 결정하는 알고리즘이 비교적 간단하다는 것이다. 하지만 성능적인 측면에서 비순환 그래프의 공유 부분을 두 번 순회하는 것은 좋지 않다. 잘못 설계된 알고리즘은 계속 탐색하고 종료하지 못하는 무한 루프에 빠질 수도 있다. 한 가지 해결책은 한 번에 검색 할 수 있는 디렉토리의 숫자를 임의로 제한하는 것이다.

3-7) Meta data

파일 사용자 ID, 파일 형태, 크기, 저장장소, 정보의 장소(offset), 버퍼, 시간 정보(생성시간, 최근 읽기,쓰기된 시간)등의 정보들이 저장된 데이터를 의미한다. 파일에 접근하는데 필요한 정보를 가진 Meta data가 있어야 파일이 제대로 관리될 수 있으며 이들은 디스크 내부에 파일과 별도로 저장된다.

3-8) 버퍼 캐쉬(buffer cache)

파일 사용자와 디스크의 사이에 자리 잡고 완충 역할을 하게 되는 장치이다. 파일을 사용할 때마다 디스크에서 일일이 읽어오려면 속도가 상당히 느리다. 따라서 처음 읽은 파일은 버퍼 캐쉬에 내용을 저장해 둠으로써 이후 사용자가 동일한 파일을 사용하길 원할 때 읽어오는 속도를 높일 수 있는 것이다. 바로 파일에 접근하는 것도 지역적 성격을 갖고 있기 때문에 버퍼 캐쉬를 사용할 수 있는 것이다. 그러나 버퍼 캐쉬가 무한정의 메모리를 사용할 수는 없다. 그러므로 용량의 제한으로 버퍼 캐쉬에 저장된 목록을 교체해야 한다. 이때 앞서 메모리 관리에서 배운 LRU Policy가 일반적으로 쓰인다. 이러한 버퍼 캐쉬는 시스템에 하나만 존재한다. 이유는 버퍼 캐쉬 상에 변화가 생기면 해당 변화를 다른 장치들도 알고 있어야 하기 때문이다.