파일은 크기가 균일하지 않음
그래서 파일을 동일한 크기 단위인 sector로 나누어 저장

디스크에 파일을 저장하는 방법은 아래의 3가지가 있음.
(메모리 관리 기법 중 페이징 기법과 유사함)

• 연속 할당
• 연결 할당
• 인덱스를 이용한 할당

연속 할당

하나의 파일이 디스크 상에 연속해서 저장되는 방식으로,
나누어진 각 블록들이 연속된 번호를 부여 받아 저장된다.

장점

• 빠른 I/O (대부분의 접근 시간은 헤더가 움직이면서 읽어 들이는 시간임)
  ➡️ 한 번의 seek/rotation으로 많은 바이트를 한 번에 transfer할 수 있다.
  (모두 연속해서 붙어 있으므로 추가적인 탐색 비용이 소요되지 않음)
  ➡️ 따라서 Realtime 파일(공간효율성보다는 속도효율성이 더 중요할 때) 또는
  이미 run 중이던 프로세스의 swapping 용도로 사용함 (프로세스의 주소공간중의 일부를 저장하는 용도)
• 임의 접근 가능

단점

• 외부 단편화가 발생
• 파일 grow가 어려움
  • 파일의 크기가 커지면 제약 사항이 발생함.
    ➡️ 파일 생성 시 얼마나 큰 hole을 배당할 것인가?
  • grow를 얼만큼 가능하게 할 것인가
    (grow 정도를 크게 할수록 내부 단편화 문제가 커짐)

연결 할당

sector들이 각각 node가 되어 Linked List 구조를 취하면서 파일을 저장한다.

장점

• 외부 단편화가 발생하지 않음

단점

• 첫 요소부터 차례대로 읽어야 하므로 임의 접근이 불가능.
• 신뢰성 문제
  • 한 sector가 고장나 pointer가 유실되면 그 이후 모든 sector로 접근할 수 없음
  • 포인터를 위한 공간이 필요하므로 공간 효율성을 떨어뜨리게 됨

변형

• File-allocation table (FAT) 파일 시스템
  ➡️ 포인터를 별도의 위치에 보관하여 신뢰성 문제와 공간 효율성 문제를 해결!
  

인덱스를 이용한 할당

파일이 어디에 나눠져 있는지 인덱스를 적어 두는 블록 하나 =인덱스 블록을 활용

장점

• 외부 단편화가 발생하지 않음
• 임의 접근이 가능

단점

• 작은 파일의 경우 공간 낭비가 심함
  (실제로 많은 파일들이 사이즈가 작음)
• 매우 큰 파일의 경우 하나의 인덱스 블록으로 커버할 수 없다

해결 방안

• linked scheme
  index block을 여러 개 두기
• multi-level index
  블록의 마지막에 다음 index 블록을 가리키는 값을 설정하여 서로 연결

UNIX

실제로 시스템은 어떻게 구현되는가..!

구조

Boot block

부팅에 필요한 정보를 담고 있는 블록
모든 파일 시스템에 존재하는 블록

Super block

파일 시스템에 관한 총체적인 정보를 담고 있는 블록
어느 부분이 비어 있는 블록인지, 어느 부분이 사용 중인 블록인지, 어디부터가 Inode 블록인지 Data 블록인지 등을 알려 주는 정보를 가짐

Inode list

파일 이름을 제외한 파일의 모든 메타 데이터를 따로 저장

파일 하나 당 Inode가 하나씩 할당됨
해당 Inode는 그 파일의 메타 데이터를 갖고 있음.

이때 파일의 이름은 디렉토리가 가지고 있는데, 디렉토리는 파일의 이름과 Inode 번호를 저장하고 있다.

direct blocks는 파일이 존재하는 인덱스를 저장하는 인덱스 블록
파일의 크기가 크지 않다면 이 블록을 이용하여 파일을 접근할 수 있다.

direct blocks으로 커버할 수 있는 크기보다 저장 용량이 큰 파일은 single indirect를 통해서 하나의 level을 두어서 저장하는 방식을 취하고, 그보다 더 큰 파일은 double indirect, 더 큰 파일은 triple indirect 방식을 취한다.

Data block

파일의 실제 내용을 보관하는 블록

이 중 디렉토리 파일은 자신의 디렉토리에 속한 파일들의 이름과 Inode 번호를 가지고 있음.

FAT 파일 시스템

• 윈도우즈 계열에서 주로 사용
  
  
• 파일의 메타 데이터의 일부(위치 정보)를 FAT에 저장하고, 나머지 정보는 디렉토리가 가지고 있다.
  (파일 이름, 접근 권한, 소유주, 파일의 첫 번째 위치 등)
• 위 사진에서 217번이 첫 번째 블록인데, 다음 블록의 위치를 FAT에 별도로 관리
• FAT 테이블 전체를 메모리에 올려 놓았으므로 연결 할당의 단점(임의 접근 불가, 신뢰성 문제, 공간 효율성 문제)을 전부 극복
  ✅ 참고로 FAT는 중요한 정보이므로 복제본을 만들어 두어야 한다.
  

빈 공간 관리

sector가 할당되고 나서 발생하는 hole을 어떻게 관리할 것인가?

Linked list

모든 free 블록을 링크로 연결 (free list)

• 연속적인 가용 공간을 찾기 어려움.
• 공간의 낭비가 없음

Grouping

Linked list의 변형
첫 번째 free 블록이 n 개의 포인터를 갖음
하나의 free 블록에 나머지 free 블록에 대한 위치 정보를 저장하는 방식

Counting

프로그램들이 종종 여러 개의 연속적인 블록을 할당하고 반납한다는 성질에 착안

Bit map or Bit vector

0이면 비어 있는 값이고, 1이면 sector 저장된 공간이다.

• 연속된 n개의 free 블록을 찾기 효과적이지만, 0 또는 1을 저장할 부가적인 공간을 필요로 한다.

디렉토리 구현

선형 리스트

<file name, file의 메타 데이터>의 리스트

• 구현이 간단
• 디렉토리 내에 파일이 있는지 찾기 위해서는 선형 탐색이 필요하다. (O(N))

해시 테이블

선형 리스트 + 해싱
해시 테이블은 file name을 이 파일의 선형 리스트의 위치로 바꾸어 준다.

• 탐색 시간이 O(1)이다.
• 해시 충돌이 발생할 수 있다.

파일의 메타 데이터의 보관 위치

• 디렉토리 내에 직접 보관
  
  
• 디렉토리에는 포인터를 두고 다른 곳에 보관
  Inode, FAT

Long file name의 지원

• <file name, file의 메타 데이터>의 리스트에서 각 엔트리는 일반적으로 고정 크기
  ‼️ 하지만 file name이 고정 크기의 엔트리 길이보다 길어지는 경우
  엔트리의 마지막 부분에 file name의 뒷 부분이 위치한 곳의 포인터를 두기
  ➡️ file 이름의 나머지 부분은 동일한 directory file의 일부에 존재
  

VFS와 NFS

Virtual File System (VFS)

서로 다른 다양한 파일 시스템에 대해 동일한 시스템 콜 인터페이스(API)를 통해 접근할 수 있게 해 주는 OS의 레이어

Network File System (NFS)

분산 시스템에서는 네트워크를 통해 파일이 공유될 수 있다.
NFS는 분산 환경에서 대표적인 파일 공유 방법

‼️ 어떤 파일 시스템을 쓰든 상관 없이 VFS 인터페이스를 사용한다.
분산 시스템에서는 네트워크를 통해 파일을 공유하기 위해 NFS 클라이언트와 NFS 서버가 이용됨

페이지 캐시와 버퍼 캐시

운영체제가 file입출력을 할 때 사용자 프로그램의 요청을 받아서 disk에서 읽어온 내용을 그냥 전달하는 게 아니라 자신의 buffer cache 영역에 읽어놓고, 그 내용을 copy로 넘겨주기 때문에 다음번에 동일한 file data에 대한 read, write system call이 오면, disk까지 가지않고 buffer cache에서 처리한다.
예전에는 sector단위는 512byte였다. 최근에는 buffer cache가 page cache와 통합이 되면서 buffer cache에서 사용하는 단위도 4KB를 사용한다(unified buffer cache).

페이지 캐시

가상 메모리의 페이징 시스템에서 사용하는 페이지 프레임을 캐싱의 관점에서 설명하는 용어
Memory-Mapped I/O를 쓰는 경우 파일의 I/O에서도 페이지 캐시를 사용한다.

Memory-Mapped I/O

파일의 일부를 가상 메모리에 매핑한다.
매핑한 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게 한다.

버퍼 캐시

파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 버퍼 캐시를 사용한다.
파일 사용의 지역성 활용
한 번 읽어 온 블록에 대한 후속 요청 시, 버퍼 캐시에서 즉시 전달
모든 프로세스가 공용으로 사용
교체 알고리즘 필요 (LRU, LFU 등)

통합 버퍼 캐시

최근의 OS에서는 기존의 버퍼 캐시가 페이지 캐시에 통합됨.

통합 버퍼 캐시를 사용하지 않을 때와 사용할 때의 차이

❌ unified buffer cache를 이용하지 않는 File I/O

read, write system call을 쓸 때는 그 내용이 buffer cache에 있든 없든 항상 운영체제에게 요청해서 받아와야 함.
mmap을 쓰게 되면 page cache에 올라온 내용은 운영체제의 도움을 받지 않고 사용자 프로세스가 직접 메모리접근을 통해 I/O를 한다(인터페이스의 차이)

mmap을 사용하는 이유
mmap을 사용하면 이미 메모리에 올라온 내용에 대해서는 kernel의 도움을 받지 않고 (운영체제를 호출하지 않고) 자신이 직접 자신의 메모리에 접근하듯이

⭕️ unified buffer cache를 이용한 File I/O

unified buffer cache를 사용하면 기존처럼 buffer cache를 따로 두지 않고, 필요에 따라 page cache에서 공간을 할당해서 쓰는 방식을 사용

read, write system call을 하는 경우 해당 내용이 buffer cache에 올라와 있든 아니든 상관없이 운영체제에게 CPU 제어권이 넘어감

CPU는 이미 올라와 있는 data는 사용자 프로그램에 copy해주고 메모리에 없다면 disk에서 읽어와서 사용자프로그램에 copy해서 전달한다.

mmap인 경우, 자신의 주소영역중에 일부를 file에 mapping하는 단계를 거치고 나면 사용자 프로그램의 주소영역에 page cache가 mapping된다.
이전처럼 buffer cache의 내용을 copy하는 것이 아니라 그냥 page cache 자체가 사용자 프로세스의 논리적 주소영역에 mapping되어 사용됨(page cache에 직접 읽고 쓴다)