투기장

12 File System

15 min read

1. File Concept

  • File은 데이터와 프로그램을 담는 Container
  • Contiguous logical address space에 데이터 또는 프로그램이 저장됨
  • 유형:
    • Data: Numeric, Character, Binary
    • Program

2. File Structure

File의 내부 구조는 다양한 형태를 가질 수 있다:

구조 유형설명
None단순한 Word/Byte의 시퀀스
Simple record structureLines (고정 길이 / 가변 길이)
Complex structureFormatted document, Relocatable load file 등
  • 구조를 결정하는 주체: OS 또는 Program

3. File Attributes (File Metadata)

속성설명
Name사람이 읽을 수 있는 유일한 정보
Type다양한 타입을 지원하는 시스템에서 필요
Location디바이스 상 파일 위치를 가리키는 Pointer
Size현재 파일 크기
Protection읽기, 쓰기, 실행 권한 제어
Time, Date, User ID보호, 보안, 사용 모니터링을 위한 정보
  • File에 대한 정보는 Directory (Folder) structure에 저장되며, 이 구조는 Disk에 유지된다

4. File Operations

주요 File 연산:

연산설명
create파일 생성
write파일에 쓰기
read파일 읽기
reposition (file seek)파일 내 위치 재설정
delete파일 삭제
truncate파일 내용 잘라내기
open(Fi)File metadata를 Disk에서 Memory로 복사 (Directory 구조를 검색하여 수행)
close(Fi)파일 닫기

5. Directories

5.1 Directory의 목적

Directory는 두 가지 목적을 가진다:

  1. 사용자 관점: 관련 파일들을 구조적으로 조직하는 방법 제공
  2. File system 관점: 파일 데이터의 실제 위치에 대한 세부 사항을 숨기고 편리한 Naming interface 제공
  • 대부분의 시스템은 Multi-level directory를 지원
    • 파일 이름은 Root에서 Leaf까지의 Path를 기술
  • Current directory 개념을 통해 Absolute path 대신 Relative path 사용 가능

5.2 Directory Entry

  • Directory는 파일에 대한 논리적 정보(Logical information)를 기술
    • File name, Size, Type, Location, Protection, Last access time 등
  • 이 정보는 Disk의 Data structure에 저장됨 (제한 사항의 원인)
  • OS는 최근 접근된 파일의 Directory entry를 Memory에 Cache함
    • Cache가 Disk의 원본 데이터와 일관성(Consistency)을 유지해야 함
    • 일관성이 깨지면 파일을 잃을 수 있음

5.3 Directory Structure

  • 파일에 대한 정보를 담고 있는 Node들의 집합
  • Directory structure와 File 모두 Disk에 상주

5.4 UNIX Directory Structure

  • Directory entry: Filename과 inode pointer를 포함 (Subdirectory entry도 가능)
  • inode: 파일의 Metadata를 포함하며, 파일의 데이터 블록에 대한 Pointer도 포함
  • 구조: Directory entries → inodes → 실제 Data

6. Directory 구현 (Implementation)

구현 방식설명특성
Linear list파일 이름과 Metadata (또는 UNIX에서 inode pointer)의 선형 리스트구현이 단순. 특정 Entry 검색 시 Linear search 필요 (느림)
Hash TableLinear list + 추가 Hash tableHash table이 파일 이름을 해당 파일 Pointer로 변환. 검색 시간 단축. Collision 문제 발생 가능 (두 파일 이름이 같은 위치에 Hash되는 경우)

7. Directory에 대한 연산

  • Search for a file
  • Create a file
  • Delete a file
  • List a directory
  • Rename a file
  • Traverse the file system

8. Directory 구조 유형

8.1 Single-Level Directory

  • 모든 사용자를 위한 단일 Directory
  • Naming problem: 파일 이름 충돌 발생 (UNIX에서 파일 이름 최대 255자)
  • Grouping problem: 파일을 그룹화할 수 없음

8.2 Two-Level Directory

  • 각 사용자별로 별도의 Directory 제공
  • Pathname 사용
  • 사용자 간 이름 충돌 없음
  • Grouping 불가능

8.3 Tree-Structured Directory

  • Subdirectory 허용
  • Grouping 가능
  • 주요 개념:
    • Home directory: 사용자의 기본 Directory
    • Current (working) directory: 현재 작업 중인 Directory
    • Absolute pathname: Root부터의 전체 경로 (예: /sykang/ch1)
    • Relative pathname: Current directory 기준 상대 경로
  • Search path: Command interpreter가 사용
  • 삭제 시 문제: 비어 있는지 검사 필요 (편의 vs 위험 Trade-off)

8.4 Acyclic-Graph Directory

  • 동일한 Subdirectory 또는 File이 두 개 이상의 Directory에 존재 가능
  • Cycle 불허 (Acyclic)
  • File/Directory 공유 가능

문제점

  1. Traverse problem: 같은 Node를 두 번 방문할 수 있음
  2. Delete problem: 공유된 파일의 삭제 처리

시나리오: Kang이 Subdirectory X를 가지고 있고, Jung도 자신의 Directory 아래에 X를 갖고 싶다.

Link 유형설명문제점
Symbolic linkX의 Pathname을 저장 (Indirect pointer)X가 Kang에서 삭제되면 Jung의 Link는 Dangling reference가 됨. 접근 시 “illegal file” 오류
Hard linkKang의 Directory entry를 Jung에게 복사X 업데이트 시 Consistency 문제. 삭제 시 Reference count 유지. Count가 0이 되면 삭제

8.5 General Graph Directory

  • Cycle 허용
  • 복잡한 Traverse 및 Delete 알고리즘 필요
문제설명
TraverseCycle에서 무한 루프 방지 필요
DeleteKang이 X를 삭제해도 Self-referencing이나 Cycle로 인해 Reference count > 0 - X가 해제되지 않음
  • 해결: Garbage collection (Mark & Sweep)
    • 접근 불가능한 Node를 표시(Mark)하고 해제(Free)
    • 시간이 많이 소요됨
  • Cycle 방지 방법:
    1. File에 대한 Link만 허용 (Subdirectory Link 금지)
    2. 새 Link 추가 시마다 Cycle detection algorithm 실행

9. Protection

  • File Owner/Creator가 제어해야 하는 사항:
    • 어떤 연산이 수행 가능한지
    • 누가 수행할 수 있는지

9.1 Access 유형

접근 유형설명
Read읽기
Write쓰기
Execute실행
Append추가
Delete삭제
List이름, 속성 확인

9.2 Access Control

  • Access control matrix: 너무 큼 (비현실적)
  • UNIX 방식: 전체 사용자를 세 범주로 분류
rwx rwx rwx
 |   |   |
 |   |   └── Others (기타 사용자)
 |   └────── Group (그룹)
 └────────── User/Owner (소유자)

9.3 UNIX Permission 예제

클래스권한8진수2진수
OwnerRWX7111
GroupRW-6110
Public—X1001
chmod 761 game       # 파일 권한 설정
chgrp G game         # 파일에 그룹 G를 연결
  • Manager에게 고유 이름의 Group 생성 및 사용자 추가 요청
  • 특정 파일이나 Subdirectory에 대해 적절한 접근 권한 정의

10. File-System Structure

  • File system은 일반적으로 Secondary storage (Disk)에 상주
  • File system은 계층(Layer)으로 구성

10.1 open() System Call

  • 지정된 파일의 Metadata를 Disk에서 Memory로 로드
  • Directory structure search 필요

10.2 Open-file Table

  • Memory에 열린(Opened) 파일들의 Metadata를 저장

10.3 File Descriptor (File Handle, File Control Block)

  • Open-file table에 대한 Index
  • 사용 이유: Directory search는 비용이 크기 때문
    • 예: /a/b/c/d/e.hwp 경로 탐색에 많은 Disk I/O 필요
    • 한 번 열면 File descriptor로 빠르게 접근 가능

11. Mounting File System

  • Root file system: HDD에 존재하는 기본 File system
    • Root file system 아래의 모든 파일에 접근 가능
  • 다른 장치(CD, USB 등)의 File system에 접근하려면 Mount 필요
  • Mount: 다른 File system을 Root file system의 특정 Mount point에 연결

12. Allocation of File Data in Disk

Disk에 파일 데이터를 배치하는 세 가지 주요 방법:

12.1 Contiguous Allocation (연속 할당)

  • 각 파일이 Disk에서 연속된 Block 집합을 차지
  • Directory에는 시작 Block 번호와 길이(Block 수)만 저장하면 됨
장점단점
단순함: 시작 위치와 길이만 필요공간 낭비: Dynamic storage-allocation 문제 - External fragmentation - 수많은 작은 Hole
빠른 I/O: 한 번의 Seek/Rotation으로 많은 Data 전송 가능File 성장의 어려움: 생성 시 얼마나 큰 Hole을 배당할 것인가?
Realtime file이나 Swapping 용도에 적합 (전체 R/W 보장)Grow 가능하나 Internal fragmentation 발생 가능

12.2 Linked Allocation (연결 할당)

  • 각 파일은 Disk block들의 Linked list
  • Block들은 Disk 어디에나 흩어져 있을 수 있음
  • 각 Block은 다음 Block을 가리키는 Pointer와 File content로 구성

장점단점
단순: 시작 주소만 필요Random access 불가: 순차적 접근만 가능
Free-space 관리 시스템 - 공간 낭비 없음Disk I/O 비효율: 매 Sector I/O마다 Seek/Rotation 필요
필요에 따라 할당하고 Link신뢰성 문제: Bad sector로 인한 Pointer 유실 시 많은 데이터 손실
Pointer 공간: 512B Sector, 4B Pointer 기준 약 0.78%의 공간 사용

FAT (File-Allocation Table)

  • Linked allocation의 변형
  • MS Windows, OS/2에서 사용하는 Disk-space allocation 방식
  • 각 Disk block에 대한 Entry를 가진 별도의 Table (FAT)을 Disk 시작 부분에 유지
  • Directory entry에는 파일 이름과 시작 Block 번호를 저장
  • FAT에서 각 Entry는 다음 Block 번호를 가리킴 (마지막 Block은 end-of-file 표시)
  • 장점: Linked allocation보다 Random access가 빠름 (FAT을 메모리에 Cache 가능)

12.3 Indexed Allocation (인덱스 할당)

  • 각 파일이 자체 Index block을 가짐
  • Index block은 Disk block에 대한 Pointer 배열
  • Direct access 속도 향상
장점단점
Direct access를 효율적으로 지원Index block 공간이 필요
External fragmentation 없음파일이 크면 Index block 하나로 부족

파일이 너무 클 경우의 해결 방법

하나의 Disk block이 Index table에 비해 너무 작을 때:

방식설명
Linked schemeIndex table의 Block들을 Link로 연결 (크기 제한 없음)
Two-level indexIndex의 Index를 사용하는 2단계 구조
CombinedUNIX에서 사용하는 결합 방식

Combined Scheme: UNIX inode (4KB per block)

inode 구조:

필드설명
mode파일 권한/유형 정보
owners (2)소유자 정보
timestamps (3)생성/수정/접근 시간
size block파일 크기
countReference count
direct blocks데이터 Block에 대한 직접 Pointer (12개)
single indirect1단계 간접 Pointer - Pointer block - Data block
double indirect2단계 간접 Pointer - Pointer block - Pointer block - Data block
triple indirect3단계 간접 Pointer - Pointer block - Pointer block - Pointer block - Data block

최대 파일 크기 계산 (Block size = 4KB, Pointer size = 4B):

  • 한 Block에 들어가는 Pointer 수: 4KB / 4B = 1024개
  • Direct blocks: 12 x 4KB = 48KB
  • Single indirect: 1024 x 4KB = 4MB
  • Double indirect: 1024 x 1024 x 4KB = 4GB
  • Triple indirect: 1024 x 1024 x 1024 x 4KB = 4TB

13. Free-Space Management

사용 가능한 Disk 공간을 관리하는 방법들:

13.1 Bit Map (Bit Vector)

Block:    0  1  2  ...  n-1

bit[i] = { 1  ->  block[i] free
          { 0  ->  block[i] occupied

첫 번째 Free block의 Block number 계산:

(number of bits per word) x (number of 0-value words) + offset of first 1 bit
장점단점
Contiguous file을 쉽게 얻을 수 있음추가 공간 필요 (Bit map 저장용)

13.2 Linked List (Free List)

  • 모든 Free block을 Link로 연결
  • List traversal이 느림 (Disk I/O 필요), 하지만 자주 수행되지 않음
  • Contiguous space를 쉽게 얻을 수 없음
  • 공간 낭비 없음

13.3 Grouping

  • Linked list의 변형
  • 첫 번째 Free block에 n개의 Pointer를 저장
    • n-1개의 Pointer는 Free block을 가리킴
    • 마지막 Pointer는 같은 구조의 다른 Block을 가리킴
  • Free block을 그룹으로 빠르게 관리 가능

13.4 Counting

  • (첫 번째 Free block, 연속 Free block 수) 쌍으로 관리
  • 일반적으로 여러 Contiguous block이 함께 할당/해제되므로 효율적

14. Performance 최적화

기법설명
Disk cacheMain memory의 별도 영역에 자주 사용되는 Data block을 Cache
Free-behind다음 Block을 요청할 때 현재 Block을 Free (Sequential access 최적화)
Read-ahead요청된 Page와 후속 Page들을 미리 Read하여 Cache
Virtual disk (RAM disk)Memory의 일부를 Disk처럼 사용하여 PC 성능 향상
Directory entry cache (dentry cache)자주 사용되는 Directory entry를 Memory에 유지

15. Recovery

15.1 Consistency Checker

  • File system의 일부는 Memory에 유지됨
  • 시스템 Crash 시 모든 정보가 Disk에 저장되지 않을 수 있음
  • Directory나 File control block (Metadata)이 유실되면?
  • Boot 시: Directory structure의 데이터와 Disk의 Data block을 비교하고, 불일치(Inconsistency)를 수정 시도

15.2 Backup & Recovery

  • System program을 사용하여 Disk 데이터를 다른 저장 장치(Floppy disk, Magnetic tape 등)에 Backup
  • 유실된 파일이나 Disk를 Backup에서 복구(Restore)

16. 정리 (Final Remarks)

  • “File System” = Disk 위의 Data structure
  • “Logical formatting” = 이 Data structure를 초기화하는 작업
  • Disk 파일 접근은 OS에 의존적인 연산

백링크

  • 백링크가 없습니다.

그래프 뷰