《計算機(jī)操作系統(tǒng) 》課件-6.4文件存儲空間管理

文件存儲空間管理是設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來記錄存儲空間的使用情況，并提供對存儲空間進(jìn)行分配和回收的方法?？臻e表法

空閑塊鏈表法位示圖

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

1.空閑表法

文件系統(tǒng)為外存上的所有空閑分區(qū)建立一張空閑表，每個空閑區(qū)占一個表項(xiàng)，包括序號、該空閑區(qū)的起始盤塊號以及空閑盤塊數(shù)等信息，再將所有空閑區(qū)按其起始盤塊號遞增的次序排列6.4文件存儲空間管理分配和回收方法類似于內(nèi)存的動態(tài)分區(qū)分配和回收

2.空閑塊鏈表法（1）空閑盤塊鏈：磁盤的每一個空閑盤塊中存放一個指針，指向另一個空閑盤塊，這樣磁盤上的所有空閑塊鏈接在一起形成一個鏈表。6.4文件存儲空間管理（2）空閑盤區(qū)鏈：每個空閑盤區(qū)包含若干個連續(xù)的空閑盤塊

分區(qū)序號、起始塊號、盤塊數(shù)等

位示圖法

利用一位二進(jìn)制位來表示磁盤中一個盤塊的使用情況。當(dāng)其值為“0”時，表示對應(yīng)的盤塊空閑；為“1”時，表示已分配。磁盤上的每個盤塊都有一個二進(jìn)制位與之對應(yīng)，所有盤塊的二進(jìn)制位構(gòu)成的集合稱為位示圖。6.4文件存儲空間管理

位示圖法

（1）盤塊的分配：i，j，b從1開始計數(shù)6.4文件存儲空間管理

順序掃描位示圖，從中找出一個或一組其值為“0”的二進(jìn)制位(“0”表示空閑時)。將所找到的一個或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位，位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算：b=n(i-1)+j式中，n代表每行的位數(shù)，i，j，b從1開始計數(shù)。

修改位示圖，令map［i,j］=1。

位示圖法

（2）盤塊的回收：i，j，b從1開始計數(shù)6.4文件存儲空間管理

將回收盤塊的盤塊號b轉(zhuǎn)換成位示圖中的行號i和列號j。轉(zhuǎn)換公式為：

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

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

成組鏈接法

例如一磁盤有512塊，編號為0?！?11＃，其中8＃～499＃是空閑盤塊。

（1）空閑盤塊的組織

把所有空閑磁盤塊按照固定數(shù)量分成若干組。若每組100塊，從后往前分組，則分組情況是：最末組為99塊：499～401；其余每組100塊，分別為：

400～301；300～201；200～101；100～86.4文件存儲空間管理

成組鏈接法

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

成組鏈接法

例如一磁盤有512塊，編號為0?！?11＃，其中8?！?99＃是空閑盤塊。

（2）空閑盤塊的鏈接將每組（第1組除外）的總塊數(shù)及相應(yīng)的塊號記錄在前一組的最末塊中對第1組，其總塊數(shù)和各塊塊號記錄在空閑盤塊棧中，放在超級塊里。

系統(tǒng)啟動后，將超級塊復(fù)制到主存中，并建立空閑盤塊號棧，棧頂指針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組超級塊（3）空閑盤塊的分配針對空閑盤塊棧進(jìn)行。

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;} }空閑盤塊棧93899899100…S_Free空閑盤塊棧1100S_Free100200…199198102101空閑盤塊棧100200S_Free…1991981021016.4文件存儲空間管理成組鏈接法（4）空閑盤塊的回收：針對空閑盤塊棧進(jìn)行。

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_F