Allocation of file data in disk

디스크에 파일을 저장하는 방법은 크게 세 가지.
파일의 크기는 불균일함. 디스크에 파일을 저장할때는 동일한 크기의 섹터 단위로 나누어 저장됨.

각각의 동일한 크기의 저장 공간을 논리적인 블럭이라고 부름. 임의의 크기의 파일을 동일크기의 블록단위로 나누어 저장하고 잇는데, 페이징 기법과 유사한 느낌이다.

Contiguous Allocation

하나의 파일이 디스크 상에 연속적으로 저장되는 방식.

• 장점
  빠른 I/O 가 가능하다.
  한번의 seek/rotation으로 많은 바이트를 한꺼번에 전송 가능
  하드디스크같은 매체는 대부분의 접근시간이 디스크 헤드 이동시간인데, 한번에 찾으므로 속도가 빨라지게 된다.
  속도효율성이 중요한 Realtime file 용도 또는 이미 작동중인 프로세스의 스왑공간 용도로 사용되기 적합.
  Direct access(=random access) 가능.

• 단점
  외부조각이 발생하게 된다.
  File grow가 어려움. 파일 크기 변화 시 유연한 저장이 어렵다. (파일크기를 키우는데 제약)
  -> 여유있게 파일을 저장하는 방법을 생각해야함.
  -> 여유있게 공간을 할당해주면, 내부조각의 문제가 발생한다.

Linked Allocation

비어있는 위치면 어디든 데이터를 저장하는 방식. 링크드 리스트처럼 연결되어 다음 데이터가 어디에 있는지 포인터를 가짐

• 장점
  외부조각이 발생하지 않는다. 공간효율이 좋음.

• 단점
  직접접근이 안된다. 처음 시작 섹터에서 보려는 위치로 타고 들어가야함. 건너뛰기가 불가능.
  디스크는 직접접근이 가능하더라도, 파일관리법을 linked allocation을 쓰면 직접접근 불가.(only 순차접근)

Reliability 문제: 한 섹터가 고장나면 포인터가 유실되면서 많은 부분을 잃게됨
Pointer를 위한 공간이 블록의 일부가 되어 공간 효율성을 떨어뜨림.
-> Sector (512 bytes), pointer(4bytes)

• 변형
  File-Allocation Table(FAT) 파일 시스템
  FAT은 포인터를 별도의 위치에 보관하여 reliability와 공간효율성 문제를 해결한 방식.

Indexed Allocation

인덱싱을 통한 직접접근을 구현한 방식.

• 장점
  외부조각이 생기지 않으면서, 직접접근이 가능하다.

• 단점
  아무리작은 파일이더라도, 인덱스를 위한 블록 1개, 데이터 저장 블록 1개로 공간을 낭비하게 된다.
  실제로 많은 파일들이 작은데, 인덱스를 위한 블록이 필요해서 배보다 배꼽이 큰 상황 연출.

매우 큰 파일의 경우 하나의 블록으로 인덱스를 저장하기엔 부족할 수 있음.
-> Linked scheme(인덱스 블록 크기를 벗어난다면 또 다른 인덱스 블록을 pointing 하여 다음 인덱스 블록을 참조하도록 하는 방식), multi-level index(2단계 페이지 테이블 쓰듯)로 문제를 해결.

---

UNIX 파일 시스템 구조

하나의 논리디스크가 존재하면 거기에는 파일 시스템이 존재한다.

유닉스에서 파일시스템은 4가지로 구성된다. boot block, super block, Inode list, data block.

Boot Block

boot block은 어떤 파일시스템이든, 동일하게 항상 0번 블록으로 존재.
컴퓨터의 부팅을 돕는 블록이며, 항상 0번 블록을 부트블록으로 설정하여 부팅에 필요한 정보를 불러온다.

Super Block

Super block은 파일 시스템에 대한 총체적인 정보를 담는다.
어디가 빈 블록이고 데이터가 있는 블록은 어디인지, Inode 블록은 어디서부터 어디까지인지 등.

iNode List

파일의 메타데이터는 그 파일을 가지고 있는 디렉토리에 기록되어있다.
하지만 디렉토리가 파일의 모든 메타데이터를 가지고있지 않음. 실제 파일 메타데이터들은 별도의 위치에 빼서 보관하고 있는데, 그곳이 바로 Inode(index node) list.

파일이름만 디렉토리가 가지고있고, 나머지 메타데이터들은 inode에 저장되어있다. 그래서 디렉토리는 해당 파일의 메타데이터를 가지고있는 inode 번호를 가지고 있게 된다.

파일의 위치정보는 어떻게 저장되고 있을까.

아이노드는 Indexed allocation 방식을 사용하는데, 파일크기가 작은 경우엔 direct blocks를 통해서 파일 위치를 가리키고, 대단히 큰 파일의 경우 indirect를 통해서 파일위치 정보에 접근할 수 있다.
대부분의 파일의 크기는 대단히 작은데, 그런 경우엔 한번의 포인터 접근(direct blocks)을 통해 파윌 위치정보를 알수있고, 대단히 큰 파일이라면 indirect을 통해 우선 디스크의 데이터블록에 접근하고 관련한 파일의 위치정보로 가는 경로로 가서 찾는 정보에 접근하게 된다.

Data Block

데이터 블록은 파일의 실제 내용을 보관함.

FAT File System

윈도우즈 계열, 모바일에서 종종 사용되는 방식.

파일의 메타데이터 중 위치정보를 FAT 에 보관. 나머지는 디렉토리(파일이름, 접근권한, 사이즈, 파일의 첫번째 데이터블록 위치 등)가 가지고 있음.

Data block의 갯수(총 블록수)만큼 FAT의 배열 크기가 결정됨.
그 배열엔 해당 블록의 다음 블록을 기록해둠.

다음 데이터 블록의 위치를 FAT을 참조하여 확인하게 된다.

---

Free-Space Management

bit map or bit vector

각각의 블록 별로 번호가 있는데, 유닉스의 경우 super block에 비트를 두어 0, 1로 해당 블록이 사용되는지 아닌지를 기록하게 됨.
비트맵은 부가적인 공간을 필요로 함. 연속적인 n개의 free block을 찾는데 효과적이다.

linked list

비어있는 블록들을 링크드 리스트로 연결해두고 첫번째 비어있는 위치를 참조할 수 있도록 함.
공간낭비가 없다. 하지만 연속적인 빈공간을 찾기는 어렵다.

grouping

링크드 리스트 방식의 변형.
첫번째 free block이 n개의 포인터를 가지고, n-1 번째 포인터는 free data block을 가리킴. 마지막 포인터가 가리키는 블록은 또 다시 n pointer를 가짐.

counting

grouping 방식처럼 비어잇는 공간을 포인팅하게하고, 그 포인팅한 곳은 해당 공간에서부터 얼마만큼 비어있는지 정보를 담아 빈공간을 빠르게 확인할 수 있게 함.
프로그램들이 종종 여러 개의 연속적인 블록을 할당하고 반납한다는 성질에서 착안.

---

Directory Implementation

디렉토리는 디렉토리 내에 존재하는 파일들의 메타데이터를 관리하는 특별한 파일이다.

Linear list

• <file name, file metadata> 의 리스트
• 구현이 간단.
• 디렉토리 내에 파일이 있는지 찾기 위해서는 linear search 필요 (time-consuming)

Hash Table

• linear list + hashing
• Hash table은 file name을 이 파일의 linear list의 위치로 바꾸어줌
• Search time을 없앰
• collision 발생 가능

File의 메타데이터 보관 위치

• 디렉토리 내 직접 보관
• 디렉토리에는 포인터를 두고 다른곳에 보관. (inode, FAT 등)

Long file name 의 지원

• <file name, file metadata>의 list에서 각 entry는 일반적으로 고정 크기
• file name이 고정 크기의 entry 길이보다 길어지는 경우 entry 의 마지막 부분에 이름의 뒷부분이 위치한 곳의 포인터를 두는 방법
• 이름의 나머지 부분은 동일한 directory file의 일부에 존재.

---

VFS and NFS

Virtual File System (VFS)

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

Network File System (NFS)

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

---

Page Cache and Buffer Cache

Page Cache

• Virtual memory 의 paging system 에서 사용하는 page frame을 caching의 관점에서 설명하는 용어
• Memory-Mapped I/O를 쓰는 경우 file의 I/O에서도 page cache 사용

Memory-Mapped I/O

• file의 일부를 virtual memory 에 mapping 시킴
• 매핑시킨 영역에 대한 메모리 접근 연산은 파일의 입출력을 수행하게함.

Buffer Cache

• 파일 시스템을 통한 I/O 연산은 메모리의 특정 영역인 buffer cache 사용
• file 사용의 locality 활용 -> 한번 읽어온 블록에 대한 후속 요청시 버퍼 캐시에서 즉시 전달
• 모든 프로세스가 공용으로 사용
• Replacement algorithm 필요 (LRU, LFU 등)

Unified Buffer Cache

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