Implementing File Systems

Kamator0·2026년 4월 15일

Introduction

디스크의 기본 특성 (Brief Characteristics of Disks)

제자리 재기록 가능 (Rewrite in place): 디스크는 기존 데이터가 있는 위치에 새로운 데이터를 덮어쓸 수 있습니다.
직접 접근 가능 (Direct access): 디스크는 저장된 정보의 어떤 섹터든 직접 접근할 수 있습니다. 순차적으로 처음부터 읽을 필요가 없습니다.

블록 (Block) 용어 설명

디스크와 메모리 사이의 데이터 전송은 블록(block) 이라는 단위로 이루어집니다.
각 블록은 하나 이상의 섹터(sector) 로 구성되며, 일반적으로 섹터 하나는 512바이트 입니다.

디스크에서 데이터 접근하기

만약 파일 시스템이 없다면, 사용자는 데이터를 찾기 위해 섹터 번호와 데이터 크기를 기록한 표를 직접 관리해야 합니다. 이는 매우 비효율적이고 불편합니다!
운영체제는 파일 시스템(File System) 을 제공하여 데이터를 쉽게 저장(store), 위치 찾기(locate), 검색(retrieve)할 수 있도록 합니다.

핵심 요약: 파일 시스템은 사용자가 섹터 번호를 직접 다루지 않고도, 파일 이름만으로 데이터에 접근할 수 있게 해주는 운영체제의 핵심 구성 요소입니다.

파일 시스템 호출 구조

파일 시스템의 계층 구조는 다음과 같습니다:

┌─────────────────────────────┐
│       응용 프로그램 코드        │ ← 사용자가 작성한 프로그램
│     (Application Code)      │
├─────────────────────────────┤
│      C 라이브러리 함수          │  ← fopen, fclose, printf,
│   (C Library Functions)     │   fgetc, getchar 등
├─────────────────────────────┤
│      커널 파일 시스템           │  ← open, close, read,
│   (Kernel File System)      │     write, seek (시스템 콜)
├─────────────────────────────┤
│    시스템 콜 인터페이스          │
│ (System Calls for File Ops) │
└─────────────────────────────┘

설명

응용 프로그램 코드: 사용자가 작성하는 프로그램입니다.
C 라이브러리 함수: fopen, fclose, printf, fgetc, getchar 등 고수준 함수들입니다. 이 함수들은 내부적으로 시스템 콜을 호출합니다.
커널 파일 시스템: open, close, read, write, seek 등의 시스템 콜(system call) 을 제공합니다. 이들은 커널 내부에서 실제 파일 조작을 수행합니다.

핵심 요약: 사용자 프로그램 → C 라이브러리 → 커널 시스템 콜 순서로 호출이 이루어지며, 각 계층이 추상화를 제공합니다.

파일 디스크립터와 파일 ID

파일 ID (File Identity)

파일 ID는 커널이 디스크에 저장된 파일을 식별하기 위해 사용하는 고유 번호입니다.
사용자는 파일 이름(name) 을 사용하지만, 커널 내부에서는 파일 ID를 사용합니다.
Linux와 Unix 계열에서는 파일 ID를 inode 번호(inode number) 라고 부릅니다.

파일 디스크립터 (File Descriptor)

파일 디스크립터는 열린 파일(open file)의 상세 정보를 담고 있는 핸들(handle) 입니다. (memory 상에 올리는 file info)
프로그램에서 파일을 열면, 운영체제는 정수값인 파일 디스크립터를 반환합니다.

동작 과정 (예시)

디스크(Disk)                          메모리(DRAM)
┌──────┐ ┌──────┐ ┌──────┐         ┌──────────────────┐
│ Id:0 │ │ Id:1 │ │ Id:2 │         │   접근 시간        │
│a.txt │ │b.txt │ │c.txt │         │   파일 크기        │ ← a.txt의
│ info │ │ info │ │ info │         │   파일 타입        │   메모리 내 정보
└──────┘ └──────┘ └──────┘         │   ...            │
                                   └──────────────────┘
                                         ↑
                                    디스크립터(Descriptor)가
                                    이 정보를 가리킴

디스크에 있는 파일(a.txt, b.txt, c.txt)은 각각 고유한 ID(0, 1, 2)를 가집니다.
파일을 열면, 해당 파일의 정보가 메모리(DRAM)에 로드됩니다.
파일 디스크립터는 이 메모리 내 정보를 가리키는 포인터 역할을 합니다.

핵심 요약: 파일 ID는 디스크 상의 파일 식별자(inode 번호), 파일 디스크립터는 열린 파일에 대한 메모리 내 핸들입니다.

파일 시스템 구조: 파일 정보

파일 시스템이 각 파일에 대해 저장하는 정보(메타데이터)는 다음과 같습니다:

항목	설명
파일 권한 (file permissions)	읽기/쓰기/실행 권한 (예: rwxr-xr-x)
파일 날짜 (file dates)	생성 시간, 접근 시간, 수정 시간
파일 소유자, 그룹, ACL	파일을 소유한 사용자, 그룹, 접근 제어 목록
파일 크기 (file size)	파일의 바이트 단위 크기
파일 데이터 블록	실제 데이터가 저장된 블록 또는 블록을 가리키는 포인터

핵심 요약: 파일 시스템은 파일의 실제 데이터뿐만 아니라, 권한·날짜·소유자·크기 등의 메타데이터도 함께 관리합니다.

Unix 커널의 열린 파일 표현 방식

파일 디스크립터 테이블 (File Descriptor Table)

한 프로세스가 열어둔 모든 파일의 디스크립터는 파일 디스크립터 테이블에 모여 있습니다.
프로세스당 하나의 파일 디스크립터 테이블이 존재합니다 (여러 개가 아님).

(열린) 파일 테이블 엔트리 (Open File Table Entry)

파일 디스크립터와 파일 정보(v-node) 사이의 중간 객체입니다.
파일 테이블 엔트리에는 다음이 포함됩니다:
- 파일 오프셋 (file offset): 현재 읽기/쓰기 위치
- 참조 카운트 (reference count): 이 엔트리를 참조하는 디스크립터 수
- 파일 정보에 대한 포인터: v-node를 가리킴
이 엔트리들은 (열린) 파일 테이블에서 관리됩니다.
커널에는 전역적으로 하나의 파일 테이블만 존재합니다.

전체 구조 (3단계)

코드 예시

int fd1, fd2; /* 파일 디스크립터 */
fd1 = open("/home/park/a.txt", O_RDONLY);  // a.txt를 읽기 전용으로 열기
fd2 = open("/home/park/b.txt", O_RDONLY);  // b.txt를 읽기 전용으로 열기

fd1은 디스크립터 테이블의 fd 3에 할당됨 (0, 1, 2는 stdin/stdout/stderr)
fd2는 fd 4에 할당됨
각각 열린 파일 테이블의 서로 다른 엔트리를 가리키고, 최종적으로 v-node 테이블의 파일 정보를 참조합니다.

핵심 요약: 디스크립터 테이블 → 열린 파일 테이블 → v-node 테이블, 이 3단계 구조로 Unix 커널은 열린 파일들을 관리합니다.

파일 메타데이터

메타데이터(Metadata)는 파일 데이터에 대한 데이터(정보) 입니다. 커널이 유지 관리하며, 사용자는 stat과 fstat 함수로 접근할 수 있습니다.

stat 구조체

struct stat {
    dev_t   st_dev;      /* 장치(device) */
    ino_t   st_ino;      /* inode 번호 */
    mode_t  st_mode;     /* 보호 모드 및 파일 타입 */
    nlink_t st_nlink;    /* 하드 링크 수 */
    uid_t   st_uid;      /* 소유자 사용자 ID */
    gid_t   st_gid;      /* 소유자 그룹 ID */
    dev_t   st_rdev;     /* 장치 타입 (inode가 장치인 경우) */
    off_t   st_size;     /* 총 크기 (바이트) */
    unsigned long st_blksize; /* 파일시스템 I/O 블록 크기 */
    unsigned long st_blocks;  /* 할당된 블록 수 */
    time_t  st_atime;    /* 마지막 접근 시간 */
    time_t  st_mtime;    /* 마지막 수정 시간 */
    time_t  st_ctime;    /* 마지막 변경 시간 */
};

메타데이터 조회 함수

int stat(const char *path, struct stat *buf);   // 경로로 파일 정보 조회
int fstat(int filedes, struct stat *buf);        // 파일 디스크립터로 파일 정보 조회

사용 예시

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>

void Stat(char* path, struct stat* pStat) 
{
    if (stat(path, pStat) < 0) {
        perror("stat");  // 에러 메시지 출력
        exit(-1);        // 프로그램 종료
    }
}

핵심 요약: 메타데이터는 파일의 크기, 소유자, 권한, 시간 정보 등을 담고 있으며, stat/fstat 시스템 콜로 조회할 수 있습니다.

파일 오프셋

파일 오프셋(File Offset) 은 파일 내에서 현재 읽기/쓰기 위치를 나타내는 값입니다.

동작 과정

파일을 처음 열었을 때:
┌─────────────────────────────────────┐
│         파일 내용                      │
└─────────────────────────────────────┘
↑
파일 오프셋: 0  (파일의 맨 처음)

512바이트를 읽은 후:
┌─────────────────────────────────────┐
│         파일 내용                      │
└─────────────────────────────────────┘
                ↑
        파일 오프셋: 512

코드 예시

char buf[512];
int fd;        /* 파일 디스크립터 */
int nbytes;    /* 읽은 바이트 수 */

/* 파일 fd를 연 후... */
/* 파일 fd에서 최대 512바이트를 읽기 */
if ((nbytes = read(fd, buf, sizeof(buf))) < 0) {
    perror("read");
    exit(1);
}
// 읽기 후 파일 오프셋은 0에서 512로 이동

핵심 요약: 파일 오프셋은 파일 내 현재 위치를 추적하며, read나 write 호출 시 자동으로 이동합니다.

UNIX 파일 구조 예시

UNIX의 파일 시스템은 여러 계층(layer)으로 구성됩니다:

각 계층 설명

논리 파일 시스템 (Logical File System)
- 파일 이름, 디렉터리 구조 등 논리적인 파일 관리
파일 구성 모듈 (File-Organization Module)
- 논리적 블록 번호를 물리적 블록 번호로 변환
기본 파일 시스템 (Basic File System)
- 블록 단위의 읽기/쓰기, 버퍼 캐시 관리
I/O 제어 (I/O Control)
- 장치 드라이버를 통한 실제 하드웨어 제어

가상 파일 시스템 (Virtual File Systems)

동기 (왜 필요한가?)

여러 파일 시스템 타입을 동시에 지원해야 합니다 — UNIX(s5fs, ufs)뿐만 아니라 비-UNIX(DOS, A/UX 등) 파일 시스템까지.
서로 다른 디스크 파티션에 다른 파일 시스템이 있을 수 있습니다. 사용자에게는 파일 시스템 타입에 관계없이 일관된 파일 트리 뷰를 제공해야 합니다.
동일한 시스템 콜 인터페이스(API) 로 다양한 파일 시스템을 사용할 수 있어야 합니다.
벤더(업체)가 자체 파일 시스템을 쉽게 만들어 커널에 모듈 방식으로 추가할 수 있어야 합니다.

해결책

AT&T의 파일 시스템 스위치 (File System Switch)
Sun Microsystem의 vnode/vfs 아키텍처

VFS의 두 가지 중요한 기능

파일 시스템 독립적인 연산과 구현을 분리: 깔끔한 VFS 인터페이스를 정의하여, 상위 계층은 어떤 파일 시스템이든 동일한 방식으로 접근합니다.
파일을 고유하게 표현하는 메커니즘 제공: VFS는 vnode (virtual inode) 라는 파일 표현 구조체에 기반합니다.

동작 흐름

write(fd, pBuffer, length)    ← 사용자의 시스템 콜
        │
        ▼
 파일 시스템 인터페이스
        │
        ▼
    VOP_WRITE(...)             ← VFS 인터페이스 (공통)
        │
   ┌────┼────────┐
   │    │        │
   ▼    ▼        ▼
ntfs:: fat::   nfs::          ← 각 파일 시스템별 구현
write  write   write
   │    │        │
   ▼    ▼        ▼
 디스크  디스크   네트워크

핵심 요약: VFS는 다양한 파일 시스템을 하나의 통일된 인터페이스로 추상화하여, 사용자와 상위 계층이 파일 시스템 종류를 신경 쓰지 않도록 합니다.

Vnode 인터페이스 구현

vnode 구조체

struct vnode {
    u_short v_flag;                     /* V_ROOT 등의 플래그 */
    u_short v_count;                    /* 참조 카운트 */
    struct vfs *vfsmountedhere;         /* 마운트 포인트 */
    struct vnodeops *v_op;              /* vnode 연산 벡터 */
    struct vfs *v_vfsp;                 /* 소속 파일 시스템 */
    struct stdata *v_stream;            /* 관련 스트림 포인터 */
    struct page *v_page;                /* 상주 페이지 리스트 */
    enum vtype v_type;                  /* 파일 타입 */
    dev_t v_rdev;                       /* 장치 파일의 장치 ID */
    caddr_t v_data;                     /* 비공개 데이터 구조체 포인터 */
    ...
};

vnodeops 벡터 (각 파일 시스템이 구현해야 하는 함수들)

struct vnodeops {
    int (*vop_open)();      /* 파일 열기 */
    int (*vop_close)();     /* 파일 닫기 */
    int (*vop_read)();      /* 파일 읽기 */
    int (*vop_write)();     /* 파일 쓰기 */
    int (*vop_ioctl)();     /* I/O 제어 */
    int (*vop_getattr)();   /* 속성 가져오기 */
    int (*vop_setattr)();   /* 속성 설정하기 */
    int (*vop_access)();    /* 접근 권한 확인 */
    int (*vop_lookup)();    /* 이름으로 찾기 */
    int (*vop_create)();    /* 파일 생성 */
    int (*vop_remove)();    /* 파일 삭제 */
    int (*vop_link)();      /* 링크 생성 */
    int (*vop_rename)();    /* 이름 변경 */
    int (*vop_mkdir)();     /* 디렉터리 생성 */
    int (*vop_rmdir)();     /* 디렉터리 삭제 */
    ...
};

파일 시스템별 구현 예시 (NTFS vs FAT)

// NTFS 파일 시스템의 구현
struct vnodeops ntfs_vnodeops = {
    ntfs_open,    // NTFS 방식의 open
    ntfs_close,   // NTFS 방식의 close
    ...
};

// FAT 파일 시스템의 구현
struct vnodeops fat_vnodeops = {
    fat_open,     // FAT 방식의 open
    fat_close,    // FAT 방식의 close
    ...
};

각 inode/rnode 구조체 내부에 v_op 포인터가 있어, 해당 파일이 속한 파일 시스템의 vnodeops를 가리킵니다. 이를 통해 같은 open() 호출이라도 NTFS 파일은 ntfs_open()을, FAT 파일은 fat_open()을 실행합니다.

핵심 요약: 다형성(polymorphism)의 원리를 활용하여, 각 파일 시스템은 동일한 인터페이스(vnodeops)를 자신만의 방식으로 구현합니다.

디렉터리

정의

디렉터리(Directory)는 모든 파일에 대한 정보를 담고 있는 노드들의 모음입니다. 파일들을 체계적으로 관리하기 위한 특수한 파일입니다.

디렉터리 열기 (Opening Directory)

디렉터리 파일을 열면 커널에게 해당 디렉터리에 접근할 준비가 되었음을 알립니다.

DIR* dirp; /* 디렉터리 포인터 */
if ((dirp = opendir("/home/park")) == NULL) {
    perror("opendir");
    exit(1);
}

opendir() 함수는 원하는 디렉터리 파일에 대한 디스크립터(포인터) 를 반환합니다.
디렉터리 엔트리 포인터는 첫 번째 엔트리에 위치합니다.

디렉터리 엔트리 읽기 (Reading Directory Entries)

현재 위치에서 디렉터리 엔트리를 메모리로 읽고, 다음 위치로 이동합니다.

struct dirent {
    char d_name[256];       /* 파일 이름 */
    unsigned char d_type;   /* 파일 타입 */  file , Dir
    ino_t d_ino;            /* inode 번호 */
    off_t d_off;            /* 오프셋 */
};

struct dirent* dentry;
DIR* dirp;

if ((dirp = opendir("/home/park")) == NULL) {
    perror("opendir");
    exit(1);
}

// 디렉터리의 모든 엔트리를 순회
while ((dentry = readdir(dirp)) != NULL) {
    printf("이름:%s, 타입:%d\n", dentry->d_name, dentry->d_type);
}

readdir()은 에러가 발생하거나 끝(end-of-file) 에 도달하면 NULL을 반환합니다.
디렉터리 블록 내의 엔트리들을 하나씩 순차적으로 읽습니다.

디렉터리 닫기 (Closing Directory)

if (closedir(dirp) < 0) {
    perror("closedir");
    exit(1);
}

커널에게 디렉터리 접근이 끝났음을 알리고, 관련 자원을 해제합니다.

디렉터리 생성 (Creating Directory)

if ((mkdir("/home/park/programs", S_IRUSR | S_IWUSR)) < 0) {
    perror("mkdir");
    exit(1);
}

mkdir()은 지정된 경로에 새 디렉터리를 생성합니다.
빈 디렉터리 엔트리를 찾아 새 엔트리를 추가합니다.

디렉터리 구현 - 선형 리스트

선형 리스트 방식

가장 단순한 구현 방법입니다.
디렉터리는 디렉터리 블록(directory block) 들로 구성됩니다.
각 디렉터리 블록은 디렉터리 엔트리(directory entry) 의 집합을 가지며, 각 엔트리에는 파일(또는 디렉터리) 이름과 파일 데이터(또는 FCB)에 대한 포인터가 있습니다.

새 파일 생성 절차

디렉터리를 검색하여 같은 이름의 파일이 없는지 확인합니다.
디렉터리의 끝에 새 디렉터리 엔트리를 추가합니다.

파일 삭제 절차

디렉터리에서 해당 파일을 검색합니다.
할당된 공간을 해제합니다.
디렉터리 엔트리를 미사용(unused)으로 표시합니다.

Dir impl - Linear List

장점

구현이 간단합니다.

단점

파일을 찾으려면 선형 검색(linear search) 이 필요하여, open(), create(), delete(), mkdir(), rmdir() 등의 성능이 저하됩니다.

해결책: 디렉터리 캐시

대부분의 운영체제는 디렉터리 캐시(directory cache) 라는 소프트웨어 캐시를 구현합니다.
가장 최근에 사용된 디렉터리 엔트리를 캐시에 저장합니다.
캐시 히트(cache hit) 시 디스크에서 디렉터리 정보를 다시 읽을 필요가 없어 성능이 향상됩니다.

논리 블록과 물리 블록

논리 블록 (Logical Block): 파일 시스템이 사용하는 추상적인 블록 번호입니다. 파일 내에서의 상대적 위치를 나타냅니다.
물리 블록 (Physical Block): 디스크 상의 실제 블록 위치입니다.

파일 시스템의 파일 구성 모듈(File-Organization Module)이 논리 블록 번호를 물리 블록 번호로 변환하는 역할을 합니다.

할당 방법 (Allocation Methods)

정의

할당 방법은 파일을 위해 디스크 공간을 어떻게 배분할 것인가를 결정하는 방식입니다. 효율적인 디스크 공간 활용과 빠른 접근은 이 할당 방법에 달려 있습니다.

세 가지 전략

전략	설명
연속 할당 (Contiguous)	파일이 연속된 블록들을 차지
연결 할당 (Linked)	각 블록이 다음 블록을 가리키는 연결 리스트
인덱스 할당 (Indexed)	별도의 인덱스 블록이 모든 블록 주소를 보관

연속 할당 (Contiguous Allocation)

기본 정책

각 파일이 디스크에서 연속된 블록 집합을 차지합니다.
파일은 첫 번째 블록의 디스크 주소와 파일 길이로 정의됩니다.
파일이 n개 블록이고 위치 b에서 시작하면, b, b+1, b+2, ..., b+n-1 블록을 차지합니다.

문제점 1: 외부 단편화 (External Fragmentation)

파일이 할당되고 삭제되면서, 빈 공간이 작은 조각들로 분열(fragmented) 됩니다.
큰 파일은 이렇게 조각난 빈 공간에 연속적으로 할당될 수 없습니다.

문제점 2: 파일 크기의 예측 불가능성

파일에 얼마나 많은 공간이 필요한지 미리 결정하기 어렵습니다.
응용 프로그램은 필요에 따라 동적으로 블록을 추가(append) 합니다.
파일 양쪽의 공간이 이미 사용 중이면 확장이 불가능합니다.

연결 할당 (Linked Allocation)

기본 개념

각 파일은 디스크 블록의 연결 리스트(linked list) 입니다.
블록들은 디스크의 어디에나 흩어져 있을 수 있습니다.
각 디렉터리 엔트리에는 파일의 첫 번째 블록과 마지막 블록에 대한 포인터가 있습니다.

파일 생성 절차

디렉터리에 새 엔트리를 생성합니다. 첫 번째 블록 포인터를 nil로 초기화합니다.
파일 크기를 0으로 설정합니다.

파일 쓰기 절차

빈 공간 관리 시스템에서 빈 블록을 찾습니다.
새 블록에 데이터를 씁니다.
파일의 마지막 블록을 찾아 그 포인터를 새 블록으로 설정합니다.
새 블록의 포인터를 nil로 설정합니다.

문제점

큰 검색 오버헤드 (랜덤 파일 접근): i번째 블록을 찾으려면 파일의 처음부터 포인터를 따라가야 합니다. 랜덤 접근이나 직접 블록 접근에 부적합합니다.
포인터를 위한 공간 낭비: 포인터가 512바이트 블록에서 4바이트를 차지하면, 디스크의 약 0.78% 가 포인터로 사용됩니다.

해결책: 클러스터 (Cluster)

블록을 여러 개 묶어 클러스터를 구성하고, 블록 대신 클러스터 단위로 할당합니다.
하지만 내부 단편화(internal fragmentation) 가 증가하는 비용이 있습니다.

FAT (File Allocation Table)

개요

FAT는 연결 할당의 중요한 변형입니다.
MS-DOS와 mp3 플레이어, 메모리 스틱 같은 임베디드 시스템에서 사용됩니다.
각 볼륨의 시작 부분에 테이블이 위치합니다.

Example

a.txt가 block (2, 5, 12) , b.txt가 block (7, 9, 14)에 있다는 것을

FAT 엔트리

테이블은 엔트리의 집합입니다.
블록 번호로 인덱싱됩니다.
파일에서 다음 블록의 번호를 포함합니다.
사용되지 않는 블록은 0 값으로 표시됩니다.
FAT16: 엔트리 크기 16비트, FAT32: 엔트리 크기 32비트

동작 예시

디렉터리 엔트리:
┌──────┬─────┬────────────┐
│ test │ ... │ 시작블록:217 │
└──────┴─────┴──────┬─────┘
                     │
                     ▼
         FAT 테이블:
         ┌─────┬───────┐
         │  0  │       │
         │ ... │       │
         │ 217 │  618  │──→ 블록 217의 다음은 블록 618
         │ ... │       │
         │ 339 │       │──→ 블록 339이 마지막 (체인의 끝)
         │ ... │       │
         │ 618 │  339  │──→ 블록 618의 다음은 블록 339
         │ ... │       │
         │ n   │  -1   │──→ -1은 파일의 끝(EOF)을 의미
         └─────┴───────┘

파일 "test"의 블록 체인: 217 → 618 → 339 → 끝

새 블록 할당

FAT에서 0 값을 가진 첫 번째 엔트리를 찾습니다.
이전 파일 끝(EOF) 값을 새 블록 주소로 교체합니다.

문제점

디스크 헤드의 상당한 탐색(seek) 횟수가 필요합니다.
해결책: FAT 테이블을 메모리에 캐싱합니다.

인덱스 할당 (Indexed Allocation)

동기

연결 할당에서 직접 파일 접근(direct file access) 이나 랜덤 파일 접근(random file access) 의 문제를 해결하기 위함입니다.

기본 개념

모든 포인터를 하나의 위치, 즉 인덱스 블록(index block) 에 모읍니다.
인덱스 블록은 디스크 블록 주소들의 배열입니다.
인덱스 블록의 i번째 엔트리는 파일의 i번째 블록을 가리킵니다.

예시

디렉터리:
┌──────┬─────────────┐
│ jeep │인덱스블록: 19 │
└──────┴──────┬──────┘
              │
              ▼
    인덱스 블록 (블록 19):
    ┌──────┐
    │   9  │ → 1번째 데이터 블록
    │  16  │ → 2번째 데이터 블록
    │   1  │ → 3번째 데이터 블록
    │  10  │ → 4번째 데이터 블록
    │  25  │ → 5번째 데이터 블록
    │  -1  │ → 미사용
    │  -1  │ → 미사용
    │  -1  │ → 미사용
    └──────┘

포인터 오버헤드 문제

파일이 한두 블록밖에 안 되더라도 인덱스 블록 전체를 할당해야 합니다 → 공간 낭비
반대로 파일이 매우 크면 하나의 인덱스 블록으로 부족할 수 있습니다.

인덱스 블록 관리 기법

1. 연결 기법 (Linked Scheme)

인덱스 블록이 하나의 디스크 블록 크기입니다.
큰 파일을 위해 여러 인덱스 블록을 연결합니다.

인덱스 블록 1 ──→ 인덱스 블록 2 ──→ nil
  │                │
  ▼                ▼
4개 데이터 블록    5개 데이터 블록

다단계 인덱스 (Multilevel Index)

1단계 인덱스 블록이 2단계 인덱스 블록을 가리킵니다.
2단계 인덱스 블록이 실제 파일 블록을 가리킵니다.

1단계 인덱스 블록 ──→ 2단계 인덱스 블록 ──→ 파일 블록

3. 결합 기법 (Combined Scheme) ⭐

인덱스 블록이 다음으로 구성됩니다:

구성 요소	설명
직접 블록 포인터 12개	작은 파일을 위해 직접 데이터 블록을 가리킴
단일 간접 블록 (single indirect)	한 단계의 인덱스 블록을 거쳐 데이터 접근
이중 간접 블록 (double indirect)	두 단계의 인덱스 블록을 거쳐 데이터 접근
삼중 간접 블록 (triple indirect)	세 단계의 인덱스 블록을 거쳐 데이터 접근

이 결합 기법은 UNIX/Linux의 inode에서 실제로 사용되는 방식입니다!

UNIX/Linux Inode 구조

Inode의 내부 구조

┌────────────────────┐
│       mode          │  ← 파일 타입 및 접근 모드
├────────────────────┤
│    owners (2)       │  ← 소유자 및 그룹 접근 식별자
├────────────────────┤
│   timestamps (3~4)  │  ← 수정 시간 등
├────────────────────┤
│       size          │  ← 파일 크기 (바이트)
├────────────────────┤
│                    │──→ 데이터 블록
│                    │──→ 데이터 블록
│   direct blocks    │──→ 데이터 블록       (12개의 직접 포인터)
│     (12개)         │──→ ...
│                    │──→ 데이터 블록
├────────────────────┤
│  single indirect   │──→ [인덱스 블록] ──→ 데이터 블록들
├────────────────────┤
│  double indirect   │──→ [인덱스] ──→ [인덱스] ──→ 데이터 블록들
├────────────────────┤
│  triple indirect   │──→ [인덱스] ──→ [인덱스] ──→ [인덱스] ──→ 데이터 블록들
├────────────────────┤
│   block count       │  ← 할당된 블록 수
├────────────────────┤
│  reference count    │  ← 이 파일을 참조하는 디렉터리 엔트리 수
├────────────────────┤
│    flags (2)        │
├────────────────────┤
│ generation number   │
├────────────────────┤
│    blocksize        │
├────────────────────┤
│ extended attr. size │  ← 확장 속성 정보 크기
├────────────────────┤
│ extended attribute  │──→ 데이터
│     blocks          │──→ 데이터
└────────────────────┘

Inode에 포함된 정보 요약

파일 타입 및 접근 모드 (mode)
소유자/그룹 식별자 (owners)
여러 수정 시간 (timestamps)
파일 크기 (바이트)
직접 블록 포인터 및 간접 블록 포인터
이 파일을 참조하는 디렉터리 엔트리 수 (reference count)
확장 속성 정보의 크기

핵심 요약: Unix/Linux inode는 결합 기법(combined scheme)을 사용하여 작은 파일은 빠르게(직접 블록), 큰 파일도 효율적으로(간접 블록) 접근할 수 있게 합니다.

소형 파일 시스템의 내부 구조

전체 구성

디스크:
┌──────────────┬──────────────────────────────────────┐
│  inode 리스트  │            데이터 영역                  │
│ (1)(2)(3)(4)(5)│                                    │
└──────┬───────┴──────────────────────────────────────┘
       │
       │   inode 번호와 역할:
       │   (1) root inode  → 디렉터리 블록 (섹터 10에 위치)
       │   (2) bin inode   → bin 디렉터리 블록
       │   (3) lib inode   → lib 디렉터리 블록
       │   (4) vi inode    → vi 데이터 블록
       │   (5) xv inode    → xv 데이터 블록

핵심 개념

inode: 파일의 정보(마지막 수정 시간, 길이, 파일/디렉터리 블록 포인터 등)를 담고 있습니다.
디렉터리 블록: 디렉터리 엔트리들로 구성되며, 파일 이름을 다음 파일/디렉터리의 inode 번호로 변환하는 역할을 합니다.

경로 해석 예시

/root/bin/vi를 찾는 과정:
1. root inode(1번) → 디렉터리 블록에서 "bin" 찾기 → inode 2번
2. bin inode(2번) → 디렉터리 블록에서 "vi" 찾기 → inode 4번
3. vi inode(4번) → 실제 vi 데이터 블록 접근

빈 공간 관리 (Free Space Management)

동기

파일 시스템은 삭제된 파일의 공간을 새 파일에 재사용해야 합니다.

빈 공간 리스트 (Free-Space List)

시스템은 빈 공간 리스트를 유지하여 빈 디스크 공간을 추적합니다.
파일이나 디렉터리에 할당되지 않은 모든 빈 블록을 기록합니다.

파일 생성 시

빈 공간 리스트에서 필요한 양의 공간을 검색합니다.
해당 공간을 새 파일에 할당합니다.
그 공간을 빈 공간 리스트에서 제거합니다.

파일 삭제 시

해당 파일의 디스크 공간을 빈 공간 리스트에 추가합니다.

비트맵 방식 (Bit Map)

빈 공간을 비트맵(bit map) 또는 비트 벡터(bit vector) 로 표현합니다.

규칙:
  bit[i] = 0  →  블록 i는 비어 있음 (free)
  bit[i] = 1  →  블록 i는 할당됨 (allocated)

예시

블록 2, 3, 4, 5, 8, 9, 10, 12, 13, 17, 25, 26, 27이 할당된 경우:

블록 번호: 0 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0
인덱스:    0 1 2 3 4 5 6 7 8 9 ...

장점

단순함: 구현이 쉽습니다.
성능: 많은 컴퓨터가 비트 조작 명령어를 제공하여 효과적으로 활용할 수 있습니다.

구현

비트맵은 디스크 접근을 줄이기 위해 메모리에 캐싱됩니다.

부팅 시:
Disk의 bitmap → DRAM으로 복사 (캐시)

파일 생성/삭제 시:
DRAM의 bitmap 수정 (빠름!)
↓ 나중에
Disk의 bitmap에도 반영 (영구 저장)

버퍼 캐시 (Buffer Cache)

동기

파일에 접근할 때마다 데이터를 디스크에서 가져와야 합니다.
하지만 디스크 접근은 큰 I/O 오버헤드를 발생시킵니다.
파일 접근 패턴을 보면, 한 번 접근한 데이터는 곧 다시 사용될 가능성이 높습니다 — 이를 시간적 지역성(temporal locality) 이라 합니다.

버퍼 캐시의 역할

버퍼 캐시는 곧 다시 사용될 블록들을 메모리에 보관하여 디스크 접근을 줄입니다.

동작 시나리오

블록 3 쓰기: 파일 시스템이 블록 3을 버퍼 캐시에 씁니다 (나중에 디스크에 동기화).
블록 3 읽기: 이미 버퍼 캐시에 있으므로 디스크를 거치지 않고 바로 읽습니다.

계층 구조

응용 프로그램 (Application)
        ↕
파일 시스템 (File System)
        ↕
버퍼 캐시 (Buffer Cache) ← 메모리에 위치
        ↕
디스크 (Disk)

핵심 요약: 버퍼 캐시는 디스크와 파일 시스템 사이에 위치하여, 자주 접근하는 블록을 메모리에 유지함으로써 느린 디스크 접근을 최소화합니다.

전체 요약표

주제	핵심 내용
파일 시스템 목적	사용자가 섹터 번호 없이 파일 이름으로 데이터 접근 가능
파일 ID	커널의 파일 식별자 (inode 번호)
파일 디스크립터	열린 파일에 대한 메모리 내 핸들
VFS	다양한 파일 시스템을 통일된 인터페이스로 추상화
vnode	VFS에서 파일을 표현하는 가상 inode
연속 할당	빠르지만 외부 단편화 문제
연결 할당	유연하지만 랜덤 접근이 느림
FAT	연결 할당의 변형, 테이블을 메모리에 캐싱
인덱스 할당	인덱스 블록으로 직접 접근 가능
inode	직접+간접 블록의 결합 기법 사용
비트맵	빈 공간을 비트로 관리, 단순하고 효율적
버퍼 캐시	시간적 지역성을 활용해 디스크 접근 최소화

Kamator0

이전 포스트

Secondary Storage Structure

다음 포스트