[week13] KOCW 운영체제(반효경교수님) - File System Implementation 1

File System Implementation 1

지난 시간 리뷰

storage에 있는 data에 접근하는 방법에는 순차접근(sequential access)과 직접접근(random access)이 있다. 그 매체에 따라 다른데 tape은 순차접근만 된다. hard disk, flash memory, CD들은 직접접근이 가능하다. 직접 접근이 가능한 매체라도 data를 어떻게 관리하느냐에 따라서 순차접근만 허용될 수도 있고 직접접근이 가능할 수도 있다(지금은 무슨말인지 몰라도 뒤에 읽다보면 이해가 된다).

Allocation of File Data in Disk

file은 크기가 일정하지 않다. 그러나 disk에 file을 저장할 때는 동일한 크기의 sector 단위로 나눠서 저장한다. file system이라던지 disk 외부에서 볼 때는 각각의 동일한 크기의 저장단위를 논리적인 블록이라고 부른다. (paging 기법과 유사)

disk에 file의 data를 저장하는 3가지 방법

Contiguous Allocation(연속할당)

하나의 file이 disk 상에 연속해서 저장되는 방법. ex) 19~24번 블록까지 연속해서 할당됨

directory라는 file은 directory 밑에있는 file들의 metadata들을 내용으로 한다(이름 및 위치정보).

단점

external fragmentation(외부단편화) 발생

File grow 어려움

• file은 수정되면 중간에 크기가 변할 수 있다. 근데, 크기가 커질 때 제약이 있다(뒤에 빈 블록이 몇개 없다면)
• 그래서 미리 file이 커질것을 대비해서 할당해놓을 수 있다.
  • 근데 그렇게 되면 internal fragmentation 발생가능

장점

Fast I/O가능

• 한번의 seek/rotation으로 많은 byte transfer 가능(디스크가 시간 잡아먹는건 대부분 head의 움직임 때문)
• 이미 run 중이던 process의 swapping용도(프로세스의 주소공간중의 일부를 저장하는 용도)
  • 공간효율성보다는 속도효율성이 더 중요할 때 사용 → realtime 용으로 사용하는 file일 때

Direct access(=random access)가능

Linked Allocation

file을 연속적으로 배치하지 않고 빈 위치면 아무곳이나 배치시킴

장점

external fragmentation 발생 안함

단점
random access(직접 접근) 불가능 → 시간 오래걸림

• disk 자체는 직접접근이 가능하지만 file을 관리하는 방식에 따라 직접접근이 불가능해질 수 있다

reliability 문제

• 한 sector가 고장나 pointer가 유실되면 많은 부분 잃어버림

pointer를 위한 공간이 block의 일부가 되어 공간 효율성 떨어뜨림

• disk에서 하나의 sector는 512 bytes로 구성된다. 그리고 disk에 저장하는 단위는 512 byte의 배수로 저장이 된다. 그런데 pointer는 4byte이므로 data를 저장할 수 있는 공간은 (512 - 4)byte가 되고, 한 sector에 들어갈 내용이 두 섹터에 저장되어야 하는 문제가 발생할 수 있음

변형

FAT(File-Allocation Table) file system

• 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

Indexed Allocation

directory에 file의 위치정보를 바로 저장하는 것이 아니라 먼저 index를 가리키게 한다. index block은 내용을 담고 있지 않고 file이 어디어디에 저장되어있다는 위치정보를 열거해놓는 블록이다.

장점

External fragmentation이 발생하지 않음

Direct access 가능

단점

Small file의 경우 공간 낭비(실제로는 많은 file들이 small)

Too Large file의 경우 하나의 block으로 index를 저장하기에 부족

• 해결방안(큰 파일 저장에 관해)
  1. linked scheme(마지막위치는 또 다른 index로 이동하기로 약속)
  2. multi-level index

UNIX 파일시스템 구조

이제까지는 개념적인 것을 공부했고, 실제로 시스템은 어떻게 file을 관리하는지 살펴보자.

boot block은 unix file system만 제일 앞에 나오는 것이 아니라 모든 file system에서 boot block이 가장 먼저 나온다. 왜냐하면 컴퓨터에 어떤 file system이 설치되어있는지 모르는 상태에서 컴퓨터의 전원을 키면 부팅을 해야한다. 어디 있는 data를 메모리로 올려서 부팅을 하는지 결정해줘야 한다. 0번 블록은 항상 boot block이다.

super block : 어디가 빈 블록이고 어디가 data가 저장되어있는 블록인지 관리, 어디가 Inode list고 어디가 data block인지 관리

우리는 file의 metadata를 directory에 저장한다고 배웠는데 사실 모든 metadata를 directory에 저장하는건 아니다. directory는 지극히 일부분만 가지고 있고(file의 이름은 directory가 가지고 있음) 실제 file의 metadata들은 Inode(index node) 라는 위치에 보관한다.

Unix file system은 Indexed Allocation을 사용한다. 작은 file이면 direct blocks를 사용하고 크기가 커질수록 single, double, triple indirect를 사용한다. 이렇게 하면 효율성도 챙길 수 있고(작은 file은 direct block으로 처리) 굉장히 큰 file들도 한정된 inode라는 공간에서 표현할 수 있다.

FAT File System

file의 metadata중 일부(위치정보만)를 FAT이라는 곳에 보관하고 있다. 나머지 metadata는 directory가 가지고 있다. 소유주, file size, file의 첫 번째 위치도 directory가 가지고 있다. FAT에는 그 블록의 다음 블록을 번호로 저장해두고 있다. linked allocation 적용한 것이지만(변형하여) 직접접근이 가능하다. 또, pointer 하나가 유실되더라도 FAT에 내용이 있기 때문에 괜찮다. FAT은 중요한 정보라서 2 copy 이상 저장하고 있다.

Free-Space Management

Bit map or bit vector

각각의 block 이 사용중인지 아닌지를 0과 1로 표시

• bit map은 부가적인 공간을 필요로 함
• 연속적인 n개의 free block을 찾는데 효과적

Linked list

모든 free block들을 link로 연결(free list)

연속적인 가용공간을 찾는 것은 쉽지 않다(실제로 사용하긴 쉽지 않다).

공간의 낭비가 없다.(장점)

Grouping

linked list 방법의 변형

첫 번째 free block이 n개의 pointer를 가짐

• n-1 pointer는 free data block을 가리킴
• 마지막 pointer가 가리키는 block은 또 다시 n pointer를 가짐

Counting

프로그램들이 종종 여러개의 연속적인 block을 할당하고 반납한다는 성질에 착안

(first free block, # of contiguous free blocks)을 유지

Directory Implementation

Linear list

<file name, file의 metadata>의 list

구현이 간단

디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요(time-consuming)

Hash Table

linear list + hashing

hash table은 file name을 이 file의 linear list의 위치로 바꿔줌

search time을 없앰

collision 발생 가능

File의 metadata 보관위치

디렉토리 내에 직접 보관

디렉토리에는 포인터를 두고 다른 곳에 보관

• inode, FAT 등

Long file name의 지원

<file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정크기

file name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법

이름의 나머지 부분은 동일한 directory file의 일부에 존재

VFS and NFS

Virtual File System(VFS)

서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해주는 OS의 layer

VFS가 필요한 이유

• 복잡한 개별 file system에 대한 추상화
• layer of abstraction(매우 중요)

Network File System(NFS)

분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음

NFS는 분산 환경에서의 대표적인 파일 공유 방법임

Page Cache and Buffer Cache

page cache

virtual memory의 paging system에서 사용하는 page frame을 caching의 관점에서 설명하는 용어

memory-mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용

memory-mapped I/O

file의 일부를 virtual memory에 mapping시킴

매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 함

buffer cache

파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용

file 사용의 locality 활용

• 한 번 읽어온 block에 대한 후속 요청시 buffer cache에서 즉시 전달

모든 프로세스가 공용으로 사용

replacement algorithm 필요(LRU, LFU 등)

unified buffer cache

최근의 OS에서는 기존의 buffer cache가 page cache에 통합됨

• buffer cache도 page 단위로 관리한다.