파일 시스템(File system) - 3. File Structure

파일 시스템(File system) - 3. File Structure

1. Data Access Patterns within File

1) sequential access

2) random access

3) keyed access

2. Issue of File Structures

1) Most files are small.

2) Much of the disk is allocated to large files

3) Many of the I/O operations are made to large files.

large file들에 대해 좋은 성능을 낼 수 있어야함

각각의 파일을 유지하는데 적은 비용이 들어야함

그래서 파일 구조에 

1) Linked Files

2) Indexed Files

2가지의 형태를 제안하게 됨.

3. Linked files & Indexed Files

1) linked files

: fd에 파일의 시작 주소가 담겨져 있고, 각 블록마다 다음 블록에 대한 주소 값이 있음.

파일 접근 패턴에서의 관점

- sequential access에서는 문제 없음

- random access에서는 문제 발생, 처음 주소부터 접근해야 해당 위치로 갈 수 있음

성능상 저하가 발생함.

공간 할당에서의 관점

- 초기에 연속된 블록들의 공간을 할당하면, fragmentation문제 발생.

- 연속되지 않은 블록들로 할당하면 문제해결.

- 공간할당에서는 문제점 없음

결론

파일시스템에서의 주요한 2가지 읽기 패턴에서

random access를 지원하지 못하므로 부적절함.

2) Indexed files

: fd내부에 block주소들을 가르키는 array가 존재하는 형태

파일 접근 패턴에서의 관점

- sequential access에서도 array를 순차적으로 접근하면 됨. 문제 없음

- random access에서 해당 인덱스에 해당하는 블록으로 바로 접근 가능함 문제 없음.

공간 할당에서의 관점

- fd는 크기가 고정되어 있으므로 array의 크기가 제한적임

- 즉 array의 개수만큼 block 주소를 가르킬 수 있으므로, 파일 크기에 대한 제한이 있게됨

- 이 문제를 해결하기 위해서 data block을 바로 가르키는 것이 아니라 또 다른 array 주소를 가르킴으로써 계층적으로 array를 구성함

- 파일 크기에 제한을 벗어나게 됨.

- 그러나 이러한 계층적 구조는 탐색을 여러번함으로써 성능상의 문제를 야기할 수 있게되는 단점이 발생함.

- 메인메모리에 cache된다면 크게 문제가 되지 않음.

4. 관련된 메카니즘

1) Buffer Cache

최근에 사용된 블록들을 메인 메모리에 임시로 보관해둠.

메모리 관리기법으로써 LRU알고리즘을 사용하게 됨.

매번 디스크를 접근하는 매우 느린연산을 보완하기 위한 기법임.

2) bitmap을 이용한 디스크의 Free block관리

블록마다 하나의 bit가 block이 사용중인지 아닌지 나타내는 Array

hw/sw string search기법을 사용해서 연속적인 사용가능한 블록을 쉽게 찾아 낼 수 있음

예를 들어 여섯개의 free block이 필요하다면, bitmap에서 111111 이라는 string을 탐색하면 됨.