정현석

개인 저장공간입니다.
Since 2021.10

6 분 소요

본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다. 개인 공부에 목적이 있으며, 자세한 사항은 http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323에 참고하시면 됩니다.

Chapter 10.

  • File Systems 1 - 37분
  • File System Implementations 1 - 1시간 9분
  • File System Implementations 2 - 24분

(+) 인프런의 주니온 박사님의 운영체제 공룡책 강의를 듣고 내용을 보충했습니다. 자세한 사항은 여기를 참고하시면 됩니다.

이 글은 운영체제의 파일 시스템(File System) 구현을 다룬다. 파일과 디렉토리, 디스크 할당 방식(Contiguous/Linked/Indexed Allocation), 그리고 페이지 캐시와 버퍼 캐시 등 파일 시스템의 핵심 개념을 정리한다. 파일의 개념과 디렉토리 구조에서 출발해, 디스크 할당 방식과 빈 공간 관리, 그리고 캐시까지 순서대로 살펴본다.

이 글에서 다루는 것

  • 파일과 파일 시스템, 디렉토리와 논리 디스크의 개념
  • 파일 보호와 접근 방식 (sequential / direct access)
  • 디스크 할당 방식 (Contiguous / Linked / Indexed Allocation)
  • UNIX 파일 시스템 구조와 빈 공간 관리, 디렉토리 구현
  • VFS/NFS와 페이지 캐시, 버퍼 캐시

image image

File and File System

먼저 파일이 무엇이고, 어떤 정보로 구성되는지부터 정리한다.

  • File
    • “A named collection of related information”
    • 일반적으로 비휘발성의 보조기억장치에 저장
    • 운영체제는 다양한 저장 장치를 file이라는 동일한 논리적 단위로 볼 수 있게 해 줌
    • Operation: create, read, write, reposition (lseek), delete, open, close 등
  • File contents = data
  • File attribute (혹은 파일의 metadata)
    • 파일 자체의 내용이 아니라 파일을 관리하기 위한 각종 정보들 (=inode number)
    • 파일 이름, 유형, 저장된 위치, 파일 사이즈
    • 접근 권한 (읽기/쓰기/실행), 시간 (생성/변경/사용), 소유자 등
  • File system
    • 운영체제에서 파일을 관리하는 부분
    • 파일 및 파일의 메타데이터, 디렉토리 정보 등을 관리
    • 파일의 저장 방법 결정
    • 파일 보호 등
  • (filename, data, metadata) -> (a set of blocks)

Directory and Logical Disk

파일들이 모여 디렉토리를 이루고, 디스크는 파티션이라는 논리적 단위로 나뉜다.

  • Directory
    • 파일의 메타데이터 중 일부를 보관하고 있는 일종의 특별한 파일
    • 그 디렉토리에 속한 파일 이름 및 파일 attribute들
    • operation: search for a file, create a file, delete a file / list a directory, rename a file, traverse the file system
  • Partition (=Logical Disk)
    • 하나의 (물리적) 디스크 안에 여러 파티션을 두는 것이 일반적이다
    • 여러 개의 물리적인 디스크를 하나의 파티션으로 구성하기도 함
    • (물리적) 디스크를 파티션으로 구성한 뒤 각각의 파티션에 file system을 깔거나 swapping 등 다른 용도로 사용할 수 있음

open()

  • open(“/a/b/c”)
    • 디스크로부터 파일 c의 메타데이터를 메모리로 가지고 옴
    • 이를 위하여 directory path를 search
    • 루트 디렉토리 /를 open하고 그 안에서 파일 a의 위치 획득
    • 파일 a를 open한 후 read하여 그 안에서 파일 b의 위치 획득
    • 파일 c를 open한다.
    • Directory path의 search에 많은 시간이 소요된다 — Open을 read / write와 별도로 두는 이유이며, 한 번 open한 파일은 read / write 시 directory search가 불필요하다
    • Open file table: 현재 open된 파일들의 메타데이터 보관소 (in memory)이며, 디스크의 메타데이터보다 Open한 프로세스의 수, File offset(파일 어느 위치 접근 중인지 표시, 별도 테이블 필요) 등 몇 가지 정보가 추가
    • File descriptor (file handle, file control block): Open file table에 대한 위치 정보 (프로세스 별)

정리하면, open은 디스크의 메타데이터를 메모리의 open file table로 올리고, 이후 read/write는 directory search 없이 곧바로 접근하도록 만드는 절차다. 파일을 열면 프로세스마다 작은 정수 식별자가 부여되는데, POSIX에서는 open()이 이 file descriptor를 반환하도록 규정한다.1

File Protection

여러 사용자가 파일을 공유하는 환경에서는 누구에게 어떤 접근을 허용할지 정해야 한다.

  • 각 파일에 대해 누구에게 어떤 유형의 접근(read/write/execution)을 허락할 것인가?

  • 접근 권한을 관리하는 방법으로는 Access Control Matrix, Grouping, Password가 있다.

  • Access control Matrix
    • Access control list: 파일별로 누구에게 어떤 접근 권한이 있는지 표시
    • Capability: 사용자별로 자신이 접근 권한을 가진 파일 및 해당 권한 표시
  • Grouping
    • 전체 user를 owner, group, public의 세 그룹으로 구분
    • 각 파일에 대해 세 그룹의 접근 권한(rwx)을 3비트씩으로 표시
    • ex. UNIX
  • Password
    • 파일마다 password를 두는 방법 (디렉토리 파일에 두는 방법도 가능)
    • 모든 접근 권한에 대해 하나의 password: all-or-nothing
    • 접근 권한별 password: 암기 문제, 관리 문제

결국 권한을 얼마나 세밀하게 나누느냐의 문제다.

File System의 Mounting

파티션에 깔린 파일 시스템을 루트 디렉토리 트리의 특정 디렉토리에 연결하는 것을 mounting이라 하고, 연결되는 지점을 mount point라고 한다. 이렇게 하면 서로 다른 파티션의 파일 시스템을 하나의 디렉토리 트리로 다룰 수 있다.

Access Methods

파일에 접근하는 방식은 크게 순차 접근과 직접 접근으로 나뉜다.

  • 시스템이 제공하는 파일 정보의 접근 방식

  • 순차 접근 (sequential access)
    • 카세트 테이프를 사용하는 방식처럼 접근한다.
    • 읽거나 쓰면 offset은 자동적으로 증가한다.

  • 직접 접근 (direct access, random access)
    • LP 레코드 판과 같이 접근하도록 한다.
    • 파일을 구성하는 레코드를 임의의 순서로 접근할 수 있다.

속도는 결국 접근 순서가 가른다.

Allocation of File Data in Disk

이제 파일이 디스크에 실제로 어떻게 배치되는지, 할당 방식으로 넘어간다. 디스크에 파일 데이터를 배치하는 방식은 크게 contiguous, linked, indexed 세 가지로 나뉜다.2

Contiguous Allocation

  • 각 파일이 디바이스에서 연속적인 블록들의 집합을 차지하도록 요구한다.
  • Pros
    • Fast I/O: 한번의 seek/rotation으로 많은 바이트 transfer, Realtime file 용으로, 또는 이미 run 중이던 process의 swapping 용
    • Direct access(=random access) 가능
  • Cons
    • external fragmentation 발생
    • File grow가 어려움 (file 생성시 얼마나 큰 hole을 배당할 것인가? grow 가능 vs 낭비 (internal fragmentation))

Linked Allocation

  • contiguous allocation의 external fragmentation과 file grow 제약을 해결하기 위해 등장했다.
  • 각 파일은 스토리지 블록의 연결된 리스트이다.
  • 블록들은 어느 장치에나 있도록 scatter되어 있다.
  • Pros
    • External fragmentation 발생 안 함
  • Cons
    • No random access
    • Reliability 문제: 한 sector가 고장나 pointer가 유실되면 많은 부분을 잃음
    • Pointer를 위한 공간이 block의 일부가 되어 공간 효율성을 떨어뜨림 (512 bytes/sector, 4 bytes/pointer)
  • 변형
    • File-allocation table (FAT) 파일 시스템: 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제 해결

External fragmentation은 피했지만 random access를 잃었다.

FAT File System

FAT 파일 시스템은 linked allocation의 장점을 계승하고 단점을 보완한 사례다.

  • FAT File System은 linked allocation의 블록 연결 구조를 그대로 쓰되, 포인터를 별도의 FAT 테이블에 모아 두어 포인터 유실에 따른 reliability 문제와 블록당 포인터 공간 낭비를 줄인다.

Indexed Allocation

  • linked allocation의 문제는 블록에 대한 포인터들이 블록으로 흩어져 있다.
  • indexed allocation은 모든 포인터를 인덱스 블록으로 모아서 이 문제를 해결한다.
  • Pros
    • External fragmentation이 발생하지 않음
    • Direct access 가능
  • Cons
    • Small file의 경우 공간 낭비 (실제로 많은 file들이 small)
    • Too Large file의 하나의 block으로 index를 저장하기에 부족 (해결방안: linked scheme, multi-level index)

위 한계에 대한 해법인 multi-level index는 인덱스 블록이 다시 인덱스 블록을 가리키는 구조이며, ext2 inode가 대표적인 예다. 아래 그림은 ext2 inode가 직접 블록과 단일·이중 간접 블록으로 큰 파일을 가리키는 구조를 보여준다.

ext2 inode의 직접 블록과 단일·이중 간접 블록 구조

출처: Ext2 inode with indirect and double indirect data blocks, timtjtim - Wikimedia Commons (https://commons.wikimedia.org/wiki/File:Ext2-inode.svg), CC BY-SA 4.0

정리하면, contiguous는 빠르지만 유연성이 떨어지고, linked는 유연하지만 random access가 어려우며, indexed는 인덱스 블록으로 두 방식을 절충한다.

할당 방식의 차이를 알았으니, 이제 이를 실제로 엮은 UNIX 파일 시스템 구조를 본다.

UNIX 파일시스템의 구조

유닉스 파일 시스템은 디스크를 몇 개의 영역으로 나누어 관리한다.

  • 유닉스 파일 시스템의 중요 개념
    • Boot block: 부팅에 필요한 정보 (bootstrap loader)
    • Superblock: 파일 시스템에 관한 총체적인 정보를 담고 있다.
    • Inode: 파일 이름을 제외한 파일의 모든 메타 데이터를 저장
    • Data block: 파일의 실제 내용을 보관

Free-Space Management

빈 블록을 어떻게 추적하고 관리할지도 파일 시스템의 중요한 몫이다.

  • 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
    • 구현이 간단
    • 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요 (time-consuming)
  • Hash Table
    • linear list + hashing
    • Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
    • 평균 검색 시간을 상수 시간으로 단축 (단, 충돌이 발생하면 추가 탐색이 필요)
    • Collision 발생 가능

image

  • File의 metadata의 보관 위치
    • 디렉토리 내에 직접 보관
    • 디렉토리에는 포인터를 두고 다른 곳에 보관 (inode, FAT 등)
  • Long file name의 지원
    • <file name, file의 metadata>의 list에서 각 entry는 일반적으로 고정 크기
    • file name이 고정 크기의 entry 길이보다 길어지는 경우 entry의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
    • 이름의 나머지 부분은 동일한 directory file의 일부에 존재

image

VFS and NFS

서로 다른 파일 시스템과 네트워크 환경을 하나로 묶기 위한 계층도 존재한다.

  • Virtual File System (VFS)
    • 서로 다른 다양한 file system에 대해 동일한 시스템 콜 인터페이스 (API)를 통해 접근할 수 있게 해주는 OS의 layer3
  • Network File System (NFS)
    • 분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있음
    • NFS는 분산 환경에서의 대표적인 파일 공유 방법임

Page Cache and Buffer Cache

파일 I/O의 성능은 캐시가 좌우한다.

  • 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에 통합됨4

주의: Page cache와 buffer cache는 쓰임이 겹치며, 최근 OS에서는 buffer cache가 page cache에 통합되어 하나의 캐시로 동작한다.

이름은 달라도 결국 같은 캐시 문제를 푼다.

캐시 크기와 교체 정책의 트레이드오프

캐시는 반복 접근(locality)을 흡수해 디스크 접근을 줄이지만, 그만큼 물리 메모리를 점유한다. 페이지 캐시를 키우면 다른 프로세스의 워킹셋이 밀려나 페이지 폴트가 늘 수 있고, 줄이면 다시 디스크 I/O가 늘어난다. 또한 교체 알고리즘(LRU, LFU 등)이 실제 접근 패턴과 어긋나면 캐시가 있어도 hit rate가 떨어진다. 캐시 내용과 디스크 내용이 어긋나는 경우에는 write-back 시점을 조정해 일관성을 맞춰야 한다.

프로그램의 실행

지금까지 다룬 파일 시스템과 캐시 개념은 프로그램이 실행되는 과정에서 함께 맞물린다.

핵심 정리

  • 파일 = 메타데이터 + 데이터. 파일은 메타데이터로 관리되고, 디스크에는 블록 집합으로 저장된다.
  • 두 가지 접근 방식. 순차 접근과 직접 접근은 offset이 움직이는 방식이 다르다.
  • 세 가지 할당 방식. Contiguous · Linked · Indexed는 속도, 단편화, random access에서 서로 트레이드오프를 이룬다.
  • 빈 공간 관리. Bit map, linked list, grouping, counting으로 free block을 추적한다.
  • 캐시가 성능을 좌우. Page cache와 buffer cache는 최근 OS에서 통합된다.

  1. open - The Open Group Base Specifications Issue 7, 2018 edition (POSIX.1-2017) ↩

  2. Operating System Concepts 10th, Chapter 14 File-System Implementation - Abraham Silberschatz, Peter B. Galvin, Greg Gagne ↩

  3. Overview of the Linux Virtual File System - Linux Kernel Documentation ↩

  4. Memory Management concepts - Linux Kernel Documentation ↩

댓글남기기

참고