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), 다단계 색인과 동일