課程設(shè)計(jì)-頁面置換算法模擬-最近最久未使用（LRU） 

課程設(shè)計(jì)（論文）題目：頁面置換算法模擬—最近最久未使用（LRU）院（系）：信息與控制工程系專業(yè)班級：計(jì)算機(jī)2012姓名：孫奇學(xué)號：201206060223指導(dǎo)教師：曾應(yīng)員2015年1月23日西安建筑科技大學(xué)華清學(xué)院課程設(shè)計(jì)（論文）任務(wù)書專業(yè)班級：計(jì)算機(jī)1201班學(xué)生姓名：孫奇指導(dǎo)教師（簽名）：曾應(yīng)員一、課程設(shè)計(jì)（論文）題目頁面置換算法模擬-最近最久未使用（LRU）算法：編寫一個(gè)頁面置換算法程序，采用最近最久未使用（LRU）置換算法，在需要頁面調(diào)出時(shí)，選擇在最近時(shí)期使用最久未使用的頁面作為淘汰頁。二、本次課程設(shè)計(jì)（論文）應(yīng)達(dá)到的目的操作系統(tǒng)課程實(shí)踐性比較強(qiáng)。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段。課程設(shè)計(jì)要求學(xué)生在完成程序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。本題目要達(dá)到目的：通過對頁面、頁表、地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實(shí)現(xiàn)過程的理解。三、本次課程設(shè)計(jì)（論文）任務(wù)的主要內(nèi)容和要求（包括原始數(shù)據(jù)、技術(shù)參數(shù)、設(shè)計(jì)要求等）1）假設(shè)每個(gè)頁面中可存放10條指令，分配給作業(yè)的內(nèi)存塊數(shù)為4。2）模擬一個(gè)作業(yè)的執(zhí)行過程，該作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時(shí)需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果4個(gè)內(nèi)存塊均已裝入該作業(yè)，則需進(jìn)行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。在所有320指令執(zhí)行完畢后，請計(jì)算并顯示作業(yè)運(yùn)行過程中發(fā)生的缺頁率。3）置換算法：最近最久未使用（LRU）置換算法四、應(yīng)收集的資料及主要參考文獻(xiàn)：操作系統(tǒng)經(jīng)典算法的編程實(shí)現(xiàn)資料非常豐富，可以在圖書館找書籍或在因特網(wǎng)上找資料，都很容易找到，但是大部分代碼是不全的，不能直接運(yùn)行，希望大家只是把它當(dāng)參考，編碼還是自己做。參考文獻(xiàn)：【1】湯小丹、梁紅兵、哲鳳屏、湯子瀛編著.計(jì)算機(jī)操作系統(tǒng)（第三版）.西安：西安電子科技大學(xué)出版社，2007.5 【2】史美林編.計(jì)算機(jī)操作系統(tǒng)教程.北京：清華大學(xué)出版社，1999.11【3】徐甲同編著.操作系統(tǒng)教程.西安：西安電子科技大學(xué)出版社，1996.8 【4】Clifford，A.Shaffer編著.數(shù)決結(jié)構(gòu)與算法分析(C++版).北京：電子工業(yè)出版社，2005.7【5】蔣立翔編著.C++程序設(shè)計(jì)技能百練.北京：中國鐵道出版社，2004.1五、審核批準(zhǔn)意見教研室主任（簽字）設(shè)計(jì)總說明本次課程設(shè)計(jì)是在學(xué)習(xí)完《操作系統(tǒng)教程》后，進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，讓計(jì)算機(jī)專業(yè)的學(xué)生更好的掌握操作系統(tǒng)的原理以及實(shí)現(xiàn)方法，加深對操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)對學(xué)生的動手能力。課程設(shè)計(jì)要求是通過對頁面，頁表地址轉(zhuǎn)換和頁面置換過程的模擬，加深對請求調(diào)頁系統(tǒng)的原理和實(shí)現(xiàn)過程的理解。同時(shí)此次課程設(shè)計(jì)的主要內(nèi)容有以下三點(diǎn)：1）假設(shè)每個(gè)頁面中可存放10條指令，分配給作業(yè)的內(nèi)存塊數(shù)為4。2）模擬一個(gè)作業(yè)的執(zhí)行過程，該作業(yè)共有320條指令，即它的地址空間為32頁，目前它的所有頁都還未調(diào)入內(nèi)存。在模擬過程中，如果所訪問的指令已在內(nèi)存，則顯示其物理地址，并轉(zhuǎn)下一條指令。如果所訪問的指令還未裝入內(nèi)存，則發(fā)生缺頁，此時(shí)需記錄缺頁的次數(shù)，并將相應(yīng)頁調(diào)入內(nèi)存。如果4個(gè)內(nèi)存塊均已裝入該作業(yè)，則需進(jìn)行頁面置換，最后顯示其物理地址，并轉(zhuǎn)下一條指令。在所有320指令執(zhí)行完畢后，請計(jì)算并顯示作業(yè)運(yùn)行過程中發(fā)生的缺頁率3）頁面置換算法-最近最久未使用（LRU）算法關(guān)鍵字：頁面置換，最近最久未使用，看未來等目錄1.設(shè)計(jì)目的 42.問題描述 53.需求分析 6HYPERLINK5.詳細(xì)設(shè)計(jì) 106.調(diào)試分析 167.使用說明 178.設(shè)計(jì)總結(jié) 179.參考文獻(xiàn) 18HYPERLINK";}}cout<<endl;cout<<"命中率："<<n-(K+1)<<"/"<<n<<endl;}功能模塊介紹5-4主函數(shù)圖1主菜單模塊程序中必須有的，負(fù)責(zé)調(diào)度函數(shù)的各個(gè)功能，是各個(gè)功能的紐帶，負(fù)責(zé)整個(gè)程序的運(yùn)行，2顯示模塊主要包含顯示函數(shù)，用于顯示主菜單，顯示操作內(nèi)容比如進(jìn)程數(shù)，物理塊數(shù)，顯示每次換頁后的結(jié)果函數(shù),，此函數(shù)是顯示在LRU算法的執(zhí)行過程中每次換頁的情況。顯示一定不用換頁的函數(shù)、：此函數(shù)是顯示最近使用過的頁面，即不用換頁的結(jié)果。3判斷模塊包括數(shù)據(jù)輸入判斷，用來判斷輸入數(shù)據(jù)是否合理以及，進(jìn)入算法判斷，判斷是否進(jìn)入算法，還是退出程序，4lru模塊計(jì)算缺頁的主要函數(shù)，以及記錄缺頁次數(shù)，計(jì)算缺頁率。6調(diào)試分析1實(shí)例測試數(shù)據(jù)1010241008內(nèi)存狀態(tài)111111111100000000022222844444具體數(shù)據(jù)見下圖2算法改進(jìn)設(shè)想本程序有缺陷，不能再次一自定義的形式輸入，要想輸入還需要人為輸入要想進(jìn)行的下一組數(shù)據(jù)，改進(jìn)方法，設(shè)計(jì)重輸入機(jī)制，用戶可以在選擇面板上重新輸入想要進(jìn)行的下一組數(shù)據(jù)，可以添加一個(gè)報(bào)錯(cuò)機(jī)制，當(dāng)你輸入的超過規(guī)定的進(jìn)程數(shù)時(shí)會出現(xiàn)報(bào)錯(cuò)。在這個(gè)系統(tǒng)中我沒有添加，因?yàn)楫?dāng)用戶輸入時(shí)會根據(jù)自己想要的進(jìn)程數(shù)輸入，要是不給加以控制會浪費(fèi)內(nèi)存。7使用說明7-2示例圖示例圖說明隨機(jī)輸入一個(gè)數(shù)，產(chǎn)生320個(gè)隨機(jī)數(shù)然后將三百二十個(gè)隨機(jī)數(shù)調(diào)入內(nèi)存物理塊數(shù)為四產(chǎn)生三十二頁計(jì)算缺頁率（因數(shù)據(jù)太多只截取部分）8設(shè)計(jì)總結(jié)頁面置換算法理解比較容易，要求實(shí)現(xiàn)的是LRU算法的實(shí)現(xiàn)。分配到我的lru算法，沒有去編寫只是寫出了大概的思路和算法框圖。其實(shí)這算法的程序編寫比較容易，雖然不全是自己編寫的，一部分是參考的網(wǎng)上的例題，但是通過對每一語句的理解，自己弄懂了整個(gè)程序的執(zhí)行原理。但是，在編寫過程中自己還是遇到了一些問題。沒有明白320條指令的意思經(jīng)過改進(jìn)知道了并改寫了程序。編程的時(shí)候覺得程序的函數(shù)定義有輔助函數(shù)，當(dāng)我在定義這個(gè)輔助函數(shù)有困難，因?yàn)槔锩娴暮瘮?shù)要相互聯(lián)系，編程時(shí)沒有考慮好整體算法思路，所以報(bào)錯(cuò)機(jī)制沒有做好，我以后再做是會事先做好整體的設(shè)計(jì)在著手編寫。最大的一個(gè)問題就是算法的正確實(shí)現(xiàn)，在程序的編寫時(shí)自己的編程技術(shù)不好，程序編的也很繁瑣，但是基本的要求已經(jīng)實(shí)現(xiàn)了，希望這次的實(shí)驗(yàn)是自己動手的一個(gè)開始，自己應(yīng)該更加努力，再接再厲。9.參考文獻(xiàn)【1】湯小丹、梁紅兵、哲鳳屏、湯子瀛編著.計(jì)算機(jī)操作系統(tǒng)（第三版）.西安：西安電子科技大學(xué)出版社，2007.5 【2】史美林編.計(jì)算機(jī)操作系統(tǒng)教程.北京：清華大學(xué)出版社，1999.11【3】徐甲同編著.操作系統(tǒng)教程.西安：西安電子科技大學(xué)出版社，1996.8 【4】Clifford，A.Shaffer編著.數(shù)決結(jié)構(gòu)與算法分析(C++版).北京：電子工業(yè)出版社，2005.7【5】蔣立翔編著.C++程序設(shè)計(jì)技能百練.北京：中國鐵道出版社，2004.110．程序源代碼#include<iostream.h>#include<stdlib.h>#include<conio.h>#include<stdio.h>#defineBsize4typedefstructBLOCK//聲明一種新類型--物理塊類型{intpagenum;//頁號intaccessed;//訪問字段，其值表示多久未被訪問}BLOCK;intpc;//程序計(jì)數(shù)器，用來記錄指令的序號intn;//缺頁計(jì)數(shù)器，用來記錄缺頁的次數(shù)staticinttemp[320];//用來存儲320條隨機(jī)數(shù)BLOCKblock[Bsize];//定義一大小為4的物理塊數(shù)組//*************************************************************voidinit();//程序初始化函數(shù)intfindExist(intcurpage);//查找物理塊中是否有該頁面intfindSpace();//查找是否有空閑物理塊intfindReplace();//查找應(yīng)予置換的頁面voiddisplay();//顯示voidsuijishu();//產(chǎn)生320條隨機(jī)數(shù),顯示并存儲到temp[320]voidpagestring();//顯示調(diào)用的頁面隊(duì)列voidLRU();//LRU算法//voidinit(){for(inti=0;i<Bsize;i++){block[i].pagenum=-1;block[i].accessed=0;pc=n=0;if((i+1)%10==0)cout<<endl;}}//intfindExist(intcurpage)//查找物理塊中是否有該頁面{for(inti=0;i<Bsize;i++){if(block[i].pagenum==curpage)returni;//檢測到內(nèi)存中有該頁面，返回block中的位置}return-1;}intfindSpace()//查找是否有空閑物理塊{for(inti=0;i<Bsize;i++){if(block[i].pagenum==-1)returni;//找到空閑的block，返回block中的位置}return-1;}intfindReplace()//查找應(yīng)予置換的頁面{intpos=0;for(inti=0;i<Bsize;i++){if(block[i].accessed>block[pos].accessed)pos=i;//找到應(yīng)予置換頁面，返回BLOCK中位置}returnpos;}voiddisplay(){for(inti=0;i<Bsize;i++){if(block[i].pagenum!=-1){printf("%02d",block[i].pagenum);}}cout<<endl;}voidsuijishu(){intflag=0;printf("請輸入一個(gè)0~320之間的隨機(jī)數(shù)：\n");scanf("%d",&pc);printf("按照要求產(chǎn)生的320個(gè)隨機(jī)數(shù)：\n");for(inti=0;i<320;i++){temp[i]=pc;if(flag%2==0)pc=++pc%320;//順序執(zhí)行下一條指令，即序號為m+1的指令 if(flag==1)pc=rand()%(pc-1);//通過隨機(jī)數(shù)，跳轉(zhuǎn)到前地址部分[0,m-1]中的某條指令處，其序號為m1 if(flag==3)pc=pc+1+(rand()%(320-(pc+1)));//通過隨機(jī)數(shù)，