운영체제 - File System 간단정리

File System

파일 시스템은 2차 저장장치의 느린 속도를 극복하기 위해 온갖 기법이 들어가서 매우 복잡하다.

여기서 하는 정리는 수박 겉핥기 정도이다.

구체적으로 더 공부하고 싶다면 대학원에 진학하면 된다

 

---

 

File 기본 개념

File 이란

파일이란 데이터와 프로그램을 위한 '그릇'이다.

프로세스처럼 데이터와 프로그램이 logical address space에 연속적으로 존재한다.

 

File Structure 종류

OS와 프로그램이 구조를 결정한다.

1. None: words, bytes의 연속
2. Simple record structure: 레코드 단위, 한 줄이 한 의미를 가짐
   - Lines: Fiexd(라인 길이 고정), Variable(라인 길이 가변)
3. Complex Structures
   - Formatted document: hwp, word, ppt 같이 그 자체적으로 내부구조가 있어서 특정 프로그램이 만들어내는 구조
   - Relocatable load file: 윈도우즈의 dll파일 같은 것

File Attribute

'File Metadata' 라고 부른다. 보통 Directory에 이 메타 데이터가 저장되고 관리된다. 실제 파일 데이터들은 메타 데이터의 위치를 따라가면 디스크 어딘가에 있는 식이다.

1. Name
2. Type: .exe, .txt와 같은 확장자를 말함
3. Location
4. Size
5. Protection: Read, Write, Execute의 권한 설정(누가 할 수 있는지 각각 설정할 수 있음). 이후 더 구체적으로 언급함
6. Time, date, and user identification: Data for protection, security, and usage moitoring

File Operations

1. create
2. write
3. read
4. repositioning within file - file seek
   (파일의 offset 바꾸는 것)
5. delete
6. truncate: 파일의 껍질은 냅두고 내용물을 다 지우는 것
7. open(Fi): 파일의 메타데이터를 디스크에서 메모리로 올리는 것
   -> 파일을 읽는 것은 path를 하나하나 찾아가야한다는 점 + 2차 저장장치의 느린속도로 인해 오래 걸리는 작업이다. 그래서 한번 힘들게 읽어온 정보를 메모리에 올려놓고 I/O 속도를 빠르게 가져가겠다는 의도이다.
8. close(Fi)

 

---

 

Directories

Directory

우리가 일반적으로 알고 있는 Folder이다(윈도우즈 기준임). 파일들을 편리하게 관리하기 위해 사용된다.

유저와 파일시스템 둘 다에게 이점이 있다.

1. For user: 파일을 체계적으로 관리할 수 있음
2. For file system: 편리한 naming interface를 제공함. 디렉토리가 있으면 파일의 유일한 이름을 결정할 수 있기 때문이다. 파일이름에는 디렉토리 이름도 다 포함되기 때문에 우리에게 같은 파일이름으로 보여도 다른 디렉토리에 동시에 존재할 수 있기 때문이다.

대부분의 시스템은 Multi-level 디렉토리를 지원한다. 

또한 대부분의 시스템은 'current directory'라는 개념을 지원해서, 파일의 상대적인 위치를 나타낼 수 있다(현재 디렉토리 기준으로 파일은 ~~있음). 이와 대조되는 개념은 절대적인 위치가 된다(루트를 기준으로 한 것).

 

A Directory Entry

• 디렉토리는 파일의 메타데이터를 'directory entry'라는 자료구조에 담아서 저장함. 그래서 형식에 맞게 저장됨.
• OS는 최근에 접근한 파일의 디렉토리 엔트리를 메모리에 캐싱해둔다.
  -> 그래서 메모리에 있는 메타데이터가 최신으로 유지될 텐데, 이를 하드디스크의 메타데이터랑 일치되도록 관리해주어야 한다. 그렇지 않다면 데이터가 날아갈 수도 있다.
• 디렉토리도 하나의 파일로 취급된다.

 

Unix Directory Structure

유닉스 계열의 OS는 디렉토리 엔트리에 파일의 메타데이터를 다 저장하는 것이 아니라, 

파일의 이름 + inode를 가리키는 포인터만 저장해둔다.

inode는 파일의 이름을 제외한 나머지 메타데이터들을 저장한 자료구조이다.

inode들은 연속적으로 있을 필요가 없고, 디렉토리 엔트리에 가벼워짐에 따라 디렉토리가 가벼워진다.

 

Directory Implementation

디렉토리의 low-level 구현은 두 가지 방법이 있다. 

1. 디렉토리 엔트리를 Linear list로 구현하기
   -> 구현은 쉬우나, 당연히 linear search를 해야해서 시간이 걸린다는 오버헤드가 있음
2. Hash Table
   -> 똑같이 linear 하지만, 해쉬를 만들어서 서치 타임을 상수시간으로 만든다. 당연히 collision문제가 있고 이는 일반 해시에서 일어나는 문제와 동일하게 해결방법을 적용하면 됨(체이닝, 오픈 어드레싱 등 여러 방법들)

디렉토리의 high-level 구현은 5가지 방법이 있다.

1. Single-Level Directory
   루트 밑에 모든 파일이 존재하는 것(디렉토리가 하나). 이름 충돌, 파일들을 그룹핑할 수 없다는 문제로 실제로 사용이 불가능.
2. Two-Level Directory
   사용자별로 디렉토리를 두는 방식. "Pathname" 라는 개념이 생겼다. 다만 single-level과 같은 문제로 사용 불가능.
3. Tree-Structured Directories
   Subdirectory를 허용하고, 그룹핑도 가능하고, Home directory(처음 시작하면 들어가는 default dir) 개념이 생긴다. 또한 Current(working) directory와 absolute, relative pathname의 개념도 생겼다. 
   단, 디렉토리를 삭제할 때 하위 디렉토리까지 삭제를 할지 안할지를 결정해야한다. 
   디렉토리가 비워져 있어야 삭제가 가능하게 하면 안전하나 편의성이 떨어지고(지울 때마다 다 비워야 하니깐), 디렉토리에 파일이 있든 없든 삭제가 가능하면 편리하지만 위험할 수 있다. 이것은 OS가 어떤 정책을 택하냐에 따라 달라진다.
4. Acyclic-Graph Directories
   -> 같은 하위디렉토리 혹은 파일이 두 개 이상의 다른 디렉토리에 존재할 수 있는 것.
   이것은 '공유' 때문에 생긴 개념이다. 여기서 생길 수 있는 문제는 traverse problem(같은 파일 두번 방문), delete problem이 있는데 delete위주로 살펴보자
   
   우선 파일 하나를 두 개의 폴더인 A, B에서 파일 X를 공유한다고 가정하자. 이 경우 파일에 접근하기 위해 Link를 해주어야 하고 이는 Symbolic link와 Hard link로 나뉜다.
   
   1) Symbolic link: 파일의 pathname만 저장하기
   파일에 접근할 수 있도록 pathname만 저장하는 것이다. A폴더에 X파일이 저장되어있고, B가 X를 이제 저장하려 할 때는 X의 pathname만 저장하는 것이다. 단 이 경우 A폴더에서 X파일을 삭제하면 B폴더는 허공을 가리키게 된다(dangling reference). 
   
   2) Hard link: 디렉토리 엔트리를 카피하기(얘가 디폴트이다)
   B 폴더에 X의 디렉토리 엔트리를 카피해서 저장하는 것인데, 이 경우에도 두 가지 문제가 생긴다
     (1) 무결성 문제(A, B에서 X가 최신으로 유지되야 함): 이건 OS가 해결해야 함
     (2) X파일을 실제로 어떻게 삭제할지: reference count를 유지한다. 처음에 A, B가 X를 가리키고 있으면 ref count는 2일 것이다. 이후 A에서 X를 지우면 ref count가 1이 되고(아직 파일은 살아있음) B에서도 X를 지우면 ref count가 0이 되면서 이제 실제로 X가 삭제되는 것이다(이제 X파일에 접근할 수 있는 폴더가 없으니깐). X파일에서 나를 가리키는 애들이 몇 명인지 세고 있다가, 값이 0이 되면 실제로 파일을 삭제하는 것이다. 
5. General Graph Directory(cycle 허용한 것)
   하위 디렉토리가 상위 디렉토리를 서브디렉토리로 가질 수 있다. OS 디자이너가 이런 방식을 채택할 수도 있는데 traverse, delete를 위해 복잡한 알고리즘이 필요하다.
   Traverse에서는 무한루프를 피하는 것이 필요하고, Delete에서는 ref count가 항상 0 이상이기 때문에(자기 참조 혹은 cycle 떄문) 파일이 삭제가 안 될 수 있다. 그래서 이를 위한 GC(garbage collection)이 필요하다.
   이런 복잡성 때문에 잘 안쓰고, cycle이 없도록 알고리즘을 돌리거나(돌려서 cycle이 없어야 링크 가능) 파일에 대한 링크만을 허용하는 방법을 쓴다(서브 디렉토리를 허용 X. 근데 이건 당연히 잘 안 쓰겠지).

Operations Performed on Directory

1. Search for a file: 당연히 빨라야 함
2. Create a file
3. Delete a file
4. List a directory
5. REname a file
6. Traverse the file system: 쭉 훑어 보는 것

 

Protection

파일의 소유자/생성자가 '누가 파일에 대해서 어떤 oper가 가능한지'를 결정한다.

파일에 대한 Read, Write, Execute 의 접근 권한 설정이다.  

접근 권한 설정은 matrix로 유지할 수 있으나 matrix가 너무 커지기 때문에 Unix는 유저를 3개의 카테고리로 나누어서 파일에 대한 권한을 관리한다

ex) file1: rwx rwx rwx  // 각각 user, group, others에 대한 접근권한을 나타냄. 비트로 나타낼 수 있겠지?

user는 owner를 의미하고, group은 owner가 속한 그룹, others 는 그 외 나머지를 말한다.

 

접근의 종류는 read, write, execute인데 이를 RWX라고 하고 3비트로 나타낸다(110, 110, 001 등).

UNIX에서는 이를 10진수로 변환해서 다음과 같은 명령어를 사용해서 권한을 설정한다.

chmod 761 game  // game이라는 파일에 대해서 owner에겐 111의 권한, group에겐 110의 권한, others에겐 001의 권한을 줌.

 

File-System Structure

파일 시스템의 코드는 OS에 있지만 모든 정보(파일 관리를 위한)는 하드디스크에 존재한다.

또한 파일 시스템은 여러 layer로 구성되어 있어 무겁다.

그러다 보니 Open() system call은 다음과 같은 행위를 한다.

• 파일의 메타데이터를 메모리에 올린다 -> directory structure에 대한 서치를 함
• Open-file table을 유지한다 -> 메모리에 올라온 (opened)파일에 대한 메타데이터를 테이블에 저장한다
• File descirptor(file handle, file control block)을 사용한다. -> open-file table에 대한 인덱스이다. 이를 이용하면 테이블에 빠르게 접근하고 빠르게 파일에 접근할 수 있게 된다. C언어 에서 fopen()에 대한 리턴 값이 이 File descriptor이다.
• 왜 이렇게 하는가?
  -> Directory search는 오래 걸리기 때문. 일단 힘들게 파일 접근 한번 했으니깐, 다시 안 하게 저장해두자는 것.

 

---

 

Allocation of File Data in Disk

실제 파일의 allocation, free space management, performace를 위한 기법, recovery 방법은 추가 필요.

 

Allocation

1. Contiguous Allocation
2. Linked Allocation
3. File-Allocation Table(FAT / for windows)
4. Indexed Allocation
   1) Linked scheme
   2) Two-level index
   3) Combined(UNIX)

 

Free space management

1. Bit map or bit vector
2. Linked list
3. Grouping
4. Counting

Performance

1. Disk cache
2. Free-behind and Read-ahead
3. Virtual disk (RAM disk)
4. Directory entry cache (dentry cache)

 

Recovery

• Consistency checker
• Journaling
• Backup