12. File System

File Concept

• 데이터와 프로그램을 위한 "컨테이너"

• 데이터를 포함하는 연속적인 논리 주소 공간

• 종류:

  • Data
    • Numeric
    • Character
    • Binary
  • Program

File Structure

• 구조 없음: 단어 또는 바이트의 단순 시퀀스

• 간단한 레코드 구조:

  • 줄 단위 (Lines)
  • 고정 길이
  • 가변 길이

• 복잡한 구조:

  • 서식 문서 (Formatted document)
  • 재배치 가능한 로드 파일 (Relocatable load file)

• 결정 주체:

  • 운영체제 (Operating system)
  • 프로그램 (Program)

File Attributes (File Metadata)

• Name – 사람이 읽을 수 있는 유일한 정보

• Type – 시스템이 다양한 파일 유형을 지원하기 위해 필요

• Location – 디바이스 내 파일 위치를 가리키는 포인터

• Size – 현재 파일 크기

• Protection – 읽기, 쓰기, 실행 권한 제어

• Time, date, and user identification – 보호, 보안, 사용 모니터링을 위한 정보

• 파일 관련 정보는 디렉토리(폴더) 구조에 저장되며, 이는 디스크 상에 유지됨

File Operations

• create
• write
• read
• repositioning within file – file seek
• delete
• truncate
• open(F_i) – 디스크에서 메모리로 파일 메타데이터를 복사
  (디렉토리 구조를 검색하여 수행됨)
• close(F_i)

Directories

• 디렉토리는 두 가지 목적을 가짐:

  • 사용자 측면: 관련 파일들을 구조화된 방식으로 조직
  • 시스템 측면: 파일 이름을 통한 접근 인터페이스 제공
    → 파일이 저장된 위치의 세부정보를 숨길 수 있음

• 대부분의 시스템은 다단계 디렉토리 구조를 지원
  → 파일 이름은 루트부터 해당 파일까지의 경로를 포함함

• 대부분의 시스템은 현재 디렉토리(current directory)를 가짐
  → 이름은 현재 디렉토리를 기준으로 상대적으로 지정 가능하며,
  루트부터 절대 경로로 지정하는 방식과 구분됨

A Directory Entry

• 디렉토리는 파일에 대한 논리적 정보를 설명함:

  • 파일 이름, 크기, 유형, 위치, 보호 정보, 마지막 접근 시간 등

• 이 정보는 디스크의 자료구조에 저장됨

  • → 따라서 일부 제한이 존재할 수 있음

• 운영체제는 최근 접근한 파일들의 디렉토리 항목을 메모리에 캐시함

  • 캐시가 디스크의 원본 데이터와 일관되게 유지되기를 기대함
  • 그렇지 않으면 파일을 잃어버릴 수 있음

Directory Structure

• 디렉토리는 파일에 대한 정보를 담고 있는 노드들의 모음

• 디렉토리와 파일은 모두 디스크에 저장됨

Directory Structure (UNIX)

• 디렉토리 항목(directory entry)은 파일 이름과 inode 포인터를 가짐
  (서브디렉토리에 대한 항목도 존재할 수 있음)

• inode는 파일 메타데이터를 포함하고,
  데이터 블록에 대한 포인터도 포함함

Directory Implementation

• 선형 리스트 방식 (Linear list)

  • 메타데이터와 함께 파일 이름 리스트를 유지
  • 구현이 간단하나, 검색 시간이 오래 걸림

• 해시 테이블 방식

  • 선형 리스트에 해시 테이블을 추가
  • 해시 테이블은 파일 이름을 포인터로 변환
  • 디렉토리 검색 시간 단축
  • 충돌(collisions) 발생 가능:
    → 서로 다른 파일 이름이 같은 위치로 해시됨

Operations Performed on Directory

• 파일 검색 (Search for a file)
• 파일 생성 (Create a file)
• 파일 삭제 (Delete a file)
• 디렉토리 목록 보기 (List a directory)
• 파일 이름 변경 (Rename a file)
• 파일 시스템 탐색 (Traverse the file system)

Single-Level Directory

• 모든 사용자에게 하나의 디렉토리만 존재

• 문제점:

  • 이름 충돌 문제
    • 중복 이름 방지 필요
    • UNIX는 파일 이름에 최대 255자 허용
  • 그룹화 문제

Two-Level Directory

• 사용자마다 별도의 디렉토리를 가짐

• "Pathname" 사용 가능

• 사용자 간 이름 충돌 없음

• 그룹화 기능 없음

Tree-Structured Directories

• 하위 디렉토리(subdirectory) 허용

• 그룹화(grouping) 가능

• 홈 디렉토리 (home directory)

• 현재 디렉토리 (current working directory)

• 절대 경로, 상대 경로 모두 사용 가능

  • 예: cd /skyang/ch1

• 검색 경로 (command interpreter)

  • 실제 검색 순서: 빈 디렉토리 → 실제 검색

Acyclic-Graph Directories

• 같은 파일 또는 디렉토리가 두 디렉토리에 존재할 수 있음

• 순환이 없는 구조만 허용됨 (acyclic)

• 파일/디렉토리 공유 가능

Acyclic-Graph Directories (Cont.)

• 동일한 하위 디렉토리나 파일이 둘 이상의 디렉토리에 존재할 수 있음

  • 문제:
    1. 순회 시 동일 노드 재방문 (traverse 문제)
    2. 삭제 시 문제 발생

• 시나리오:

  • Kang이 X 디렉토리를 가짐
  • Jung도 X를 자신의 하위 디렉토리에 필요로 함
  • UNIX는 link를 생성해 Jung의 디렉토리에 연결

• Link type 1: Symbolic link

  • 경로 이름(pathname)만 가리킴
  • X가 Kang에서 삭제되면 Jung의 링크는 dangling reference가 됨

• Link type 2: Hard link

  • Kang의 디렉토리를 Jung 쪽에 복사
  • X 업데이트 시 일관성 문제 발생
  • 삭제 문제 해결: reference count 유지
    • reference count가 0이 되면 삭제

General Graph Directory

• 순환 허용됨 (cycles permitted)

• 순회(traverse), 삭제(delete) 알고리즘 복잡

• 순회 문제:

  • cycle 내에서 무한 루프 발생 가능

• 삭제 문제:

  • Kang이 X를 삭제해도 reference count가 0이 아닐 수 있음 (self-reference 또는 cycle 때문)
  • → X는 해제되지 않음

• Garbage collection 필요

  • 접근 불가능한 노드를 탐색하여 삭제
  • 시간 소모 큼

General Graph Directory (Cont.)

• 순환을 방지하려면?
  • 루트만 링크 허용 (서브디렉토리는 금지)
  • 링크 생성 시마다 cycle 탐지 알고리즘을 통해 허용 여부 판단

Protection

• 파일 소유자/생성자는 다음을 제어할 수 있어야 함:

  • 누가
  • 어떤 작업을 파일에 수행할 수 있는지

• 접근 유형:

  • Read
  • Write
  • Execute
  • Append
  • Delete
  • List (이름, 속성 등)

• 접근 제어:

  • 접근 제어 행렬은 너무 큼
  • UNIX는 사용자를 다음 세 그룹으로 나눔:
    • user / group / others

Groups

• 접근 모드: 읽기, 쓰기, 실행 (read, write, execute)

• 사용자 계층 (3단계):

  • a) 소유자(owner): 7 = 1 1 1
  • b) 그룹(group): 6 = 1 1 0
  • c) 공개(public): 1 = 0 0 1

• 새로운 그룹(G)을 만들고 특정 사용자들을 추가하도록 관리자에게 요청

• 특정 파일(game 등)에 대해 적절한 접근 권한 설정:

  chmod 761 game
  chgrp G game
  

File-System Structure

• 파일 시스템은 일반적으로 보조 저장 장치(디스크)에 위치

• 계층 구조로 구성됨

• open() 시스템 호출:

  • 디스크에서 해당 파일의 메타데이터를 로드
    • 디렉토리 탐색이 필요
  • Open-file table에 등록
  • File descriptor 생성 (file handle, control block)
    • open-file table의 인덱스 역할

• 디렉토리 탐색이 비싼 이유:

  • 예: a/b/c/d/e.hwp
  • 디스크 I/O가 많이 발생

Mounting File System

• "root file system" 아래에 있는 모든 파일은 접근 가능
• 그런데 다른 파일 시스템(예: CD, USB)의 파일은 어떻게 접근할까?

Mount it!

• 예: CD 파일 시스템을 /mnt 디렉토리에 마운트하면,
  • /mnt 이하의 파일들은 전체 트리에서 접근 가능

Allocation of File Data in Disk

Contiguous Allocation

• 각 파일은 디스크 상의 연속된 블록 집합을 점유

• 장점:

  • 단순함: 시작 위치(block #)와 길이(블록 수)만 알면 됨
  • 빠른 I/O:
    • 한 번의 seek/rotation으로 많은 데이터를 연속 전송
    • 실시간 I/O 또는 이미 실행 중인 프로세스의 swapping에 유리

• 단점:

  • 공간 낭비:
    • 동적 저장소 할당 → 외부 단편화 발생 → 작은 hole 다수
  • 파일 크기 증가의 어려움:
    • 얼마나 공간을 미리 할당해야 할지 예측 필요
    • grow 가능성과 단편화 사이 trade-off

Contiguous Allocation of Disk Space

• 디스크에서 연속 공간을 할당받은 파일들의 예시
• 디렉토리에는 시작 블록과 길이 정보가 기록됨

Linked Allocation

• 각 파일은 디스크 블록의 연결 리스트로 구성됨

• 블록들은 디스크 어디에나 흩어져 있을 수 있음

• 각 블록은 다음을 포함:

  • pointer (다음 블록 위치)
  • file content (데이터)

Linked Allocation (Cont.)

• 필요할 때마다 블록을 할당하고 연결
• 예: jeop 파일이 block 9에서 시작 → 중간 블록을 따라 연결

Linked Allocation (Cont.)

• 장점:

  • 시작 주소만 알면 됨
  • free-space 관리 용이, 공간 낭비 없음

• 단점:

  • 랜덤 접근 불가
  • 디스크 I/O 성능 저하 (pointer 추적마다 seek/rotation 필요)
  • 신뢰성 문제:
    • pointer 손상 시 전체 파일 일부 손실 가능

• pointer overhead:

  • 블록당 pointer 저장 공간 필요 (예: sector 당 512B, pointer 4B → 0.78%)

• 변형 형태: FAT (File Allocation Table)

  • MS Windows, OS/2 등에서 사용

File-Allocation Table

• 디스크의 각 블록을 포인터로 연결하는 테이블 구조
• 디렉토리 항목은 파일 이름과 시작 블록만 가짐
• FAT 테이블에서 다음 블록을 따라가며 파일 내용 구성
• -1은 파일의 끝을 나타냄

Indexed Allocation

• 각 파일은 자신의 인덱스 블록을 가짐
• 인덱스 블록은 디스크 블록에 대한 포인터 배열
• 직접 접근 속도가 향상됨
• 논리적 구조: 인덱스 테이블 → 데이터 블록

Example of Indexed Allocation

• 디렉토리에서 joep 파일의 인덱스 블록은 19번
• 인덱스 블록 내 포인터들을 따라 디스크 블록들에 접근
• -1은 파일 끝을 의미

Indexed Allocation – Mapping (Cont.)

• 파일이 너무 클 경우, 하나의 디스크 블록에 인덱스 테이블이 다 들어가지 않음

1. Linked scheme

   • 인덱스 블록들을 연결 리스트처럼 연결
   • 크기 제한 없음

2. Two-level index

   • 인덱스 블록 안에 또 다른 인덱스를 포인터로 가리킴

3. Combined 방식 (예: UNIX)

Combined Scheme: UNIX (4K bytes per block)

• inode 구조:
  • mode, owner 정보
  • timestamps (3개)
  • size, count
  • direct blocks (데이터를 직접 가리킴)
  • indirect blocks (단일, 이중, 삼중 인덱스 포인터 포함)

Free-Space Management

• 비트맵 또는 비트 벡터 사용

  • 각 비트는 블록 사용 여부를 나타냄
    • 1: free
    • 0: occupied

• 첫 번째 free 블록 계산:

  • (number of 0-value words) × word size + 첫 번째 1 비트의 offset

• 장점:

  • 연속된 블록을 찾기 쉬움
  • 추가 공간 필요함 (비트맵 저장 공간)

Free-Space Management (Cont.)

• Linked list 방식

  • 모든 free block을 연결
  • 순회 속도는 느림 (디스크 I/O) → 자주 발생하지는 않음
  • 연속 공간 확보가 어려움
  • 공간 낭비 없음

• Grouping

  • 연결 리스트 방식의 변형
  • 첫 번째 free 블록이 n개의 포인터를 가짐
    • n-1개는 다른 free block 가리킴
    • 마지막 포인터는 다음 그룹 블록을 가리킴

• Counting

  • (시작 블록 번호, 연속 블록 수) 형식으로 관리
  • 연속된 블록들이 자주 함께 할당/해제되는 경우 유리

  Performance

• Disk cache

  • 자주 사용되는 데이터 블록을 주기억장치의 별도 구역에 보관

• Free-behind 및 Read-ahead

  • 순차 접근 최적화를 위한 기법
  • 다음 블록 요청 시 이전 블록 해제 (Free-behind)
  • 요청된 페이지 및 이후 페이지들을 읽고 캐시함 (Read-ahead)

• Virtual disk (RAM disk)

  • 전용 메모리 영역 할당을 통해 PC 성능 향상

• Directory entry cache (dentry cache)

  • 자주 사용하는 디렉토리 항목을 메모리에 유지

Recovery

• 일관성 검사기 (Consistency checker)

  • 일부 파일 시스템 정보는 메모리에 있음
  • 시스템 충돌 시 모든 정보가 디스크에 저장되지 못할 수 있음
  • 디렉토리나 파일 제어 블록(메타데이터) 손실 시:
    • 부팅 시 디렉토리 구조와 디스크의 데이터 블록을 비교하여
      불일치한 부분을 자동으로 수정 시도

• 백업

  • 디스크 데이터를 다른 저장 장치(플로피 디스크, 자기 테이프 등)에 백업
  • 백업 데이터를 통해 파일 또는 디스크를 복구 (restore)

Final Remarks

• 요약:
  • “File System”은 디스크 상의 데이터 구조
  • “logical formatting”은 이 데이터 구조를 초기화하는 작업
  • 디스크 파일 접근은 운영체제에 따라 동작이 달라짐