操作系統實驗之存儲管理
時間：
佳洲1085由 分享
操作系統實驗之存儲管理
操作系統實驗存儲管理是加深對存儲管理的作用和工作原理的理解，下面由學習啦小編為大家整理了操作系統實驗存儲管理的相關知識，希望大家喜歡!操作系統實驗——存儲管理
實驗三 存儲管理(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 |
(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)打印初始頁表、每次調出(要調出一頁時)和裝入的頁號、執行最后一條指令后在主存中的頁面號(即數組的值)。