2022. 6. 11. 12:55ㆍMajor`/운영체제
File
"A named Collection of related Information"
논리적으로는 byte단위로 저장되어있다고 볼 수 있지만 실제 물리적으로는 "Block"단위로 Disk에 저장되어 있다
이 Block들이 Disk 여러곳에 흩어져 있는데 파일은 "흩어진 관련된 Block들을 모아놓은 것"이다
- 당연한 말이지만 파일은 "비휘발성 기억장치(Disk)"에 저장되어 있다
File Attribute (File's Metadata)
파일 내부의 내용이 아니라, 파일을 관리하기 위한 정보들을 File's Metadata라고 한다
- 파일 이름
- 유형
- 저장된 위치
- 파일 사이즈
- 접근 권한(r w x)
- 시간 (생성된 / 변경된 / 사용된)
- 소유자
- ....
▶ 그러면 OS입장에서는 "파일의 구조"에 대해서 얼마나 자세히 알아야 할까?
OS가 파일의 구조를 더 자세히 알면 알수록 user는 편해지지만, 그에 반해서 OS 내부 코드는 더욱더 복잡해질 수 있다
현대 OS들은 파일의 구조에 대해서 굉장히 적은 support를 부여한다
File 내부구조는 일반적으로 "512 bytes : Block"으로 구성되어 있다. 따라서 일정한 크기의 Block이므로 "Internal Fragmentation"이 발생할 수 있다
Directory
디렉토리란 파일 시스템 내부에 존재하는 것으로, 효율적인 파일 사용을 위해서 디스크에 존재하는 파일에 대한 여러 정보를 가지고 있는 "특수한 형태의 파일"이다
Directory는 하위 파일들의 Metadata 일부를 보관하고 있는 특별한 파일이다
- 각 파일의 {이름, 위치, 크기, 할당방식, 형태, 소유자, 계정정보, ...}를 보유
Directory가 제공해주는 기능은 다음과 같다
<Efficiency>
파일을 빠르게 찾을 수 있도록 Efficiency를 제공한다
<Naming>
파일의 이름을 지을 때 제약조건이 없도록 해준다
<Grouping>
유사한 파일들을 Grouping해준다
1. Single-Level Directory
모든 파일을 하나의 디렉토리 내에 위치해서 관리되는 구조이다
- 모든 파일이 Unique한 이름을 가져야 한다
- 모든 파일이 같은 디렉토리 내에서 유지가 되므로 user가 파일에 대한 이해를 쉽게 할 수 있다
- 파일이나 user수가 증가하게 되면 파일 관리가 복잡해진다
>> Naming & Grouping 관련 문제가 발생한다
2. Two-Level Directory
중앙에 Master File Directory(MFD)가 존재하고, 그 아래에 각 user별로 서로 다른 User File Directory(UFD)가 존재한다
<MFD>
- 각 user들의 이름, 계정 번호, UFD를 가리키는 포인터를 보유한다
- 결론적으로 UFD를 관리한다
<UFD>
- 오직 하나의 user가 가지고 있는 파일에 대한 정보만 갖고 있다 :: 해당 user의 파일을 관리
- 하나의 UFD에는 Unique한 파일 이름을 사용해야 하지만, 서로 다른 UFD간에는 동일한 파일 이름이 존재해도 된다
이 방식은 각 user가 서로 다른 user의 UFD를 검색할 수 없기 때문에 업무 협력/파일 공유가 어렵다
특정 파일을 저장할 때는 "User Name + File Name}을 같이 지정해야 하기 때문에 파일 이름이 길어진다
3. Tree-Structured Directory
하나의 Root Directory 아래로 여러개의 Sub Directory로 구성된 구조이다
- DOS/Windows/UNIX 등의 OS에서 사용되는 디렉토리 구조이다
- 각 디렉토리는 {서브 디렉토리 or 파일}을 가질 수 있다
- 서로 다른 디렉토리 내에 동일한 이름의 파일이나 디렉토리를 생성할 수 있다
- 디렉토리 {create / drop}이 편리하다
- 디렉토리 탐색에는 Pointer를 사용하고, 경로명은 {Absolute / Relative}를 사용한다
4. Acyclic-Graph Directory
Acyclic Directory는 하위 파일이나 하위 디렉토리를 공동으로 사용할 수 있는 것으로, Cycle이 허용되지 않는 구조이다
- 디스크 공간 절약 가능
- 하나의 파일이나 디렉토리가 여러 개의 Path Name을 가질 수 있다
- 디렉토리 구조가 복잡하고, 공유된 하나의 파일을 탐색할 경우 다른 경로로 2번 이상 찾아갈 수 있기 때문에 시스템 성능이 저하될 수 있다
- 공유된 파일을 삭제할 경우 Dangling Pointer가 발생할 수 있다
>> Dangling Pointer는 Pointer입장에서 "나는 이제 아무것도 가리키지 않는 포인터가 되었구나"이다
5. General Graph Directory
트리구조에 Link를 추가해서 Cycle을 허용하는 그래프 구조이다
- 디렉토리와 파일 공유에 완전한 융통성이 존재한다
- 탐색 알고리즘이 간단하고, 파일/디렉토리를 access하기 쉽다
- 사용되지 않는 디스크 공간을 되착기 위해 Garbage Collector가 필요하다
- 불필요한 파일을 제거해서 사용 공간을 늘리기 위해서 Reference Counter가 필요하다
File Operations
Create : 파일 생성
Write : 파일에 대한 쓰기
Reposition within file (LSEEK)
파일의 크기는 굉장히 크기 때문에 어느 위치를 읽고 쓸지를 가리키는 "포인터"가 존재한다
>> Reposition은 "현재 접근하고 있는 위치를 수정"해주는 연산이다
Delete : 삭제
Truncate : 내용 전부 삭제
Open : 파일 열기
Close : 파일 닫기
※ Open File
파일에 대한 open()이란 "해당 파일의 Metadata를 메모리에 적재하는 행위"이다
예를 들어서 open("/a/b/c")를 통해서 최종적으로 Disk로부터 파일 "c"의 metadata를 메인 메모리에 올리는 과정을 살펴보자
- Root Directory : "/"를 open해서 그 안에서 File "a"의 위치를 획득
- Root Directory의 Metadata 확인 → File "a"의 Metadata를 메모리에 올리기
- 파일 "a"를 open하고 read해서 그 안에서 File "b"의 위치를 획득
- File "a"의 Metadata 확인 → File "b"의 Metadata를 메모리에 올리기
- 파일 "b"를 open하고 read해서 그 안에서 File "c"의 위치를 획득
- File "b"의 Metadata 확인 → File "c"의 Metadata를 메모리에 올리기
- 파일 "c"를 Open
열려진 파일을 관리할때는 "여러 데이터"가 필요하다
<File Pointer>
각 프로세스가 파일 어느부분을 읽고있는지
>> Locally하게 OS가 프로세스마다 관리
<File-Open Counter>
해당 파일이 Open된 횟수
>> Global하게 OS가 딱 하나 관리
<Disk Location of the File>
파일이 Disk 어디에 존재하는지
<Access Right>
파일을 정상적으로 access할 수 있는지 없는지
Open File의 Locking에 대한 정보는 다음과 같다
<Shared Lock vs Exclusive Lock>
Shared Lock : Reader's
Exclusive Lock : Writer's
<Mandatory vs Advisory>
Mandatory
- Kernel이 직접적으로 관여하는 Kernel Level Lock이다
- 특정 파일에 어느 프로세스가 이미 접근하고 있으면 다른 프로세스는 Lock이 풀릴때까지 대기한다
- Linux상에서 File System Mount할 때 -o mand로 설정해야 한다
- Linux의 default는 Mandatory Lock이 설정되어 있지 않다
>> Lock된 파일 접근에 대한 Deadlock이 발생할 수 있기 때문에 주의해야 한다
Advisory
- Kernel이 관여하지 않는 Locking이다
- process level에서 Lock 여부를 확인해서 처리
- A 프로세스가 파일을 Lock해도 B 프로세스에서 파일 Lock을 확인하지 않으면 해당 파일에 접근이 가능하다
File Protection
인증된 user라고 해도 파일의 모든 권한을 인가받으면 안된다
File Protection이란 각 파일에 대해서 user에게 어떤 유형의 접근을 허용할것인가와 관련된 것이다
- read
- write
- execution
Memory의 경우 프로세스는 부여받은 영역을 독자적으로 사용하기 때문에 "접근 유형"만 필요하다
하지만 File의 경우 여러 프로세스가 동시에 access가능하기 떄문에 {누가 접근 & 접근 유형} 총 2가지가 필요하다
1. Access Control Matrix
ACM은 2가지로 나눌 수 있다
(1) ACLs (Access Control Lists)
ACLs는 Matrix를 Column으로 자른 것으로 "특정 파일에 대해서 각 user가 어떤 권한을 가지고 있는지"를 나타낸 것이다
(2) Capability (C-List)
C-List는 Matrix를 Row로 자른 것으로 "특정 user가 각 파일에 대해서 어떤 권한을 가지고 있는지"를 나타낸 것이다
>> 이런 방식으로 나누어도 일반적인 Overhead가 너무 크기 때문에 파일 시스템에서는 "Grouping"을 통해서 파일을 보호한다
2. Grouping
Grouping이란 전체 user를 {Owner / Group / Public} 총 3그룹으로 구분한다
그리고 각 파일에 대해서 세 그룹 각각의 권한을 3bit씩 표현한다
>> 따라서 파일별로 9bit만 사용하면 되기 때문에 굉장히 효율적이다
맨앞에 d는 "directory"를 나타내고 그 다음부터 9bit로 {Owner / Group / Public}각 그룹에 대한 권한을 표시한 것을 볼 수 있다
"-"로 표시된 것은 {r w x}중에서 표시된 권한을 가지고 있지 않다는 의미이다
3. Password
이 방식은 단순하게 파일마다 Password를 걸어서 파일을 보호하는 방식이다
만약 모든 접근 권한에 대해서 하나의 Password를 걸어둔다면 "All - Or - Nothing"이 될 것이다
반면에 권한별로 Password를 지정해놓으면 {암기 & 관리}상에 문제가 발생할 수 있다
Access Methods
Access Methods란 파일 접근 방법과 관련된 것이다
1. Sequential Access (순차 접근)
카세트/비디오 테이프를 사용하는 방식처럼 접근하는 것이다.
특정 부분 x를 읽고 싶으면 현재 위치부터 차례대로 포인터를 x까지 이동시켜야 한다
만약 {a -> b -> c}라는 순서가 존재 & 현재 위치는 a
여기서 파일 c를 읽고 싶다면 a, b부터 차례대로 접근을 해서 c에 도달해야 한다
2. Direct Access/Random Access (임의 접근)
LP 레코드판처럼 접근하는 것이다
파일을 구성하는 record를 임의의 순서로 접근할 수 있다
Disk Structure
Disk구조도 {논리적 Disk / 물리적 Disk}로 나눌 수 있다
하나의 물리적 Disk에는 여러 논리적 Disk : "Partition"이 존재한다
CPU가 논리적 주소를 보듯이, OS는 "논리적 Disk : Partition"을 본다
각각의 Partition에는 서로 다른 File System을 설치할 수 있고, Demand Paging : Swapping용도로 활용할 수도 있다
File System Structure
File System은 일반적으로 서로 다른 Layer들로 구성되어 있다
1. I/O Control
Device Driver & Interrupt Handler가 담당해준다
파일의 실제 위치를 input으로 받는다
2. Basic File System
내부적으로 Cache와 같은 Buffer가 존재한다
매번 I/O Control까지 내려가서 Interrupt를 하면 속도가 느리기 때문에 Request가 Buffer에 존재하면 Buffer 내용을 그대로 전달하고 buffer에 없으면 그제서야 I/O Control로 내려가서 Device Driver와 연동해서 파일로부터 데이터를 받는다
3. File-Organizaton Module
Logical File Blocks - Physical File Blocks간의 Mapping정보를 보유하고, 파일 시스템상에 Free Space도 관리해준다
4. Logical File System
파일 시스템이 필요로 하는 "모든 Metadata"를 FCB에 저장해서 관리한다 (File Description을 저장해서 관리)
- name / ownership / permissions
- Reference Count / Time Stamps / Pointer to other FCBs
- Pointer to data blocks on disk
파일 구조는 물론이고, 디렉토리 구조까지 저장해서 관리해준다
File System Data Structure
1. Boot Control Block
Booting Device 0번지에 존재하는 "Boot Loader"를 메모리에 올려서 Kernel을 가져와준다
>> BCB란 Booting Device전용 Block
2. Volume Control Block
VCB에는 다음 정보들을 저장한다
- Volume에 존재하는 Block의 개수
- Block Size
- Free Block Count
- Free Block Pointers
- Free FCB Count
- FCB Pointers
파일 시스템 자체 정보를 VCB에 저장하므로, VCB가 깨지면 파일 시스템 자체를 사용할 수 없다
따라서 VCB는 copy해서 여러 메모리에 둔다
3. Directory
ID / FCB Pointers와 연관된 파일 이름을 관리한다
4. per-file FCB
Incode Number / Permissions / Size / Dates / ..등을 관리한다
File System Mount
Root File System에서 다른 Partition의 File System에 접근할 때 Mounting 연산을 활용한다
Mount는 그냥 서로 다른 파일 시스템간에 "연결고리"라고 보면 된다
따라서 특정 디렉토리에 다른 파일 시스템을 Mounting해놓으면 그 디렉토리로 가면 다른 파일 시스템에 접근할 수 있다
Allocation of File Data in Disk
파일은 각각 크기가 균일하지 않은데, 파일은 동일한 크기의 Block단위로 저장된다
이에 따라서 Disk도 동일한 크기의 Block으로 나누어진다
그러면 Disk에 각 파일을 어떻게 Allocation할까??
1. Contiguous Allocation
이 방식은 말그대로 "File의 Block들"을 연속적으로 적재하는 것이다
Directory는 해당 파일의 {Start Block 지점 & 할당된 길이}를 보유한다
Mail의 경우 19 Block에서 시작해서, 6개의 Block을 할당받았다고 볼 수 있다 (19 ~ 24)
▶ 장점
<Fast I/O>
디스크 접근시간의 대부분은 Head가 이동하는 시간이다.
연속적으로 할당이 되어있기 때문에 시작 지점까지만 seek해서 그냥 읽으면 된다
<Direct Access>
▶ 단점
<External Fragmentation / Internal Fragmentation>
만약 Block이 [20]이고 파일의 크기가 [150]이라고 하고 현재 Disk상에 연속적인 Block이 {6개, 7개, 8개}가 따로 존재한다고 하자
>> {20 20 20 20 20 20 10}
이러면 [150]짜리는 6개, 7개에는 할당되지 못하고 8개에 할당되어야 하는데 8개중 마지막 Disk Block에는 파일의 [10]만큼만 들어가기 때문에 Internal F가 발생하고, 나머지 아예 사용하지 않는 1개의 Block은 External F이다
<File Grow가 어렵다>
파일은 수정됨에 따라 크기가 증가할 수 있고 감소할 수 있다
"증가"를 고려해서 File을 얼마나 큰 hold에 할당해줄까는 굉장히 중요한 문제이다
파일의 크기가 증가되려면 굉장히 큰 hole을 할당받아야 하지만, 만약 일단 큰 hole을 할당해줬는데 파일 크기가 그대로면 내부 조각이 발생한다
2. Linked Allocation
Linked Allocation은 File의 Block들을 연속적으로 배치하고 빈 위치에 넣는 것이다
여기서 각 파일의 Block은 다음 Block을 가리키는 "Pointer"를 보유한다
시작은 9번지에 있다
9번지가서 읽고 있는데, 해당 block의 마지막에 "이 다음은 16번지에 있어"라고 알려줌
9번지 다읽고 16번지 가서 읽다가 "이 다음은 1번지에 있어"라고 알려줌
16번지 다읽고 1번지 가서 읽다가 "이 다음은 10번지에 있어"라고 알려줌
1번지 다읽고 10번지 가서 읽다가 "이 다음은 25번지에 있어"라고 알려줌
25번지 다읽음 >> 25번지 마지막에 -1이라고 표시되어 있음 = "-1"은 파일의 끝을 나타낸다
▶ 장점
외부 조각이 발생하지 않는다
▶ 단점
<Direct Access 불가능>
4번째 Block을 보려면 {1 - 2 - 3}으로 연결되는 곳에서 각각의 Pointer를 봐야하기 때문에 4번째 Block은 direct access가 불가능하다
<신뢰성 문제>
하나의 sector에 오류가 발생하게 되면 다음 block을 가리키는 Pointer까지 유실되기 때문에 이후 많은 양의 데이터를 잃을 수 있다
<Pointer 공간>
결국 하나의 Block 내부에 다음 Block을 가리키기 위한 Pointer를 위한 공간을 별도로 마련해야 하기 때문에 공간 효율성을 떨어뜨릴 수 있다
>> 512 bytes/sector :: 4 bytes/pointer
Linked Allocation의 Pointer공간 문제를 해결하기 위해서 FAT : File-Allocation Table이라는 것이 탄생하였다
FAT는 Pointer를 위한 공간을 아예 별도의 위치에 보관해서 {신뢰성/공간 효율성}문제를 해결한다
3. Indexed Allocation
Indexed Allocation은 디렉토리가 {File & File's Index Block}을 보유한다
Index Block으로 가게되면 해당 파일의 모든 Block들에 대한 Disk Index Number를 가지고 있기 때문에 Direct Access가 가능하다
"-1"은 아무 내용도 없다는 의미이므로 "jeep"이라는 파일은 {9 16 1 10 25} 총 5개의 Block이 Disk에 적재되어 있다는 것을 알 수 있다
▶ 장점
- 외부 조각 발생 X
- 직접 접근 가능
▶ 단점
파일의 크기가 너무 작은 경우 Index-Block을 적재하는 공간이 많이 필요하지 않기 때문에 이미 할당된 index block의 공간이 낭비된다고 볼 수 있다
반면에 파일의 크기가 너무 큰 경우 하나의 Index-Block으로 전체 Index를 저장하기에는 부족하다
해결방안 1) Linked Scheme
너무 커서 하나의 Index-Block에 담기지 못할 경우 "Index-Block의 마지막에 또 다른 Index-Block을 가리키는 Pointer"값을 설정해주자
- Index Block(Header, Block Addresses, Pointer to another index block)
해결방안 2) Multi Level Scheme
Multi Level Paging처럼 하나의 Index가 직접적으로 파일의 위치를 알려주는게 아니라 또 다른 Index-Block을 가리키게 만들기
UNIX's File System
1. Boot Control Block
Booting Device 0번지에 존재하는 "Boot Loader"를 메모리에 올려서 Kernel을 가져와준다
>> BCB란 Booting Device전용 Block
2. Super Block
파일 시스템과 관련된 전체적인 정보를 보유한 Block이다
- Data Block에서 "어디가 빈 곳이고 어디가 실제 사용중인가"
- 어디까지가 Inode List이고 어디부터가 Data Block인지
3. Inode List
FCB의 역할을 수행해준다
파일의 이름을 제외한 "파일의 모든 Metadata"를 저장
- 파일 하나당 Inode가 하나씩 할당
- 파일 이름은 디렉토리가 보유
Inode는 {Direct Blocks / Single Indirect / Double Indirect / Triple Indirect}로 해당 파일의 위치 정보를 구현한다
4. Data Block
파일의 실제 내용을 보관
- Directory File : {(File 이름, Inode 번호) / (File 이름, Inode 번호) / ...}
Free Space Management
1. Bit Map / Bit Vector
Disk Block별로 {0 / 1}bit를 두어서 Free Space를 관리한다
- 0 : Free
- 1 : 사용중
<장점>
연속적인 n개의 free block을 찾을 때 효과적
<단점>
Bit Map을 위한 부가적인 공간이 Disk에 필요하다
2. Linked List
모든 Free Block들을 Link로 연결
<장점>
Bit Map에 비해 추가적 공간이 필요없다
<단점>
연속적인 Free Block을 찾기 어렵다
3. Grouping
첫번째 Free Block이 Index 역할을 해서 "N개의 Pointer"를 가진다
N-1 Pointer는 Free Data Block을 가리킨다
...
마지막 Pointer가 가리키는 Block은 또 다시 n개의 Pointer를 가진다
4. Counting
프로그램들이 종종 여러개의 연속적인 Block을 할당하고 반납한다는 성질에서 탄생한 방법이다
{First Free Block / # of Contiguous Free Blocks}정보를 유지한다
- 빈 블록 첫번째 :: 해당 빈 블록이 몇개의 연속적인 빈 블록인지
Page Cache
Memory-Mapped I/O
File의 일부를 가상 메모리에 Mapping시키기
Mapping시킨 영역에 대한 메모리 접근 연산은 파일의 I/O를 수행하게 된다
Buffer Cache
파일 시스템을 통한 I/O연산은 메모리 특정 영역인 Buffer Cache를 사용
>> File 사용의 Locality를 이용하는 방식이다
- 한번 읽어온 Block에 대해서 나중에 또 request가 오면 Buffer Cache에서 바로 전달
모든 프로세스가 공통으로 사용하는 Cache이다
>> LRU/LFU 등 Replacement Algorithm이 필요하다
VFS (Virtual File System)
user가 file system에 접근하려면 system call을 통해서 접근한다
근데 file system이 여러개면 system call도 file system별로 달라야 한다
>> 서로 다른 file system에 대해서 "동일한 system call interface"를 통해서 접근할 수 있게 해주는 OS의 Layer이 VFS이다
NFS (Network File System)
분산 시스템에서는 네트워크를 통해서 파일이 공유될 수 있다
