操作系統(tǒng)實(shí)驗(yàn)6_磁盤存儲(chǔ)空間管理

1、實(shí)驗(yàn)五磁盤存儲(chǔ)空間管理一、實(shí)驗(yàn)內(nèi)容模擬磁盤空閑空間的表示方法，以及模擬實(shí)現(xiàn)磁盤空間的分配和回收。二、實(shí)驗(yàn)?zāi)康拇疟P初始化時(shí)把磁盤存儲(chǔ)空間分成許多塊扇區(qū)，這些空間可以被多個(gè)用戶共享。用戶作業(yè)在執(zhí)行期間常常要在磁盤上建立文件或把已經(jīng)建立在磁盤上的文件刪去，這就涉及到磁盤存儲(chǔ)空間的分配和回 收。一個(gè)文件存放到磁盤上，可以組織成順序文件連續(xù)文件、鏈接文件串聯(lián)文件、索引文件等，因此，磁盤存儲(chǔ)空間的分配有兩種方式，一種是分配連續(xù)的存儲(chǔ)空間，另一種是可以分配不連續(xù)的存儲(chǔ)空間。怎樣有效地管理磁盤存儲(chǔ)空間是操作系統(tǒng)應(yīng)解決的一個(gè)重要問(wèn)題，通過(guò)本實(shí)驗(yàn)使學(xué)生掌握磁盤存儲(chǔ)空間的 分配和回收算法。三、實(shí)驗(yàn)題目本實(shí)驗(yàn)?zāi)M三種

2、磁盤存儲(chǔ)空間的管理方法。第一題：連續(xù)的磁盤存儲(chǔ)空間的分配和回收。提示:(1) 要在磁盤上建立順序文件時(shí)，必須把按序排列的邏輯記錄依次存放在磁盤的連續(xù)存儲(chǔ)空間中?？?假定磁盤初始化時(shí)，已把磁盤存儲(chǔ)空間劃分成假設(shè)干等長(zhǎng)的塊扇區(qū)，按柱面號(hào)和盤面號(hào)的順序給每一塊確定一個(gè)編號(hào)。隨著文件的建立、刪除、磁盤存儲(chǔ)空間被分成許多區(qū)每一區(qū)包含假設(shè)干塊，有的區(qū)存放著文件，而有的區(qū)是空閑的。當(dāng)要建立順序文件時(shí)必須找到一個(gè)適宜的空閑區(qū)來(lái)存放文件記錄，當(dāng)一 個(gè)文件被刪除時(shí)，那么該文件占用的區(qū)應(yīng)成為空閑區(qū)。為此可用一張空閑區(qū)表來(lái)記錄磁盤存儲(chǔ)空間中尚未占 用的局部，格式如下：序號(hào)起始空閑塊號(hào)空閑塊個(gè)數(shù)狀態(tài)156未分配2143

3、未分配32130未分配4空表目(2) 要建立文件時(shí)，先查找空閑區(qū)表，從狀態(tài)為“未分配的登記欄目中找出一個(gè)塊數(shù)能滿足要求的 區(qū)，由起始空閑塊號(hào)能依次推得可使用的其它塊號(hào)。假設(shè)不需要占用該區(qū)的所有塊時(shí)，那么剩余的塊仍應(yīng)為 未分配的空閑塊，這時(shí)要修改起始空閑塊號(hào)和空閑塊數(shù)。假設(shè)占用了該區(qū)的所有塊，那么相應(yīng)登記欄中的狀 態(tài)修改成“空表目。刪除一個(gè)文件時(shí)，從空閑區(qū)表中找一個(gè)狀態(tài)為“空表目的登記欄目，把歸還的起 始?jí)K號(hào)和塊數(shù)填入對(duì)應(yīng)的位置。磁盤存儲(chǔ)空間的分配和回收算法類似于主存儲(chǔ)器的可變分區(qū)方式的分配和回收。同學(xué)們可參考實(shí)驗(yàn)四的第一題。(3) 當(dāng)找到空閑塊后，必須啟動(dòng)磁盤把信息存放到指定的塊中，啟動(dòng)磁盤必

4、須給出由三個(gè)參數(shù)組成的 物理地址：柱面號(hào)、磁道號(hào)和物理記錄號(hào)。故必須把找到的空閑塊號(hào)換算成磁盤的物理地址。為了減少移臂次數(shù)，磁盤上的信息按柱面上各磁道順序存放。現(xiàn)假定一個(gè)盤組共有200個(gè)柱面，編號(hào)0-199每個(gè)柱面有20個(gè)磁道編號(hào)0-19，同一柱面上的各磁道分布在各盤面上，故磁道號(hào)即盤面號(hào)。，每個(gè)磁道被分成等長(zhǎng)的6個(gè)物理記錄編號(hào) 0-5，每個(gè)盤面被分成假設(shè)干個(gè)扇區(qū)，故每個(gè)磁道上的物理記空閑塊號(hào) 錄號(hào)即為對(duì)應(yīng)的扇區(qū)號(hào)。那么，空閑塊號(hào)與磁盤物理地址的對(duì)應(yīng)關(guān)系如下：假設(shè)M=空閑塊號(hào)，m=6 那么物理記錄號(hào) =m 磁道號(hào)= M 柱面號(hào)=M 20(4) 刪除一個(gè)文件時(shí)，從文件目錄表中可得到該文件在磁盤上

5、的起始地址和邏輯記錄個(gè)數(shù)，假定每個(gè)邏輯記錄占磁盤上的一塊，那么可推算出歸還后的起始空閑塊號(hào)和塊數(shù)，登記到空閑區(qū)表中。 換算關(guān)系如下：起始空閑塊號(hào)=柱面號(hào)20+磁道號(hào)6+物理記錄號(hào)空閑塊數(shù)=邏輯記錄數(shù)(5) 請(qǐng)?jiān)O(shè)計(jì)磁盤存儲(chǔ)空間的分配和回收程序，要求把分配到的空閑塊轉(zhuǎn)換成磁盤物理地址，把歸還的 磁盤空間轉(zhuǎn)換成空閑塊號(hào)。假定空閑區(qū)表的初值如提示1中指出，現(xiàn)有一文件要占用10塊，運(yùn)行你所設(shè)計(jì)的分配程序，顯示或打印分配后的空閑區(qū)表以及分配到的磁盤空間的起始物理地址。然后，有一文件被刪除，它占用的磁盤 空間為：1號(hào)柱面2號(hào)磁道，0號(hào)物理記錄開(kāi)始的 4塊，運(yùn)行你所設(shè)計(jì)的回收程序，顯示或打印回收后的 空閑區(qū)表

6、。第二題：用位示圖管理磁盤存儲(chǔ)空間提示:(1) 為了提高磁盤存儲(chǔ)空間的利用率，可在磁盤上組織成鏈接文件、索引文件，這類文件可以把邏輯 記錄存放在不連續(xù)的存儲(chǔ)空間。為了表示哪些磁盤空間已被占用，哪些磁盤空間是空閑的，可用位示圖來(lái)指出。位示圖由假設(shè)干字節(jié)構(gòu)成，每一位與磁盤上的一塊對(duì)應(yīng)，“1 狀態(tài)表示相應(yīng)塊已占用，“ 0 狀態(tài)表示該塊為空閑。位示圖的形式與實(shí)驗(yàn)四中的位示圖一樣，但要注意，對(duì)于主存儲(chǔ)空間和磁盤存儲(chǔ)空間應(yīng)該 用不同的位示圖來(lái)管理，絕不可混用。(2) 申請(qǐng)一塊磁盤空間時(shí)，由分配程序查位示圖，找出一個(gè)為“0的位，計(jì)算出這一位對(duì)應(yīng)塊的磁盤物理地址，且把該位置成占用狀態(tài)“ 1 。假設(shè)現(xiàn)在有一個(gè)盤

7、組共 80個(gè)柱面，每個(gè)柱面有兩個(gè)磁道，每個(gè) 磁道分成4個(gè)物理記錄。那么，當(dāng)在位示圖中找到某一字節(jié)的某一位為“0時(shí)，這個(gè)空閑塊對(duì)應(yīng)的磁盤物理地址為：柱面號(hào)=字節(jié)號(hào)磁道號(hào)=位數(shù) 4物理記錄號(hào)=位數(shù)4(3) 歸還一塊磁盤空間時(shí)，由回收程序根據(jù)歸還的磁盤物理地址計(jì)算出歸還塊在位示圖中的對(duì)應(yīng)位， 把該位置成“ 0。按照2中假設(shè)的盤組，歸還塊在位示圖中的位置計(jì)算如下：字節(jié)號(hào)=柱面號(hào)位數(shù)=磁道號(hào)4+物理記錄號(hào)(4) 設(shè)計(jì)申請(qǐng)一塊磁盤空間和歸還一塊磁盤空間的程序。要求能顯示或打印程序運(yùn)行前和運(yùn)行后的位 示圖；分配時(shí)把分配到的磁盤空間的物理地址顯示或打印出來(lái)，歸還時(shí)把歸還塊對(duì)應(yīng)于位示圖的字節(jié)號(hào)和 位數(shù)顯示或打印

8、出來(lái)。(5) 假定已有如表6-1的磁盤空間被占用了，現(xiàn)在要申請(qǐng)五塊磁盤空間，運(yùn)行分配程序，按4中要求顯示或打印運(yùn)行的結(jié)果。然后再歸還如表6-2的空間，運(yùn)行回收程序，按4中的要求顯示或打印運(yùn)行結(jié)果。表6-1柱面號(hào)磁道號(hào)物理記錄號(hào)001002010013100112柱面號(hào)磁道號(hào)物理記錄號(hào)002010101第三題：模擬 UNIX系統(tǒng)的空閑塊成組鏈接法，實(shí)現(xiàn)磁盤存儲(chǔ)空間的管理。提示:(1) 假定磁盤存儲(chǔ)空間已被劃分成長(zhǎng)度為n的等長(zhǎng)塊，共有 M塊可供使用。UNIX系統(tǒng)中采用空閑塊成組鏈接的方法 來(lái)管理磁盤存儲(chǔ)空間，將磁盤中的每N個(gè)空閑塊N<M丨分成一組，最后一組可以缺乏N塊，每組的第一塊中登記了下

9、一組空閑塊的塊數(shù)和塊號(hào)，第一組的塊數(shù)和塊號(hào)登記在專用塊中，登記的 格式如下：當(dāng)?shù)谝豁?xiàng)內(nèi)容為“ 0時(shí)，那么第二項(xiàng)起指出的空閑塊是最后一組。(2) 現(xiàn)模擬UNIX系統(tǒng)的空閑塊成組鏈接，假定共有8塊可供使用，每3塊為一組，那么空閑塊成組鏈接的初始狀態(tài)為：開(kāi)始時(shí)，空閑塊號(hào)是順序排列的，但經(jīng)假設(shè)干次的分配和歸還操作后，空閑塊的鏈接就未必按序排列了。用二維數(shù)組 A : array 0M-1 of array 0n-1來(lái)模擬管理磁盤空間，用Ai表示第I塊，第0塊A0作為專用塊。(3) 成組鏈接的分組情況記錄在磁盤物理塊中，為了查找鏈接情況，必須把它們讀入主存，故當(dāng)磁盤初始化后，系統(tǒng)先將專用塊內(nèi)容復(fù)制到主存中

10、。定義一個(gè)數(shù)組MA存放專用塊內(nèi)容，即MA: =A0。申請(qǐng)一塊磁盤空間時(shí)，查 MA，從中找出空閑塊號(hào)，當(dāng)一組的空閑塊只剩第一塊時(shí)，那么應(yīng)把該塊中指出的下一 組的空閑塊數(shù)和塊號(hào)復(fù)制到專用塊中，然后把該塊分配給申請(qǐng)者。當(dāng)一組的空閑塊分配完后那么把專用塊內(nèi)容下一組鏈接情況復(fù)制到主存，再為申請(qǐng)者分配。分配算法如圖6-1。圖6-1采用成組鏈接的分配算法(4) 歸還一塊時(shí)給出歸還的塊號(hào)，叵當(dāng)前組不滿規(guī)定塊數(shù)時(shí)，將歸還塊登記入該組；假設(shè)當(dāng)前組已滿， 那么另建一新組，這時(shí)歸還塊作為新一組的第一塊，應(yīng)把主存中登記的一組鏈接情況MA復(fù)制到歸還塊中,然后在MA重新登記一個(gè)新組。歸還一塊的算法如圖6-2。圖6-2采用成組鏈接的回收算法(5) 設(shè)計(jì)分配和歸還磁盤空間的程序，能顯示或打印分配的磁盤空間的塊號(hào)，在完成一次分配或歸還后能顯示或打印各空閑塊組的情況各組的空閑塊數(shù)和塊號(hào)。本實(shí)驗(yàn)省去了塊號(hào)與物理地址之間的轉(zhuǎn)換工作，而在實(shí)際的系統(tǒng)中必須進(jìn)行塊號(hào)與物理地址的轉(zhuǎn)換工作。(6) 運(yùn)行你所設(shè)計(jì)的程序，假定空閑塊鏈接的初始狀態(tài)如提示2，現(xiàn)先分配4塊，再依次歸還第 2塊和第6塊。把執(zhí)行后分配到的塊號(hào)依次顯示或打印出來(lái)，且顯示或打印空閑塊組的情況。在上次執(zhí)行的根底上繼續(xù)分配