計算機操作系統(tǒng)（第二版）課件：文件存儲空間管理

解決問題：當(dāng)你創(chuàng)建文件時，系統(tǒng)如何在磁盤上為你的文件分配所需要的磁盤空間？當(dāng)你刪除文件時，系統(tǒng)如何回收文件所占據(jù)的磁盤空間？文件存儲空間管理：數(shù)據(jù)結(jié)構(gòu)、分配和回收方法空閑表法

空閑塊鏈表法位示圖

成組鏈接法

文件存儲空間管理實際上FAT表也可以管理磁盤存儲空間1、分析空閑表法的概念、分配與回收算法、性能優(yōu)缺點（簡單不討論）2、分析空閑盤塊鏈表法的概念、分配與回收算法、性能優(yōu)缺點3、位示圖：1）分析說明位示圖的概念2）分析說明分配磁盤塊算法3）分析說明回收磁盤塊算法4）分析性能特點，可以進(jìn)一步改進(jìn)性能嗎？4、成組鏈接法（引導(dǎo)講授）6.4文件存儲空間管理

1.空閑表法（方便連續(xù)分配）表項：序號、該空閑區(qū)的起始盤塊號、空閑盤塊數(shù)所有空閑區(qū)按起始盤塊號遞增的次序排列6.4文件存儲空間管理分配和回收方法類似于內(nèi)存的動態(tài)分區(qū)分配和回收如果要為某個文件分配10個塊，系統(tǒng)會從哪一個空閑分區(qū)中分配？如果刪除某文件，它所占用的磁盤空間是9-12塊，則回收后的結(jié)果是怎樣的？

2.空閑塊鏈表法（方便離散分配）（1）空閑盤塊鏈：每個空閑盤塊中存放一個指針，指向下一個空閑盤塊6.4文件存儲空間管理（2）空閑盤區(qū)鏈：每個空閑盤區(qū)包含若干個連續(xù)的空閑盤塊

分區(qū)序號、起始塊號、盤塊數(shù)等刪除文件時，如何回收磁盤塊呢？回收到鏈?zhǔn)走€是鏈尾？這種方法在分配和回收磁盤空間時，效率是高還是低？如何為文件分配一個磁盤塊？3.位示圖法：Linux

（1）位示圖概念：空閑已分配6.4文件存儲空間管理如何為文件分配一個磁盤塊？如何回收一個磁盤塊？

位示圖法（2）盤塊的分配：假設(shè)i，j，b從1開始計數(shù)6.4文件存儲空間管理

順序掃描位示圖，找出一個值為“0”的二進(jìn)制位（i，j）

將找到的二進(jìn)制位（i，j）b=n(i-1)+j修改位示圖，map［i,j］=1。

（3）盤塊的回收：

將盤塊號b轉(zhuǎn)換成位示圖中（i，j）：

i=(b-1)DIVn+1j=(b-1)MODn+1

修改位示圖：map［i,j］=0

某文件管理系統(tǒng)在磁盤上建立了位示圖(bitmap)，記錄磁盤的使用情況。若磁盤上的物理塊依次編號為：0、1、2、…，系統(tǒng)中字長為32位，每一位對應(yīng)文件存儲器上的一個物理塊，取值0和1分別表示空閑和占用，如下圖所示。129130131132ABCD提交假設(shè)將4195號物理塊分配給某文件，那么該物理塊的使用情況在位示圖中的（）字中描述0單選題10分某文件管理系統(tǒng)在磁盤上建立了位示圖(bitmap)，記錄磁盤的使用情況。若磁盤上的物理塊依次編號為：0、1、2、…，系統(tǒng)中字長為32位，每一位對應(yīng)文件存儲器上的一個物理塊，取值0和1分別表示空閑和占用，如下圖所示。第3位置“0”第3位置“1”第4位置“0”第4位置“1”ABCD提交假設(shè)將4195號物理塊分配給某文件，那么系統(tǒng)應(yīng)該將該物理塊所在字的（）。（從第1位開始計數(shù)）0單選題10分一個系統(tǒng)某時刻位示圖如下圖所示，若要給文件f1分配一個塊，塊號從1開始計數(shù)，則該文件分到的塊號為（）34355455ABCD提交單選題10分4.成組鏈接法：Unix（1）空閑盤塊的組織

對所有空閑盤塊分組：

例如一磁盤有512塊，編號為0?！?11＃，其中8?！?99＃是空閑盤塊。每組100塊，從后往前分組，則分組情況是：最末組為99塊：499～401；其余每組100塊，分別為：

400～301；300～201；200～101；100～8.

6.4文件存儲空間管理成組鏈接法

（1）空閑盤塊的組織6.4文件存儲空間管理498…402499最末組40199塊399398…302400第4組301100塊299298…202300第3組201100塊199198…102200第2組101100塊99…9100第1組893塊4.成組鏈接法（1）空閑盤塊的組織

空閑盤塊的鏈接：

①從第2組開始，每組的總塊數(shù)及空閑塊號記錄在前一組的最末塊中②對第1組，其總塊數(shù)和各塊塊號記錄在空閑盤塊棧中，放在超級塊里。系統(tǒng)啟動后，主存中建立空閑盤塊號棧：

棧頂指針S_Free=第1組總塊數(shù)。6.4文件存儲空間管理498…402499最末組401399398…302第4組301299298…202第3組201199198…102第2組10199…9第1組8100101102198199200…100201202298299300…200號塊100301302398399400…300號塊1004014024984990…400號塊100號塊93899899100…S_Free空閑盤塊棧第5組超級塊組長塊卷資源結(jié)束標(biāo)記

count=當(dāng)前組空閑盤塊總數(shù)；

S_Free--；

b=*S_Free; if(count＞1）then {count--; returnb;} elseif(count==1)then {if(b==0)then

拒絕分配，返回0；

else {將b中內(nèi)容讀入空閑盤塊棧；

count=當(dāng)前組空閑盤塊總數(shù)；

S_Free=count；

returnb;} }空閑盤塊棧6.4文件存儲空間管理成組鏈接法（3）空閑盤塊的分配：針對空閑盤塊棧進(jìn)行93899899100…S_Free9299899100…S_Free分配8#塊后的空閑盤塊棧

count=當(dāng)前組空閑盤塊總數(shù)；

S_Free--；

b=*S_Free; if(count＞1）then {count--; returnb;} elseif(count==1)then {if(b==0)then

拒絕分配，返回0；

else {將b中內(nèi)容讀入空閑盤塊棧；

count=當(dāng)前組空閑盤塊總數(shù)；

S_Free=count；

returnb;} }空閑盤塊棧100200…199198102101空閑盤塊棧100200S_Free…1991981021016.4文件存儲空間管理成組鏈接法（3）空閑盤塊的分配：針對空閑盤塊棧進(jìn)行S_Free93899899100…1100100#塊內(nèi)容分配給文件

count=當(dāng)前組空閑盤塊總數(shù)；

b:回收塊號；（如回收50、60號塊）

if（count＜100)then {*S_Free=b; count++; S_Free++; return;} elseif(count==100)then {將空閑盤塊棧內(nèi)容寫入b中；

count=1；

S_Free=0； *S_Free=b; S_Free++; return;}S_Free99200…199198102空閑盤塊?！?010060號塊100200…19919810250空閑盤塊棧160S_Free6.4文件存儲空間管理成組鏈接法（4）空閑盤塊的分配：針對空閑盤塊棧進(jìn)行回收50#塊回收60#塊某文件系統(tǒng)采用成組鏈接法管理磁盤空間。系統(tǒng)共有1000個磁盤塊，盤塊號為0-999，其中104-999是空閑塊，每一組為100個塊。請完成以下問題：（1）畫出此時空閑盤塊棧的內(nèi)容。（2）現(xiàn)有一個進(jìn)程要釋放5個物理塊，其塊號為：90、80、100、101、85，畫出回收完成后空閑盤塊棧內(nèi)容。（3）在（2）的基礎(chǔ)上假定一個進(jìn)程要求分配8個空閑塊，畫出分配后的空閑盤塊棧，給出依次分配的盤塊號。課堂小組討論（8分鐘）空閑盤塊棧

97200…199198106105104

210185