前言
??上篇文章介紹了文件的物理結(jié)構(gòu)并介紹了文件分配的三種方式——連續(xù)分配、鏈接分配和索引分配闽铐。
??本文介紹操作系統(tǒng)對(duì)文件存儲(chǔ)空間的管理蝶怔。
本文內(nèi)容
1 存儲(chǔ)空間的劃分與初始化
??存儲(chǔ)空間的劃分：將物理磁盤劃分為一個(gè)個(gè)文件卷（邏輯卷、邏輯盤）兄墅。
??在存儲(chǔ)空間初始化時(shí)踢星，需要將各個(gè)文件卷劃分為目錄區(qū)、文件區(qū)隙咸。
(1) 目錄區(qū)：主要存放文件目錄信息（FCB）沐悦、用于磁盤存儲(chǔ)空間管理的信息成洗。
(2) 文件區(qū)主要存放文件數(shù)據(jù)。
??有些系統(tǒng)支持超大型文件藏否，可支持由多個(gè)物理磁盤組成一個(gè)文件卷瓶殃。
2 存儲(chǔ)空間管理——空閑表法
??空閑表法：即用一張表記錄磁盤中空閑的盤塊★醯海空閑表的表項(xiàng)由空閑盤的起始?jí)K號(hào)和空閑盤塊數(shù)組成碌燕。如下圖所示
??如何分配磁盤塊：與內(nèi)存管理中的動(dòng)態(tài)分區(qū)分配類似，為一個(gè)文件分配連續(xù)的存儲(chǔ)空間继薛。同樣可以采用首次適應(yīng)算法修壕、最佳適應(yīng)算法、最壞適應(yīng)算法遏考，臨近適應(yīng)算法來(lái)決定要為文件分配哪些區(qū)間慈鸠。
??空閑表法適用于連續(xù)分配方式。
??例如灌具，如果新創(chuàng)建的文件請(qǐng)求3個(gè)塊青团，按照首次適用算法，從10號(hào)塊開(kāi)始有5個(gè)連續(xù)的塊可以滿足需求咖楣，所以把10督笆、11、12三個(gè)塊分配給文件诱贿，分配后的空閑盤塊表如下
??如何回收磁盤塊：與內(nèi)存管理中的動(dòng)態(tài)分配很類似娃肿，當(dāng)回收某個(gè)存儲(chǔ)區(qū)時(shí)需要分為四種情況
(1) 回收區(qū)前后都沒(méi)有相鄰空閑區(qū)——為空閑盤塊表增加一個(gè)表項(xiàng)即可。
(2 回收區(qū)前后都是空閑區(qū)——將回收區(qū)和回收區(qū)前后的兩個(gè)空閑區(qū)合并為一個(gè)空閑區(qū)珠十。
(3) 回收區(qū)前是空閑區(qū)——將回收區(qū)和前空閑合并為一個(gè)空閑區(qū)料扰。
(4) 回收區(qū)后是空閑區(qū)——將回收區(qū)和后空閑合并為一個(gè)空閑區(qū)。
??這里以回收區(qū)前后都是空閑區(qū)為例焙蹭，磁盤是第一幅圖的狀態(tài)晒杈，如果回收21、22號(hào)磁盤塊孔厉，那么回收后的空閑盤塊表如下圖所示拯钻。
??其他情況與之類似，回收時(shí)注意表項(xiàng)能合并的話就需要合并烟馅。
3 存儲(chǔ)空間管理——空閑鏈表法
??空閑鏈表法分為兩種：空閑盤塊鏈和空閑盤區(qū)鏈
(1) 空閑盤塊鏈：以盤塊為單位組成一條空閑鏈说庭。空閑盤塊中存儲(chǔ)著下一個(gè)空閑盤塊的指針郑趁。
(2) 空閑盤區(qū)鏈：以盤區(qū)為單位組成一條空閑鏈刊驴。每個(gè)空閑盤區(qū)中的第一個(gè)盤區(qū)記錄了盤區(qū)的長(zhǎng)度、下一個(gè)盤區(qū)的指針。
??下圖分別表示空閑盤塊鏈和空閑盤區(qū)鏈捆憎。
空閑盤區(qū)鏈中每個(gè)盤區(qū)中的第一個(gè)盤塊記錄了盤區(qū)長(zhǎng)度和指向下一個(gè)盤區(qū)的指針舅柜。如21、22躲惰、23號(hào)3個(gè)盤塊組成的盤區(qū)致份，21號(hào)盤塊中記錄了指向下一個(gè)盤區(qū)的指針（即指向6、7號(hào)盤塊組成的盤區(qū)的指針）和盤區(qū)的長(zhǎng)度3础拨，其他的盤塊類似氮块。
?? 3.1 空閑盤塊鏈
??操作系統(tǒng)保存著鏈頭、鏈尾指針诡宗。
??如何分配：如過(guò)某文件申請(qǐng)K個(gè)盤塊滔蝉，則從鏈頭開(kāi)始依次摘下K個(gè)盤塊分配，并修改空閑鏈的鏈頭指針塔沃。
??如何回收：回收的盤塊依次掛到鏈尾蝠引，并修改空閑鏈的鏈尾指針。
??下圖表示分配了3個(gè)盤塊
??下圖表示回收了3個(gè)盤塊
??從上面可以看出蛀柴，空閑盤塊法適用于離散分配的物理結(jié)構(gòu)螃概。為文件分配多個(gè)盤塊時(shí)可能要重復(fù)多次操作。
?? 3.1 空閑盤區(qū)鏈
??操作系統(tǒng)保存著鏈頭鸽疾、鏈尾指針吊洼。
??如何分配：若某文件申請(qǐng)K個(gè)盤塊，由于空閑盤區(qū)鏈將連續(xù)的盤塊組成一個(gè)盤區(qū)制肮，所以若某個(gè)盤區(qū)大小滿足可以實(shí)現(xiàn)一次分配融蹂，同樣可以采用首次適用、最佳適用等算法弄企，從鏈頭開(kāi)始檢索，按照一定的規(guī)則找到一個(gè)大小符合要求的空閑盤區(qū)分配給文件区拳。若沒(méi)有合適的連續(xù)空閑塊拘领，也可以將不同的盤區(qū)的盤同時(shí)分配給一個(gè)文件，同樣分配后也需要修改相應(yīng)的指針鏈和盤區(qū)大小等數(shù)據(jù)樱调。
??如何回收：若回收區(qū)和某個(gè)空閑盤區(qū)相鄰约素，則需要將回收區(qū)合并到空閑盤區(qū)中。若回收區(qū)沒(méi)有和任何空閑區(qū)相鄰笆凌，將回收區(qū)作為一個(gè)單獨(dú)的一個(gè)空閑盤區(qū)掛到鏈尾圣猎。同樣也需要修改鏈表指針和盤區(qū)大小等信息。
??下圖表示按照首次適用算法分配3個(gè)盤區(qū)
回收過(guò)程和空閑盤塊法的回收類似乞而，這里不再贅述送悔。
??從上面可以看出，空閑盤區(qū)鏈對(duì)離散分配、連續(xù)分配都適用欠啤。為一個(gè)文件分配多個(gè)盤塊時(shí)效率更高荚藻。
4 存儲(chǔ)空間管理——位示圖法
??位示圖：磁盤內(nèi)存被劃分為一個(gè)個(gè)磁盤塊，可以用二進(jìn)制位對(duì)應(yīng)一個(gè)盤塊洁段∮τ“0”代表盤塊空閑，“1”代表盤塊已分配祠丝。位示圖一般用連續(xù)的“字”來(lái)表示疾呻，下圖中一個(gè)字的字長(zhǎng)是16位，字中的每一位對(duì)應(yīng)一個(gè)盤塊写半。因此可以用（字號(hào)岸蜗，位號(hào)）對(duì)應(yīng)一個(gè)盤塊號(hào)。
注：字號(hào)和位號(hào)也可以從1開(kāi)始污朽，本例中都是從0開(kāi)始的散吵。
??如何實(shí)現(xiàn)盤塊號(hào)與（字號(hào)、位號(hào)）相互轉(zhuǎn)換：
（字號(hào)蟆肆，位號(hào)） = （i,j）的二進(jìn)制位對(duì)應(yīng)的盤塊號(hào) b = n*i + j.
b號(hào)盤塊對(duì)應(yīng)的字號(hào) i = b / n矾睦，位號(hào) j = b % n。
(1) ??（0,1）—> b = 16 * 0 + 1 = 1號(hào)塊炎功，從左側(cè)圖可以看出1號(hào)圖已分配枚冗，同時(shí)位示圖中（0,1）的二進(jìn)制位也是1表示已分配。
(2) ?? (1,10) —> b = 16 * 1 + 10 = 26號(hào)塊蛇损，從左側(cè)可以看出26號(hào)塊是未分配的赁温。
(3) ??b = 13 —> i = 13 / 16 = 0，j = 13 % 16 =13淤齐，對(duì)應(yīng)的（字號(hào)股囊，位號(hào)） = （0，13）更啄，從位示圖可以查出對(duì)應(yīng)的二進(jìn)制位為0稚疹，表示未分配。
??如何分配：若文件需要K個(gè)塊祭务，①順序掃描位示圖内狗，找到K個(gè)相鄰或不相鄰的“0”；②根據(jù)字號(hào)义锥、位號(hào)算出對(duì)應(yīng)的盤塊號(hào)柳沙，將相應(yīng)的盤塊分配給文件；③將相應(yīng)的位設(shè)置為“1”拌倍。
??如何回收：①根據(jù)回收的盤塊號(hào)計(jì)算出對(duì)應(yīng)的字號(hào)赂鲤、位號(hào)噪径；②將相應(yīng)的二進(jìn)制位設(shè)置為“0”。
??從上面可以看出：位示圖法對(duì)連續(xù)分配和離散分配都適用蛤袒。
5 存儲(chǔ)空間管理——成組鏈接法
??空閑表法熄云、空閑鏈表法不適用大型文件系統(tǒng)，因?yàn)榭臻e表或空閑聯(lián)泵钫妫可能過(guò)大缴允。UNIX系統(tǒng)中采用了成組鏈接法對(duì)磁盤空閑塊進(jìn)行管理。這是將上述兩種方法相結(jié)合的而形成的一種空閑管理方法珍德。
??文件卷的目錄區(qū)中專門用一個(gè)磁盤塊作為超級(jí)塊练般，當(dāng)系統(tǒng)啟動(dòng)時(shí)需要將超級(jí)塊讀入內(nèi)存。并且要保證與外存中的“超過(guò)塊”的數(shù)據(jù)一致锈候。
(1) 超級(jí)塊實(shí)際上是一個(gè)棧結(jié)構(gòu)薄料，用來(lái)存放當(dāng)前可用的一組空閑盤塊號(hào)（最多含100個(gè)號(hào)）以及棧中尚有空間的塊號(hào)數(shù)量N。
(2) 文件區(qū)中的所有空閑盤塊分為若干個(gè)組泵琳，假設(shè)所有空閑盤塊號(hào)是201~9999（實(shí)際中盤塊是不要求連續(xù)的摄职，不要求連續(xù)的，不要求連續(xù)的获列，這里是為了表述方便谷市，認(rèn)為空閑盤塊連續(xù)的），將這些盤塊進(jìn)行分組击孩，每組100個(gè)迫悠。
(3) 每一組含有的盤塊總數(shù)N和該組的所有盤號(hào)塊記入前一組的第一個(gè)盤塊中。這樣各組的第一個(gè)盤塊可以鏈成一條鏈巩梢。
(4) 如果是最后一組创泄，那么將前一個(gè)分組的第一個(gè)盤塊的中存放空閑盤塊鏈的結(jié)束標(biāo)志符，如“-1”表示下一組是最后一個(gè)分組了括蝠。
??內(nèi)存的分配過(guò)程：分配過(guò)程是從棧頂取出一空閑盤塊號(hào)鞠抑，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格忌警，若該盤塊號(hào)已是棧底（即第一個(gè)盤塊）碍拆，這是當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。由于在該盤塊號(hào)所對(duì)應(yīng)的盤塊中記有下一組可用的盤塊號(hào)慨蓝，因此，不能直接將它分配掉端幼，需要將它記錄的下一組信息保存下來(lái)礼烈，所以比須調(diào)用磁盤讀過(guò)程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中婆跑，作為新的盤塊號(hào)棧的內(nèi)容此熬，并把原棧底對(duì)應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。然后，再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū))犀忱。最后募谎，把棧中的空閑盤塊數(shù)減1 并返回。
??下面舉例說(shuō)明
??如果此時(shí)新建一個(gè)文件需要一個(gè)磁盤塊阴汇，那么此時(shí)第一組有100個(gè)空閑塊数冬，所以是足夠分配的，將棧頂?shù)谋P塊號(hào)即201號(hào)盤塊對(duì)應(yīng)的盤塊分配出去搀庶，如下圖
??如果此時(shí)又創(chuàng)建一個(gè)新的文件拐纱，需要99個(gè)磁盤塊，就需要將剩下的99個(gè)盤塊全部分配出去哥倔，但是此時(shí)300號(hào)盤塊記錄了下一組信息秸架，如果分配出去，信息就是丟失咆蒿，所以需要將300號(hào)盤塊從外存（磁盤）讀入內(nèi)存东抹，將300號(hào)盤塊記錄的信息，寫入空閑盤塊號(hào)棧沃测，然后才能將這99塊空閑塊分配出去缭黔。具體過(guò)程如下圖所示
??
??內(nèi)存的回收過(guò)程：在系統(tǒng)回收空閑盤塊時(shí)，須調(diào)用盤塊回收過(guò)程進(jìn)行回收芽突。它是將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部试浙，并執(zhí)行空閑盤塊數(shù)加 1 操作。當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá) 100 時(shí)寞蚌，表示棧已滿田巴，便將現(xiàn)有棧中的100 個(gè)盤塊號(hào)記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底挟秤。
??以分配的第一個(gè)圖為例壹哺，201盤塊被分配出去了，如果此刻有個(gè)文件被刪除了艘刚，其占用的盤塊是199號(hào)管宵，系統(tǒng)需要回收這個(gè)盤塊，發(fā)現(xiàn)此時(shí)空閑盤塊號(hào)棧中記錄空閑塊數(shù)為99攀甚，直接將盤塊號(hào)記錄棧頂箩朴，將空閑盤塊數(shù)加1即可。
??如果此時(shí)又有一個(gè)文件被刪除了秋度，其占用的盤塊是190炸庞，此時(shí)空閑盤塊號(hào)數(shù)已經(jīng)達(dá)到100了，就需要將現(xiàn)在空閑盤塊棧中信息記入新回收的塊中荚斯。
6 小結(jié)
