5. 파일 시스템

디스크의 특징

- 디스크는 제자리에서 재사용이 가능하다.

- 디스크는 정보 블록에 직접 접근이 가능하다.

블록 (Block) ?

- 데이터는 블록이라고 하는 대량의 바이트 단위로 디스크와 메모리 간에 전달된다.

- 일반적으로, 512바이트인 하나 이상의 섹션이 있다.

-> 이 블록들을 직접 다루려고하면? 매우 힘들것이다... 그래서 파일 시스템을 쓰자

파일 시스템을 이용하면, 데이터를 쉽게 저장, 검색 및 활용이 가능하다.

이 파일시스템은 어떻게 구현할까?

디렉토리 구현

-   Directory Block으로 구성됐다.

-   각각의 Directory Block은 Directory Entry(파일     또는 디렉토리의 이름과 데이터를 가리키는 포인터) 세트가     있다.

-   장점 : 구현하기 단순하다. 쉽다

-   단점 : 파일을 찾는데 선형탐색이 필요하다. 이는 일부

       성능저하를 일으킬 수 있음.

-   해결책 : 디렉토리 캐시 사용. 최근에 사용한 디렉토리를            캐시에 저장한다.

그렇다면, 디스크엔 파일을 어떻게 할당(Allocation)할까?

3가지 방법이 있다.

1. Contiguous Allocation

- 각 파일은 디스크의 블록을 연속적으로 차지한다.

- 파일은 첫 번째 블록의 주소와, 길이로 정의된다.

- 파일 블록이 b에서 시작하고, 길이가 n이면 -> 블록 b, b+1, b+2, ...... , b+n-1 을 

차지한다.

- 당연히 문제가 발생한다.. 바로 External Fragmentation 발생. 위 그림처럼 빈 공간이 발생해도,   큰 파일 생성되면 할당을 못한다. 

  또, 사용 패턴을 알 수 없다. 응용 프로그램은 필요에 따라 블록을 추가로 생성하기 때문에, 모자라면 

큰일!

- 그래서 연속적으로 할당하는것 말고, 다른 방법을 찾았다.

2. Linked Allocation

- 앞의 할당이 배열이라면, 이건 마치 연결리스트이다.

- 각 파일은 디스크 블록의 링크된 목록이다.

- 디스크 블록은 더이상 연결되어있지 않고, 

어디에나 흩어져있다.

- 각 디렉토리 항목에는 start, end 포인터가 

있다.

- 이것도 역시 문제가 발생

- 만약 해당 파일의 블록에서 i번째 블록이 

필요한데, 처음부터 순차적으로 다 봐야한다.

  오버헤드가 크게 발생한다.!

3. Linked Allocation - FAT

- 테이블은 일련의 항목이다.

- 블록 번호에 의해 색인된다.

- 파일의 다음 블록 번호를 포함

- 사용되지 않는 블록은 0으로 표시

- FAT16 : 엔트리 크기가 16비트

  FAT32 : 엔트리 크기가 32비트

- 역시 검색의 오버헤드 발생.

- 해결책은? cache

4. Indexed Allocation

- 직접 파일 접근, 혹은 임의의 파일 접근 문제를 

해결한다.

- 즉, 순서대로 안가고 원하는 부분 쏙 

읽을 수 있다. (Linked에서 못한거)

- 모든 포인터를 Index Block에 모은다.

- Index Block?

디스크 블록 주소의 배열

인덱스 블록의 i번째 항목은 파일의 i번째 항목을 가리킨다.

역시 또 문제발생한다.

pointer overhead

파일은 수천개의 블록이 있을수도 ...

그러면, 모든 인덱스 블록에 포인터 할당해야하는데 오바임

Index Block 관리 기술

1. Linked Scheme

                                                                                   

그림처럼 파일이 커지면 다른블록이랑 연결시킴

2. Multilevel index

첫 번째 블록은 두 번째 블록 가리키고, 두 번째 블록은 실제 파일 데이터 블록을 가리킴

이런거 이번 하반기 NHN 필기시험에 나왔던거같은데,,

3. Combined Scheme

- 위에것들 합친거같다.

- 총 15개의 Index Block이 있다.

- 처음 12개는 직접 블록(Direct Block)

으로, 실제 데이터를 직접 가리킴

- 그 다음 3개는 간접 블록(Indirect     Block), 다단계 색인과 동일