課程設(shè)計的報告 頁面置換算法-先進(jìn)先出算法

...wd......wd......wd...淮陰工學(xué)院操作系統(tǒng)課程設(shè)計報告選題名稱:頁面置換算法系〔院〕: 管理工程學(xué)院 專業(yè): 信息管理與信息系統(tǒng) 班級:信管1131姓名:周夏青、張婷婷學(xué)號:1131807102、1131807103指導(dǎo)教師:陸華奇、邱軍林學(xué)年學(xué)期: 2015~2016學(xué)年第1學(xué)期 2015 年12 月20 日頁面置換算法——先進(jìn)先出算法一、實驗?zāi)康摹安僮飨到y(tǒng)課程設(shè)計〞是理解和穩(wěn)固操作系統(tǒng)基理論、原理和方法的重要實踐環(huán)節(jié)。主要任務(wù)是實現(xiàn)操作系統(tǒng)和相關(guān)系統(tǒng)軟件的設(shè)計，其中涉及進(jìn)程創(chuàng)立，同步，進(jìn)程間通信，存儲管理，文件系統(tǒng)等操作系統(tǒng)概念。先進(jìn)先出算法給出頁面訪問的順序與分配給作業(yè)的主存塊數(shù)，使用隊列作為數(shù)據(jù)構(gòu)造編寫算法，實現(xiàn)統(tǒng)計缺頁次數(shù)與頁面置換操，用C語言編程并用文檔形式給出算法分析與實現(xiàn)過程。二、實驗要求1、輸入當(dāng)前要調(diào)用的頁面號a[i]2、判斷該頁面是否已在隊列內(nèi)，〔1〕假設(shè)在隊列內(nèi)，不執(zhí)行任何操作〔2〕假設(shè)不在隊列內(nèi)。那么執(zhí)行以下操作3、判斷隊列是否已滿〔1〕假設(shè)隊列未滿，直接把該頁面號a[i]存入隊列〔2〕假設(shè)隊列已滿，刪除并返回隊頭元素，然后把該頁面號a[i]存入隊列4、輸出置換次數(shù)，依次輸出置換出的頁面三、實驗內(nèi)容FIFO算法總是淘汰最先調(diào)入主存的頁面，即淘汰在主存中駐留時間最長的頁面，認(rèn)為駐留時間最長的頁不再使用的可能性較大。代碼如下：#include<stdio.h>#defineM24#defineN4voidFIFO(inta[N],intb[M]){inti,j,k;intc[M]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};floats;for(i=0;i<N;i++){a[i]=b[i];for(j=0;j<=i;j++){printf("%d",a[j]);}printf("\n");}k=N;for(j=N;j<M;j++){for(i=0;i<N;i++)if(b[j]==a[i]){c[j]=1;break;}if(c[j]==1){for(i=0;i<N;i++)printf("%d",a[i]);}if(c[j]==0){a[k%N]=b[j];k++;for(i=0;i<N;i++)printf("%d",a[i]);}printf("\n");}s=k*1.0/M;printf("中斷次數(shù)為：%d\n",k);printf("缺頁率為：%f\n",s);}voidmain(){inta[N]={0,0,0,0};intb[M]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,5,2,6,4};FIFO(a,b);}〔如圖1-2〕圖SEQ圖\*ARABIC1圖SEQ圖\*ARABIC2其運行結(jié)果如下：圖SEQ圖\*ARABIC3假設(shè)改變置換總次數(shù)，其運行如下：〔如圖4-6〕圖SEQ圖\*ARABIC4圖SEQ圖\*ARABIC5圖SEQ圖\*ARABIC6假設(shè)改變物理塊，其運行結(jié)果如下：〔如圖7-9〕圖SEQ圖\*ARABIC7圖SEQ圖\*ARABIC8圖SEQ圖\*ARABIC9由結(jié)果可以看出,使用FIFO算法，總是淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面以淘汰。四、實驗總結(jié)通過這次課程設(shè)計，我們組能夠進(jìn)一步掌握一些關(guān)于內(nèi)存分配管理的算法，進(jìn)一步了解了什么是缺頁中斷，以及處理缺頁中斷的調(diào)度算法。通過合作編程，我們都加深了對理論學(xué)習(xí)的理解。這個程序的主要思想就是要實現(xiàn)換頁，若何樣輸出淘汰的序列，計算缺頁次數(shù)和缺頁率。在程序中主要就是將在訪問串中將來再也不出現(xiàn)的或是在離當(dāng)前最遠(yuǎn)的位置上出現(xiàn)的頁淘汰掉。當(dāng)距離相等的時候就比較使用的次數(shù)，淘汰使用次數(shù)較少的那頁。該過程就可以用FIFO算法來實現(xiàn)，當(dāng)主函數(shù)調(diào)用任意其中函數(shù)時來實現(xiàn)其算法。參考書目1、計算機操作系統(tǒng)教程徐甲同等編西安電子科技大學(xué)出版社2、計算機操作系統(tǒng)〔第三版〕湯小丹、梁紅兵、哲鳳屏、湯子瀛編著的西安電子科技大學(xué)出版3、C語言程序設(shè)計教程李清政、葉斌、雷輝、陳世強主編中國鐵道出版社4、C++面向?qū)ο蟪绦蛟O(shè)計李濤、李琳、陳良斌等編著高等教育出版社5、計算機操作系統(tǒng)教程周長林等編高等教育出版社指導(dǎo)教師評語學(xué)號11318071021131807103姓名周夏青、張婷婷班級信管1131選題名稱數(shù)據(jù)排序序號評價內(nèi)容權(quán)重〔%〕得分1考勤記錄、學(xué)習(xí)態(tài)度、工作作風(fēng)與表現(xiàn)。52自學(xué)情況：上網(wǎng)檢索機時數(shù)、文獻(xiàn)閱讀情況〔筆記〕。103論文選題是否先進(jìn)，是否具有前沿性或前瞻性。54成果驗收：是否完成設(shè)計任務(wù)；能否運行、可操作性若何等。205報告的格式標(biāo)準(zhǔn)程度、是否圖文并茂、語言標(biāo)準(zhǔn)及流暢程度；主題是否鮮明、重心是否突出、論述是否充分、結(jié)論是否正確；是否提出了自