作業系統實驗之儲存管理

　　作業系統實驗儲存管理是加深對儲存管理的作用和工作原理的理解，下面由小編為大家整理了作業系統實驗儲存管理的相關知識，希望大家喜歡!
　　作業系統實驗——儲存管理
　　實驗三 儲存管理***3學時***
　　一、實驗目的
　　***1***加深對儲存管理的作用和工作原理的理解。
　　***2***進一步認識主存空間的分配和回收方法。
　　***3***進一步認識虛擬儲存器的工作原理。
　　二、實驗型別
　　綜合型。
　　三、預習內容
　　預習課本儲存管理有關內容，包括各種記憶體分配方法和利用分頁式儲存管理實現虛擬儲存器策略方法。
　　預習課本檔案系統有關內容，包括檔案和目錄的建立和刪除等基本原理。
　　四、實驗要求與提示
　　本實驗有三個題，其中第一必做，第二、第三題中任選一個。
　　第一題：模擬分頁式儲存管理中硬體的地址轉換和產生缺頁中斷。
　　【提示】
　　***1***分頁式虛擬儲存系統是把作業資訊的副本存放在磁碟上，當作業被選中時，可把作業的開始幾頁先裝入主存且啟動執行。為此，在為作業建立頁表時，應說明哪些頁已在主存，哪些頁尚未裝入主存，頁表的格式為：

頁號	標誌	主存塊號	在磁碟上的位置

　　其中，
　　l 標誌——用來表示對應頁是否已經裝入主存，標誌位=1，則表示該頁已經在主存，標誌位=0，則表示該頁尚未裝入主存。
　　l 主存塊號——用來表示已經裝入主存的頁所佔的塊號。
　　l 在磁碟上的位置——用來指出作業副本的每一頁被存放在磁碟上的位置。
　　***2***作業執行時，指令中的邏輯地址指出了參加運算的運算元存放的頁號和單元號，硬體的地址轉換機構按頁號查頁表，若該頁對應標誌為“1”，則表示該頁已在主存，這時根據關係式：
　　絕對地址=塊號´塊長+單元號
　　計算出欲訪問的主存單元地址。如果塊長為2的冪次，則可把塊號作為高地址部分，把單元號作為低地址部分，兩者拼接而成絕對地址。按計算出的絕對地址可以取到運算元，完成一條指令的執行。若訪問的頁對應標誌為“0”，則表示該頁不在主存，這時硬體發“缺頁中斷”訊號，由作業系統按該頁在磁碟上的位置，把該頁資訊從磁碟讀出裝入主存後再重新執行這條指令。
　　***3***設計一個“地址轉換”程式來模擬硬體的地址轉換工作。當訪問的頁在主存時，則形成絕對地址，但不去模擬指令的執行，而用輸出轉換後的地址來代替一條指令的執行。當訪問的頁不在主存時，則輸出“*該頁頁號”，表示產生了一次缺頁中斷。該模擬程式的演算法如圖3-1。
　　***4***假定主存的每塊長度為128個位元組;現有一個共七頁的作業，其中第0頁至第3頁已經裝入主存，其餘三頁尚未裝入主存;該作業的頁表為：

0	1	5	011
1	1	8	012
2	1	9	013
3	1	1	021
4	0		022
5	0		023
6	0		121

　　如果作業依次執行的指令序列為：

操作	頁號	單元號	操作	頁號	單元號
+	0	070	移位	4	053
+	1	050	+	5	023
´	2	015	存	1	037
存	3	021	取	2	078
取	0	056	+	4	001
-	6	040	存	6	084

　　執行設計的地址轉換程式，顯示或列印執行結果。因僅模擬地址轉換，並不模擬指令的執行，故可不考慮上述指令序列中的操作。
　　圖3-1 地址轉換模擬演算法
　　第二題：用先進先出***FIFO***頁面排程演算法處理缺頁中斷。
　　【提示】
　　***1***在分頁式虛擬儲存系統中，當硬體發出“缺頁中斷”後，引出作業系統來處理這個中斷事件。如果主存中已經沒有空閒塊，則可用FIFO頁面排程演算法把該作業中最先進入主存的一頁調出，存放到磁碟上。然後再把當前要訪問的頁裝入該塊。調出和裝入後都要修改頁表中對應頁的標誌。
　　***2***FIFO頁面排程演算法總是淘汰該作業中最先進入主存的那一頁，因此可以用一個數組來表示該作業已在主存的頁面。假定作業被選中時，把開始的m個頁面裝入主存，則陣列的元素可定為m個。例如：
　　P[0]，P[1]…，P[m-1]
　　其中，每一個P[i] ***i =0, 1, …, m-1*** 表示一個在主存中的頁面號。它們的初值為：
　　P[0]： =0, P[1]： =1, …, P[m-1]： =m-1
　　用一指標K指示當要裝入新頁時，應淘汰的頁在陣列中的位置，K的初值為“0”。
　　當產生缺頁中斷後，作業系統選擇P[k]所指出的頁面調出，然後執行：
　　P[k]： =要裝入頁的頁號
　　k： = ***k+1*** mod m
　　再由裝入程式把要訪問的一頁資訊裝入到主存中。重新啟動剛才那條指令執行。
　　***3***編制一個FIFO頁面排程程式，為了提高系統效率，如果應淘汰的頁在執行中沒有修改過，則可不必把該頁調出***因在磁碟上已有副本***而直接裝入一個新頁將其覆蓋。因此在頁表中增加是否修改過的標誌，為“1”表示修改過，為“0”表示未修改過，格式為：

頁號	標誌	主存塊號	修改標誌	在磁碟上的位置

　　由於是模擬排程演算法，所以，不實際地啟動調出一頁和裝入一頁的程式，而用輸出調出的頁號和裝入的頁號來代替一次調出和裝入的過程。
　　把第一題中程式稍作改動，與本題結合起來，FIFO頁面排程模擬演算法如圖3-2。
　　***4***如果一個作業的副本已在磁碟上，在磁碟上的存放地址以及已裝入主存的頁和作業依次執行的指令序列都同第一題中***4***所示。於是增加了“修改標誌”後的初始頁表為：

頁號	標誌	主存塊號	修改標誌	在磁碟上的位置
0	1	5	0	011
1	1	8	0	012
2	1	9	0	013
3	1	1	0	021
4	0		0	022
5	0		0	023
6	0		0	121

　　按依次執行的指令序列，執行你所設計的程式，顯示或列印每次調出和裝入的頁號，以及執行了最後一條指令後的陣列P的值。
　　***5***為了檢查程式的正確性，可再任意確定一組指令序列，執行設計的程式，核對執行的結果。
　　第三題：用最近最少用***LRU***頁面排程演算法處理缺頁中斷。
　　【提示】
　　***1***在分頁式虛擬儲存系統中，當硬體發出“缺頁中斷”後，引出作業系統來處理這個中斷事件。如果主存中已經沒有空閒塊，則可用LRU頁面排程演算法把該作業中距現在最久沒有被訪問過的一頁調出，存放到磁碟上。然後再把當前要訪問的頁裝入該塊。調出和裝入後都要修改頁表中對應頁的標誌。
　　圖3-2 FIFO頁面排程模擬演算法
　　***2***LRU頁面排程演算法總是淘汰該作業中距現在最久沒被訪問過的那頁，因此可以用一個數組來表示該作業已在主存的頁面。陣列中的第一個元素總是指出當前剛訪問的頁號，因此最久沒被訪問過的頁總是由最後一個元素指出。如果主存只有四塊空閒塊且執行第一題中提示***4***假設的指令序列，採用LRU頁面排程演算法，那麼在主存中的頁面變化情況如下：

3		0		6		4		5		1		2		4		6
2		3		0		6		4		5		1		2		4
1		2		3		0		6		4		5		1		2
0		1		2		3		0		6		4		5		1

　　當產生缺頁中斷後，作業系統總是淘汰由最後一個元素所指示的頁，再把要訪問的頁裝入淘汰頁所佔的主存塊中，頁號登記到陣列的第一個元素中，重新啟動剛才那條指令執行。
　　***3***編制一個LRU頁面排程程式，為了提高系統效率，如果淘汰的頁在執行中沒有修改過，則可不必把該頁調出。參看第二題中提示***3***。模擬排程演算法不實際地啟動調出一頁和裝入一頁的程式而用輸出調出的頁號和裝入的頁號來代替。把第一題中程式稍作改動，與本題結合起來，LRU頁面排程模擬演算法如圖3-3。
　　圖3-3 LRU頁面排程模擬演算法
　　***4***按第一題中提示***4***的要求，建立一張初始頁表，頁表中為每一頁增加“修改標誌”位***參考第二題中提示***4******。然後按依次執行的指令序列，執行設計的程式，顯示或列印每次調出和裝入的頁號，以及執行了最後一條指令後陣列中的值。
　　***5***為了檢查程式的正確性，可再任意確定一組指令序列，執行設計的程式，核對執行的結果。
　　五、思考題
　　***1***先進先出頁面排程演算法的思想?
　　***2***最近最少用***LRU***頁面排程演算法思想?
　　***3***比較兩種排程演算法的效率***哪種排程演算法使產生缺頁中斷的次數少***?
　　***4***分析在什麼情況下采用哪種排程演算法更有利?
　　六、實驗報告
　　***1***實驗題目***第二題或第三題***。
　　***2***程式中使用的資料結構及符號說明。
　　***3***實現的核心程式碼。
　　***4***列印初始頁表、每次調出***要調出一頁時***和裝入的頁號、執行最後一條指令後在主存中的頁面號***即陣列的值***。

作業系統死鎖
作業系統實驗之銀行家演算法