操作系統(tǒng)課程設(shè)計(jì)頁(yè)面置換算法(LRU算法)參考模板

1、實(shí) 驗(yàn) 報(bào) 告題 目名 稱頁(yè)面置換算法(LRU算法)院 系信 息 學(xué) 院班 級(jí)1106402完成時(shí)間2013-05-17指導(dǎo)老師肖賽男本次實(shí)驗(yàn)成績(jī)組長(zhǎng)聯(lián)系電話李國(guó)件地址394600097組員（姓名，學(xué)號(hào)）呂赟1106402-38主要任務(wù)算法的組織，綜合調(diào)度，程序運(yùn)行界面的實(shí)現(xiàn)組員（姓名，學(xué)號(hào)）蔡祥1106402-09主要任務(wù)算法的實(shí)現(xiàn)，測(cè)試，實(shí)驗(yàn)報(bào)告的完成主要原理及所參考的資料（實(shí)驗(yàn)原理：頁(yè)面置換算法(LRU算法) 假定一個(gè)能夠存放M個(gè)頁(yè)面的內(nèi)存，當(dāng)發(fā)生缺頁(yè)時(shí)，調(diào)入一個(gè)頁(yè)面，通過(guò)LRU算法求出應(yīng)該置換出的頁(yè)面號(hào)。輸入一連串的頁(yè)面號(hào)，程序自動(dòng)選擇調(diào)出的頁(yè)面并計(jì)算缺頁(yè)率。

2、設(shè)計(jì)頁(yè)面置換算法，這里采用最近最久未使用置換算法LRU。LRU算法的實(shí)現(xiàn)要?dú)w功于一個(gè)8位的寄存器的實(shí)現(xiàn)。1 / 7包括實(shí)驗(yàn)內(nèi)容及條件）主要參考書計(jì)算機(jī)操作系統(tǒng)原理 西安大學(xué)出版社 湯子瀛主編操作系統(tǒng) 電子工業(yè)出版社 William Stallings著主要算法流程圖（包括實(shí)驗(yàn)步驟）算法流程圖：輸入頁(yè)面訪問(wèn)序號(hào)取訪問(wèn)頁(yè)的頁(yè)號(hào)查夜表是否缺頁(yè)否置換出寄存器數(shù)組頁(yè)面標(biāo)號(hào)最小的頁(yè)面是按算法不同淘汰一頁(yè)面調(diào)入所訪問(wèn)的頁(yè)面實(shí)驗(yàn)說(shuō)明：執(zhí)行程序時(shí)，當(dāng)主存沒有可用頁(yè)面時(shí)，為了選擇淘汰主存中的哪一頁(yè)面，騰出1個(gè)空閑塊以便存放新調(diào)入的頁(yè)面。淘汰哪個(gè)頁(yè)面的首要問(wèn)題是選擇何種置換算法。該程序采用LRU方法選擇，依置換策略

3、選擇一個(gè)可置換的頁(yè)面并計(jì)算它們的缺頁(yè)率以便比較。本實(shí)驗(yàn)涉及的主要算法細(xì)節(jié)說(shuō)明（包括數(shù)據(jù)結(jié)構(gòu)）#include<math.h>#include<conio.h>#define M 3#include<stdio.h>int reg2M;int count;int num;int N;/*初始化函數(shù)，數(shù)組reg0i存放頁(yè)面號(hào)，初始化為-1，reg1i當(dāng)作寄存器，初始化為0*/void init()int i;count=0;num=0; N=pow(2,7); /*二進(jìn)制數(shù)10000000*/for(i=0;i<M;i+)reg0i=-1;reg1i=0;

4、/*尋找數(shù)組a中的最小值，返回最小值對(duì)應(yīng)的下標(biāo)*/int min(int a)int i,index=0;int min=a0;for(i=1;i<M;i+)if(min>ai)min=ai;index=i;return index;/*判斷頁(yè)面號(hào)x是否在數(shù)組中，如果在，返回對(duì)應(yīng)的下標(biāo)；否則返回-1*/int isIn(int x,int a)int i;int index=-1;for(i=0;i<M;i+)if(ai=x)index=i;break;return index;/*判斷虛擬的內(nèi)存中是否已經(jīng)存滿了頁(yè)面，如果滿了，則返回-1，沒有滿則返回找到空的對(duì)應(yīng)的第一個(gè)下標(biāo)

5、*/int isFull(int a)int i,index=-1;for(i=0;i<M;i+)if(ai=-1)index=i;break;return index;/*頁(yè)面置換方法*/void swap(int x)int i,k,temp,temp0;int index=isIn(x,reg0); /*判斷x是否在reg0數(shù)組中*/if(index!=-1)reg1index=reg1indexN; /*reg1index異或二進(jìn)制數(shù)10000000*/elsetemp=isFull(reg0);if(temp!=-1) /*內(nèi)存沒有滿，直接調(diào)入頁(yè)面*/reg0temp=x;re

6、g1temp=reg1tempN;else if(temp=-1)k=min(reg1); /*置換出寄存器中數(shù)值最小的對(duì)應(yīng)的下標(biāo)的頁(yè)面*/temp0=reg0k; /*臨時(shí)保留要換出的頁(yè)面號(hào)*/reg0k=x;reg1k=reg1kN;printf("the page %d is exchanged out!n",temp0);/*打印要置換出的頁(yè)號(hào)*/count+; /*置換次數(shù)加1*/for(i=0;i<M;i+)reg1i=reg1i>>1; /*寄存器中的所有數(shù)右移一位*/main()int x;system("cls");i

7、nit();printf("Input a sort of pagesn");printf("while you input -1 ,it will stop!n");scanf("%d",&x);/*輸入頁(yè)面號(hào)，直到頁(yè)面號(hào)為-1*/while(x!=-1)num+; /*輸入的頁(yè)面次數(shù)加1*/swap(x);scanf("%d",&x);/*打印缺頁(yè)數(shù)和缺頁(yè)率*/printf("the count of Exchanged is: %d n",count);printf(&qu

8、ot;the rate of exchanged is: %fn",count*1.0/num);getch();本次實(shí)踐計(jì)劃、進(jìn)度安排及完成情況05月09號(hào)商討如何實(shí)現(xiàn)本次實(shí)驗(yàn)以及同學(xué)之間的分工.05月10號(hào)查閱相關(guān)資料.05月16號(hào)05月17號(hào)基本完成程序修改完善程序.代碼測(cè)試.完成實(shí)驗(yàn)報(bào)告.主要測(cè)試方法及測(cè)試數(shù)據(jù)，包括測(cè)試結(jié)果及測(cè)試人實(shí)驗(yàn)結(jié)果：Input a sort of pageswhile you input -1 ,it will stop!7012the page 7 is exchanged out!03the page 1 is exchanged out!04t

9、he page 2 is exchanged out!2the page 3 is exchanged out!43the page 0 is exchanged out!0the page 2 is exchanged out!-1The count of exchange is: 6The rate of exchange is: 0.500000本次實(shí)驗(yàn)的心得體會(huì)（每位同學(xué)一段）李國(guó)紅通過(guò)這次實(shí)驗(yàn)，讓我了解了頁(yè)式存儲(chǔ)管理的過(guò)程。在這次實(shí)驗(yàn)中，我首次用了C中重要的但我們又不常用的按位異或操作和移位操作來(lái)實(shí)現(xiàn)寄存器的功能，使我對(duì)C有更深的認(rèn)識(shí)。本次實(shí)驗(yàn)也讓我學(xué)到了LRU算法。呂赟通過(guò)本次課程設(shè)計(jì)，對(duì)LRU頁(yè)面調(diào)度算法有了更深入的理解和掌握，進(jìn)一步的鞏固和復(fù)習(xí)了操作系統(tǒng)中關(guān)于LRU頁(yè)面調(diào)度算法的知識(shí)，進(jìn)一步的了解結(jié)構(gòu)化、模塊化程序設(shè)計(jì)的方法蔡祥通過(guò)這次實(shí)驗(yàn)，讓我了解了頁(yè)面儲(chǔ)存管理