快捷導(dǎo)航

利用C語言實(shí)現(xiàn)頁面置換算法的詳細(xì)過程

更新時(shí)間：2022年11月25日 10:53:47 作者：braylon_zhang

一個(gè)好的頁面置換算法,應(yīng)具有較低的頁面更換頻率,從理論上講,應(yīng)該保留最近重復(fù)訪問的頁面,將以后都不再訪問或者很長時(shí)間內(nèi)不再訪問的頁面調(diào)出,下面這篇文章主要給大家介紹了關(guān)于利用C語言實(shí)現(xiàn)頁面置換算法的相關(guān)資料,需要的朋友可以參考下

操作系統(tǒng)實(shí)驗(yàn)

頁面置換算法（FIFO、LRU、OPT）

概念：

1.最佳置換算法（OPT）（理想置換算法）：從主存中移出永遠(yuǎn)不再需要的頁面；如無這樣的頁面存在，則選擇最長時(shí)間不需要訪問的頁面。于所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時(shí)間內(nèi)不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。

2.先進(jìn)先出置換算法（FIFO）：是最簡單的頁面置換算法。這種算法的基本思想是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇駐留主存時(shí)間最長的頁面進(jìn)行淘汰，即先進(jìn)入主存的頁面先淘汰。其理由是：最早調(diào)入主存的頁面不再被使用的可能性最大。

3．最近最久未使用（LRU）算法：這種算法的基本思想是：利用局部性原理，根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁面，在最近的將來可能也不會再被訪問。所以，這種算法的實(shí)質(zhì)是：當(dāng)需要淘汰一個(gè)頁面時(shí)，總是選擇在最近一段時(shí)間內(nèi)最久不用的頁面予以淘汰。

題目：

編寫一個(gè)程序，實(shí)現(xiàn)本章所述的FIFO、LRU和最優(yōu)頁面置換算法。首先，生成一個(gè)隨機(jī)的頁面引用串，其中頁碼范圍為0-9.將這個(gè)隨機(jī)頁面引用串應(yīng)用到每個(gè)算法，并記錄每個(gè)算法引起的缺頁錯(cuò)誤的數(shù)量。實(shí)現(xiàn)置換算法，一遍頁面幀的數(shù)量可以從1~7。

代碼

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int numbers[20]={7,0,1,2,
                 0,3,0,4,
                 2,3,0,3,
                 2,1,2,0,
                 1,7,0,1};//本地?cái)?shù)據(jù)，與課本一致，方便測試
int nums=0;//輸入棧的個(gè)數(shù)，為了方便使用，
int stack[20][7]={10};

void begin();
void randomnum();//用于產(chǎn)生隨機(jī)數(shù)
void init();//初始化
void FIFO();//FIFO算法
void LRU();//LRU算法
void OPT();//最優(yōu)頁面置換算法（OPT）
void print();//輸出

int main() {
    begin();
    FIFO();
    LRU();
    OPT();
    return 0;
}
void begin()//開始菜單界面
{
    int i,j,k;
    printf("請輸入頁面幀的數(shù)量(1-7)：");
    scanf("%d",&nums);
    for(k=0;;k++)
    {
        printf("是否使用隨機(jī)數(shù)產(chǎn)生輸入串（0：是，1：否）");
        scanf("%d",&j);
        if(j==0)
        {
            randomnum();
            break;
        }
        else if(j==1)
        {
            break;
        }
        else
        {
            printf("請輸入正確的選擇！\n");
        }
    }

    printf("頁面引用串為：\n");
    for(i=0;i<20;i++)
    {
        printf("%d  ",numbers[i]);
    }
    printf("\n");
    init();
}
void randomnum()//如果需要使用隨機(jī)數(shù)生成輸入串，調(diào)用該函數(shù)
{
    srand(time(0));//設(shè)置時(shí)間種子
    for(int i = 0; i < 20; i++) {
        numbers[i] = rand() % 10;//生成區(qū)間0`9的隨機(jī)頁面引用串
    }
}
void init()//用于每次初始化頁面棧中內(nèi)容，同時(shí)方便下面輸出的處理
{
    int i,j;
    for(i=0;i<20;i++)
        for(j=0;j<nums;j++)
            stack[i][j]=10;
}

void print()//輸出各個(gè)算法的棧的內(nèi)容
{
    int i,j;
    for(i=0;i<nums;i++)
    {
        for(j=0;j<20;j++)
        {
            if(stack[j][i]==10)
                printf("*  ");
            else
                printf("%d  ",stack[j][i]);
        }
        printf("\n");
    }

}

void FIFO()//FIFO算法
{
    init();
    int i,j=1,n=20,k,f,m;
    stack[0][0]=numbers[0];

    for(i=1;i<20;i++)
    {
        f=0;
        for(m=0;m<nums;m++)
        {
            stack[i][m]=stack[i-1][m];
        }
        for(k=0;k<nums;k++)
        {
            if(stack[i][k]==numbers[i])
            {
                n--;
                f=1;
                break;
            }
        }
        if(f==0)
        {
            stack[i][j]=numbers[i];
            j++;
        }
        if(j==nums)
            j=0;
    }
    printf("\n");
    printf("FIFO算法：\n");
    print();
    printf("缺頁錯(cuò)誤數(shù)目為：%d\n",n);
}

void LRU()//LRU算法
{
    int i,j,m,k,sum=1,f;
    int sequence[7]={0};//記錄序列
    init();
    stack[0][0]=numbers[0];
    sequence[0]=nums;
    for(i=1;i<nums;i++)//前半部分，頁面空置的情況
    {
        for(j=0;j<nums;j++)
        {
            stack[i][j]=stack[i-1][j];
        }

        for(j=0;j<nums;j++)  //判斷要插入的是否在棧中已經(jīng)存在
        {
            f=0;
            if(stack[i][j]==numbers[i])
            {
                f=1;
                sum--;
                sequence[j]=nums;
                break;
            }
        }

        for(j=0;j<nums;j++)
        {
            if(sequence[j]==0&&f==0)
            {
                stack[i][j]=numbers[i];
                sequence[i]=nums;//最近使用的優(yōu)先級列為最高
                break;
            }
        }
        for(j=0;j<i;j++)//將之前的優(yōu)先級序列都減1
        {
            if(sequence[j]!=0)
               sequence[j]--;
        }
        //sequence[i]=nums;
        sum++;
    }

    for(i=nums;i<20;i++)//頁面不空，需要替換的情況
    {
        int f;
        f=0;
        for(j=0;j<nums;j++)
        {
            stack[i][j]=stack[i-1][j];
        }
        for(j=0;j<nums;j++)//判斷輸入串中的數(shù)字，是否已經(jīng)在棧中
        {
            if(stack[i][j]==numbers[i])
            {
                f=1;
                k=j;
                break;
            }
        }
        if(f==0)//如果頁面棧中沒有，不相同
        {
            for(j=0;j<nums;j++)//找優(yōu)先序列中為0的
            {
                if(sequence[j]==0)
                {
                    m=j;
                    break;
                }
            }
            for(j=0;j<nums;j++)
            {
                sequence[j]--;
            }
            sequence[m]=nums-1;
            stack[i][m]=numbers[i];
            sum++;
        }
        else//如果頁面棧中有，替換優(yōu)先級
        {
           if(sequence[k]==0)//優(yōu)先級為最小優(yōu)先序列的
           {
               for(j=0;j<nums;j++)
               {
                   sequence[j]--;
               }
               sequence[k]=nums-1;
           }
           else if(sequence[k]==nums-1)//優(yōu)先級為最大優(yōu)先序列的
           {
               //無需操作
           }
           else//優(yōu)先級為中間優(yōu)先序列的
           {
               for(j=0;j<nums;j++)
               {
                   if(sequence[k]<sequence[j])
                   {
                       sequence[j]--;
                   }
               }
               sequence[k]=nums-1;
           }
        }
    }
    printf("\n");
    printf("LRU算法：\n");
    print();
    printf("缺頁錯(cuò)誤數(shù)目為：%d\n",sum);
}

void OPT()//OPT算法
{
    int i,j,k,sum=1,f,q,max;
    int seq[7]={0};//記錄序列
    init();
    stack[0][0]=numbers[0];
    seq[0]=nums-1;

    for(i=1;i<nums;i++)//前半部分，頁面空置的情況
    {
        for(j=0;j<nums;j++)
        {
            stack[i][j]=stack[i-1][j];
        }

        for(j=0;j<nums;j++)  //判斷要插入的是否在棧中已經(jīng)存在
        {
            f=0;
            if(stack[i][j]==numbers[i])
            {
                f=1;
                sum--;
                //b++;
                seq[j]=nums;
                break;
            }
        }

        for(j=0;j<nums;j++)
        {
            if(seq[j]==0&&f==0)
            {
                stack[i][j]=numbers[i];
                seq[j]=nums;//最近使用的優(yōu)先級列為最高
                break;
            }
//            else if(seq[j]==0&&f==1){
//                b++;
//                sum--;
//                seq[j]=nums-1;
//                break;
//            }
        }
        for(j=0;j<nums;j++)//將之前的優(yōu)先級序列都減1
        {
            if(seq[j]!=0)
               seq[j]--;
        }

        sum++;
    }
    for(i=nums;i<20;i++)//后半部分，頁面棧中沒有空的時(shí)候情況
    {
        //k=nums-1;//最近的數(shù)字的優(yōu)先級
        for(j=0;j<nums;j++)//前面的頁面中內(nèi)容賦值到新的新的頁面中
        {
            stack[i][j]=stack[i-1][j];
        }
        for(j=0;j<nums;j++)
        {
            f=0;
            if(stack[i][j]==numbers[i])
            {
                f=1;
                break;
            }
        }
        if(f==0)//頁面中沒有，需要替換的情況
        {
            for(q=0;q<nums;q++)//優(yōu)先級序列中最大的就是最久不會用的，有可能出現(xiàn)后面沒有在用過的情況
            {
                seq[q]=20;
            }
            for(j=0;j<nums;j++)//尋找新的優(yōu)先級
            {
                for(q=i+1;q<20;q++)
                {
                    if(stack[i][j]==numbers[q])
                    {
                        seq[j]=q-i;
                        break;
                    }
                }
            }
            max=seq[0];
            k=0;
            for(q=0;q<nums;q++)
            {
                if(seq[q]>max)
                {
                    max=seq[q];
                    k=q;
                }
            }
            stack[i][k]=numbers[i];
            sum++;
        }
        else
        {
            //頁面棧中有需要插入的數(shù)字，無需變化，替換的優(yōu)先級也不需要變化
        }
    }
    printf("\n");
    printf("OPT算法：\n");
    print();
    printf("缺頁錯(cuò)誤數(shù)目為：%d\n",sum);
}

運(yùn)行結(jié)果截圖：

頁面幀數(shù)目為4的時(shí)候，使用隨機(jī)產(chǎn)生串

測試與書上例子是否有出入

使用隨機(jī)串

總結(jié)

設(shè)置多個(gè)數(shù)組，一個(gè)用來模仿棧，一個(gè)用來存要存取的頁面，還有在OPT算法和LRU算法中，記錄棧中每個(gè)數(shù)據(jù)的替換優(yōu)先級。
之前的代碼寫的有點(diǎn)爛，重新看了一次才感覺之前的有多爛，哈哈哈哈哈，這個(gè)代碼能在linux上跑通的，在windows上肯定也沒得問題

您可能感興趣的文章: