[운영체제] 9. File Systems (2)

키워드

contiguous allocation, linked allocation, indexed allocation, unix file system, fat file system, free-space management, directory implementation, vfs, nfs, page cache, buffer cache

 

Allocation of File Data in Disk

• Contiguous Allocation (연속 할당)
• Linked Allocation (연결 할당)
• Indexed Allocation (인덱스로 할당)
  
  
• Disk에 file 저장 시 보통 동일한 크기의 섹터 단위로 나누어 저장
• 파일 시스템이나 disk 외부에서 볼 때 각각의 동일한 크기의 저장 단위를 논리적인 블럭이라 부른다.
• 즉, 임의의 크기의 파일을 임의의 크기의 블럭 단위로 나누어 저장
  -> 메모리 관리의 페이징 기법과 유사

 

Contiguous Allocation

(=연속 할당)

• 하나의 file이 disk 상에 연속해서 저장되는 방법

단점

• external fragmentation
  -> 외부 조각이 생길 수 있음
• File grow(파일 크기의 증가)가 어려움
  • file 생성 시 얼마나 큰 hole을 배당할 것인가?
  • grow 가능 vs. 낭비 (internal fragmentation)

장점

• Fast I/O
  • 한 번의 seek/rotation으로 많은 바이트 transfer
  • Realtime file 용으로, 또는 이미 run 중이던 process의 swapping 용
• Direct access(=random access) - 직접 접근 가능

 

Linked Allocation

(=연결 할당)

• 파일의 데이터를 디스크에 연속적으로 배치하지 않고 빈 위치면 아무데나 들어갈 수 있게 배치

장점

• External fragmentation (외부 조각) 발생 안 함

단점

• Direct access(직접 접근)이 되지 않음
• No random access
• Reliability 문제
  -> 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
• Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림
  -> 512 bytes/sector, 4 bytes/pointer

변형

• File-Allocation Table(FAT) 파일 시스템
  -> 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

 

Indexed Allocation

장점

• External fragmentation(외부 조각)이 발생하지 않음
• Direct access 가능

단점

• 아무리 작은 사이즈라 하더라도 block이 두 개 필요 (index, 실제 데이터 저장)
  -> Small file의 경우 공간 낭비 (실제로 많은 file들이 작다.)
• Too large file의 경우 하나의 block으로 index를 저장하기에 부족
  -> 해결방안
  • linked schema
  • multi-level index

 

UNIX 파일시스템의 구조

• 어떤 파일시스템이든 Boot block이 항상 제일 앞에 나옴 -> 약속
• UNIX 파일시스템의 경우 디렉토리는 메타데이터를 지극히 일부분만 가지고 있고
  실제 파일의 메타데이터는 별도의 위치에 보관 -> Inode list(Index node)
• 파일의 메타데이터를 전부 Inode가 가지고 있지 않고 딱 한가지, 파일의 이름은 디렉토리가 직접 가지고 있음
  즉, directory는 file 이름과 Inode 번호를 가지고 있다.
  
  
• inode의 크기는 고정 -> 위치 정보를 나타내는 pointer 개수도 유한함
• 하지만 큰 파일도 표현할 수 있어야 한다. -> direct blocks, single indirect, ... 을 통해 위치 정보를 구성
• 파일 크기가 굉장히 작은 데이터는 direct index만을 가지고 표현 가능
• 대단히 큰 파일인 경우 indirect를 이용해 표현
  -> single indirect는 따라가면 index block이 있고 거기엔 pointer가 위치
  -> 더 큰 파일은 double, triple, ...

 

FAT File System

• file의 메타데이터 중 일부를 FAT에 보관(대부분이 아닌 지극히 제한적인 위치 정보)
• 나머지 메타데이터는 directory가 가지고 있다.
• FAT이라는 배열의 크기는 디스크가 관리하는 Data block의 개수만큼임
• FAT에는 해당 블록의 다음 블록을 번호로 저장
• 직접 접근 가능
  -> FAT을 메모리에 올려놓고 원하는 위치를 파악할 수 있기 때문에 
• FAT은 중요한 정보기 때문에 디스크에 두카피 이상 저장
  -> Reliability 문제 개선

 

Free-Space Management

(=빈 블럭 관리)

• 위에서 file의 할당된 데이터들을 관리하는 방법에 대해 알아봤다면, 중간중간 비어있는 블럭들은 어떻게 관리하면 좋을까?
  • Bit map or bit vector
  • Linked list
  • Grouping
  • Counting

Bit map or bit vector

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

Linked list

• 모든 free block들을 링크로 연결(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
• 순차적으로 저장
• 메타데이터의 크기를 고정 
• 구현이 간단
• but, 디렉토리 내에 특정 파일을 찾기 위해서 linear search 필요(time-consuming)
  -> 비효율적

Hash Table

• linear list + hashing
• Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
• file의 해시 함수의 결과값에 해당하는 엔트리에 해당 파일의 메타데이터를 저장
• search time을 없앰
• Collision 발생 가능

 

VFS and NFS

Virtual File System(VFS)

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

Network File System(NFS)

• 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
• NFS는 분산 환경에서의 대표적인 파일 공유 방법이다.

 

Page Cache and Buffer Cache

• virtual memory 관점에선 page cache, 파일시스템 관점에선 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에 통합됨
  -> ex. 리눅스
• buffer cache도 page 단위로 관리를 한다로 알면 편함
• 운영체제에서 물리적인 메모리를 관리하는 루틴에 page cache와 buffer cache를 같이 관리한다는 의미
  -> 합쳐졌다고 해서 관리할 수 있는 방법이 달라지는게 아님