頁面置換算法模擬實驗報告

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