File System

In-Memory Structure

• 메모리 내에서 파일을 관리하는 기법
• 파일의 리스트를 저장하는 File Table을 메모리 내에 저장

• File Table
  Entry 하나 당 File 하나의 정보 저장(count, offset, attribute)

• Per-process File Descriptor Table
  각 프로세스는 자신이 사용하는 File들을 File Table에서 주소로 참조

• 프로세스들은 System Call을 통해 File table에 있는 File을 접근

  추신: 모든 프로세스는 기본적으로 standard input/output/error 파일을 참조

Virtual File System

File System의 공통적인 부분을 묶어서 관리

Layerd File System

File System을 계층별로 나누어서 관리·개발

On-Disk Structure

• 디스크 내에서 파일을 관리하는 기법

• File Control Block(i node)가 존재

• 왼쪽은 하나의 디스크를 MBR(부트로더가 저장된 파티션)과 Partition 1~3으로 분할 한 상황 + Partition 1이 Default Partition(OS가 들어가있는 파티션)

• Boot Block
  부팅에 필요한 파일(운영체제)가 저장된 공간
  → 윈도우는 Boot Sector

• Super Block
  파티션안에 저장된 모든 파일의 정보(타입, 블록개수) 저장
  → 윈도우는 Master File Table

• Bitmaps
  몇 번째 Block이 사용중인지 아닌지를 1비트단위 테이블로 저장
  → 디스크에 블록이 총 1000개라면 1000비트의 크기가 됨

• i-nodes
  파일의 FCB(File Control Block)들을 모두 저장
  → Unix에서 FCB를 i-node라 부르기에 i-nodes

• root dir
  루트 디렉토리를 정의

• files & directories
  모든 파일과 디렉토리를 저장

보통 Block = 4kb
만약 400GB disk를 사용한다면 bitmaps의 크기는?
400GB ÷ 4kb = 백만 → 1Mbit = 125kbyte

Disk Block

디스크의 Sector 크기는 보통 512Byte = 0.5kb
파일의 block은 4kb이므로 파일의 한 block은 8개의 sector를 차지

Free Space Management

앞에 추신으로 나온 내용과 똑같음
블록 하나당 1비트씩 줘서 1이면 빈 블록, 0이면 사용중인 블록

File Control Block(i-node)

• 파일의 권한, 생성·접근·수정 일자, 크기, 소유주, ACL 저장
• 다음 데이터 블록의 주소를 저장하는 포인터도 저장

Directory

• In the directory entry
  디렉토리 안에 있는 파일들의 FCB를 다 넣는 방법

• In the separate data structure
  디렉토리 안의 파일의 이름만을 가지고 포인터로 FCB를 포인팅
  → Unix에서 사용

• A hybrid approach
  FCB에서 중요한 정보만 디렉토리에 가지고 특정된 것들만 포인팅
  → Windows에서 사용

Allocation Methods

• 파일하나는 여러개의 블록을 사용
• 블록끼리 순차적으로도 있겠지만, 문제가 발생할 수 있음
• 어떻게 블록들을 Disk에 Allocation 해야할까?

Contiguous Allocation

• 디렉토리는 파일의 시작주소(start)와 그 길이(length)를 저장

• 장점

  • 파일의 위치를 찾을 때 이름, 위치, 길이만 알면 됨
  • 연속적으로 할당되었 때문에 Spatial Locality를 잘 활용함
  • Arm Seek Time 또한 작음

• 단점

  • 파일의 크기는 서로 동일하지 않으므로 Fragmentation 발생
  • 파일이 더 커지려고 하는데 뒤에서 막는 상황에는 적용 불가

• 그래서 크기가 변하지 않는 CD-ROM 같은 곳에 적용

Linked Allocation

• 디렉토리는 파일의 시작주소와 끝주소를 저장

• 각 블록은 다음의 블록의 포인터를 저장

• 장점

  • 파일의 위치를 찾을 때 이름, 위치, 길이만 알면 됨
  • Fragmentation이 없음
  • 파일의 크기가 서로 달라도 제약이 없음

• 단점

  • Spatial Locaility가 떨어져서 Arm Seek Time이 길어짐
  • 중간의 한 Block이 포인터 정보가 깨진다면 뒤의 블록은 다 날림

• File-Allocation Table에서 사용
  

Indexed Allocation

• 디렉토리는 파일의 이름과 index block을 가리키는 포인터 저장

• index block은 한 파일의 block들의 주소를 모두 저장

• 장점

  • Fragmentation이 없음
  • 하나가 손상되어도 다 날아갈일이 없음

• 단점

  • index block 때문에 파일 하나당 하나의 블록을 더 사용
  • 파일크기가 1개의 블록이라면 index block도 1개라서 2배가 됨

• i-node
  

• 왼쪽은 i-node 한 개를 뜻

• 파일크기가 12블록 이하면 direct blocks 하나에 저장

• 그 이상이면 single indirect로 i-node를 1024개 접근

• 12 + 1024개로도 안되면 double indirect로 1024^2개 접근

• 이것도 부족하면 triple indirect로 1024^3개로 접근

• single = 4MB, double = 4GB, triple = 4TB

UFS에서의 예제: /bin/a.out 파일에 접근하는 상황

1. 루트 경로(/)에서 디렉토리를 저장하는 10000주소 접근
2. 디렉토리에서 bin의 i-node인 100주소를 Get하고 접근
3. /bin에서 디렉토리 정보를 답는 11000주소 접근
4. 디렉토리에서 a.out의 i-node인 500주소를 Get하고 접근
5. direct block 12개는 바로 Get
6. 그 이상은 single indirect block으로 650주소로 한번 참조
7. 650주소의 i-node에서 남은 데이터를 Get

Other Consideration

Block Size

적절한 Frame 수처럼 Block도 성능과 크기를 비교해서 4KB로 설정

Read-Ahead

Spatial Locality을 이용해서 근처에 있는 데이터블록을 미리 읽는 방식

Buffer Cache

• in-memory partition table

• buffer cache
  파일을 읽으면 메모리안의 buffer cache에 저장, 자주 읽는 파일 저장

• directory cache
  자주가는 디렉토리 또한 캐시에 저장

• 통상적으로 위 3개의 캐시를 buffer cache라고 부름

Caching Writes

• write back
  • 캐시에 데이터가 어느정도 찰 때 디스크로 저장
  • 불일치한 상황 자주 발생(Unreliable, inconsistency)
  • 일정주기로 write하므로 오버헤드가 상대적으로 적음
• write through
  • 캐시가 갱신될 때마다 디스크로 저장
  • 불일치한 상황 거의 없음(Reliable, consistency)
  • 계속 write하므로 오버헤드가 상대적으로 큼

Log Structured File Systems

Journaling file systems

• disk에 데이터가 아닌 그 보다 더 적은 크기인 로그 데이터를 저장

• 만약 시스템 다운되었다가 다시 켜지는 상황
  → disk에 있는 log를 보고 데이터를 회복 후 log를 삭제
  → 재부팅을 했는데 log가 있다는 것은 제대로 작동이 안됐음을 의미