“計(jì)算機(jī)操作系統(tǒng)”課程設(shè)計(jì)大作業(yè)

頁(yè)面置換算法模擬實(shí)驗(yàn)（含完整資料，可直接提交）一、題目： 頁(yè)面置換算法模擬實(shí)驗(yàn)二、目的分別采用最佳（Optimal）置換算法、先進(jìn)先出（FIFO）頁(yè)面置換算法和最近最少使用（LRU）置換算法對(duì)用戶輸入的頁(yè)面號(hào)請(qǐng)求序列進(jìn)行淘汰和置換，從而加深對(duì)頁(yè)面置換算法的理解。三、內(nèi)容和要求請(qǐng)用C/C++語(yǔ)言編一個(gè)頁(yè)面置換算法模擬程序。用戶通過鍵盤輸入分配的物理內(nèi)存總塊數(shù)，再輸入用戶邏輯頁(yè)面號(hào)請(qǐng)求序列，然后分別采用最佳（Optimal）置換算法、先進(jìn)先出（FIFO）頁(yè)面置換算法和最近最少使用（LRU）置換算法三種算法對(duì)頁(yè)面請(qǐng)求序列進(jìn)行轉(zhuǎn)換，最后按照課本P150頁(yè)圖4-26的置換圖格式輸出每次頁(yè)面請(qǐng)求后各物理塊內(nèi)存放的虛頁(yè)號(hào)，并算出總的缺頁(yè)率（缺頁(yè)次數(shù)/總的請(qǐng)求次數(shù)）。最后三種頁(yè)面置換算法的優(yōu)缺點(diǎn)。三種頁(yè)面置換算法的思想可參考教材P149-P152頁(yè)。假設(shè)頁(yè)面號(hào)請(qǐng)求序列為4、3、2、1、4、3、5、4、3、2、1、5,當(dāng)分配給某進(jìn)程的物理塊數(shù)分別為3塊和4塊時(shí)，試用自己編寫的模擬程序進(jìn)行頁(yè)面轉(zhuǎn)換并輸出置換圖和缺頁(yè)次數(shù)、缺頁(yè)率四、提交內(nèi)容本大作業(yè)每個(gè)人必須單獨(dú)完成。最后需提交的內(nèi)容包括：源程序（關(guān)鍵代碼需要注釋說明）、可運(yùn)行程序、運(yùn)行結(jié)果、算法思路及流程圖、心得體會(huì)。大作業(yè)嚴(yán)禁抄襲。發(fā)現(xiàn)抄襲一律以不及格論。請(qǐng)大家嚴(yán)格按照大作業(yè)題目來編寫程序，不要上交以前布置的大作業(yè)。如果提交的大作業(yè)題目與本文檔要求不符，成績(jī)一律為及格。目錄TOC\o"1-5"\h\z摘要 2%正文 2\o"CurrentDocument"1、設(shè)計(jì)思路 32、各模塊的偽碼算法 63、函數(shù)的調(diào)用關(guān)系圖 144、測(cè)試 20設(shè)計(jì)總結(jié) 21參考文獻(xiàn) 22致謝 23\o"CurrentDocument"附錄：部分源程序代碼 24UNIX中，為了提高內(nèi)存利用率，提供了內(nèi)外存進(jìn)程對(duì)換機(jī)制；內(nèi)存空間的分配和回收均以頁(yè)為單位進(jìn)行；一個(gè)進(jìn)程只需將其一部分（段或頁(yè)）調(diào)入內(nèi)存便可運(yùn)行；還支持請(qǐng)求調(diào)頁(yè)的存儲(chǔ)管理方式。當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，發(fā)現(xiàn)其所在頁(yè)面不在內(nèi)存，就立即提出請(qǐng)求（向CPU發(fā)出缺頁(yè)中斷），由系統(tǒng)將其所需頁(yè)面調(diào)入內(nèi)存。這種頁(yè)面調(diào)入方式叫請(qǐng)求調(diào)頁(yè)，為實(shí)現(xiàn)請(qǐng)求調(diào)頁(yè)，核心配置了四種數(shù)據(jù)結(jié)構(gòu)：頁(yè)表、頁(yè)框號(hào)、訪問位、修改位、有效位、保護(hù)位等。此設(shè)計(jì)為了了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)學(xué)生的能力。關(guān)鍵字UNIX 請(qǐng)求調(diào)頁(yè) 數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)管理編輯器調(diào)試C程序一、設(shè)計(jì)思路頁(yè)面置換算法：當(dāng)CPU接收到缺頁(yè)中斷信號(hào)，中斷處理程序先保存現(xiàn)場(chǎng)，分析中斷原因，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過查找頁(yè)表，得到該頁(yè)所在外存的物理塊號(hào)。如果此時(shí)內(nèi)存未滿，能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須按某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出，是否重新寫盤由頁(yè)表的修改位決定，然后將缺頁(yè)調(diào)入，修改頁(yè)表。利用修改后的頁(yè)表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過程對(duì)用戶是透明的。此設(shè)計(jì)為了了解UNIX的命令及使用格式，熟悉UNIX/LINUX的常用基本命令，練習(xí)并掌握UNIX提供的vi編輯器來編譯C程序，學(xué)會(huì)利用gcc、gdb編譯、調(diào)試C程序，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問題，培養(yǎng)學(xué)生的動(dòng)手能力。二、設(shè)計(jì)目的1、用C語(yǔ)言實(shí)現(xiàn)頁(yè)面置換算法。2、了解內(nèi)存分頁(yè)管理策略3、掌握調(diào)頁(yè)策略4、掌握一般常用的調(diào)度算法5.選取調(diào)度算法中的典型算法，模擬實(shí)現(xiàn)。三、設(shè)計(jì)任務(wù)在Window98/2000系統(tǒng)的環(huán)境下運(yùn)行程序；通過從一般常用的調(diào)頁(yè)算法中選取典型算法程序，了解頁(yè)面管理的相關(guān)細(xì)節(jié)，并用程序設(shè)計(jì)實(shí)現(xiàn)該算法實(shí)驗(yàn)。四、設(shè)計(jì)內(nèi)容與步驟分頁(yè)存儲(chǔ)管理將一個(gè)進(jìn)程的邏輯地址空間分成若干大小相等的片，稱為頁(yè)面或頁(yè)。五、調(diào)頁(yè)策略1）何時(shí)調(diào)入頁(yè)面如果進(jìn)程的許多頁(yè)是存放在外存的一個(gè)連續(xù)區(qū)域中，則一次調(diào)入若干個(gè)相鄰的頁(yè)，會(huì)比一次調(diào)入一頁(yè)的效率更高效一些。但如果調(diào)入的一批頁(yè)面中的大多數(shù)都未被訪問，則又是低效的?？刹捎靡环N以預(yù)測(cè)為基礎(chǔ)的預(yù)調(diào)頁(yè)策略，將那些預(yù)計(jì)在不久之后便會(huì)被訪問的頁(yè)面，預(yù)先調(diào)入內(nèi)存。如果預(yù)測(cè)較準(zhǔn)確，那么，這種策略顯然是很有吸引力的。但目前預(yù)調(diào)頁(yè)的成功率僅為50%。且這種策略主要用于進(jìn)程的首次調(diào)入時(shí)，由程序員指出應(yīng)該先調(diào)入哪些頁(yè)。2)請(qǐng)求調(diào)頁(yè)策略當(dāng)進(jìn)程在運(yùn)行中需要訪問某部分程序和數(shù)據(jù)時(shí)，若發(fā)現(xiàn)其所在的頁(yè)面不在內(nèi)存，便即提出請(qǐng)求，由os將其所需頁(yè)面調(diào)入內(nèi)存。由請(qǐng)示調(diào)頁(yè)策略所確定調(diào)入的頁(yè)，是一定會(huì)被訪問的，再加之請(qǐng)求調(diào)頁(yè)策略比較易于實(shí)現(xiàn)，故在目前的虛擬存儲(chǔ)器中，大多采用此策略。但這種策略每次僅調(diào)入一頁(yè)，故須花費(fèi)較大的系統(tǒng)開銷，增加了磁盤I/O的啟用頻率。3)從何處調(diào)入頁(yè)面在請(qǐng)求分頁(yè)系統(tǒng)中的外存分為兩部分：用于存放文件的文件區(qū)和用于存放對(duì)換頁(yè)面的對(duì)換區(qū)。通常，由于對(duì)換區(qū)是采用連續(xù)分配方式，而事件是采用離散分配方式，故對(duì)換區(qū)的磁盤I/O速度比文件區(qū)的高。這樣，每當(dāng)發(fā)生缺頁(yè)請(qǐng)求時(shí)，系統(tǒng)應(yīng)從何處將缺頁(yè)調(diào)入內(nèi)存，可分成如下三種情況：(1)系統(tǒng)擁有足夠的對(duì)換區(qū)空間，這時(shí)可以全部從對(duì)換區(qū)調(diào)入所需頁(yè)面，以提高調(diào)頁(yè)速度。為此，在進(jìn)程運(yùn)行前，便須將與該進(jìn)程有關(guān)的文件，從文件區(qū)拷貝到對(duì)換區(qū)。(2)系統(tǒng)缺少足夠的對(duì)換區(qū)空間，這時(shí)凡是不會(huì)被修改的文件，都直接從文件區(qū)調(diào)入；而當(dāng)換出這些頁(yè)面時(shí)，由于它們未被修改而不必再將它們換出時(shí)，以后需要時(shí)，再?gòu)膶?duì)換區(qū)調(diào)入。(3)UNIX方式。由于與進(jìn)程有關(guān)的文件都放在文件區(qū)，故凡是未運(yùn)行過的頁(yè)面，都從文件區(qū)調(diào)入。而對(duì)于曾經(jīng)運(yùn)行過但又被換出的頁(yè)面，由于被放在對(duì)換區(qū)，因此在下次時(shí)，應(yīng)從對(duì)換區(qū)調(diào)入。由于UNIX系統(tǒng)允許頁(yè)面共享，因此，某進(jìn)程所請(qǐng)求的頁(yè)面有可能已被其它進(jìn)程調(diào)入內(nèi)存，此時(shí)也就無須再?gòu)膶?duì)換區(qū)調(diào)入。3頁(yè)面調(diào)入過程每當(dāng)程序所要訪問的頁(yè)面未在內(nèi)存時(shí)，便向CPU發(fā)出一缺頁(yè)中斷，中斷處理程序首先保留CPU環(huán)境，分析中斷原因后，轉(zhuǎn)入缺頁(yè)中斷處理程序。該程序通過查找頁(yè)表，得到該頁(yè)在外在原物理塊后，如果此時(shí)內(nèi)存能容納新頁(yè)，則啟動(dòng)磁盤I/O將所缺之頁(yè)調(diào)入內(nèi)存，然后修改頁(yè)表。如果內(nèi)存已滿，則須先按照某種置換算法從內(nèi)存中選出一頁(yè)準(zhǔn)備換出；如果該頁(yè)未被修改過，可不必將該頁(yè)寫回磁盤；但如果此頁(yè)已被修改，則必須將它寫回磁盤，然后再把所缺的頁(yè)調(diào)入內(nèi)存，并修改頁(yè)表中的相應(yīng)表項(xiàng)，置其存在位“1”，并將此頁(yè)表項(xiàng)寫入快表中。在缺頁(yè)調(diào)入內(nèi)存后，利用修改后的頁(yè)表，去形成所要訪問數(shù)據(jù)的物理地址，再去訪問內(nèi)存數(shù)據(jù)。整個(gè)頁(yè)面的調(diào)入過程對(duì)用戶是透明的。六、頁(yè)面置換算法在進(jìn)程運(yùn)行過程中，若其所要訪問的頁(yè)面不在內(nèi)存而需把它們調(diào)入內(nèi)存，但內(nèi)存已無空閑空間時(shí)，為了保證該進(jìn)程能正常運(yùn)行，系統(tǒng)必須從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送磁盤的對(duì)換區(qū)中。但應(yīng)將哪個(gè)頁(yè)面調(diào)出，須根據(jù)一定的算法來確定。通常，把選擇換出頁(yè)面的算法稱為頁(yè)面置換算法(Page_ReplacementAlgorithms)。一個(gè)好的頁(yè)面置換算法，應(yīng)具有較低的頁(yè)面更換頻率。從理論上講，應(yīng)將那些以后不再會(huì)訪問的頁(yè)面換出，或?qū)⒛切┰谳^長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問的頁(yè)面調(diào)出。㈠常見置換算法①最佳置換算法（Optimal）：它是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰頁(yè)面，將是以后永不使用的或許是在最長(zhǎng)（未來）時(shí)間內(nèi)不再被訪問的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人目前還無法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，因而該算法是無法實(shí)現(xiàn)的，便可以利用此算法來評(píng)價(jià)其它算法。②先進(jìn)先出缶邛。）頁(yè)面置換算法：這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。該算法實(shí)現(xiàn)簡(jiǎn)單只需把一個(gè)進(jìn)程已調(diào)入內(nèi)存的頁(yè)面，按先后次序鏈接成一個(gè)隊(duì)列，并設(shè)置一個(gè)指針，稱為替換指針，使它總是指向最老的頁(yè)面。③LRU置換算法：LRU（LeastRecentlyUsed）置換算法的描述FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。由于無法預(yù)測(cè)各頁(yè)面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問字段，用來記錄一個(gè)頁(yè)面自上次被訪問以來所經(jīng)歷的時(shí)間t,，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰。七、各模塊的偽碼算法(1)先進(jìn)先出算法偽碼算法voidfifo()本設(shè)計(jì)含源文件等全套完整設(shè)計(jì)資料聯(lián)系Q：1415736481獲取代做其它設(shè)計(jì)題目queye-3;十十本設(shè)計(jì)含源文件等全套完整設(shè)計(jì)資料聯(lián)系Q：1415736481獲取代做其它設(shè)計(jì)題目無先先出的缺頁(yè)率比.未使用警法的缺艮率為C""F二'新建文件夾\Debus\CppLexe”03333423O3444修整09003311116元道先出算法:012036"ressanykeytocontinueMu算法：7012036?TT修1N200120312R017IZH201H1791177Q3121201701白匕修修21113322(d 7 7711902 2 21G00Q0G444SSO300SO1113333333最佳覃換算法的缺頁(yè)率為:缺貝率：45.0^最佳置換OPT算法;701203642^772222229177311111本設(shè)計(jì)含源文件等全套完整設(shè)計(jì)資料聯(lián)系51415736481聯(lián)系51415736481獲取?代做其它設(shè)計(jì)盤目湯子瀛，哲鳳屏.《計(jì)算機(jī)操作系統(tǒng)》.西安電子科技大學(xué)學(xué)出版社..王清，李光明，《計(jì)算機(jī)操作系統(tǒng)》.冶金工業(yè)出版社..孫鐘秀等，操作系統(tǒng)教程.高等教育出版社.曾明，Linux操作系統(tǒng)應(yīng)用教程.陜西科學(xué)技術(shù)出版社..張麗芬，劉利雄.《操作系統(tǒng)實(shí)驗(yàn)教程》.清華大學(xué)出版社..孟靜，操作系統(tǒng)教程一一原理和實(shí)例分析.高等教育出版社.周長(zhǎng)林，計(jì)算機(jī)操作系統(tǒng)教程.高等教育出版社.張堯?qū)W，計(jì)算機(jī)操作系統(tǒng)教程，清華大學(xué)出版社.任滿杰，操作系統(tǒng)原理實(shí)用教程，電子工業(yè)出版社這次課程設(shè)計(jì)，我從“紙上談兵”到可以自己動(dòng)腦動(dòng)手分析調(diào)試程序，收獲不少。首先要感謝有了這次實(shí)踐的機(jī)會(huì)，給了自己一個(gè)舞臺(tái)，同時(shí)也是對(duì)自身的檢驗(yàn)。還有多虧了老師們從理論到上機(jī)親自指導(dǎo)的辛苦教授，給予了我們最大幫助和全面指導(dǎo)，在這里，尤其感謝我的指導(dǎo)老師***老師、以及我的《操作系統(tǒng)》的授課老師***老師，你們不辭辛苦，在給很多學(xué)生指導(dǎo)的情況下還不厭其煩的給我們心指導(dǎo)，在這里，我衷心向你們致謝！最后還要感謝熱心的同學(xué)們，在我陷入誤區(qū)的時(shí)候，是他們熱心的幫助使我擺脫困境。最后衷心感謝所有給予我?guī)椭椭笇?dǎo)的老師和同學(xué)，沒有他們的幫助我的程序也不會(huì)完成得這么順利。附錄：部分源程序代碼#include””charfind(intj);intfindo(intj);intl(intj);intqueye;doublequeyelu;charz='％';chara[4][20]={'7','0','1','2','0','3','0','4','2','3','0','3','2','1','2','0',T,'7','0',T};//chara口口；〃先進(jìn)先出算法voidfifo()〃先進(jìn)先出算法(inti=2,m,j;queye=1