【作業系統】模拟頁面置換算法、缺頁率計算（C++源碼）

模拟頁面置換算法、缺頁率計算

• ​​一、設計目的​​
• ​​二、問題描述​​
• ​​三、問題要求​​
• ​​四、算法流程圖​​
• ​​五、資料初始化​​
• ​​六、主要實作​​
• ​​七、進入模拟FIFO運算過程​​
• ​​八、顯示所有結果，程式結束​​
• ​​九、源代碼（C++）​​

一、設計目的

了解頁面置換算法。

二、問題描述

先進先出（FIFO）頁面置換算法程式設計，通過對FIFO算法的模拟，進一步了解程序的基本概念，加深對程序運作狀态和程序排程過程、排程算法的了解。

三、問題要求

用C++語言程式設計實作對FIFO算法的模拟。

四、算法流程圖

圖3-1 算法流程圖

五、資料初始化

六、主要實作

七、進入模拟FIFO運算過程

1. 循環初始化通路記憶體表（BS）為-100，主要目的是為了表示記憶體頁的一個空閑狀态。
2. 循環周遊我們的通路序列，從第一個開始一次判斷，如果目前這個通路數在記憶體頁清單内已近存在表示改值已經命中，進行下一次判斷，如果目前的下标小于記憶體塊數目則直接存入記為缺頁标記值（bno）加一，否則記為命中未缺頁，标記值（bno）加一。如果，目前的通路值不在記憶體塊序列中flag記為0，則記為缺頁将目前的值存入記憶體塊，并且标記值加一（bno）
3. 根據上一步中我們流下的标記值統計缺頁的操作次數，循環顯示每個序列号的缺頁情況，并且計算缺頁率。

八、顯示所有結果，程式結束

九、源代碼（C++）

#include<iostream>
using namespace std;  
  
#define Max1 25//通路序列數組大小  
#define Max2 15//記憶體塊表數組大小  
  
int saveCount[Max1][Max1];  
int x_save, y_save;  
int now_couont = 0;  
  
struct pt {  
    int pno;    //頁号  
    int bno;    //塊号  
    int flag;   //狀态位，為0時在不記憶體，為1時在記憶體  
    int order;  //優先序列  
};  
  
// 輸入   
void input(int *a, int n)  
{  
    for (int i = 0; i < n; i++) {  
        cin >> *a;  
        a++;  
    }  
}  
  
// 輸出序列  
void output(int *a, int n)  
{  
    for (int i = 0; i < n; i++) {  
        cout << *a << ' ';  
        a++;  
    }  
    cout << '\n';  
}  
  
// 算法本體  
void fifo(int*List_pages, int*bs, int n, int m)//n 序列個數  m 塊個數  
{  
    pt ptlist[Max1];//定義結構數組  
  
  
    int k = 0, flag, cn = 0, i, j;//cn——統計缺頁數  
    for (j = 0; j < m; j++)//賦初值 m 塊個數  
    {   
        bs[j] = -100;  
    }  
  
    for (i = 0; i < n; i++)// 通路序列循環  n 序列個數  
    {  
        flag = 0;  
        // 判斷目前的值是否已經在 記憶體塊中 ，如果在 flag 直接 = 1  
        for (j = 0; j < m; j++)  
            if (List_pages[i] == bs[j]) {  
                flag = 1;  
                break;  
            }  
  
        if (flag == 1)//命中  
        {  
            if (i >= m) {   
                ptlist[i].bno = j + 1;  
                ptlist[i].flag = 1; //命中，已存入，未缺頁  
                ptlist[i].pno = List_pages[i];//ye  
            }  
            else { // 前 m 頁直接載入就好了  
                ptlist[i].flag = 0;//缺頁，還未存入  
                ptlist[i].pno = List_pages[i];  
                bs[k] = List_pages[i];//将目前頁存入記憶體塊  
                ptlist[i].bno = k + 1;  
                k = (k + 1) % m;//循環隊列  
                cn++;  
            }  
        }  
        else { // 因為 目标值不在塊中  
            ptlist[i].flag = 0;//缺頁，還未存入  
            ptlist[i].pno = List_pages[i];  
  
            bs[k] = List_pages[i];//将目前頁存入記憶體塊  
            ptlist[i].bno = k + 1;  
            k = (k + 1) % m;//循環隊列  
            cn++;  
        }  
          
        cout << "第 " << i << "次進入 \n";  
        for (int i = 0; i < m; i++)  
        {  
            saveCount[now_couont][i] = bs[i];  
        }  
        now_couont++;  
    }  
    cout << "計算結果：\n";  
    cout << "---------------------------------------------------------------------\n";  
    cout << "缺頁個數：" << '\t' << cn << '\n';  
    cout << "---------------------------------------------------------------------\n";  
    cout << "通路次數：" << '\t' << n << '\n';  
    cout << "---------------------------------------------------------------------\n";  
    cout << "缺頁率為：" << '\t' << (float)cn / n << '\n';  
    cout << "---------------------------------------------------------------------\n";  
    cout << "操作順序：\n";  
    cout << "---------------------------------------------------------------------\n";  
    for (i = 0; i < m; i++)  
    {  
        cout << List_pages[i] << "\t!!缺頁,還未存入!!\t" << "現已直接存入記憶體塊!\t" << ptlist[i].bno << '\n';  
        cout << "本次序列： >>>>>  ";  
        for (int j = 0; j < y_save; j++)  
        {  
            if (saveCount[i][j] != -1 && saveCount[i][j] != -100)  
                cout << saveCount[i][j] << ' ';  
        }  
        cout << endl;  
        cout << "---------------------------------------------------------------------\n";  
    }  
    for (i = m; i < n; i++)  
    {  
        if (ptlist[i].flag == 0)  
            cout << List_pages[i] << "\t!!缺頁,還未存入!!\t" << "操作：調出塊号為：" << ptlist[i].bno << "--頁号為" << ptlist[i].pno << "的程序" << '\n';  
        else  
            cout << List_pages[i] << "\t!!命中,已經存入!!\t" << "操作：查詢塊号為：" << ptlist[i].bno << "--頁号為" << ptlist[i].pno << "的程序" << '\n';  
        cout << "本次序列： >>>>>  ";  
        for (int j = 0; j < y_save; j++)  
        {  
            if (saveCount[i][j] != -1 && saveCount[i][j] != -100)  
                cout << saveCount[i][j] << ' ';  
        }  
        cout << endl;  
        cout << "---------------------------------------------------------------------\n";  
    }  
  
}  
  
void initGroup(int x , int y)  
{  
    x_save = x;  
    y_save = y;  
    for (int i = 0; i < Max1; i++)  
        for (int j = 0; j < Max1; j++)  
            saveCount[i][j] = -1;  
}  
  
void main()  
{  
    int List_pages[Max1], bs[Max1];  
    int n, m;  
  
    cout << "輸入記憶體塊大小：\n";  
    cin >> m;  
    cout << "輸入序列個數：\n";  
    cin >> n;  
    initGroup(n, m);  
  
    cout << "請輸入通路序列：\n";  
    input(List_pages, n);  
    cout << "通路序列：" << endl;  
    output(List_pages, n);  
    cout << "---------------------------------------------------------------------\n";  
    cout << '\n';  
    fifo(List_pages, bs, n, m);  
}