課程設(shè)計(jì) 分頁(yè)方式的地址轉(zhuǎn)換

1、 操作系統(tǒng)課程綜合實(shí)踐題目：分頁(yè)方式的地址轉(zhuǎn)換和處理缺頁(yè)中斷 班級(jí)： 姓名： 學(xué)號(hào)： 指導(dǎo)教師： 2008年 12 月分頁(yè)方式的地址轉(zhuǎn)換和處理缺頁(yè)中斷摘要：在計(jì)算機(jī)系統(tǒng)中，為了提高主存利用率，往往把輔助存儲(chǔ)器（如磁盤(pán)）作為主存儲(chǔ)器的擴(kuò)充，使多道運(yùn)行的作業(yè)的全部邏輯地址空間總和可以超出主存的絕對(duì)地址空間。用這種辦法擴(kuò)充的主存儲(chǔ)器稱(chēng)為虛擬存儲(chǔ)器。模擬分頁(yè)式虛擬存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和缺頁(yè)中斷，以及采用先進(jìn)先出（FIFO）頁(yè)面調(diào)度算法處理缺頁(yè)中斷。通過(guò)本實(shí)驗(yàn)理解在分頁(yè)式存儲(chǔ)管理中怎樣實(shí)現(xiàn)虛擬存儲(chǔ)器。關(guān)鍵字：頁(yè)表；分頁(yè)方式；缺頁(yè)中斷；LRU算法1.設(shè)計(jì)思路 （1）模擬分頁(yè)式存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和

2、產(chǎn)生缺頁(yè)中斷的設(shè)計(jì)思路作業(yè)執(zhí)行時(shí)，指令中的邏輯地址指出參加運(yùn)算的操作數(shù)存放的地址，該地址被解釋為頁(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ì)算出欲訪(fǎng)問(wèn)的主存單元地址。如果塊長(zhǎng)為2的冪次，則可把塊號(hào)作為高地址部分，把單元號(hào)作為低地址部分，兩者拼接而成絕對(duì)地址。按計(jì)算出的絕對(duì)地址可以取到操作數(shù)，完成一條指令的執(zhí)行。若訪(fǎng)問(wèn)的頁(yè)對(duì)應(yīng)標(biāo)志為“0”，則表示該頁(yè)不在主存，這時(shí)硬件發(fā)“缺頁(yè)中斷”信號(hào)，由操作系統(tǒng)按該頁(yè)在磁盤(pán)上的位置，把該頁(yè)信息從磁盤(pán)讀出裝入主存后再重新執(zhí)行這條指令。設(shè)計(jì)一個(gè)“地址轉(zhuǎn)換”程序來(lái)模擬硬件的地

3、址轉(zhuǎn)換工作。當(dāng)訪(fǎng)問(wèn)的頁(yè)在主存時(shí)，則形成絕對(duì)地址，但不去模擬指令的執(zhí)行，而用輸出轉(zhuǎn)換后的地址來(lái)代替一條指令的執(zhí)行。當(dāng)訪(fǎng)問(wèn)的頁(yè)不在主存時(shí)，則輸出“*該頁(yè)頁(yè)號(hào)”，表示產(chǎn)生了一次缺頁(yè)中斷。該模擬程序的算法如圖1。假定主存的每塊長(zhǎng)度為128個(gè)字節(jié)；現(xiàn)有一個(gè)共七頁(yè)的作業(yè)，其中第0頁(yè)至第3頁(yè)已經(jīng)裝入主存，其余三頁(yè)尚未裝入主存；該作業(yè)的頁(yè)表為：頁(yè)號(hào)標(biāo)志主存塊號(hào)在磁盤(pán)上的位置015011118012219013311021400225002360121（2）用最近最少用（LRU）頁(yè)面調(diào)度算法處理缺頁(yè)中斷設(shè)計(jì)思路在分頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，當(dāng)硬件發(fā)出“缺頁(yè)中斷”后，引出操作系統(tǒng)來(lái)處理這個(gè)中斷事件。如果主存中已經(jīng)沒(méi)有空

4、閑塊，則可用LRU頁(yè)面調(diào)度算法把該作業(yè)中距現(xiàn)在最久沒(méi)有被訪(fǎng)問(wèn)過(guò)的一頁(yè)調(diào)出，存放到磁盤(pán)上。然后再把當(dāng)前要訪(fǎng)問(wèn)的頁(yè)裝入該塊。調(diào)出和裝入后都要修改頁(yè)表中對(duì)應(yīng)頁(yè)的標(biāo)志。LRU頁(yè)面調(diào)度算法總是淘汰該作業(yè)中距現(xiàn)在最久沒(méi)被訪(fǎng)問(wèn)過(guò)的那頁(yè)，因此可以用一個(gè)數(shù)組來(lái)表示該作業(yè)已在主存的頁(yè)面。數(shù)組中的第一個(gè)元素總是指出當(dāng)前剛訪(fǎng)問(wèn)的頁(yè)號(hào)，因此最久沒(méi)被訪(fǎng)問(wèn)過(guò)的頁(yè)總是由最后一個(gè)元素指出。如果主存只有四塊空閑塊且執(zhí)行第一題中提示 假設(shè)的指令序列，采用LRU頁(yè)面調(diào)度算法，那么在主存中的頁(yè)面變化情況如下：306451246230645124123064512012306451當(dāng)產(chǎn)生缺頁(yè)中斷后，操作系統(tǒng)總是淘汰由最后一個(gè)元素所指示的

5、頁(yè)，再把要訪(fǎng)問(wèn)的頁(yè)裝入淘汰頁(yè)所占的主存塊中，頁(yè)號(hào)登記到數(shù)組的第一個(gè)元素中，重新啟動(dòng)剛才那條指令執(zhí)行。編制一個(gè)LRU頁(yè)面調(diào)度程序，為了提高系統(tǒng)效率，如果淘汰的頁(yè)在執(zhí)行中沒(méi)有修改過(guò)，則可不必把該頁(yè)調(diào)出。參看第二題中提示。模擬調(diào)度算法不實(shí)際地啟動(dòng)調(diào)出一頁(yè)和裝入一頁(yè)的程序而用輸出調(diào)出的頁(yè)號(hào)和裝入的頁(yè)號(hào)來(lái)代替。把第一題中程序稍作改動(dòng)，與本題結(jié)合起來(lái)，LRU頁(yè)面調(diào)度模擬算法如圖3。按第一題中提示的要求，建立一張初始頁(yè)表，頁(yè)表中為每一頁(yè)增加“修改標(biāo)志”位（參考第二題中提示）。然后按依次執(zhí)行的指令序列，運(yùn)行設(shè)計(jì)的程序，顯示或打印每次調(diào)出和裝入的頁(yè)號(hào)，以及執(zhí)行了最后一條指令后數(shù)組中的值。為了檢查程序的正確性，可

6、再任意確定一組指令序列，運(yùn)行設(shè)計(jì)的程序，核對(duì)執(zhí)行的結(jié)果。2.流程圖（1）模擬分頁(yè)式存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和產(chǎn)生缺頁(yè)中斷的流程圖如下圖1 地址轉(zhuǎn)換模擬算法如果作業(yè)依次執(zhí)行的指令序列為：操作頁(yè)號(hào)單元號(hào)操作頁(yè)號(hào)單元號(hào)+0070移位4053+1050+5023´2015存1037存3021取2078取0056+4001-6040存6084運(yùn)行設(shè)計(jì)的地址轉(zhuǎn)換程序，顯示或打印運(yùn)行結(jié)果。因僅模擬地址轉(zhuǎn)換，并不模擬指令的執(zhí)行，故可不考慮上述指令序列中的操作。（2）用最近最少用（LRU）頁(yè)面調(diào)度算法處理缺頁(yè)中斷流程圖圖2 LRU頁(yè)面調(diào)度模擬算法3. 主要數(shù)據(jù)結(jié)構(gòu)及其說(shuō)明 （1）分頁(yè)式虛擬存儲(chǔ)系統(tǒng)是把

7、作業(yè)信息的副本存放在磁盤(pán)上，當(dāng)作業(yè)被選中時(shí)，可把作業(yè)的開(kāi)始幾頁(yè)先裝入主存且啟動(dòng)執(zhí)行。為此，在為作業(yè)建立頁(yè)表時(shí)，應(yīng)說(shuō)明哪些頁(yè)已在主存，哪些頁(yè)尚未裝入主存，頁(yè)表的格式為：頁(yè)號(hào)標(biāo)志主存塊號(hào)在磁盤(pán)上的位置其中，標(biāo)志用來(lái)表示對(duì)應(yīng)頁(yè)是否已經(jīng)裝入主存，標(biāo)志位=1，則表示該頁(yè)已經(jīng)在主存，標(biāo)志位=0，則表示該頁(yè)尚未裝入主存。主存塊號(hào)用來(lái)表示已經(jīng)裝入主存的頁(yè)所占的塊號(hào)。在磁盤(pán)上的位置用來(lái)指出作業(yè)副本的每一頁(yè)被存放在磁盤(pán)上的位置。（2）定義相關(guān)數(shù)據(jù)結(jié)構(gòu)如下typedef structint address; /進(jìn)程的邏輯地址int meaddress; /進(jìn)程的物理地址int page; /進(jìn)程所在頁(yè)號(hào)int ad

8、d; /進(jìn)程的位移量arccell,AdjMatrixMAX;typedef structchar vexMAX; /進(jìn)程名AdjMatrix arcs; /指向進(jìn)程地址的數(shù)組int vexnum; /進(jìn)程總數(shù)Pro;typedef struct int page; /頁(yè)號(hào)int block; /塊號(hào)int status; /該頁(yè)是否在內(nèi)存的狀態(tài)位pa_cell,pa_matrixMAX;typedef structpa_matrix ptab; /指向頁(yè)表相關(guān)信息的數(shù)組pa_tab; （3）定義必要函數(shù)：void create_ptable(pa_tab & pa) /創(chuàng)建頁(yè)表voi

9、d exchange(Pro & P,pa_tab & pa) /地址轉(zhuǎn)換函數(shù)4.結(jié)束語(yǔ) 在計(jì)算機(jī)系統(tǒng)中，為了提高主存利用率，往往把輔助存儲(chǔ)器（如磁盤(pán)）作為主存儲(chǔ)器的擴(kuò)充，使多道運(yùn)行的作業(yè)的全部邏輯地址空間總和可以超出主存的絕對(duì)地址空間。模擬分頁(yè)式虛擬存儲(chǔ)管理中硬件的地址轉(zhuǎn)換和缺頁(yè)中斷，以及采用最近最少用（LRU）頁(yè)面調(diào)度算法處理缺頁(yè)中斷。用這種辦法擴(kuò)充的主存儲(chǔ)器稱(chēng)為虛擬存儲(chǔ)器。通過(guò)本實(shí)驗(yàn)理解在分頁(yè)式存儲(chǔ)管理中怎樣實(shí)現(xiàn)虛擬存儲(chǔ)器。分頁(yè)式虛擬存儲(chǔ)系統(tǒng)是把作業(yè)信息的副本存放在磁盤(pán)上，當(dāng)作業(yè)被選中時(shí)，可把作業(yè)的開(kāi)始幾頁(yè)先裝入主存且啟動(dòng)執(zhí)行。為此，在為作業(yè)建立頁(yè)表時(shí)，應(yīng)說(shuō)明哪些頁(yè)已在主存，哪些頁(yè)尚未裝入主存。LRU頁(yè)面調(diào)度算法總是淘汰該作業(yè)中距現(xiàn)在最久沒(méi)被訪(fǎng)問(wèn)過(guò)的那頁(yè)，因此可以用一個(gè)數(shù)組來(lái)表示該作業(yè)已在主存的頁(yè)面。數(shù)組中的第一個(gè)元素總是指出當(dāng)前剛訪(fǎng)問(wèn)的頁(yè)號(hào)，因此最久沒(méi)被