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

728x90

25. File System Implementations 1 (반효경)

순차적인 접근, 직접접근

매체에 따라서 테이프는 순차접근만 가능하다. 하드디스크, 플래시메모리, CD는 건너뛸 수 있기에 직접접근이 가능하다.

직접접근이 가능한 매체여도 데이터를 어떻게 관리하느냐에

따라서 순차접근만 가능한 경우일 수도 있는데 오늘은 그 이야기를 할 거다.

디스크에 어떻게 파일 데이터를 할당할 것인지! 디스크에 파일을 어떻게 저장할 건지!

디스크 내부에서는 섹터 단위로 데이터를 저장하고 있다. 임의의 크기의 파일을 블록 단위로 저장하고 있다.

연속 할당 Contiguous Allocation

하나의 파일이 디스크 상에 연속해서 저장되는 방식

블록 2개는 0, 1번을 차지하고,

블록 6개다 -> 19번 ~ 24번까지 차지하는 것을 말한다.

디렉토리 파일 : 디렉토리 밑에 있는 파일들의 메타 데이터를 말하는데,

디렉토리 밑에 5개의 파일이 있고, 이 파일의 이름, 위치 정보를 디렉토리가 가지고 있다.

count의 경우 0번부터 길이가 2니까 0 1

list의 경우 28번부터 길이가 4니까 28 29 30 31

단점 :

1. 외부 조각(external fragmentation)이 생길 수도 있다. 각각의 파일 길이가 균일하지 않아서 중간에 내용이 들어있지 않은 블록이 있고, 그 크기가 균일하지 않다. 또한, 그 비어있는 공간이 활용되지 못하는 상황이 발생할 수 있다.

2. 파일의 크기가 커지는데 제약이 있다.

예를 들어, 14 15 16 파일의 크기가 4개, 5개 사이즈로 키울 수 있지만 그 이상으로는 키울 수는 없다. 빈 블록이 2개 뿐이기에

지금은 길이가 3이지만, 길이가 5로 커질 것을 대비해서 미리 2를 할당해두는 것은 당장 사용되지 않는 것이기 때문에 내부 조각(internal fragmentation)이 발생한다. -> 공간 낭비 상황

3. 중간 중간 hole이 발생

장점:

1. 빠른 I/O가 가능하다.

특히, 하드디스크와 같은 매체는 디스크 헤드가 바깥쪽 -> 안쪽 트랙으로 이동하는 시간에 많은 시간을 소요하는데,

한 번 디스크 헤드가 19번 위치를 seek하면 24번까지 읽어올 수 있다.

많은 양의 데이터를 연속으로 빠르게 받아올 수 있는 장점.

2. swapping area는 임시로 저장해두는 공간으로 속도 효율성을 위한 곳이기 때문에

프로세스의 swap area 용도로 프로세스의 주소 공간의 용도로 사용하기에 좋다.

3. 데드라인이 있는 realtime file용으로 사용하기 적합하다. 왜냐하면 빠르기 때문에.

4. 직접 접근이 가능하다.

예를 들어, mail이라는 데이터는 19번

부터 연속적으로 6개가 저장되어 있다는 것을 알기 때문에 mail 내에서 3번째 데이터를 보고 싶다고 할 경우에 바로 접근이 가능하다.

연결 할당 Linked Allocation

파일의 데이터를 디스크에 연속적으로 배치하지 않고,

jeep이라는 데이터가 첫 번째 블록은 9번에 있고, 두 번째 블록은 16번에 있고, 세 번째 블록은 1번에 있고, .. 연결 시켜둔 후 마지막 블록은 -1로 표시해놓는다.

파일의 시작 위치만 디렉토리가 가지고 있고, 그 다음 위치는 그 위치에 가면 있다.

장점:

1. 외부 조각이 발생하지 않는다는 점!

단점:

1. 직접 접근이 안된다. only 순차 접근만 가능

앞에서부터 4번째 블록을 보려고 하면, 처음부터 순차적으로 접근해야 알 수 있다.

디스크 헤드가 항상 이동해야 하고, 순차 접근에 의해 시간이 많이 든다.

2. Realiability 문제, 중간에 섹터가 불량이 나는 경우 그 뒷부분은 잃게 된다.

3. 섹터는 512 바이트, 포인터는 4 바이트가 차지하니까 실제 데이터가 차지하는 공간 효율성은 떨어지게 된다.

FAT File-allocation-table 파일 시스템이 Linked Allocation을 변형해서 나왔다.

인덱스 할당 Indexed Allocation

디렉토리에 파일의 위치 정보를 바로 저장하는 것이 아닌 위치 정보를 19번이라는 인덱스 블록에 처음 저장한다.

장점:

1. 직접 접근이 가능하다.

2. 순차 접근에서 발생하는 hole도 생기지 않는다. - 외부조각이 발생하지 않는다.

단점:

1. 인덱스 블록이 하나 필요하고, 실제 데이터를 저장하는 블록이 하나 필요하다. - 공간 낭비

2. 큰 파일의 경우, 인덱스 블록 하나로 표시하기 어렵다. - 공간 낭비

해결 방안)

- linked scheme : 인덱스 블록의 가장 마지막 인덱스(19번 인덱스 블록에서 -1)를 따라가면 또 인덱스 블록이 나온다.

- multi level index : 인덱스가 2단계 페이지 테이블처럼 한 단계를 더 거쳐야 인덱스를 볼 수 있는 방식.

실제 파일 시스템에서는 어떻게 사용하는가?

어떻게 더 효율적으로, 시간을 줄여서 잘 저장할 수 있을지?

UNIX 파일시스템의 구조

저장되는 구조가 Boot, Super, Inode list, Data Block이 순서대로 저장이 된다.

Boot Block - 어떤 파일 시스템이든 간에 동일한 약속!

컴퓨터 전원을 켜면 0번 블록을 메모리에 올리면 bootstrap loader라고 하는 부팅을 하는데 필요한 정보가 있다.

파일 시스템에서 운영체제의 커널의 위치가 어디인지 찾아서 컴퓨터를 정상적으로 켤 수 있게 한다.

Super Block - 파일 시스템의 총체적인 정보

어디가 빈 블록, 어디가 사용 중인 블록인지를 총체적으로 관리한다.

Inode List - 파일의 메타 데이터 관리

파일의 메타데이터는 그 파일의 디렉토리에 가면 메타데이터가 기록된다.

근데 디렉토리가 메타데이터를 다 가지고 있지 않고, 실제로는 별도의 위치에 빼서 저장하고 있는데 그 위치가 Inode List다.

빨간색 네모가 파일 하나 당 inode 하나씩 할당된다.

파일의 메타데이터를 가지고 있는데, 파일의 소유주, 위치 정보, 접근 권한 등을 가지고 있다.

대신 파일의 이름은 디렉토리가 직접 가지고 있다. 그리고 디렉토리는 inode의 번호를 가지고 있다.

UNIX 파일 시스템은 인덱스 파일 시스템을 변형해서 사용하고 있어서 파일 위치 정보를 direct / single / double / triple index pointer로 파일의 위치 정보를 가리킨다.

대부분 파일의 크기는 작아서 한 번의 인덱스 접근으로 위치 정보를 알 수 있는데,

(위에서 봤듯이, 멀티 레벨 인덱스 방식과 같이...)

큰 파일의 경우 double indirect -> triple indirect pointer를 통해 몇 단계를 거쳐서 접근할 수 있다.

FAT File System - 마이크로소프트 DOS

Boot - FAT - Root directory - Data Block

FAT - 파일의 메타데이터 중 위치 정보를 여기에 보관

위치 정보만 여기에 보관하고 나머지는 디렉토리가 가지고 있다.

첫 번째 위치가 어딘지도 디렉토리가 가지고 있다.

217번 그 다음 블록이 무엇인지를 FAT에 담고 있다.

그래서 FAT이라는 배열의 크기는 Data block이 관리하는 블록의 크기만큼 된다.

그리고 그 블록의 다음 블록이 어딘지를 담고 있다. 217번 entry를 가면 618 -> 339 -> EOF (끝)

실제 블록에 접근하는 것이 아닌 FAT만 확인하면 그 파일의 다음 위치를 알 수 있다.

따라서,

FAT의 장점

1. 직접 접근이 가능하다는 점! -> 해당 파일의 4번째 블록을 보려면, FAT의 테이블에 가서 메모리에 올라간 블록들의 순서만 알면 가능

2. 포인터 하나가 유실되어도 FAT에 내용이 있고, FAT 자체가 중요한 내용을 담고 있어서 여러번의 카피(?)가 있다.

-> reliability 문제극복

3. 512 바이트 충분히 활용 가능

위 Linked Allocation 단점을 상당히 개선해서 활용하고 있다.

Free Space Management

비어있는 블록은 어떻게 관리하는가?

1. bit map, bit vector

각각의 블록마다 번호가 있는데, 각각의 블록이 사용 중인지 아닌지 0과 1로 표시하고,

비트맵은 부가적인 공간을 필요로 하는데 많은 공간은 아니다.

장점은 연속적인 빈 블록을 찾는데 효과적이다.

2. Linked list

모든 free block들을 링크로 연결

회색이 비어 있는 공간인데, 비어 있는 블록의 첫 번째 위치만 포인터로 가지고 있는 방식

비트맵보다 추가적인 공간 낭비는 없으나, 연속적인 빈 공간을 찾기는 어렵다.

실제로 사용하기는 어려움

3. grouping

linked list 방법의 변형, 인덱스 형식으로

연속적인 빈 블록을 찾기에는 효과적이지 않다.

4. Counting

빈블록의 위치를 가리키고, 몇 개가 비어있는지까지 알려줘서 위 grouping보다 연속적인 빈 블록을 찾기 나은 편이다.

Directory Implementation

디렉토리를 어떻게 구현하는가?

디렉토리에 어떻게 파일을 저장하는가?

Linear list

파일의 이름, 파일의 메타 데이터를 순차적으로 저장하는 방식

구현이 간단

Hash Table

예를 들어서, cccc라는 파일 이름을 해시 함수를 적용했더니 3이 나와서 해시 테이블의 3번에 파일의 메타 데이터를 저장해두는 것

이런 식으로 하면 그 파일의 이름을 해시함수에 적용하고, 그 파일의 해시함수 결과값이 있는지 없는지만 확인하면 되니까.

문제는 Collision이 발생 가능

*디렉토리에 파일의 메타 데이터를 전부 보관할 수 있지만, 다른 곳에 보관할 수도 있다.

inode, FAT 등

*긴 파일이름의 지원

- 긴 글자는 포인터를 통해 저장하는 방식

VFS and NFS

Virtual File System

사용자가 파일 시스템에 접근할 때는 운영체제에게 시스템 콜을 해야 하는데, 어떤 파일 시스템을 사용하든지 상관없이

VFS를 상위에 둬서 사용자 입장에서 동일한 시스템 콜 인터페이스를 둬서 사용하기 쉽게 해주는 OS 레이어

Network File System

파일 시스템이 원격에 저장되어서 접근할 경우에 이걸 사용하는데,

클라이언트가 서버를 통해 원격의 파일 시스템을 접근하기 위해서 VFS를 통해 접근 요청 -> NFS client -> NFS server -> VFS 를 통해 접근이 가능하다.