頁面置換算法模擬實(shí)驗(yàn)報(bào)告

..實(shí)驗(yàn)編號(hào)４名稱頁面置換算法模擬實(shí)驗(yàn)?zāi)康耐ㄟ^請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法模擬設(shè)計(jì),以便：1、了解虛擬存儲(chǔ)技術(shù)的特點(diǎn)2、掌握請(qǐng)求頁式存儲(chǔ)管理中頁面置換算法實(shí)驗(yàn)內(nèi)容與步驟設(shè)計(jì)一個(gè)虛擬存儲(chǔ)區(qū)和內(nèi)存工作區(qū),并使用FIFO和LRU算法計(jì)算訪問命中率。<程序設(shè)計(jì)> 先用srand<>函數(shù)和rand<>函數(shù)定義和產(chǎn)生指令序列,然后將指令序列變換成相應(yīng)的頁地址流,并針對(duì)不同的算法計(jì)算相應(yīng)的命中率。<程序1>#include<windows.h> //Windows版,隨機(jī)函數(shù)需要,GetCurrentProcessId<>需要//#include<stdlib.h>//Linux版,隨機(jī)函數(shù)srand和rand需要#include<stdio.h> //printf<>需要#defineTRUE1#defineFALSE0#defineINVALID-1#defineNULL0#definetotal_instruction320 //共320條指令#definetotal_vp32 //虛存頁共32頁#defineclear_period50 //訪問次數(shù)清零周期typedefstruct{//定義頁表結(jié)構(gòu)類型〔頁面映射表PMT intpn,pfn,counter,time;//頁號(hào)、頁框號(hào)<塊號(hào)>、一個(gè)周期內(nèi)訪問該頁面的次數(shù)、訪問時(shí)間}PMT;PMTpmt[32];typedefstructpfc_struct{//頁面控制結(jié)構(gòu) intpn,pfn; structpfc_struct*next;}pfc_type;pfc_typepfc[32];pfc_type*freepf_head,*busypf_head,*busypf_tail;//空閑頁頭指針,忙頁頭指針,忙頁尾指針intNoPageCount;//缺頁次數(shù)inta[total_instruction];//指令流數(shù)組intpage[total_instruction],offset[total_instruction];//每條指令的頁和頁內(nèi)偏移voidinitialize<int>;voidFIFO<int>;//先進(jìn)先出voidLRU<int>;//最近最久未使用voidNRU<int>;//最近最不經(jīng)常使用/****************************************************************************main<>*****************************************************************************/voidmain<>{ inti,s;//srand<10*getpid<>>;//用進(jìn)程號(hào)作為初始化隨機(jī)數(shù)隊(duì)列的種子//Linux版 srand<10*GetCurrentProcessId<>>;//用進(jìn)程號(hào)作為初始化隨機(jī)數(shù)的種子//Windows版 s=rand<>%320;//在[0,319]的指令地址之間隨機(jī)選取一起點(diǎn)m for<i=0;i<total_instruction;i+=4>{//產(chǎn)生指令隊(duì)列 if<s<0||s>319>{ printf<"wheni==%d,error,s==%d\n",i,s>; exit<0>; } a[i]=s;//任意選一指令訪問點(diǎn)m?！矊㈦S機(jī)數(shù)作為指令地址m a[i+1]=a[i]+1;//順序執(zhí)行下一條指令 a[i+2]=rand<>%<s+2>;//在[0,m+1]的前地址之間隨機(jī)選取一地址,記為m' a[i+3]=a[i+2]+1;//順序執(zhí)行一條指令 s=a[i+2]+<int>rand<>%<320-a[i+2]>;//在[m',319]的指令地址之間隨機(jī)選取一起點(diǎn)m if<<a[i+2]>318>||<s>319>>printf<"a[%d+2,anumberwhichis:%dands=%d\n",i,a[i+2],s>; } for<i=0;i<total_instruction;i++>{//將指令序列變成頁地址流 page[i]=a[i]/10; offset[i]=a[i]%10;} for<i=4;i<=32;i++>{//內(nèi)存塊分別為4塊、5塊、...32塊時(shí)的命中率printf<"%2dpageframes",i>;FIFO<i>;//計(jì)算用FIFO置換時(shí),有i個(gè)內(nèi)存塊時(shí)的命中率LRU<i>;//最近最久未使用 NRU<i>;//最近最不經(jīng)常使用 printf<"\n">; }}/***************************************************************************initialize<>形參：內(nèi)存塊數(shù)功能：初始化*****************************************************************************/voidinitialize<inttotal_pf>//初始化相關(guān)數(shù)據(jù)結(jié)構(gòu),形參total_pf是用戶進(jìn)程的內(nèi)存頁面數(shù){ inti; NoPageCount=0;//缺頁次數(shù),初始化為0 for<i=0;i<total_vp;i++>{ pmt[i].pn=i;//填邏輯頁號(hào) pmt[i].pfn=INVALID;//物理頁面號(hào)為-1 pmt[i].counter=0;//置頁面控制結(jié)構(gòu)中的訪問次數(shù)為0 pmt[i].time=-1; //置頁面控制結(jié)構(gòu)中的時(shí)間為-1 } for<i=0;i<total_pf-1;i++>{//建立pfc[i-1]和pfc[i]之間的連接 pfc[i].next=&pfc[i+1];pfc[i].pfn=i; } pfc[total_pf-1].next=NULL; pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0];//頁面隊(duì)列的頭指針為pfc[0]}/*****************************************************************************FIFO算法形參：內(nèi)存塊數(shù)輸出：命中率*****************************************************************************/voidFIFO<inttotal_pf>//形參total_pf是用戶進(jìn)程的內(nèi)存頁面數(shù){ inti; pfc_type*p; initialize<total_pf>;//初始化相關(guān)數(shù)據(jù)結(jié)構(gòu) busypf_head=busypf_tail=NULL; for<i=0;i<total_instruction;i++>{//訪問每條指令 if<pmt[page[i]].pfn==INVALID>{//缺頁 NoPageCount+=1;//失效<缺頁>次數(shù)增1 if<freepf_head==NULL>{//無空閑頁面 p=busypf_head->next; pmt[busypf_head->pn].pfn=INVALID; freepf_head=busypf_head;//釋放忙頁面隊(duì)列的第一個(gè)頁面 freepf_head->next=NULL; busypf_head=p; } p=freepf_head->next;//按FIFO方式調(diào)新頁面入內(nèi)存 freepf_head->next=NULL; freepf_head->pn=page[i]; pmt[page[i]].pfn=freepf_head->pfn; if<busypf_tail==NULL>busypf_head=busypf_tail=freepf_head; else{ busypf_tail->next=freepf_head;//free頁面減少一個(gè) busypf_tail=freepf_head; } freepf_head=p; } } printf<"FIFO:%6.4f",1-<float>NoPageCount/320>; }/****************************************************************************LRU算法〔最近最久未使用形參：內(nèi)存塊數(shù)輸出：命中率*****************************************************************************/voidLRU<inttotal_pf>//形參total_pf是給用戶進(jìn)程的內(nèi)存塊數(shù){ intmin,minj,i,j,present_time;initialize<total_pf>; present_time=0; for<i=0;i<total_instruction;i++>{ if<pmt[page[i]].pfn==INVALID>{//頁面失效 NoPageCount++; if<freepf_head==NULL>{//無空閑頁面 min=32767; for<j=0;j<total_vp;j++>//找出time的最小值 if<min>pmt[j].time&&pmt[j].pfn!=INVALID>{min=pmt[j].time; minj=j; } freepf_head=&pfc[pmt[minj].pfn];//騰出一個(gè)單元 pmt[minj].pfn=INVALID; pmt[minj].time=-1; freepf_head->next=NULL; } pmt[page[i]].pfn=freepf_head->pfn;//有空閑頁面,改為有效 pmt[page[i]].time=present_time; freepf_head=freepf_head->next;//減少一個(gè)free頁面 } elsepmt[page[i]].time=present_time;//更新該頁面的訪問時(shí)間〔并非真的時(shí)間,而是循環(huán)次數(shù),每執(zhí)行一條指令,時(shí)間加1 present_time++;//當(dāng)前時(shí)間加1 } printf<"LRU:%6.4f",1-<float>NoPageCount/320>;}/****************************************************************************NRU算法〔最近最不經(jīng)常使用形參：內(nèi)存塊數(shù)輸出：命中率*****************************************************************************/voidNRU<inttotal_pf>{ inti,j,dp,cont_flag,old_dp; initialize<total_pf>; dp=0;for<i=0;i<total_instruction;i++>{ if<pmt[page[i]].pfn==INVALID>{//缺頁 NoPageCount++; if<freepf_head==NULL>{//無空閑頁面 cont_flag=TRUE; old_dp=dp; while<cont_flag> if<pmt[dp].counter==0&&pmt[dp].pfn!=INVALID>cont_flag=FALSE; else{ dp++;if<dp==total_vp>dp=0; if<dp==old_dp> for<j=0;j<total_vp;j++> pmt[j].counter=0; } freepf_head=&pfc[pmt[dp].pfn]; pmt[dp].pfn=INVALID; freepf_head->next=NULL; } pmt[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } else pmt[page[i]].counter=1; if<i%clear_period==0> for<j=0;j<total_vp;j++> pmt[j].counter=0; } printf<"NUR:%6.4f",1-<float>NoPageCount/320>;}實(shí)驗(yàn)結(jié)果〔寫出結(jié)果,截圖也可總結(jié)〔收獲,未實(shí)現(xiàn)的步驟這次操作系統(tǒng)課程設(shè)計(jì),讓我們對(duì)操作系統(tǒng)有了更深的認(rèn)識(shí),首先操作系統(tǒng)是一管理電腦硬件與軟件資源的程序,同時(shí)也是計(jì)算機(jī)系統(tǒng)內(nèi)核與基石。操作系統(tǒng)是一個(gè)龐大的管理控制程序,大致包括5個(gè)方面的管理功能：進(jìn)程與處理機(jī)管理、作業(yè)管理、存儲(chǔ)管理、設(shè)備管理、文件管理。我們這次課程設(shè)計(jì)的題目是頁面置換算法,是屬于存儲(chǔ)器管理。在進(jìn)程運(yùn)行過程中,若其訪