實(shí)驗(yàn)六_虛擬存儲(chǔ)器.doc

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