블록할당 3가지방법

• 연속할당(contiguous allocation): p378(11.15)
» 디스크 탐구시간(seek time)이 최소
» 순차접근과 직접접근 모두
» 동적 기억장치 할당
» 외부단편 문제
» 파일 크기 결정(preallocation) 문제
-> extent(다른 연속할당 덩어리)로 연결
파일의 블록주소 : <시작위치, 블록 개수, 다음 extent로 link)

• 연결 할당(linked allocation): p380(11.16)
» 디스크 블록의 연결 리스트 구성
» 외부 단편 없음
» 파일 커져도 문제 없음
» pointer space overhead -> block들의 clusters로 보완
» 신뢰성 떨어짐 -> doubly linked list로 보완
» 직접 접근이 비효율적
» (예) FAT(File Allocation Table): p382(11.17) MS-DOS, OS/2각
• 각 partition 시작 부분에
• 테이블의 각 항복
: <블록 번호, 파일에서의 다음 블록 번호>
• 잦은 참조로 인해 caching 해야 함

• 색인 할당(indexed allocation) : p383(11.18)
» 각 파일에 색인 블록(index block): paging과 유사
» 직접접근 가능
» 색인 블록의 memory overhead
» 색인 블록의 구현
• 연결 체계(linked scheme) : 다음 색인 블록으로 연결
• 다중레벨 색인 (multilevel index) : 간접 색인
(예) 블록크기: 4096 bytes = 1024 항목 x 4 bytes pointers
2-level indexing 경우 최대 블록 개수: 1024 x 1024
파일 최대 크기:1024 x 1024 x 4K = 4G
• 혼합 체계 (combined scheme) : BSD Unix , p411(11.7)
12 direct blocks: 불록주소 = ~48K (4K x 12)
3 indirect blocks:
» single indirect blocks: ~ 4M (1024 x 4K)
» double indirect blocks: ~ 4G (1024 x 1024 x 4K)
» triple indirect blocks: 실제 사용 않음
Q: 한 파일의 최대 블록 수?
Q: 한 파일의 최대 크기?
• 성능
» 연속(직접 접근) + 연결(순차 접근)
» 연속(작은 파일) + 색인(큰 파일)