Computer Science/Operating System

10. File System

728x90

Motivation

예전에는 storage가 비쌌음. 어떻게 stroage를 관리할 것인가에 대한 issue. 특히 1990년대 이후에는 멀티미디어 파일을 관리해야하는데, 이에 대한 metric은 끊기지 않고 가져와야하는 것으로 바뀜. 그리고 현대에는 큰 데이터를 다뤄야하는 문제가 발생하게 됨

→ 즉, 시대가 변함에 따라 optimal한 기준이 바뀌게 됨

추가적으로 file system은 잘못만들면 파일이 날라가는 critical한 문제가 있음. 그래서 따른 OS 영역보다 천천히 발전됨. (Robustness에 대해 계속 검증이 이뤄짐)

→ OS 입장에서는 file system이 바뀌어도 코드를 안바뀌고 싶음. 그래서 등장한 개념이 virtual file system

💡

추가적으로 process management와 memory management와 달리 file system은 다양한 형태가 존재한다.

What is File System

Types

Disk-based file system

Linux : Ex2, Ex3, Ex4

Microsoft : MS-DOS

💡

Linux의 경우에는 대부분 다 지원함

Network-based file systems

NFS, NCP

NAS, SAN

하드디스크에 존재하지 않고, 다른 컴퓨터에 있는 storage에 존재하는 file system을 내 컴퓨터에서 사용가능한 것

Special file systems

실제 storage가 아니라 가상으로 존재하는 file system이 존재한다.

대표적으로 /proc file system, /sys file system

💡

No real disk space, only virtual

Purpose and responsibilities

오랫동안 non-volatile하게 정보를 저장하고 싶어서 등장한 개념이 file system이다.

큰 용량의 정보를 저장할 수 있어야 한다.

process가 끝나더라도 정보가 남아있을 수 있어야 한다.

File system Responsibilities

storage에 있는 정보를 추상화해서 file 형태로 제공해야 한다.

많은 file이 storage에 있을 수 있기 때문에 잘 구성해야 한다.

data에 대한 공유에 대한 부분을 허용해야 한다.

security에 대한 부분도 신경써야 한다.

💡

Virtual memory의 경우, 서로 다른 process들 사이의 주소 공간이 분리되면서 공유되고 결정적으로 physical memory의 크기보다 더 큰 logical address를 가지는 여러 process를 실행할 수 있게하는 것이 목표이다.

File

Non-volatile storage에 저장이 되어있는 정보들의 collection

→ power가 나가고 system이 reboot해도 정보가 남아있음

💡

OS는 이러한 정보를 file의 형태로 processor나 user에게 제공한다.

File structures

Flat : 연속된 byte의 sequence

Simple record structure

Complex structure

💡

즉, file의 structure는 다양하게 정의될 수 있다.

File types

file은 type을 가지고 있다.

file system이 이해하는 type이 존재한다.
→ Device냐 directory냐 link냐 등등

OS가 이해하는 type이 존재한다.
executable file인지, source code인지, object code인지 등등

application이 이해하는 type이 존재한다.
ex) jpg, mp4

그래서 운영체제 입장에서는 file type을 어떻게 인식할 것인가?

Microsoft
→ name + extension

Unix
‘filename + extension”와 같은 형태를 허락하지만, OS 입장에서는 extension에만 의존하지는 않는다.
💡
UNIX 운영체제의 경우, 8byte의 연속으로 모든 파일을 인식한다. 즉 단순히 byte들의 sequence로 인식한다. 따라서 user나 appliation이 해당 file의 내용을 해석하고 적합한 file인지를 직접 체크를 해야 한다.
따라서 Unix 시스템에서 파일의 확장자를 통해 파일 유형을 식별하는 기능이 없으며, 대신 파일을 해석하고 적절한 구조로 변환하기 위해 각 응용 프로그램은 자체 코드를 포함해야 한다.
즉 Unix 시스템에서는 파일 확장자가 파일의 유형을 나타내는 공식적인 수단이 아니기 때문에, 응용 프로그램은 파일을 해석하고 적절한 데이터 구조로 변환하는 코드를 포함해야 한다.
💡
Maximum flexibility를 제공하지만, support는 약한 편이다.

File Attributes

여러 management와 관련된 file에 대한 정보가 필요하다. file system이 가지고 있는 file들에 대해서 모든 attribute를 가지고 있어야 한다.

File system에 특정 file이 만들어질 때 file에 대한 모든 attribute가 지정이 된다.

💡

결과적으로 file attribute는 inode가 가지고 있게 된다.

File Access

file system은 여러가지의 access method를 제공한다.

Sequential

한번에 한 byte씩 순차적으로 access

Direct access

주어진 block number와 byte number를 가지고 곧바로 access

Record access

특정 형태의 record로 만들고 record단위로 access

record가 뭔지
파일 시스템에서 레코드(record)는 데이터를 저장하는 최소 단위입니다. 레코드는 파일 내에서 구조화된 데이터의 논리적인 단위로 사용됩니다. 일반적으로 레코드는 연관된 필드(fields)의 집합으로 구성되며, 각 필드는 해당 레코드의 특정 속성을 나타냅니다.

Index access

index를 기반으로 access

File Allocation Methods

storage에 file을 저장하는 방식. 효율적인 storage 관리가 필요하게 된다.

Contiguous Allocation

출발과 몇개를 할당하고 있는지에 대한 정보를 담고 있음

장점
1. 구현이 쉬움
1. Random access가 쉬움

단점
1. Growing하기가 어려움
1. Wasteful of space (dynamic allocation에서 나타난 문제와 비슷하다.)

그래서 CD-ROM에 자주 사용함 : 파일의 크기를 미리 알 수 있고, 크기가 증가하지 않으므로

Linked Allocation

특정 file이 쓰고 있는 disk block이 연속적일 필요가 아니라 pointer로 유지를 하는 것

→ 정보를 여기저기 흩어져 있음

이렇게 되면 빈 block에 대해서 고민하지 않아도 됨

💡

Random access가 어려워짐. 또한 1개의 block이 망가지면 문제가 발생할 수 있음

Indexed Allocation

index를 담고 있는 block를 둔다.

→ 즉 19가 jeep이라는 파일에 필요한 index를 다 담고 있는 것

실제로 UNIX에서 사용하고 있는 방법

💡

i-node 자료구조의 기본이 됨

file access와 file allocation의 차이가 뭐야?
파일 할당은 파일 시스템이 디스크 공간을 파일에 할당하는 방식을 말합니다. 주요 파일 할당 방식에는 연속 할당, 연결 할당(예: 링크드 리스트), 그리고 인덱스 할당 등이 있습니다.
한편, 파일 접근은 파일 시스템이 사용자나 애플리케이션에게 파일에 접근할 수 있는 방식을 제공하는 것을 말합니다. 주요 파일 접근 방식에는 순차 접근, 직접 접근, 인덱스 접근 등이 있습니다.
파일 할당 방식은 파일 접근 방식을 결정하는 한 요소이긴 하지만, 반드시 같은 방식을 사용해야 하는 것은 아닙니다. 예를 들어, 파일을 연결 할당 방식으로 할당하더라도 사용자나 애플리케이션이 해당 파일에 직접 접근할 수 있게 만들 수 있습니다. 이는 파일 시스템이 디스크 공간을 어떻게 관리하고, 사용자나 애플리케이션이 파일에 어떻게 접근하는지에 따라 달라집니다.

File operation

File을 user가 access하기 위해 필요한 system call이다.

이 중에 가장 중요한 system call이 open이다.

→ Initial path는 cache를 사용 : 사실 생각해보면 여러번 사용할 것이므로 cache를 사용하는 것이 유리하다.

구체적인 예시를 통해 살펴보도록 하자.

File를 찾는데 overhead를 줄이기 위해서 OS는 open-file table 이라는 자료구조에 열려있는 모든 file에 대한 정보를 저장해놓는다. (file attribute도 open file table에 저장되어있다.)

💡

즉 open file table이라는 kernel의 자료구조를 정의 (즉 process가 open하고 있는 file에 대한 meta정보를 가지고 있음)

그래서 만약 file operation이 요청되면, open-file table을 활용해서 찾게 된다.

예를 들어 open() system call을 호출하면 해당 file에 대한 정보가 open-file table에 있는지 확인하고, 없다면 directory search를 해서 open-file table에 해당 정보를 저장한다. (해당 directory의 entry를 open file table의 entry로 복사한다.) 이후 open() system call은 file descripter 라는 pointer를 제공한다. 해당 pointer는 open-file table의 entry를 지시하는 포인터이다. (해당 pointer는 모든 I/O operation에 사용되게 된다.)

Open file table에는 어떤 정보가 들어있는가
1. 파일 및 디렉토리의 이름: 디렉토리 내에 포함된 파일과 하위 디렉토리의 이름 목록을 추적합니다.
1. 접근 권한: 디렉토리의 접근 권한 정보를 저장합니다. 이 정보는 해당 디렉토리에 대한 읽기, 쓰기, 실행 등의 권한을 지정합니다.
1. 디렉토리의 위치: 디스크 상에서 디렉토리의 위치를 추적합니다.
1. 디렉토리 열림 상태: 디렉토리가 현재 열려있는지, 접근 가능한지 등의 정보를 포함할 수 있습니다.
1. 현재 디렉토리 위치: 작업 디렉토리와 같이 현재 디렉토리 위치를 추적하는 정보가 있을 수 있습니다.

File Sharing

여러 개의 process 혹은 여러 user가 Storage에 있는 file을 공유할 수 있다. (그래야 소통도 할 수 있고, 동기화도 할 수 있기 때문이다.)

하지만, file을 sharing하는데 고려해야하는 몇 가지 문제점이 존재한다.

1개의 file을 여러 process가 동시에 access를 하는 상황에서, 어느 것은 read를 수행하고 어느 것은 write를 수행하면 어떻게 되는가?
💡
일종의 concurrent access issue가 발생하게 된다.

그래서 UNIX 운영체제의 경우는 locking 을 통해 file에 대한 concurrency control을 진행하게 된다. (flock(), fcntl() system call)

Protection issue

Protection

Protection을 수행하기 위해서는 file system이 일종의 protection system을 구현해야 한다.

Generalize files to objects (the “what”)

Generalize users to subjects (the “who”)

Generalize read/write to actions (the “how”)

💡

즉, 어떤 file을 누가 어떻게 할 것인가에 대한 명시가 필요하게 된다. 이러한 특성을 해당 file의 attribute에 명시하게 된다.

UNIX의 경우 Access list and groups 라는 개념을 사용하게 된다.

→ 사용할 수 있는 access의 group을 3가지로 나눈다. (owner, groups, public)

→ 그리고 해당 group의 access를 지정한다.

💡

해당 내용처럼 구현하기 위해서는 관리자가 group을 만들고 특정 유저를 group에 넣어야 한다.

Directories

Advantage

user관점 : Directory를 통해 file를 구조화시킬 수 있게 됨

file system 관점 : 일종의 naming interface를 제공. 이를 통해 logical file들의 논리적 구성과 physical file들의 실제 저장 위치를 분리할 수 있게 된다. 즉 파일들이 디렉토리 내에서의 구성과 디스크 상의 물리적인 저장 위치가 일치하지 않을 수 있는 것이다.

💡

Directory 안에 있는 file들과 sub-directory에 대한 정보는 directory 자체가 가지고 있다.

좋은 directory의 기준
1. Efficiency : 빠르게 해당 파일을 찾을 수 있어야 한다.
1. Naming : user 입장에서 다양하게 이름을 표현할 수 있어야 한다.
1. Grouping : 유사한 특성을 가지는 file을 grouping할 수 있어야 한다.

Directory Internals

Directory안에 list of (file name, file attributes) 가 저장되어있다.

💡

사실 directory 또한 하나의 file인데, 단지 특별한 meta data 를 가지고 있다고 생각해주면 된다.

Directories in a file system store metadata associated with files and subdirectories. The metadata may include information such as file names, sizes, permissions, timestamps, and pointers to the actual file data. Directories provide a hierarchical structure that organizes and links these metadata entries to the respective files and subdirectories.

💡

Directory와 page table은 meta data를 저장하고 관리하고 있다는 측면에서는 비슷한 개념이라고 생각할 수 있다.

Attributes는 다음과 같은 것들이 해당된다.

size, protection, creation time, access time

Location on disk, etc

💡

즉 요약하면, file과 directory 모두 storage에 저장되고 전원이 꺼져도 그 정보가 유지된다.

추가적으로 directory와 file을 구분하지 않으므로 directory에 대한 open file table entry가 존재한다.

Location of metadata

In the directory entry

Separate

Hybrid

Directory structure

Tree-structured directories

💡

Binary search 형태로 찾는 것도 빠르게 할 수 있고, grouping도 용이하게 된다.

Acyclic-graph directories

Tree structured directories의 변형이다. 다른 directory가 file을 공유할 수 있게 된 것이다. 이러한 형태의 directory구조를 UNIX가 사용하고 있다.

💡

closed path이지만 cycle이 만들어지지는 않는다.

추가적으로 UNIX의 경우에는 link 라는 자료구조를 사용해서 서로 다른 directory가 동일한 file을 지시할 수 있게 되는데, link를 삭제하는 행동은 원본 file에는 영향을 주지 않는다. 또한 만약 file을 지웠다면, 해당하는 link를 지워주는 것은 유저(programmer)가 수행해주어야 한다.

Pathname Translation

다음과 같이 open(”a/b/c”, …) 명령어를 실행시켰다고 가정하자. 해당 file을 찾고 open file table을 업데이트 한 후 file descriptor를 return 해야한다.

💡

overhead가 상당히 큰 편이다. 이러한 측면때문에 open()이 read()와 write()와 구분되는 것이다.

이러한 측면 때문에 OS에서는 cache prefix lookups 를 통해 속도를 올리고자 한다.

ex) /a/b, /a/bb, /a/bbb 의 경우에는 /a 를 공유하고 있다. 따라서 a에 대한 meta정보를 cache에 넣어서 빠른 접근이 가능하게끔하는 것이다.

💡

일종의 TLB처럼 자주 사용하는 정보를 cache에 넣어서 속도의 향상을 노리겠다는 것.

💡

Linux에서는 dentry cache가 해당 기능을 담당하고 있다.

추가적으로 open()의 실제 기능은 해당 파일의 metadata를 가져와서 open file table을 업데이트하는 기능을 수행하는 것이다.

Mounting

2개의 Directory가 있는 상황에서 특정 directory의 구조를 또 다른 directory 구조에 덮어씌울 수 있다. (mount, umount)

💡

Dynamic하게 sub-directory구조를 다른 directory구조에 mapping할 수 있는 기능을 제공하는 것

Directory Operations (UNIX)

Directory에 대한 operation을 실제 user가 할 수 있다.

DIR *opendir (const char *name)

struct dirent *readdir (DIR *dir)

void seekdir (DIR *dir, off_t offset)

int closedir (DIR *dir)

💡

Unix의 경우 Directory의 구현은 inode라는 meta 정보를 써서 directory를 file과 동일하게 구현한다.

Implementing File System

Implementor’s view

어떻게 file과 directory를 저장해야 효율적으로 저장할 수 있을 것인가?

disk space는 어떻게 관리해야할 것인가

effective하고 reliable하게 관리할 수 있을 것인가?

→ 가장 중요한 것이 효율적으로 관리하고, disk space를 잘 관리하면서 빨라야한다는 것.

💡

File system을 이해하기 위해서는 on-disk structure와 in-memory structure를 정확하게 이해해야 한다.

On-disk structures

디스크에 존재하는 file system에 관련된 구조이다.

Boot control block

운영체제를 부팅할 때 필요한 정보를 담고 있음

UNIX에서는 이를 boot block라고 부르고, Windows에서는 partition boot sector 라고 부른다.

Partition control block

하드 디스크를 여러 개의 partition으로 쪼개고 각각의 file system마다 다른 file system을 설치할 수 있음. 따라서 각 partition마다 고유한 file system에 대한 정보가 있어야 한다. 그러한 meta정보를 partition control block에다가 담는 것이다. UFS의 경우에는 superblock이라 불리고, windows의 경우에는 Master File Table 라고 불린다.

💡

해당 정보로는 해당 partition안에 있는 block의 개수, block의 size, 비어있는 block의 개수, 비어있는 File control block (FCB)의 개수 등등

Directory structure

Directory를 저장하는 구조

Individual files

각 File을 저장하는 구조 (File data + FCB)

일반적으로 1개의 file에 대해서는 1개의 FCB를 가진다.

이때 FCB (File control block)은 특정 파일과 관련된 meta data와 정보를 포함하는 구조이다. 이는 파일의 이름, 크기, 권한, 속성, 디스크 상의 위치 등과 같은 파일에 대한 정보를 저장하는 역할을 수행하게 된다. 즉 FCB는 파일의 속성과 데이터에 대한 접근 및 관리를 운영 체제에 제공하는 역할을 수행하게 된다.

Unix 운영체제에서는 이러한 File control block를 inode 라고 부른다. (매우 중요하다.)

💡

즉 file에 대한 attribute를 담고 있는 block이다

inode와 open file table 사이의 관계는 어떻게 되는가?
파일을 open할 때, 운영 체제는 해당 파일의 inode에서 파일의 메타 데이터를 읽어와서 Open File Table (OFT)에 저장합니다. inode는 파일 시스템에서 파일에 대한 메타 데이터를 저장하는 구조로, 파일의 크기, 권한, 소유자, 생성 시간, 수정 시간 등의 정보를 포함합니다.
OFT는 열린 파일에 대한 정보를 추적하고 유지하는 인메모리 구조입니다. OFT에는 파일의 상태, file discriptor, 현재 파일 위치 등의 정보뿐만 아니라, 일반적으로 해당 파일의 inode에 대한 포인터 또는 참조도 저장합니다.
💡
추가적으로 해당 file의 접근 및 파일 오프셋(파일을 어디까지 읽었는지), 상태(파일이 열려있는지 닫혀있는지, 읽기 또는 쓰기 작업이 가능한지, 락이 설정되어 있는지) 등에 대한 정보들은 open file table에 저장되어있다. 이러한 정보들은 inode에는 존재하지 않는다.
파일을 open할 때, 운영 체제는 해당 파일의 inode를 디스크에서 읽어와 OFT에 저장하고, OFT의 파일 항목에는 해당 inode에 대한 포인터 또는 참조를 할당합니다. 이를 통해 OFT는 열린 파일에 대한 작업을 수행하면서 필요한 경우 해당 inode의 메타 데이터에 접근할 수 있습니다.
💡
정확하게는 대응되는 inode를 inode cache에 두는 것이다. 즉 대응되는 inode가 inode cache에 있는지를 먼저 확인하고 존재한다면 해당 inode에 대한 포인터를 open file table에 저장하고, 없으면 해당 inode를 inode cache에 저장한 후 해당 포인터를 open file table에 저장하게 된다.
따라서, 파일을 open할 때 운영 체제는 해당 파일의 inode에서 메타 데이터를 가져와 OFT에 저장합니다. OFT는 열린 파일에 대한 메타 데이터를 인메모리에서 유지하고, 파일의 상태와 위치를 추적하며 필요한 경우 해당 inode의 메타 데이터에 접근할 수 있습니다.

master boot record : partition에 대한 여러 meta data 정보를 가지고 있음. 이때 각 partition에 특정 file-system을 입히는 것이다.

boot block : 특정 OS를 booting하는데 필요한 자료들

이후부터는 file-system마다 조금씩 다르다. 이 중 super block은 특정 file system에 대한 meta정보를 가지고 있음 (block의 개수나 크기 등등)

💡

만약 file의 개수가 변경되면 super block의 내용이 바뀌어야 함

i-nodes : file 당 1개씩 존재한다. 예를 들어 500개의 file이 있다고 하면, 500 i-node가 존재하는 것이다. (128byte)

예를 들어, 생성 시간, 주인, permission, 파일의 크기, 등등에 대한 정보

💡

i-node : 해당 파일과 관련된 meta정보와 해당 파일들이 위치한 포인터들을 저장해두고 있다.

추가적으로 swap space의 경우 일반적으로 특정 partition을 아얘 구분해서 swap space로 사용하게 된다. 따라서 master boot record는 어느 partition이 swap space인지 알고 있다.

In-memory structures

On disk structure을 kernel이 활용하기 위해서는 main memory에 자료구조가 형성이 되어야 한다. kernel이 개입하려면 RAM 상에 정보가 존재해야하기 때문이다. 따라서 file-system에 관련된 on-disk 자료구조도 일부는 main memory에 부분적으로 copy가 되어서 존재해야 한다.

💡

추가적으로 caching을 통한 성능 향상도 이를 통해 가능해진다.

In-memory partition table

특정 partition에 대한 meta 정보가 있어야 한다. 그래야 특정 partition에 어떠한 file system이 설치가 되었는지를 알 수 있다.

In-memory directory structure

Directory에 대한 정보도 있어야 한다.

System-wide open-file table

여러 개의 process가 사용하고 있는 file들을 system 차원에서 관리

Per-process open-file table

프로세스 당 open file table을 관리

💡

만약 변경된 사항이 있으면 원본인 on-disk memory structure에 write back하는 절차를 거치게 된다.

file table : 커널이 관리하는 어떤 process가 어떤 file을 접근하고 있는지에 대한 자료구조 (각자 process 별로 open file table이 존재한다.)

💡

정확하게는 system-wide open-file table이 존재하고, per-process open-file table이 존재한다. system-wide open table에 각 open 된 file들에 대한 FCB의 복사본이 저장되고, per-process open-file table에는 system-wide open table을 pointing하고 있다. (책 568p 참고할 것)

Free-Space Management

빈 block을 어떻게 모니터링하고 tracking할 것인가에 대한 이슈

Bitmap

i-node에서는 bit map을 둔다.

💡

하지만, bitmap을 저장하기 위한 extra space가 필요한 문제가 있음

Linked List

free block들을 linked list로 관리를 하는 것

💡

하지만 연속적인 free block를 access하는데 overhead가 커진다는 단점이 존재

Grouping

Disk block 하나를 할당을 해서 n개의 free block에 대한 address를 저장해두는 방식

💡

단, 맨 마지막 free block은 다른 n개의 free block의 주소를 저장하는 역할을 수행하게 된다.

Counting

빈 free block의 시작주소와 해당 free block을 기준으로 연속적으로 몇개의 block이 free인지에 대한 정보를 저장해둠

Disk Caching

Storage에서의 접근 속도는 굉장히 느림. 그래서 main memory의 일부분을 cache로 쓰는 것

→ 빈번이 access하는 storage의 일부분을 RAM에다가 올려놓고, 속도를 올리고 싶은 것 (locality를 반영하고 싶은 것)

이러한 main memory와 storage 사이의 개념을 buffer cache라고 부른다.

💡

즉 disk에 있는 file의 일부분을 RAM으로 옮기고, storage보다 빠른 속도인 DRAM의 속도를 이용하겠다는 것.

→ 실험 결과 매우 작은 4MB cache만으로도 충분히 효과적임을 확인할 수 있다.

하지만

disk block이 main memory에 있게 되므로 일관성 이슈가 있게될 수 있다.

buffer cache로 사용하는 공간과 virtual memory로 사용하는 공간을 나눠야하는 문제가 발생하게 된다.

추가적으로 buffer cache의 관리정책은 일반적으로 LRU방식으로 진행해주면 된다. (용량이 상대적으로 적을 수 밖에 없으므로)

Memory mapped I/O가 무엇이고 그 과정은 어떻게 되는가?
메모리 매핑 입출력(Memory-mapped I/O)은 파일이나 네트워크 소켓 등의 데이터를 프로세스의 가상 메모리 주소 공간에 매핑하는 것을 말합니다. 메모리 매핑된 파일의 경우, 파일의 일부 또는 전부가 가상 메모리 주소에 매핑되어, 마치 메모리에 로드된 배열을 처리하듯이 파일에 접근할 수 있게 됩니다.
메모리 매핑 입출력에서 페이지 캐시가 사용되는 과정은 다음과 같습니다:
1. 프로세스가 mmap() 시스템 호출을 사용하여 파일을 메모리에 매핑하면, 운영체제는 파일의 일부 또는 전부를 가상 메모리 주소와 연결합니다. 이 시점에서 실제 데이터는 아직 메모리에 로드되지 않습니다.
1. 프로세스가 해당 가상 주소를 읽거나 쓰려고 하면, 운영체제는 이를 '페이지 폴트'로 인식하고, 해당 파일의 데이터를 물리 메모리로 로드합니다. 이때 로드된 데이터는 페이지 캐시에 저장됩니다.
1. 프로세스가 다시 같은 주소를 접근하려고 하면, 운영체제는 페이지 캐시에 있는 데이터를 사용하여 빠른 응답을 할 수 있습니다. 이렇게 페이지 캐시는 디스크 I/O를 최소화하고 시스템 성능을 향상시키는 역할을 합니다.
1. 만약 프로세스가 매핑된 파일의 데이터를 변경하면, 운영체제는 이 변경 사항을 페이지 캐시에 반영하고, 나중에 이 변경 사항을 디스크에 다시 기록('write-back')합니다.

Memory mapped I/O에서 virtual memory를 참조하는 정확한 과정이 어떻게 되는가?
가상 메모리 시스템에서 주소 변환 및 데이터 접근의 과정은 일반적으로 다음과 같이 진행됩니다:
1. CPU는 가상 주소를 생성하고 이를 사용하여 메모리에 접근을 시도합니다.
1. MMU(Memory Management Unit)는 가장 먼저 TLB(Translation Lookaside Buffer)를 확인합니다. TLB는 가장 최근에 참조된 가상 주소와 해당 물리 주소 간의 매핑을 캐시하는 작은, 빠른 메모리입니다. 만약 TLB에 가상 주소에 대한 항목이 있으면, 그것을 사용하여 물리 주소를 바로 찾습니다.
1. 만약 TLB에 가상 주소에 대한 항목이 없으면, MMU는 페이지 테이블을 참조하여 물리 주소를 찾습니다. 이 결과는 TLB에 저장되어 다음 번에 빠르게 접근할 수 있도록 합니다. 이 과정은 TLB 미스라고 하며, 이러한 미스를 처리하는 데는 상당한 시간이 소요됩니다.
1. 이제 물리 주소를 얻었으므로, 운영 체제는 이 주소를 사용하여 RAM에서 데이터를 직접 읽습니다.
1. 만약 요청된 페이지가 메모리에 없는 경우 (즉, 페이지 폴트가 발생한 경우), 운영 체제는 디스크에서 해당 페이지를 로드해야 합니다. 이때 페이지 캐시가 사용됩니다. 운영 체제는 페이지 캐시를 먼저 확인하여 요청된 페이지가 이미 캐시되어 있는지 확인합니다.
1. 페이지 캐시에 요청된 페이지가 있는 경우, 운영 체제는 그것을 메모리에 로드하고, 페이지 테이블과 TLB를 업데이트합니다.
1. 페이지 캐시에 요청된 페이지가 없는 경우, 운영 체제는 디스크에서 해당 페이지를 읽고, 그것을 페이지 캐시와 메모리에 로드하며, 페이지 테이블과 TLB를 업데이트합니다.
이런 식으로, TLB, 페이지 테이블, 페이지 캐시는 모두 가상 메모리 시스템에서 데이터 접근을 최적화하는 데 사용됩니다.

그러면 TLB랑 page cache의 차이는 무엇인가?
그런 측면에서 보면, TLB와 페이지 캐시가 모두 locality를 활용한다는 점에서 유사성이 있습니다. 하지만 TLB와 페이지 캐시가 저장하는 정보의 종류는 완전히 다릅니다.
1. TLB (Translation Lookaside Buffer): 이것은 가장 최근에 사용된 일부 가상 주소와 물리 주소 사이의 매핑을 저장합니다. 즉, TLB는 주소 변환 정보만을 저장합니다. 실제 데이터를 저장하지 않습니다.
1. 페이지 캐시: 이것은 디스크에서 읽은 실제 데이터를 저장합니다. 이 데이터는 메모리에 저장된 페이지 형태로 존재하며, 이 페이지들은 파일 시스템으로부터 읽은 데이터를 나타냅니다. 따라서 페이지 캐시는 실제 데이터를 저장합니다.
따라서 TLB와 페이지 캐시는 용도가 다르며, 각각 서로 다른 정보를 저장합니다. TLB는 가상 주소를 물리 주소로 변환하는 데 사용되는 정보를 저장하고, 페이지 캐시는 디스크에서 읽은 실제 데이터를 저장합니다. 두 정보는 모두 메모리 접근과 데이터 입출력의 효율성을 높이는 데 중요하지만, 그 역할과 저장하는 정보는 서로 다릅니다.

그러면 block cache와 page cache와의 차이는 무엇인가?
Linux에서 블록 캐시(block cache)와 페이지 캐시(page cache)는 파일 시스템 데이터를 캐싱하는 데 사용되는 구조로, 성능을 향상시키는데 중요한 역할을 합니다. 두 캐시 모두 디스크 I/O를 줄이고, 파일 데이터에 대한 빠른 접근을 제공하려는 목적을 가지고 있지만, 사용하는 방식과 역사적인 배경에 차이가 있습니다.
블록 캐시(Block Cache): 블록 캐시는 오래된 시스템에서 파일 시스템의 블록을 캐싱하는데 사용되었습니다. 블록은 파일 시스템이 디스크를 관리하는 기본 단위이며, 일반적으로 여러 바이트로 구성되어 있습니다. 블록 캐시는 이런 블록들을 메모리에 캐싱하여 디스크 액세스를 최소화하고 성능을 향상시킵니다.
페이지 캐시(Page Cache): 페이지 캐시는 Linux 2.4 커널부터 도입된 방식으로, 블록 캐시를 대체하는 방식으로 사용됩니다. 페이지 캐시는 메모리 관리 단위인 "페이지"를 사용하여 파일 시스템의 데이터를 캐싱합니다. 이는 메모리 관리와 파일 시스템 캐싱 간의 통합을 가능하게 하며, 디스크 I/O 성능을 향상시킵니다. 페이지 캐시는 메모리 효율성을 높이고, 더욱 복잡한 작업을 수행할 수 있게 합니다.
결론적으로, 블록 캐시와 페이지 캐시는 비슷한 목적을 가지고 있지만, 사용하는 데이터 단위와 역사적인 배경에 차이가 있습니다. 현재의 Linux 시스템에서는 페이지 캐시가 주로 사용되며, 블록 캐시는 더 이상 널리 사용되지 않습니다.

오늘날, 이 buffer cache와 page cache는 대부분 unified buffer cache라는 하나의 cache로 통합되었다. 즉, 페이지 캐시와 버퍼 캐시는 동일한 물리적 메모리를 공유하며, 따라서 하나의 캐시에서 다른 캐시로 메모리를 쉽게 이동할 수 있습니다.

Recovery

예측 불가능한 상황이 발생할 수 있다. 예를 들어 쓰다가 power가 나간다거나 그런 것. 굉장히 consistency가 중요해짐

예를 들어 앞서 살펴본 것처럼, on-disk structure에 있는 super block과 inode를 복사해서 사용해서 사용하고 있는 중이였는데, power가 나가게 되면 inconsistency가 발생하게 된다. (in-memory structure에 있는 내용과 on-disk structure에 있는 내용이 달라지게 된다.)

💡

특히 이러한 문제는 굉장히 중요한 issue인 이유가, 잘못 해결하게 되면 정보가 전부 날아갈 수 있다.

File system consistency를 확인할 수 있는 program들이 존재한다.

windows : scandisk

UNIX : fsck (file system check)

💡

하지만, 사용자 관점에서는 운영체제가 지원하는 inconsistency의 해결만을 믿을 수는 없다. 따라서 back up 을 진행해두어야 한다.

UNIX File System (Indexed Allocation)

→ 보통 128 byte를 사용한다.

현재 파일의 위치를 “direct blocks, single indirect, double indirect” 가 해당 정보를 담고 있다.

direct block : 실제 해당 file에 속한 data block들의 index를 가지고 있음.

만약 block 사이즈를 4kb이고, direct block의 element가 10개면 40kb까지밖에 커버할 수 없다.

→ 그래서 또 다른 block을 index block으로 두는 것

💡

1024개를 추가적으로 더 가질 수 있음 (4kb / 4byte : 1024)

즉 1034 * 4kb까지는 single indirect만으로 커버가 가능한 것

→ 만약 그것도 부족하면 double indirect하는 것

하지만 file이 클 수록 버벅거린다는 단점이 발생할 수 있음

→ 사실 이 부분은 fair하기는 하지만, multimedia 시대에는 큰 용량에 대한 커버를 해야하는 문제가 발생하게 됨 (즉 index block의 threashold를 넘으면 문제가 발생함)

Linux Ext2 File System

Characteristic of Ext2

block size를 변경가능

inode의 수를 미리 지정가능

disk block를 group으로 partition (기본적으로 disk block안에 하나의 file을 담자는 idea)

→ On disk structure

Boot Block(boot sector)을 제외하고 동일한 사이즈의 Block Group으로 나눔. 각 group의 첫번째를 superblock으로 할당한다.

💡

Superblock : 특정 file system에 대한 meta정보를 가지고 있음 (block 사이즈는 어떻게 되고, 몇 개의 file이 있는지, 빈 block이 몇 개 있는지)

💡

Group Descriptors : Group에 대한 meta정보를 가지고 있음 (이거는 group의 개수에 비례하게 됨)

💡

Data block Bitmap : Data Block들 중에 빈 block이 어디에 있는지에 대한 정보 관리하는 bitmap

💡

Inode table : 해당 group에 속해있는 파일에 대한 inode들을 저장 (linux의 경우, inode가 128byte)

💡

Data Blocks : 실제 데이터가 있는 공간

추가적으로 빨간색으로 표기된 부분은 각 block group에 copy된다. 즉 하나의 group에서 오류가 발생해도 괜찮게끔 설계된 것이다.

Default options

block size : 1024 bytes

One inode for each group of 8,192 bytes
→ 즉 8block 마다 inode를 할당한다.
→ 추가적으로 전체 5% 정도롤 reserved block를 비어둠

이후에 다음과 같은 과정을 거치게 된다.

다음과 같이 1.4MB밖에 안되는 플로피디스크에도 Ext2 file system을 활용할 수 있다.

💡

여기서는 굉장히 작기때문에 group이 1개밖에 안되는 것

여기서 8개의 block마다 1개의 inode를 할당한다고 했고, 1개의 block size가 1KB이므로, 1.44MB/8K를 해서 184가 나오는 것이다. 추가적으로 1개의 inode는 128KB이므로, 1개의 block 당 inode를 8개 담을 수 있다. 따라서 inode를 담을 수 있는 block 23개가 필요하게 된다.

Creating the Ext2 Filesystem

💡

Ext2 filesystems are created by /sbin/mke2fs

위 명령어를 실행하게 되면, 해당 파티션에 위와 같은 구조로 disk block이 configure하게 된다.

Virtual File System

그런데 linux의 경우에는 20~30개의 file system을 지원한다. 또한 user 관점에서는 어떠한 file system을 사용하고 있는지에 대한 정보를 모른다.

→ 그러면 어떻게 kernel이 유저와 실제 구현된 file syst em을 분리를 시킬 수 있을까? Virtual file system을 이용하기 때문!

실제 file system 위에 abstraction software layer(VFS)를 입히는 것. 또한 VFS가 user부터의 모든 system call을 담당해서 abstraction을 시키는 것

File system은 워낙 diverse하다. 다양한 file system을 어떻게 kernel이 구현할 수 있게끔 할 것인가? 즉 abstraction할 수 있을 것인가

→ 어지간하면 kernel을 수정하지 않으면서 넣을 수 있을 것인가?

사용자 입장에서는 VFS만 알면 된다. (즉 몇 개의 system call만 알면된다.)

→ 개발자들이 system call에 대한 규약을 맞춰서 코딩을 하게끔 강제시키는 것

💡

이를 통해 VFS는 서로 다른 file system이어도 user에게 동일한 interface를 제공할 수 있고, 일종의 서로 다른 file system에 대해서 kernel abstraction을 제공하는 것이다.

Virtual File System (VFS)

A kernel software layer that handles all system calls related to a standard UNIX filesystem

목적이 무엇인가?
1. File system에 관계없이 동일한 interface
1. 표준 file system에 정의하는 함수들을 코딩하면 된다. 즉 kernel abstraction을 제공한다.

→ 이렇게 하지 않으면 새로운 file system이 지원하기 위해서는 kernel이 계속 바뀌어야 한다는 문제점이 발생한다.

💡

유저 입장에서는 기능이 완전히 동일하게 된다. interface가 동일하기 때문에

즉 VFS layer를 잘 구현하는 것이 kernel에서 가장 중요한 역할이다.

Virtual File System : Linux

linux에서는 VFS를 지원하기 위해서 4개의 자료구조를 유지하고 있다.

The `superblock` object

특정 file system에 대한 metadata를 가지고 있는 자료구조

The `inode` object

각 file마다 존재하는 meta정보들은 inode에 있다. 이러한 inode를 담기위한 kernel 자료구조

The `file` object

현재 process가 open하고 있는 file에 대한 자료구조

The `dentry` object

directory를 구현하기 위해 linux가 사용하고 있는 kernel의 자료구조

선 아래가 on-disk structure이고 선 위에가 in-memory structure이다. 파일이 만들어지고 없어짐에 따라서 superblock의 내용도 바뀌기 때문에 계속해서 on disk안에 있는 superblock의 내용도 업데이트 해주어야 한다. (in memory안에 있는 superblock은 on-disk에서 copy한 것이다.)

💡

file이라고 표기된 것이 현재 process가 열고있는 file에 대한 정보이다. In-memory 상에 있는 inode는 on disk상에 있는 inode를 copy한 것이다.

💡

linux에서는 directory에 해당하는 노드를 dentry라고 하는 kernel 자료구조로 구현하고 있다.

💡

여기에서 inode라고 하는 것은 on-disk안에 있는 inode를 cache한 것이다. 해당 kernel 자료구조 안에는 원본 inode number를 가지고 있다. 해당 정보를 통해 원본 inode가 어딨는지 알 수 있게 된다.

PCB의 element 중 file system과 관련된 정보를 담고있는 것이 2개가 있다.

fs : filesystem (현재 해당 process가 access하고 있는 file system에 대한 정보를 가지고 있음)

files : file_struct에 대한 포인터를 저장하고 있음.

💡

files_struct는 일종의 per-process open_file table이다. 해당 entry에는 global open_file table의 entry에 대한 pointer를 저장하고 있다.

→ 이걸 계속 따라가다보면 inode가 있음

💡

Linux에서는 per-process open file table(일반적으로 files_struct 구조체에 의해 표현됨)가 실제로 파일 디스크립터들의 배열을 포함하고 있습니다. 이 배열의 각 항목은 file 구조체의 인스턴스에 대한 포인터를 저장합니다.

file 구조체는 실질적으로 전역 open file table의 한 부분을 나타냅니다. Linux에서 file 구조체는 실질적으로 전역 open file table의 한 항목(또는 entry)을 나타냅니다. 각 file 구조체는 개별적으로 열린 파일에 대한 정보를 포함하며, 이 정보는 전역적인 파일 상태, 파일 작업, 그리고 파일 시스템에 대한 참조(예: 해당 파일이 저장된 파일 시스템, inode 정보 등)를 포함합니다.

inode와 open file table에 저장되는 정보가 비슷한 것 같은데 차이가 무엇인가?
inode는 파일의 메타데이터와 속성 정보를 포함하고 있으며, 일반적으로 파일의 접근 및 상태 정보를 직접적으로 포함하지는 않습니다.
inode는 파일 시스템에서 파일을 식별하고 파일의 메타데이터를 저장하는 데 사용되는 데이터 구조입니다. inode에는 파일의 크기, 소유자 정보, 접근 권한, 생성 시간, 수정 시간 등과 같은 메타데이터와 속성 정보가 저장됩니다. 이러한 정보를 통해 파일 시스템은 파일을 식별하고 파일에 대한 작업을 수행할 수 있습니다.
반면에 파일의 접근 및 상태 정보는 주로 오픈 파일 테이블(Open File Table)과 관련되어 있습니다. 오픈 파일 테이블은 프로세스의 열린 파일에 대한 정보를 유지하며, 해당 파일에 대한 파일 디스크립터, 파일 오프셋, 상태 등의 정보를 포함합니다. 오픈 파일 테이블은 프로세스가 파일에 접근하고 작업을 수행할 때 필요한 정보를 제공하고 관리합니다.
따라서, 파일의 접근 및 상태 정보는 일반적으로 inode에 직접 포함되지 않고, 오픈 파일 테이블과 관련된 자료구조에서 관리됩니다. inode는 주로 파일의 메타데이터와 속성 정보를 저장하는 데 사용되며, 파일의 접근 및 상태 정보는 open file table에서 관리됩니다.

위에 존재하는 inode는 on-disk에 있는 inode인가?
아니다. 해당 inode는 cahce된 inode이다. 이를 통해 만약 파일의 정보가 변경되어 inode의 수정이 필요할 때 storage에 접근하지 않고 DRAM의 속도를 그대로 이용할 수 있게 된다. 파일에 대한 작업이 필요할 때, 먼저 inode 캐시에서 해당 파일의 inode를 찾습니다. 이를 통해 디스크에서 inode를 다시 읽어오는 비용을 줄이고, 메모리 내의 inode를 더 빠르게 액세스할 수 있다. 따라서, 파일의 변경 등으로 인해 inode를 수정해야 할 때에도 inode 캐시를 사용하여 메모리 내에서 빠르게 수정 작업을 처리할 수 있다. 이는 디스크 접근을 줄이고 DRAM의 빠른 속도를 활용하여 파일 시스템의 성능을 향상시키는 데 도움이 된다.

Exact procedure

특정 프로세스가 새로운 파일을 열 때, 먼저 전역 오픈 파일 테이블(Global Open File Table)을 검색합니다. 이 과정에서는 해당 파일이 이미 열려있는지 확인합니다. (즉 대응되는 entry가 존재하고, 실제로 해당 파일이 open되어있는지를 확인한다.)
- 파일을 찾기 위해 전역 오픈 파일 테이블의 엔트리를 sequential하게 탐색한다.
- 해당 파일이 이미 열려있는 경우, 해당 파일의 파일 디스크립터(Global Open File Table의 index)를 프로세스의 개별 오픈 파일 테이블(Per-process Open File Table)에 저장합니다.
- 해당 파일이 없는 경우, 다음 단계로 진행합니다.

만약 파일이 전역 오픈 파일 테이블에 존재하지 않는다면, 해당 파일의 inode를 inode 캐시(Inode Cache)에서 찾습니다. 이는 디스크 접근을 최소화하기 위한 캐싱 메커니즘입니다.
- inode 캐시를 검색하여 해당 파일의 inode를 찾습니다.
- 만약 inode 캐시에 존재한다면, 해당 파일의 파일 디스크립터(Inode Cache의 index)를 전역 오픈 파일 테이블에 저장하고 이를 프로세스의 개별 오픈 파일 테이블에 저장합니다.
- 만약 inode 캐시에 존재하지 않는다면, 다음 단계로 진행합니다.

파일의 inode가 inode 캐시에 존재하지 않는 경우, 디렉터리 탐색(Directory Search)을 통해 해당 inode를 디스크에서 찾습니다.
- 파일의 경로를 디렉터리 구조를 따라 디스크에서 탐색하여 해당 파일의 inode를 찾습니다.
- 해당 inode를 inode 캐시에 저장합니다.
- 해당 파일의 파일 디스크립터를 전역 오픈 파일 테이블에 저장하고 이를 프로세스의 개별 오픈 파일 테이블에 저장합니다.

요약하자면, 파일을 열 때 프로세스는 다음과 같은 과정을 거칩니다:

전역 오픈 파일 테이블을 검색하여 파일의 존재 여부를 확인하고 파일 디스크립터를 프로세스의 개별 오픈 파일 테이블에 저장합니다.

전역 오픈 파일 테이블에 파일이 존재하지 않는 경우, inode 캐시에서 해당 파일의 inode를 찾습니다. 존재할 경우 파일 디스크립터를 저장하고, 존재하지 않을 경우 디렉터리 탐색을 통해 해당 inode를 찾아 저장합니다.

이후 프로세스는 파일을 찾았거나 생성한 후 파일 디스크립터를 사용하여 파일에 접근하고 작업을 수행합니다.

추가적으로 Directory Search는 다음과 같은 과정으로 진행된다.

주의해야할 지점은 Directory 도 file로 취급된다는 점이다.

디렉터리 탐색은 상위 디렉토리부터 시작하여 하위 디렉토리로 탐색하는 방식으로 진행됩니다.

탐색을 시작할 때 가장 상위 디렉토리, 즉 루트 디렉토리의 dentry에서 시작한다. (root directory에 해당하는 dentry는 반드시 dentry cache에 존재한다.)

디렉터리 엔트리를 탐색하는 도중에 하위 directory가 현재 directory의 d_subdirs에 있는지 여부를 검사한다.

만약 존재한다면, 해당 dentry를 사용하여 탐색을 계속 진행합니다. 만약 존재하지 않는다면, storage에서 해당 디렉터리의 inode를 storage에서 inode cache로 가져옵니다. 그리고 해당 inode를 지시하는 dentry를 생성하고, 해당 dentry를 dentry cache에 저장합니다.
💡
부모의 inode의 data block에는 해당 디렉토리에 대응되는 directory entry를 지시하고 있는 것이 존재하기 때문이다.

하위 디렉토리로 이동하여 다시 하위 디렉토리의 디렉터리 엔트리를 탐색합니다. 마찬가지로 해당 디렉터리의 dentry 캐시를 검사하여 캐시된 정보를 활용합니다.

최종적으로 원하는 파일이나 디렉토리의 dentry를 찾았을 때, 해당 dentry와 연결된 inode를 사용하여 파일에 접근하고 작업을 수행합니다.

💡

디렉터리 탐색을 통해 찾은 해당 파일이나 디렉토리의 inode는 inode cache에 저장됩니다. 또한 dentry의 경우에는 반드시 memory 상에 존재한다.

💡

결과적으로 최대한 locality를 이용하기 위해서 cache를 이용하자는 개념이 포함되어 있는 것이다.

struct dentry {
    ...
    struct dentry *d_parent;      /* parent directory */
    struct qstr d_name;
    struct inode *d_inode;        /* Where the name belongs to - NULL is
                                  * negative */
    unsigned char d_iname[DNAME_INLINE_LEN];    /* small names */
    ...
    const struct dentry_operations *d_op;
    struct super_block *d_sb;            /* The root of the dentry tree */
    ...
    struct list_head d_child;            /* child of parent list */
    struct list_head d_subdirs;           /* our children */ 
    ...
} __randomize_layout;

💡

즉, d_subdirs이라는 정보를 통해 하위 디렉토리에 대한 dentry list를 가지고 있다. 만약 해당 정보가 d_subdirs에 없으면 해당하는 정보를 inode에서 가져온다.

특정 inode의 데이터 블록에는 다음과 같은 정보가 저장될 수 있습니다:

디렉터리 엔트리(Directory Entry): 디렉터리의 데이터 블록에는 해당 디렉터리에 포함된 파일 및 하위 디렉터리의 이름과 해당 파일의 inode 번호가 저장됩니다. 이 디렉터리 엔트리는 디렉터리의 데이터 블록 내에 저장되어 있습니다.
💡
inode 번호를 알면 대응되는 inode는 쉽게 찾을 수 있다. 즉 inode 번호는 고유한 식별자로 사용될 수 있다.

파일 데이터: 일반 파일의 경우, 해당 파일의 데이터는 해당 inode의 데이터 블록에 저장됩니다. 파일의 실제 내용은 이러한 데이터 블록에 저장되어 있으며, 파일 시스템에서 파일의 내용을 참조할 때 이 데이터 블록을 읽어옵니다.

요약하자면, 특정 inode의 데이터 블록에는 디렉터리 엔트리나 파일의 데이터가 저장됩니다. 디렉터리의 데이터 블록에는 해당 디렉터리에 속한 파일 및 하위 디렉터리의 정보가 저장되며, 파일의 데이터는 해당 파일의 inode의 데이터 블록에 저장됩니다.

Contents

새소식

인기 검색어

10. File System

File system Responsibilities

In-memory partition table

In-memory directory structure

System-wide open-file table

Per-process open-file table

The `superblock` object

The `inode` object

The `file` object

The `dentry` object

당신이 좋아할만한 콘텐츠

티스토리툴바

10. File System

File system Responsibilities

In-memory partition table

In-memory directory structure

System-wide open-file table

Per-process open-file table

The superblock object

The inode object

The file object

The dentry object

당신이 좋아할만한 콘텐츠

티스토리툴바

The `superblock` object

The `inode` object

The `file` object

The `dentry` object