一、實(shí)驗(yàn)內(nèi)容
利用高級(jí)語言，實(shí)現(xiàn)存儲(chǔ)分配算法，開發(fā)一個(gè)存儲(chǔ)管理的模擬程序,對(duì)內(nèi)存空間的管理和分配。內(nèi)存空間的管理可采用固定分區(qū)管理方式，可變分區(qū)管理方式,頁(yè)式存儲(chǔ)管理，段式存儲(chǔ)管理等方案。
二、實(shí)驗(yàn)?zāi)康?/span>
一個(gè)好的計(jì)算機(jī)系統(tǒng)不僅要有一個(gè)足夠容量的、存取速度高的、穩(wěn)定可靠的主存儲(chǔ)器，而且要能合理地分配和使用這些存儲(chǔ)空間。當(dāng)用戶提出申請(qǐng)存儲(chǔ)器空間時(shí)，存儲(chǔ)管理必須根據(jù)申請(qǐng)者的要求，按一定的策略分析主存空間的使用情況，找出足夠的空閑區(qū)域分配給申請(qǐng)者。當(dāng)作業(yè)撤離或主動(dòng)歸還主存資源時(shí)，則存儲(chǔ)管理要收回作業(yè)占用的主存空間或歸還部分主存空間。主存的分配和回收的實(shí)現(xiàn)雖與主存儲(chǔ)器的管理方式有關(guān)的，通過本實(shí)驗(yàn)幫助學(xué)生理解在不同的存儲(chǔ)管理方式下應(yīng)怎樣實(shí)現(xiàn)主存空間的分配和回收。
三、實(shí)驗(yàn)環(huán)境
1．PC微機(jī)。
2．Windows 操作系統(tǒng)。
3．C/C++/VB開發(fā)集成環(huán)境。
四、實(shí)驗(yàn)題目
本實(shí)驗(yàn)?zāi)M在兩種存儲(chǔ)管理方式下的主存分配和回收。
第一題：在可變分區(qū)管理方式下采用首次適應(yīng)算法實(shí)現(xiàn)主存分配和實(shí)現(xiàn)主存回收。
算法設(shè)計(jì)思想：
(1) 可變分區(qū)方式是按作業(yè)需要的主存空間大小來分割分區(qū)的。當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)需要的主存量查看是否有足夠的空閑空間，若有，則按需要量分割一個(gè)分區(qū)分配給該作業(yè)；若無，則作業(yè)不能裝入。隨著作業(yè)的裝入、撤離，主存空間被分成許多個(gè)分區(qū)，有的分區(qū)被作業(yè)占用，而有的分區(qū)是空閑的。例如：
|
0
5k
10k
14k
26k
32k
128k
|
操作系統(tǒng)
|
|
作業(yè)1
|
|
作業(yè)3
|
|
空閑區(qū)
|
|
作業(yè)2
|
|
空閑區(qū)
|
為了說明哪些區(qū)是空閑的，可以用來裝入新作業(yè)，必須要有一張空閑區(qū)說明表，格式如下：
|
|
起 址
|
長(zhǎng) 度
|
狀 態(tài)
|
|
第一欄
|
14 K
|
12 K
|
未 分 配
|
|
第二欄
|
32 K
|
96 K
|
未 分 配
|
|
M
M
|
|
|
空 表 目
|
|
|
|
空 表 目
|
|
|
|
M
M
|
其中，起址——指出一個(gè)空閑區(qū)的主存起始地址。
長(zhǎng)度——指出從起始地址開始的一個(gè)連續(xù)空閑的長(zhǎng)度。
狀態(tài)——有兩種狀態(tài)，一種是“未分配”狀態(tài)，指出對(duì)應(yīng)的由起址指出的某個(gè)長(zhǎng)度的區(qū)域是空閑區(qū)；另一種是“空表目”狀態(tài)，表示表中對(duì)應(yīng)的登記項(xiàng)目是空白（無效），可用來登記新的空閑區(qū)（例如，作業(yè)撤離后，它所占的區(qū)域就成了空閑區(qū)，應(yīng)找一個(gè)“空表目”欄登記歸還區(qū)的起址和長(zhǎng)度且修改狀態(tài)）。由于分區(qū)的個(gè)數(shù)不定，所以空閑區(qū)說明表中應(yīng)有適量的狀態(tài)為“空表目”的登記欄目，否則造成表格“溢出”無法登記。
上述的這張說明表的登記情況是按提示（1）中的例所裝入的三個(gè)作業(yè)占用的主存區(qū)域后填寫的。
(2) 當(dāng)有一個(gè)新作業(yè)要求裝入主存時(shí)，必須查空閑區(qū)說明表，從中找出一個(gè)足夠大的空閑區(qū)。有時(shí)找到的空閑區(qū)可能大于作業(yè)需要量，這時(shí)應(yīng)把原來的空閑區(qū)變成兩部分：一部分分給作業(yè)占用；另一部分又成為一個(gè)較小的空閑區(qū)。為了盡量減少由于分割造成的空閑區(qū)，而盡量保存高地址部分有較大的連續(xù)空閑區(qū)域，以利于大型作業(yè)的裝入。為此，在空閑區(qū)說明表中，把每個(gè)空閑區(qū)按其地址順序登記，即每個(gè)后繼的空閑區(qū)其起始地址總是比前者大。為了方便查找還可使表格“緊縮”，總是讓“空表目”欄集中在表格的后部。
(3) 采用首次適應(yīng)算法（順序分配算法）分配主存空間。
按照作業(yè)的需要量，查空閑區(qū)說明表，順序查看登記欄，找到第一個(gè)能滿足要求的空閑區(qū)。當(dāng)空閑區(qū)大于需要量時(shí)，一部分用來裝入作業(yè)，另一部分仍為空閑區(qū)登記在空閑區(qū)說明表中。
由于本實(shí)驗(yàn)是模擬主存的分配，所以把主存區(qū)分配給作業(yè)后并不實(shí)際啟動(dòng)裝入程序裝入作業(yè)，而用輸出“分配情況”來代替。首次適應(yīng)分配算法如圖4-1。
(4) 當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束撤離時(shí)，作業(yè)所占的區(qū)域應(yīng)該歸還，歸還的區(qū)域如果與其它空閑區(qū)相鄰，則應(yīng)合成一個(gè)較大的空閑區(qū)，登記在空閑區(qū)說明表中。例如，在提示（1）中列舉的情況下，如果作業(yè)2撤離，歸還所占主存區(qū)域時(shí)，應(yīng)與上、下相鄰的空閑區(qū)一起合成一個(gè)大的空閑區(qū)登記在空閑區(qū)說明表中。歸還主存時(shí)的回收算法如圖4-2。
(5) 請(qǐng)按首次適應(yīng)算法設(shè)計(jì)主存分配和回收的程序。然后按（1）中假設(shè)主存中已裝入三個(gè)作業(yè)，且形成兩個(gè)空閑區(qū)，確定空閑區(qū)說明表的初值。現(xiàn)有一個(gè)需要主存量為6K的作業(yè)4申請(qǐng)裝入主存；然后作業(yè)3撤離；再作業(yè)2撤離。請(qǐng)你為它們進(jìn)行主存分配和回收，把空閑區(qū)說明表的初值以及每次分配或回收后的變化顯示出來或打印出來。
第二題：在分頁(yè)式管理方式下采用位示圖來表示內(nèi)存分配情況，實(shí)現(xiàn)內(nèi)存空間的分配和回收。
算法設(shè)計(jì)思想：
(1) 分頁(yè)式存儲(chǔ)器把主存分成大小相等的若干塊，作業(yè)的信息也按塊的大小分頁(yè)，作業(yè)裝入主存時(shí)可把作業(yè)的信息按頁(yè)分散存放在主存的空閑塊中，為了說明內(nèi)存中哪些塊已經(jīng)被占用，哪些塊是尚未分配的空閑塊，可用一張位示圖來指出。位示圖可由若干存儲(chǔ)單元來構(gòu)成，其中每一位與一個(gè)物理塊對(duì)應(yīng)，用0/1表示對(duì)應(yīng)塊為空閑/已占用。
(2) 假設(shè)某系統(tǒng)的內(nèi)存被分成大小相等的64塊，則位示圖可用8個(gè)字節(jié)來構(gòu)成，另用一單元記錄當(dāng)前空閑塊數(shù)。如果已有第0，1，4，5，6，9，11，13，24，31，共10個(gè)主存塊被占用了，那么位示圖情況如下：
|
字 位
節(jié) 數(shù)
號(hào)
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
|
0
|
1
|
1
|
0
|
0
|
1
|
1
|
1
|
0
|
|
1
|
0
|
1
|
0
|
1
|
0
|
1
|
0
|
0
|
|
2
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
3
|
1
|
0
|
0
|
0
|
0
|
0
|
0
|
1
|
|
4
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
5
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
6
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
|
7
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
0
|
圖4-1 首次適應(yīng)分配模擬算法
圖4-2 內(nèi)存回收算法
(3) 當(dāng)要裝入一個(gè)作業(yè)時(shí)，根據(jù)作業(yè)對(duì)主存的需要量，先查當(dāng)前空閑塊數(shù)是否能滿足作業(yè)要求，若不能滿足則輸出分配不成功。若能滿足，則查位示圖，找出為“0”的一些位，置上占用標(biāo)志“1”，從“當(dāng)前空閑塊數(shù)”中減去本次占用塊數(shù)。
按找到的計(jì)算出對(duì)應(yīng)的塊號(hào)，其計(jì)算公式為：
塊號(hào)= j?8+i
其中，j表示找到的是第n個(gè)字節(jié)，i表示對(duì)應(yīng)的是第n位。
根據(jù)分配給作業(yè)的塊號(hào)，為作業(yè)建立一張頁(yè)表，頁(yè)表格式：
|
頁(yè) 號(hào)
|
塊 號(hào)
|
|
0
|
|
|
1
|
|
|
2
|
|
|
M
M
|
|
(4) 當(dāng)一個(gè)作業(yè)執(zhí)行結(jié)束，歸還內(nèi)存時(shí)，根據(jù)該作業(yè)的頁(yè)表可以知道應(yīng)歸還的塊號(hào)，由塊號(hào)可計(jì)算出在位示圖中的對(duì)應(yīng)位置，把對(duì)應(yīng)位的占用標(biāo)志清成“0”，表示對(duì)應(yīng)的塊已成為空閑塊。歸還的塊數(shù)加入到當(dāng)前空閑塊數(shù)中。由塊號(hào)計(jì)算在位示圖中的位置的公式如下：
字節(jié)號(hào) j=[塊號(hào)/8] （[ ]表示取整）
位數(shù) i={塊號(hào)/8} （{ }表示取余）
(5) 設(shè)計(jì)實(shí)現(xiàn)內(nèi)存分配和回收的程序。假定位示圖的初始狀態(tài)如（2）所述，現(xiàn)有一信息量為5頁(yè)的作業(yè)要裝入，運(yùn)行你所設(shè)計(jì)的分配程序，為作業(yè)分配主存且建立頁(yè)表（格式如（3）所述）。然后假定有另一作業(yè)執(zhí)行結(jié)束，它占用的塊號(hào)為第4，5，6和31塊，運(yùn)行你所設(shè)計(jì)的回收程序，收回作業(yè)歸還的內(nèi)存塊。
要求能顯示和打印分配或回收前后的位示圖和當(dāng)前空閑塊數(shù)，對(duì)完成一次分配后還要顯示或打印為作業(yè)建立的頁(yè)表。