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