欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2022年11月25日 10:53:47   作者:braylon_zhang  
一個(gè)好的頁面置換算法,應(yīng)具有較低的頁面更換頻率,從理論上講,應(yīng)該保留最近重復(fù)訪問的頁面,將以后都不再訪問或者很長(zhǎng)時(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)不再需要的頁面;如無這樣的頁面存在,則選擇最長(zhǎng)時(shí)間不需要訪問的頁面。于所選擇的被淘汰頁面將是以后永不使用的,或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。

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

3.最近最久未使用(LRU)算法:這種算法的基本思想是:利用局部性原理,根據(jù)一個(gè)作業(yè)在執(zhí)行過程中過去的頁面訪問歷史來推測(cè)未來的行為。它認(rèn)為過去一段時(shí)間里不曾被訪問過的頁面,在最近的將來可能也不會(huì)再被訪問。所以,這種算法的實(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ù),與課本一致,方便測(cè)試
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("請(qǐng)輸入頁面幀的數(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("請(qǐng)輸入正確的選擇!\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)先級(jí)列為最高
                break;
            }
        }
        for(j=0;j<i;j++)//將之前的優(yōu)先級(jí)序列都減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)先級(jí)
        {
           if(sequence[k]==0)//優(yōu)先級(jí)為最小優(yōu)先序列的
           {
               for(j=0;j<nums;j++)
               {
                   sequence[j]--;
               }
               sequence[k]=nums-1;
           }
           else if(sequence[k]==nums-1)//優(yōu)先級(jí)為最大優(yōu)先序列的
           {
               //無需操作
           }
           else//優(yōu)先級(jí)為中間優(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)先級(jí)列為最高
                break;
            }
//            else if(seq[j]==0&&f==1){
//                b++;
//                sum--;
//                seq[j]=nums-1;
//                break;
//            }
        }
        for(j=0;j<nums;j++)//將之前的優(yōu)先級(jí)序列都減1
        {
            if(seq[j]!=0)
               seq[j]--;
        }

        sum++;
    }
    for(i=nums;i<20;i++)//后半部分,頁面棧中沒有空的時(shí)候情況
    {
        //k=nums-1;//最近的數(shù)字的優(yōu)先級(jí)
        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)先級(jí)序列中最大的就是最久不會(huì)用的,有可能出現(xiàn)后面沒有在用過的情況
            {
                seq[q]=20;
            }
            for(j=0;j<nums;j++)//尋找新的優(yōu)先級(jí)
            {
                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)先級(jí)也不需要變化
        }
    }
    printf("\n");
    printf("OPT算法:\n");
    print();
    printf("缺頁錯(cuò)誤數(shù)目為:%d\n",sum);
}

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

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

測(cè)試與書上例子是否有出入

使用隨機(jī)串

總結(jié)

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

相關(guān)文章

  • C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)

    C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)

    這篇文章主要介紹了C語言中如何在結(jié)構(gòu)體內(nèi)定義函數(shù)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-02-02
  • C語言實(shí)現(xiàn)2048游戲(ege圖形庫版)

    C語言實(shí)現(xiàn)2048游戲(ege圖形庫版)

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)2048游戲,ege圖形庫版,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-12-12
  • C++Vector容器常用函數(shù)接口詳解

    C++Vector容器常用函數(shù)接口詳解

    最近我學(xué)習(xí)了C++中的STL庫中的vector容器,對(duì)于常用容器,我們不僅要會(huì)使用其常用的函數(shù)接口,我們還有明白這些接口在其底層是如何實(shí)現(xiàn)的。所以特意整理出來一篇博客供我們學(xué)習(xí)
    2022-08-08
  • C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式

    C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)正整數(shù)的四則運(yùn)算表達(dá)式,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-06-06
  • C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求

    C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求

    使用C++編程發(fā)送HTTP請(qǐng)求通常需要使用第三方的HTTP庫或框架,本文主要介紹了C++使用HTTP庫和框架輕松發(fā)送HTTP請(qǐng)求,感興趣的可以了解一下
    2023-12-12
  • C++單例設(shè)計(jì)模式詳細(xì)講解

    C++單例設(shè)計(jì)模式詳細(xì)講解

    單例模式(Singleton Pattern)是最簡(jiǎn)單的設(shè)計(jì)模式之一。這種類型的設(shè)計(jì)模式屬于創(chuàng)建型模式,它提供了一種創(chuàng)建對(duì)象的最佳方式,這種模式涉及到一個(gè)單一的類,該類負(fù)責(zé)創(chuàng)建自己的對(duì)象,同時(shí)確保只有單個(gè)對(duì)象被創(chuàng)建
    2022-06-06
  • Qt讀寫CSV文件的三種方式及優(yōu)劣對(duì)比

    Qt讀寫CSV文件的三種方式及優(yōu)劣對(duì)比

    最近的要用到CSV格式的數(shù)據(jù),所以這篇文章講述一下QT讀取CSV文件數(shù)據(jù),下面這篇文章主要給大家介紹了關(guān)于Qt讀寫CSV文件的三種方式及優(yōu)劣對(duì)比的相關(guān)資料,需要的朋友可以參考下
    2023-11-11
  • short與int轉(zhuǎn)換的小例子

    short與int轉(zhuǎn)換的小例子

    short與int轉(zhuǎn)換的小例子,需要的朋友可以參考一下
    2013-04-04
  • C語言與C++中關(guān)于字符串使用的比較

    C語言與C++中關(guān)于字符串使用的比較

    字符串是我們?cè)偈煜げ贿^的東西了,任何語言中字符串都是基礎(chǔ)都要經(jīng)常用到,那么在不同語言中字符串的用法一樣嗎?下面我們來看看C語言與C++中字符串使用的比較
    2022-05-05
  • c++和python實(shí)現(xiàn)順序查找實(shí)例

    c++和python實(shí)現(xiàn)順序查找實(shí)例

    這篇文章主要介紹了c++和python實(shí)現(xiàn)順序查找實(shí)例,流程即將目標(biāo)數(shù)值和數(shù)據(jù)庫中的每個(gè)數(shù)值進(jìn)行比較,如果相同則搜索完成,如果不同則繼續(xù)比較下一處,下面來看看具體的實(shí)例操作吧,需要的朋友可以參考一下
    2022-03-03

最新評(píng)論