作業系統›Ch10 檔案管理第 3 題／共 28 題
3. File Allocation、Contiguous Allocation、Linked Allocation、Indexed Allocation
#OS-10-003中File AllocationContiguous AllocationLinked AllocationIndexed Allocation
關於檔案配置（file allocation），block 大小為 4,096 bytes，指向一個 block 的指標（pointer）大小為 8 bytes。我們要把一個 N-byte 的檔案配置到無限大的磁碟空間，且不允許使用 file allocation table。
- Contiguous allocation 為此檔案配置 W 個 blocks。
- Linked allocation（不使用 clustering）為此檔案配置 X 個 blocks 及對應的指標。
- Linked allocation（使用 clustering，以 2 個 blocks 為一個 cluster）為此檔案配置 Y 個 blocks 及對應的指標。
- Indexed allocation（其中 index 本身使用不做 clustering 的 linked allocation）為此檔案配置 Z 個 blocks 及對應的指標。
請選出正確的敘述。
參考答案與解析
答案 (D)(E)。設block=4096bytes、pointer=8bytes。N→∞時：W≈N/4096（contiguous無額外開銷）；X≈N/4088（linked每block扣8bytes做next指標）；Y（clustering，2 blocks/cluster，每cluster僅1個指標）≈N/4092；Z（indexed，index本身用linked串接，每個index block可存(4096-8)/8=511個data指標）≈N/4096×(512/511)。代數化簡：W/X→(4096-8)/4096=511/512（不是選項(A)的512/513）；W/Y→(8192-8)/8192=1023/1024（不是選項(B)的1024/1025）；W/Z→511/512（同(A)一樣的511/512，不是選項(C)的512/513）；X/N→1/4088，Y/N→1/4092，因4088<4092，X>Y成立，(D)對；X/N與Z/N代入精確代數可證明兩者完全相等（1/(B-P)=512/(511B)在B=4096,P=8時剛好成立，因為512×8=4096=B），故X=Z，(E)對。
📄 台大115
▤完整推導請見《WH 資工筆記 · 作業系統》Ch10 檔案管理