實驗六_虛擬存儲器.doc

實驗六 虛擬存儲器一、實驗內容模擬分頁式虛擬存儲管理中硬件的地址轉換和缺頁中斷，以及選擇頁面調度算法處理缺頁中斷。二、實驗目的在計算機系統(tǒng)中，為了提高主存利用率，往往把輔助存儲器（如磁盤）作為主存儲器的擴充，使多道運行的作業(yè)的全部邏輯地址空間總和可以超出主存的絕對地址空間。用這種辦法擴充的主存儲器稱為虛擬存儲器。通過本實驗幫助同學理解在分頁式存儲管理中怎樣實現(xiàn)虛擬存儲器。三、實驗題目本實驗有三道題目，其中第一題必做，第二，三題中可任選一個。第一題：模擬分頁式存儲管理中硬件的地址轉換和產生缺頁中斷。提示（1） 分頁式虛擬存儲系統(tǒng)是把作業(yè)信息的副本存放在磁盤上，當作業(yè)被選中時，可把作業(yè)的開始幾頁先裝入主存且啟動執(zhí)行。為此，在為作業(yè)建立頁表時，應說明哪些頁已在主存，哪些頁尚未裝入主存，頁表的格式為：頁號標志主存塊號在磁盤上的位置其中，標志-用來表示對應頁是否已經裝入主存，標志位=1，則表示該頁已經在主存，標志位=0，則表示該頁尚未裝入主存。主存塊號-用來表示已經裝入主存的頁所占的塊號。在磁盤上的位置-用來指出作業(yè)副本的每一頁被存放在磁盤上的位置。（2） 作業(yè)執(zhí)行時，指令中的邏輯地址指出了參加運算的操作存放的頁號和單元號，硬件的地址轉換機構按頁號查頁表，若該頁對應標志為“1”，則表示該頁已在主存，這時根據(jù)關系式： 絕對地址=塊號塊長+單元號計算出欲訪問的主存單元地址。如果塊長為2的冪次，則可把塊號作為高地址部分，把單元號作為低地址部分，兩者拼接而成絕對地址。若訪問的頁對應標志為“0”，則表示該頁不在主存，這時硬件發(fā)“缺頁中斷”信號，有操作系統(tǒng)按該頁在磁盤上的位置，把該頁信息從磁盤讀出裝入主存后再重新執(zhí)行這條指令。（3） 設計一個“地址轉換”程序來模擬硬件的地址轉換工作。當訪問的頁在主存時，則形成絕對地址，但不去模擬指令的執(zhí)行，而用輸出轉換后的地址來代替一條指令的執(zhí)行。當訪問的頁不在主存時，則輸出“* 該頁頁號”，表示產生了一次缺頁中斷。該模擬程序的算法如圖6-1。開始取一條指令取指令中訪問的頁號 查頁表 否是該頁標志=1？形成絕對地址輸出“*”頁號表示發(fā)生缺頁中斷輸出絕對地址有后繼指令？取下一條指令結束圖6-1 地址轉換模擬算法（4） 假定主存的每塊長度為128個字節(jié)；現(xiàn)有一個共七頁的作業(yè)，其中第0頁至第3頁已經裝入主存，其余三頁尚未裝入主存；該作業(yè)的頁表為：015011118012219013311021400225002360121如果作業(yè)依次執(zhí)行的指令序列為：操作頁號單元號操作頁號單元號+070移位4053+150+5023215存1037存321取2078取056+4001640存6084（5） 運行設計的地址轉換程序，顯示或打印運行結果。因僅模擬地址轉換，并不模擬指令的執(zhí)行，故可不考慮上述指令序列中的操作。第二題：用先進先出（FIFO）頁面調度算法處理缺頁中斷。提示：（1） 在分頁式虛擬存儲系統(tǒng)中，當硬件發(fā)出“缺頁中斷”后，引出操作系統(tǒng)來處理這個中斷事件。如果主存中已經沒有空閑塊，則可用FIFO頁面調度算法把該作業(yè)中最先進入主存的一頁調出，存放到磁盤上，然后再把當前要訪問的頁裝入該塊。調出和裝入后都要修改頁表頁表中對應頁的標志。（2） FIFO頁面調度算法總是淘汰該作業(yè)中最先進入主存的那一頁，因此可以用一個數(shù)組來表示該作業(yè)已在主存的頁面。假定作業(yè)被選中時，把開始的m個頁面裝入主存，則數(shù)組的元素可定為m個。例如： P0，P1，.，Pm-1其中每一個Pi（i=0，1，.，m-1）表示一個在主存中的頁面號。它們的初值為： P0:=0，P1:=1，.，Pm-1:=m-1用一指針k指示當要裝入新頁時，應淘汰的頁在數(shù)組中的位置，k的初值為“0”。當產生缺頁中斷后，操作系統(tǒng)選擇Pk所指出的頁面調出，然后執(zhí)行：Pk:=要裝入頁的頁號 k:=(k+1) mod m再由裝入程序把要訪問的一頁信息裝入到主存中。重新啟動剛才那條指令執(zhí)行。（3） 編制一個FIFO頁面調度程序，為了提高系統(tǒng)效率，如果應淘汰的頁在執(zhí)行中沒有修改過，則可不必把該頁調出（因在磁盤上已有副本）而直接裝入一個新頁將其覆蓋。因此在頁表中增加是否修改過的標志，為“1”表示修改過，為“0”表示未修改過，格式為：頁號 標志 主存塊號 修改標志 在磁盤上的位置由于是模擬調度算法，所以，不實際啟動輸出一頁和裝入一頁的程序，而用輸出調出的頁號和裝入的頁號來代替一次調出和裝入的過程。把第一題中程序稍作修改，與本題結合起來，F(xiàn)IFO頁面調度模擬算法如圖6-2。（4） 磁盤上，在磁盤上的存放地址以及已裝入主存的頁和作業(yè)依次執(zhí)行的指令序列都同第一題中（4）所示。于是增加了“修改標志”后的初始頁表為： 頁號 標志 主存塊號 修改標志 在磁盤上的位置015 0011118 0012219 0013311 002140 002250 002360 0121按依次執(zhí)行的指令序列，運行你所設計的程序，顯示或打印每次調出和裝入的頁號，以及執(zhí)行了最后一條指令后的數(shù)組P的值。（5） 為了檢查程序的正確性，可再任意確定一組指令序列，運行設計的程序，核對執(zhí)行的結果。開始取一條指令取指令中訪問的頁號L 查頁表 否（產生缺頁中斷）是該頁標志=1？形成絕對地址是是存指令？置L頁修改標志為“1”否輸出絕對地址有后繼指令？否是結束模擬硬件地址轉換取下一條指令模擬FIFO頁面調度j:=Pkj頁修改標志為1輸出“out j”(接下頁)(接上頁)輸出“in L”修改頁表Pk:=L, k:=(k+1) mod m圖6-2 FIFO頁面調度模擬算法第三題：用最近最少用（LRU）頁面調度算法處理缺頁中斷。提示(1) 在分頁式虛擬存儲系統(tǒng)中，當硬件發(fā)出“缺頁中斷”后，引出操作系統(tǒng)來處理這個中斷事件。如果主存中已經沒有空閑塊，則可用LRU頁面調度算法把該作業(yè)中最先進入主存的一頁調出，存放到磁盤上，然后再把當前要訪問的頁裝入該塊。調出和裝入后都要修改頁表頁表中對應頁的標志。(2) LRU頁面調度算法總是淘汰該作業(yè)中距現(xiàn)在最久沒有訪問過的那一頁，因此可以用一個數(shù)組來表示該作業(yè)已在主存的頁面。數(shù)組中的第一個元素總是指出當前剛訪問的頁號，因此最久沒被訪問的頁總是由最后一個元素指出。如果主存中只有四塊空閑塊且執(zhí)行第一題提示（4）假設的指令序列，采用LRU頁面調度算法，那麼在主存中的頁面變化情況如下：306451246230645134123064512012306451(3) 編制一個LRU頁面調度程序，為了提高系統(tǒng)效率，如果應淘汰的頁在執(zhí)行中沒有修改過，則可不必把該頁調出。參看第二題中提示（3）。模擬調度算法不實際啟動輸出一頁和裝入一頁的程序，而用輸出調出的頁號和裝入的頁號來代替。把第一題中的程序稍作改動，與本題集合起來，LRU頁面調度模擬算法如圖6-3。(4) 按第一題中提示（4）的要求，建立一張初始頁表，表中為每一頁增加“修改標志”位（參考第二題中提示（4）。然后按依次執(zhí)行的指令序列，運行你所設計的程序，顯示或打印每次調出和裝入的頁號，以及執(zhí)行了最后一條指令后的數(shù)組中的值。(5) 為了檢查程序的正確性，可再任意確定一組指令序列，運行設計的程序，核對執(zhí)行的結果。開始取一條指令取指令中訪問的頁號L 查頁表 否（產生缺頁中斷）是該頁標志=1？形成絕對地址是是存指令？否置L頁修改標志為“1”輸出絕對地址否有后繼指令？是結束模擬硬件地址轉換取下一條指令模擬LRU頁面調度j:=被淘汰的頁號(接下頁)(接上頁)輸出“out j”j頁修改標志為1輸出“in L”調整數(shù)組，j退出數(shù)組，L數(shù)組第一個元素中修改頁表圖6-3 LRU頁面調度算法四、實驗報告（1） （第一題必