[운영체제] Chapter 11. File Systems Implementation (1)

[운영체제] Chapter 11. File Systems Implementation (1)

2023. 2. 1. 18:57ㆍCS/운영체제

728x90

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

Allocation of File Data in Disk, Contiguous Allocation, Linked Allocation, Indexed Allocation, UNIX 파일시스템의 구조, FAT File System, Free-Space Management, Directory Implementation, VFS and NFS

1. 디스크에 파일을 저장하는 방법

1-1. Contiguous Allocation

하나의 파일이 디스크상에 연속해서 저장되는 방법
디스크에 파일을 저장할 때는 보통 동일한 크기의 섹터 단위로 나누어 저장한다.
- 파일시스템과 디스크 외부에서는 논리적인 블럭이라고 부르고
- 디스크 내부에서는 섹터라고 부른다.
디렉터리는 파일들의 메타데이터를 내용으로 가지는 파일이다. 해당 파일에는 파일의 이름과 위치 정보 등이 저장되어 있어 시작 위치와 길이를 가지고 디스크에 연속적으로 적재할 수 있다.
단점
- 파일들의 크기가 균일하지 않고 연속적으로 파일을 적재해야 하기 때문에
- 외부 조각 문제: 비어 있는 공간이 블럭 2개인데 블럭 3개로 구성된 파일은 들어갈 수 없어 비어있는 공간을 활용할 수 없다.
- File grow가 어렵다: 파일은 중간중간 수정하며 크기가 커질 수 있는데 이를 대비해서 파일 생성 시 얼마나 큰 hole을 배당할 것인가?
  - 커질 것을 대비해서 grow가능 vs 낭비(내부 조각 문제: 누군가에게 이미 할당을 했는데 아직 사용되지 않는 공간)
장점
- 빠른 입출력: 한 번의 seek/rotation으로 많은 바이트를 전송할 수 있다.
  - realtime file용: deadline이 있고, 빠른 입출력이 필요
  - 이미 run 중이던 프로세스의 swaping area용: 프로세스가 끝나면 지워질 데이터들, 대용량의 크기를 빠르게 디스크로 swap out, 메모리로 swap in 해야 하기 때문에 속도 효율성 > 공간 효율성
- 직접 접근 가능: 시작 위치에 숫자를 더하면 중간 위치 블럭을 미리 볼 수 있다.

1-2. Linked Allocation

파일의 데이터를 디스크에 연속적으로 배치하지 않고 빈위치 아무 곳에나 배치하는 방법
디렉터리에는 시작 위치와 종료 위치만 가지고 있고 중간 위치는 실제 위치에 기록되어 있다.
장점
- 외부 조각 문제 발생하지 않음
단점
- 임의 접근 불가: 중간 위치를 보려면 앞에 부분을 모두 탐색해서 내용을 봐야 중간 위치를 알 수 있다.
  - 디스크는 직접 접근이 가능한 매체지만 파일 관리 방법을 linked allocation으로 하면 직접 접근을 할 수 없고 순차 접근만 할 수 있다. 건너뛰기 불가
  - seek 하는데 시간이 많이 걸린다.
- Reliability 문제: 한 섹터가 고장 나 포인터가 유실되면 뒷부분을 완전히 다 놓치는 문제가 발생할 수 있다.
- Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨린다.
  - 디스크의 섹터는 512 byte, 컴퓨터에서 디스크에 접근할 때는 디스크 저장 단위 512 byte의 배수로 구성되어야 한다.
  - 하지만 다음 위치를 가리키는 포인터는 4 byte → 실제 데이터 저장 공간은 (512 - 4) byte
  - 이렇게 되면 한 섹터에 저장될 내용이 포인터 때문에 두 섹터에 저장되어야 하는 문제가 발생한다.
변형: File-allocation table(FAT) 파일 시스템: 포인터를 별도의 위치에 보관해서 reliability와 공간 효율성 문제를 해결하는 방법

1-3. Indexed Allocation

직접 접근이 가능하게 하기 위해 디렉터리에 위치 정보를 바로 저장하는 것이 아니라 인덱스 블럭을 저장하는 방법
인덱스 블럭에는 파일의 내용 대신 어디 어디에 저장되어 있는지 위치 정보를 block 하나에 쭉 열거
장점
- 외부 조각 문제 발생하지 않음
- 직접 접근 가능: 인덱스 블럭만 살펴보면 직접 접근이 가능하다.
단점
- 작은 크기의 파일일 경우 공간 낭비가 발생한다.
  - 아무리 작은 파일이더라도 index, 실제 데이터 저장으로 2개의 블럭이 필요하기 때문
  - 실제 많은 파일들의 크기가 작다.
- 너무 큰 파일의 경우 하나의 블럭으로 인덱스를 저장하기 부족하다.
  - 해결방안) linked scheme: 인덱스 블럭이 파일의 크기를 다 커버하지 못할 때 맨 마지막에 내용이 아니라 또 다른 인덱스 블럭을 가리키게 한다.
  - 해결방안) multi-level index: 하나의 인덱스 블럭이 직접 파일의 위치를 가리키게 하는 게 아니라 또 다른 인덱스를 가리키게 한다.

2. 파일시스템의 구조

실제 파일 시스템에서 어떤 할당 방법을 어떻게 변형해서 쓰는가?

2-1. UNIX

유닉스 파일 시스템의 중요 개념
- Boot block: 부팅에 필요한 정보 (bootstrap loader)
  - 항상 0번 블럭에 저장, 메모리에 올리면 OS 커널 위치를 찾아 메모리에 올려 정상적인 부팅이 이루어지게 함
  - 어떤 파일시스템이건 제일 먼저 앞에 나옴
- Superblock: 파일 시스템에 관한 총체적인(어디가 빈 블럭인지, 사용 중인 블럭인지) 정보를 담고 있다.
- Inode: 파일 이름을 제외한 파일의 모든 메타 데이터를 저장한다.
  - indexed allocation 활용
  - 파일 이름은 디렉터리가 직접 저장
  - 메타 데이터에 위치 정보가 있고, 크기는 고정되어 있기 때문에 위치 정보를 나타내는 포인터의 개수는 유한하다
    → direct block, single indirect, double indirect, triple indirect로 나누어 사용
    - direct에는 굉장히 작은 파일을 가리키게 하고, triple은 3단계 인덱스 구조로 3개의 인덱스를 통과해야 실제 파일의 위치 정보를 확인할 수 있다.
    - 장점: 대부분의 파일은 크기가 작기 때문에 효율적으로 사용하고, 굉장히 큰 파일을 한정된 크기의 아이노드를 사용해서 지원할 수 있다.
- Data block: 파일의 실제 내용을 보관한다.

2-2. FAT

포인터를 별도의 위치에 보관하여 reliability와 공간 효율성의 문제를 해결하는 방법
FAT 파일 시스템의 중요 개념
- Boot block: 부팅에 필요한 정보
- FAT: 메타데이터 중 위치 정보를 보관하는 별도의 테이블, Data block의 개수만큼 FAT 배열의 크기
  - linked allocation을 활용하는데 직접 접근이 가능하다.
    - linked allocation을 활용해서 다음 위치를 찾기 위해서 실제 블럭을 접근해야 되는 것이 아니라 FAT만 확인하면 다음 위치가 어디인지를 알 수 있다.
    - linked allocation은 순차 접근만 가능한데, FAT는 작은 테이블이고 이미 메모리에 올라가 있는 상황이다. 테이블을 쭉 따라가면 곧바로 파일의 n번째 위치를 파악할 수 있어서 실제 디스크에서는 직접 접근을 할 수 있다.
- Root directory
- Data block - directory file: 이름을 비롯한 접근 권한, 소유주, 크기 등 모든 것을 디렉터리가 가지고 있다.
  - 파일의 첫 번째 위치 정보를 가지고 있으며, 파일 주소를 따라가면 파일의 첫 번째 내용을 확인할 수 있다.
linked allocation의 단점을 모두 보완한다.
- 직접 접근 가능
- Reliability 문제 개선: 포인터가 유실되더라도 FAT에 내용이 있다. 또한 Datablock과 FAT 내용이 완전 분리되어 있고 FAT는 중요한 정보이기 때문에 2개 이상의 copy가 존재한다.
- 섹터에서 포인터를 분리했기 때문에 512 byte를 모두 활용할 수 있어 공간 효율성 문제를 해결했다.

3. Free-Space Management

3-1. Bit map or bit vector

각각의 블럭별로 블럭 번호를 붙여 (UNIX의 경우) super block에 bit를 둬서 사용 중인지 비어있는지를 표시한다.
- bit[i] = 0: block[i]는 비어있는 블럭
- bit[i] = 1: block[i]는 이미 파일에 할당된 블럭
Bit map은 부가적인 공간을 필요로 한다.
- block 하나에 1 비트가 필요하기 때문에 많은 공간을 차지하지는 않는다.
연속적인 n개의 free block을 찾는데 효과적이다.
- 가능하면 연속적인 빈 공간에 프로그램을 할당해 주면 디스크 헤드가 여러 번 이동할 필요 없이 많은 양의 데이터를 한꺼번에 읽어올 수 있다.
파일이 새로 만들어지거나 파일의 크기가 커지면 비어있는 블럭 중에 하나를 할당해야 하고, 삭제되면 bit을 1에서 0으로 변경해 주는 일을 파일 시스템에서 관리한다.

3-2. Linked list

모든 비어있는 block들을 링크로 연결하고, 비어있는 block의 첫 번째 위치만 포인터로 가지고 있는다.
연속적인 가용 공간을 찾는 것이 쉽지 않다.
bit map 방식에 비해 추가적인 공간의 낭비가 없다.

3-3. Grouping

index 형식으로 grouping 해서 빈 블럭의 위치를 가리킬 수 있다.
linked list 방법을 변형해서 free block을 관리하는데 활용할 수 있다.
첫 번째 비어있는 block이 n개의 포인터를 가지고(index 역할)
- 1부터 n-1까지의 포인터는 비어있는 데이터 block을 가리킨다.
- 마지막 n번째 포인터가 가리키는 block은 또다시 n개의 포인터를 가져서 비어있는 block을 가리킨다.
비어있는 공간을 한꺼번에 찾기에는 linked list 방법보다는 효율적이지만, 연속적인 빈 block을 찾기에는 썩 효과적이지 않다.

3-4. Counting

(빈 block의 첫 번째 위치, 로부터 몇 개가 빈 block인지)을 쌍으로 유지
프로그램들이 종종 여러 개의 연속적인 block을 할당하고 반납한다는 성질에 착안

4. Directory Implementation

디렉터리 파일에 내용을 어떻게 저장할 것인지에 대해서

4-1. Linear list

<file namem, file의 메타데이터>의 리스트
구현이 간단하다.
엔트리의 크기가 고정되어 있기 때문에 디렉터리 내에 파일이 있는지 찾기 위해서는 linear search가 필요하다.
- linear search는 순차적으로 검색하는 방법으로 모든 항목을 다 검색해 보아야 하기 때문에 시간이 많이 걸린다. → 비효율적

4-2. Hash Table

linear list + hashing
Hash table은 파일 이름을 이 파일의 linear list의 위치로 바꾸어줌
- Hash 함수: 어떤 input이 주어지더라도 Hash 함수를 적용하면 그 결괏값이 어떤 특정 범위 안의 숫자로 한정된다.
- Hash 함수의 결괏값에 해당하는 엔트리에 그 파일의 메타데이터를 저장한다.
검색 시간을 없앰
같은 값의 Hash 함수의 결괏값들이 있을 수 있어 Collision이 발생할 수 있다.

4-3. 파일의 메타데이터의 보관 위치

디렉터리 내에 직접 보관
디렉터리에는 포인터를 두고 다른 곳에 보관 ex) inode, FAT 등

4-4. Long file name의 지원

<파일 이름, 파일의 메타데이터>의 리스트에서 각 항목은 일반적으로 고정 크기
- 대부분의 메타데이터는 길이가 한정되어 있다: 접근 권한 9 byte 등
- 문제는 파일 이름
파일 이름이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
- 이름의 나머지 부분은 동일한 디렉터리 파일의 일부에 존재한다.

5. VFS and NFS

Virtual File System(VFS)
- 사용자가 파일 시스템에 접근할 때 개별 파일 시스템 종류와 상관없이 VFS 인터페이스를 사용해서
- 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 layer
Network File System(NFS)
- 원격에 저장되어 있는 파일 시스템에 접근하는 방법
- 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다
- NFS는 분산 환경에서의 대표적인 파일 공유 방법
client와 server에 NFS 모듈이 둘 다 있어야 한다.

[복습]

디스크에 파일을 저장하는 방법
- contiguous allocation: 하나의 파일이 디스크상에 연속해서 저장하는 방법, 섹터 단위
  - 외부조각 문제, file grow 어려움,
  - 빠른 입출력, 직접 접근 가능
- linked allocation: 연속적으로 배치하지 않고 빈위치 아무 곳에나 배치하는 방법
  - 외부조각 문제 발생하지 않음
  - 임의 접근 불가, reliability 문제, pointer를 위한 공간으로 공간 효율성이 떨어짐
- indexed allocation: 인덱스 블럭에 파일 내용 대신 위치 정보를 block 하나에 열거하는 방법
  - 외부 조각 문제 발생하지 않음, 직접 접근 가능
  - 작은 크기의 파일은 공간 낭비, 너무 큰 파일은 하나의 블럭으로 인덱스를 저장하기 부족
파일 시스템의 구조
- UNIX: Inode: 파일 이름을 제외한 파일의 모든 메타데이터를 저장
- FAT: 메타데이터 중 위치 정보를 보관하는 별도의 테이블을 두어 reliability와 공간효율성 문제 해결
Free-space management: bitmap or bit vector, linked list, grouping, counting
Directory implementation: linear list, hash table, 파일의 메타 데이터 보관 위치, long file name 지원
VFS: 개별 파일 시스템의 종류와 상관없이 VFS 인터페이스를 통해 동일한 시스템 콜 인터페이스에 접근할 수 있게 해주는 OS layer
NFS: 원격에 저장되어 있는 파일 시스템에 접근하는 방법, 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다.

이화여자대학교 반효경 교수님의 [2014년 1학기 운영체제] 강의 정리입니다.

https://core.ewha.ac.kr/publicview/C0101020140520134614002164?vmode=f

반효경 [운영체제] 25. File System Implementations 1

설명이 없습니다.

core.ewha.ac.kr