4. Partitions

디스크는 여러 partition으로 나누어질 수 있다. 또는 여러 디스크를 하나로 확장할 수 있다.
각 partition은

• raw : NO file system, 포맷되지 않았음, data access 빨리 하려고 사용하기도 함
• cooked : file system

포맷 = 운영체제가 올라간다
minidisk / volume = partition with file system 포맷된 partition

file system layout

file system은 disk에 저장된다.
디스크는 1개 이상의 partition으로 나누어져 있다.

제일 앞의 sector 0는 Master Boot Record(MBR) ; booting 정보
그 다음은 Partition table (start & end address of partitions)

각 파티션의 첫번째 block은 boot block
MBR에 의해 load되어 booting될 때 실행된다.

Mounting

추가적인 file system을 현재 file system에 붙이는 것
file system은 사용되기 전에 mount 되어야 한다.

root partition OS kernel을 담고 있다.
다른 partition들은 부팅될 때 자동으로 mounting 되거나 수동으로 나중에 mount할 수 있다.
Own directory structure : Linux
Different name space : Windows ex. C, D drive

Virtual File System (VFS)

가상 파일 시스템.
같은 system call interface(API)가 다른 파일시스템에 사용될 수 있다.

5. Data Structures

file system은 기본적으로 on-disk
in-meory는 cache 역할을 하여 access 성능을 높여준다.

On-disk structures

• Boot Control Block : booting하는데 필요한 정보 (boot block(UFS)/partition boot sector(NTFS))
• Volume Control Block : partition detail(# of size of blocks, free block count, pointers, free FCB count) (super-block(UFS) / master file table(NTFS))
• Directory structure
• File Control Block(FCB) (i-node(UFS))

In-Memory Data Structures

file system management / performance improvement via caching

• in-memory mout table : 어떤 file system인지, 각 mounted volume 정보
• in-memory directory structure : directory information
• system-wide open-file table : user별 FCB
• per-process open-file table : process별, 위의 index를 갖고 있는 포인터
• Buffers
  
  file open하려고 하면 먼저, system-wid open-file table을 찾는다
  
  각 프로세스별로 open-file table을 가지고 있고, open을 호출하면 disk에서 메모리로 올리고, system-wide open-file table업데이트 후, per-process를 업데이트한다. 그리고 그 index가 file descriptor
  per process는 파일 호출 순서에 따라 똑같은 FCB에 따라 갖고 있는 정보가 다를 수 있다.

6. Directory Implementation

• array
• Linear List : data block을 가리키는 file name list
  구현하기 쉽지만, 찾기 어렵다
• Hash table : 찾는 시간을 줄일 수 있다.
  collision : hash function을 통해 얻은 hash 값이 같아서 같은 entry에 배정되는 상황
  이러한 collision이 많으면 결국 그 entry에 해당하는 list를 search하는 과정이 발생
  fixed size : 만약에 크기 늘어나게 만들면 이미 들어가 있는 애들도 모두 hash해야 한다(reshuffling)

7. Block Allocation

File system은 일정한 크기로 block(multiple of sectors)을 나누어 사용한다.
track이나 sector단위로 사용하면 너무 작은 단위의 access가 발생하여, 성능이 줄어들기 때문이다.

Block allocation method는 어떻게 disk block을 파일에게 할당할 것인지를 의미

1) Contiguous Allocation

연속적 할당

하나의 파일에 대해서는 disk의 연속적인 block을 할당해주는 것이다.

• 간단하다. starting location(block #)과 length(number of blocks)만 알면 된다.
• random access가 가능하다. ; 어디로 가야 하는지 바로 알 수 있다. 접근하고자 하는 곳에 바로 갈 수 있다.
• wasteful of space 공간 낭비 (dynamic storage-allocation problem)
  fragmentation --> shuffling
• file이 커질 수 없다.

Extent-Based Systems

modified contiguous allocation shceme
extent 는 연속적인 블록.
초기에 파일을 위해 할당, file을 위한 양이 충분치 않으면 다른 extent가 추가된다.
extent가 너무 크면 internal fragmentation problem

2) Linked Allocation

각 파일은 블록의 linked list로 되어 있다.
disk에서 여러 위치로 흩뿌려져 있다.

• 간단하다. starting address만 필요
• free space management system : 공간 낭비가 없다.
• NO random access 가고자 하는 곳에 바로 못감 무조건 linked list 하나씩 거쳐가야 함
• space required for the pointers : 포인터를 위한 공간이 요구된다.
  block : data + pointer (실제 data의 공간이 줄어든다)
• 특정 block 문제 생기면, 그 뒤에 찾아갈 수 없다 --> doubly linked list로 해결가능

예시,

File Allocation Table

window FAT32 file system
(window, NTFS도 있다.)

<Window의 on disk 구조>

[Boot Block][2 FAT] [Data Area]

• Boot Block : (512 bytes) Boot code & Metadata
• FAT : 2개, 하나 깨지면 복구하려고
• Data Area : 0번째 block에는 root directory 배열

root directory 배열 하나

하나의 block size가 1024 byte라면, root directory에 몇 개의 file이 생길 수 있을까?
: 2^10 / 2^5 = 32개

root directory entry가 가지는 start block의 index(FAT)를 따라가면,
FAT에는 start block 다음에 취해야 할 행동이 적혀 있다.
즉, end-of-file이 적혀 있다면, 파일이 하나의 start block만으로도 내용이 끝난 것이고,
index가 적혀 있다면, start block 다음에 가야 할 block index가 있으니 내용이 한 block으로 끝나지 않았다는 것을 의미한다.
(아까 위에서 boot block 다음에 있던 것이 FAT)

FAT는 12/16/32의 크기를 가질 수 있는데, 커질수록 data area가 커진다.
block size를 1024 byte라고 가정했을 때,

• 12 : 2^12 X 2^10 = 2^22 byte = 4 MB
• 16 : 2^16 X 2^10 = 2^26 byte = 64 MB
• 32 : 2^32 X 2^10 = 2^42 byte = 4 TB

test file의 start block #에 먼저 내용이 시작된다.
그리고 start block #을 따라 FAT에서 block #를 찾아갔더니, end-of-file이 적혀있지 않다. 추가적인 block이 필요했다는 뜻. 즉 file size가 1024 byte보다 많아서, 다음 block 내용까지 봐야 한단다. block #를 따라 또 읽으면 된다.
그리고 그 block #를 따라 FAT를 또 본다. index가 적혀 있다면 파일을 이어 읽고, 그 index를 FAT에서 찾아 end-of-file이 나올 때까지 반복한다.

즉 이 test file은 총 block을 3개 사용한다. (217, 618, 339)
마지막 339 block에서 파일 내용이 끝나므로 마지막 block은 일부만 data가 채워져 있을 수도 있다.
즉 이 파일의 크기는
1024 X 2 < file_size <= 1024 X 3 이다.

3)Indexed Allocation

index block이 모든 포인터들을 모아둔다.

• random access 가능 ex.1025번째 access하고 싶다 --> 1024 + 1 : 2번째 블록으로 가면 되겠네
• Dynamic access without external fragmentation; overhead of index block
  index block이 하나로 안 되면, linked list로 만들어야
• file maximum size of 256K words and block size of 512 words
  block index 512 words, pointer 1 words --> 512 words block..?
  512 X 512 = 2^18 word = 256K words

Combined Scheme : UNIX

FCB 크기 정해져 있으므로 direct block pointer 뿐만 아니라 single indirect, double indirect도 사용한다.

Ex. Accessing the Block

Block size = 1024 bytes, 10 direct, indirect/double/triple 1
attribute 없다고 가정

• case1 : access byte offset 9000 of a file
  9000/1024 = 8.xx --> 8번째 block에 있겠다
  8번째 direct : block #367
  9000 - 1024 X 8 = 367
  8번째 block의 367번째로 가면 된다.

• case2 : access byte offset 350,000 of a file
  direct 영역 1024 X 10 = 10 X 2^10 = 10 KB
  single 영역
  
  1024/4 = 256 pointer
  256 X 1K = 256K
  10K ~ +256K
  double 영역 start : 10K + 256K = 272,384)
  350,000 - 272,384 = 77,616

Ex. Maximum File Size

Total size =

• (# of direct block pointer * block size)
• (# of block pointers in block * block size)
• (# of block pointers in one block)^2 * block size
• (# of block pointers in one block)^3 * block size

ex. Block size = 1024 bytes, pointer size = 4 bytes
10 direct, 1 indirect, 1 double, 1 triple
Maximum File size = (10 1K) + (1K/4 1K) + ((1K/4)^2 1K) + ((1K/4)^3 1024)

increasing block size ? pointer 개수 늘어남
adding one more indirection?
direct 없애고 single로 채우는 방법도