1、實驗?zāi)康?/span>

（1）熟悉虛擬存儲器頁面置換過程；

（2）通過編寫和調(diào)試頁面置換算法的模擬程序以加深對頁面置換算法的理解；

（3）掌握LRU算法的原理；

（4）熟悉OPT和FIFO頁面置換算法原理。

2、 實驗要求??

??? 編寫并調(diào)試一個頁面置換模擬程序，采用LRU（最近最久未使用頁面置換）算法。已知系統(tǒng)為一進程分配的物理塊數(shù)，進程運行過程中引用的頁面號，編程使用LRU算法輸出置換的頁號、缺頁中斷次數(shù)及缺頁率。

3、算法描述

??? LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t，當(dāng)須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。 如下圖所示（第一行數(shù)據(jù)是進程運行過程中引用的頁號，假設(shè)開始時3個物理塊是空的）：

4、源程序代碼

#include<stdio.h>
#define N 3 //物理塊的個數(shù) 
int Nl = 20;//頁面訪問序列的長度 
void LRU(int block[],int blockN,int list[],int listN)//LRU替換算法
{
    int  i, j;//定義替換次數(shù)
	int rep1 = 0;//缺頁次數(shù)
	int rep2 = 0;//置換頁面次數(shù)
	int DisplacedPages[20] = {0};
    int time[N];//各個物理塊最近一次訪問至現(xiàn)在的時間

    for(i = 0;i < blockN;i++)//初始化 
        time[i] = 0;
 
    for(i = 0;i < listN; i++)
	{   
		for(j = 0; j < blockN; j++) //更新時間記錄 
			if(block[j] != -1)
                time[j]++;
        for(j = 0; j < blockN; j++)
            if(block[j] == list[i]) //命中 
			{
                time[j] = 0;
                break;
            }
            else if(block[j] == -1) //未命中但塊中為空 
            	break;
		if(j < blockN && block[j] == -1)//未命中且物理塊未滿,直接存入
		{
            block[j] = list[i];
            time[j] = 0; 
			rep1++;
        }
        else if(j == blockN)//需要替換 
		{
            int max = 0;
            for(int k = 0;k < blockN;k++)//尋找最久未訪問的地址所在的物理塊的位置
			{
                if(time[max] < time[k])
                    max = k;
            }
			DisplacedPages[rep2] = block[max];
			rep2++;
			rep1++;
            block[max] = list[i];
            time[max] = 0;
        }
        
        printf("當(dāng)前訪問的頁面為：%d\n",list[i]);
		printf("訪問后物理塊內(nèi)的頁面為：");
    	for(int m = 0;m < blockN;m++)//顯示當(dāng)前物理塊的狀態(tài) 
		{
        	if(block[m] == -1)
            	break;
        	printf("|%d|  ",block[m]);
    	}
		if (j == blockN)
			printf("置換了%d\n", DisplacedPages[rep2-1]);
    	printf("\n");
    }
    
    printf("缺頁的次數(shù)為:%d  缺頁率:%d/%d=%.2f\n", rep1, rep1, listN, (float)(rep1)/(float)listN);
	printf("置換的頁面為：");
	for (i=0; i<rep2; i++)
		printf("%d,", DisplacedPages[i]);
}

int main()
{
	int block[N], list[20] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};//默認序列
	int df = 1;
    for(int i = 0;i < N;i++)//初始化 
    {
		block[i] = -1;
    } 
	printf("是否使用默認序列？(1:否  其他數(shù)字:是)");
	scanf("%d", &df);
   if (df == 1)
   {
	   printf("請輸入頁面?zhèn)€數(shù)：");
	   scanf("%d", &Nl);
	   printf("請輸入頁面訪問序列:\n");
	   for(i = 0;i < Nl;i++)
		   scanf("%d", &list[i]);
   }
   LRU(block, N, list, Nl);//調(diào)用LRU頁面置換算法 
   printf("\n");
   return 0;
} 

5、運行結(jié)果

文章來源地址http://www.zghlxwxcb.cn/news/detail-503334.html

到了這里，關(guān)于LRU頁面置換算法（C語言實現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！