天天看點
傳回

作業系統課設(頁面置換算法C++版)

運作結果

（1）data.txt文本檔案：

作業系統課設(頁面置換算法C++版)
圖1 輸入檔案

将頁面引用串輸入到名為data.txt的文本檔案中，以空格隔開。

（2）各種置換算法的輸出結果：

作業系統課設(頁面置換算法C++版)
圖2 OPT頁面置換算法運作結果
作業系統課設(頁面置換算法C++版)
圖3 FIFO頁面置換算法運作結果
作業系統課設(頁面置換算法C++版)
圖4 LRU頁面置換算法運作結果      
圖5 Clock頁面置換算法運作結果      
圖6 LRU頁面置換算法運作結果

完整代碼 

#include <iostream>
#include <vector>
#include <string>
#include <fstream>

#define random(a,b) (rand()%(b-a)+a)

using namespace std;

// 總虛頁數
int t;
// 實頁數
int size;
// 序列
vector<int> v;

// 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
void print(vector<pair<int, vector<int>>> res, int lackPageNum, int totalNum){

    for (int i = 0; i < size; ++i) {

        // 周遊每一個序列的第i個數
        for (int j = 0; j < res.size(); ++j) {
            printf("|");
            pair<int, vector<int>> cur = res[j];

            int isLack = cur.first;
            vector<int> v = cur.second;
            if(!isLack || v.size() < (i + 1)){
                printf("   ");
            }else{
                printf("%3d", v[i]);
            }
            printf("  ");
        }
        puts("|");
    }

    printf("缺頁數為：%d\n", lackPageNum);
    printf("命中數：%d\n", (totalNum - lackPageNum));
    printf("缺頁率為：%.3f%%\n", (lackPageNum * 100.0 / totalNum));
    printf("命中率為：%.3f%%\n", ((totalNum - lackPageNum) * 100.0 / totalNum));
}

void FIFO(){

    // 結果<是否缺頁,頁面>
    vector<pair<int, vector<int>>> res;

    // 上一頁
    vector<int> pre;

    // 判斷是否缺頁的
    bool flag;

    int lackPageNum = 0;

    for(int num: v){

        flag = true; // 是否缺頁

        for (int i = 0; i < pre.size(); ++i) {
            if(num == pre[i]){
                flag = false;
            }
        }

        if(!flag){
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){

            pre.push_back(num);

        }else{

            // 缺頁則換出隊頭
            pre.erase(pre.begin());
            pre.push_back(num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("FIFO(先進先出)算法：\n");
    print(res, lackPageNum, t);
    puts("");
    puts("");
}

void LRU(){

    // <是否缺頁,頁面>
    vector<pair<int, vector<int>>> res;

    // 上一頁
    vector<int> pre;

    // 判斷是否缺頁的
    bool flag;
    // 缺頁數
    int lackPageNum = 0;

    // 目前頁在隊中那個位置
    int idx = 0;

    for(int num: v){

        flag = true; // 是否缺頁

        for (int i = 0; i < pre.size(); ++i) {
            if(num == pre[i]){
                flag = false;
                idx = i;
            }
        }

        if(!flag){
            // 換到隊頭
            pre.erase(pre.begin() + idx);
            pre.insert(pre.begin(), num);
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){
            pre.insert(pre.begin(), num);
        }else{
            // 缺頁則換出隊尾
            pre.erase(pre.end()-1);
            pre.insert(pre.begin(), num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("LRU(最近最久未使用)算法：\n");
    print(res, lackPageNum, t);
    puts("");
    puts("");
}

void OPT(){

    // <是否缺頁,頁面>
    vector<pair<int, vector<int>>> res;

    // 上一頁
    vector<int> pre;

    // 判斷是否缺頁的
    bool flag;
    // 缺頁數
    int lackPageNum = 0;

    for(int k = 0; k < v.size(); k++){

        int num = v[k];
        flag = true; // 是否缺頁

        for (int i = 0; i < pre.size(); ++i) {
            if(num == pre[i]){
                flag = false;
            }
        }

        if(!flag){
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){
            pre.push_back(num);
        }else{
            // 最後面的數在v中的位置
            int last = -1;
            // 最後面的數在pre中的位置
            int idx;
            // 目前pre[i] 是否存在與v中
            bool isExit;
            // 缺頁則換出pre中在v序列最後面的或者不在後面的序列的
            for (int i = 0; i < pre.size(); ++i) {
                isExit = false;
                for (int j = k + 1; j < v.size(); ++j) {
                    if(pre[i] == v[j]){
                        isExit = true;
                        if(j > last){
                            idx = i;
                            last = j;
                        }
                        break;
                    }
                }
                // 目前pre[i] 根本不在v中,則直接退出循環
                if(!isExit){
                    idx = i;
                    break;
                }
            }

            pre.erase(pre.begin() + idx);
            pre.insert(pre.begin()+ idx, num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("OPT(最佳)置換算法：\n");
    print(res, lackPageNum, t);
    puts("");
    puts("");
}

void setToOne(int &num, int idx){
    num = num + (1 << idx);
}

// 統一右移
void rightMove(vector<pair<int, int>> & visNum){

//    puts("");
    for(pair<int, int> &p: visNum){
//        printf("%d ", p.second);
        p.second = p.second >> 1;
    }

//    puts("");
}
// 判斷是否在visNum中
bool isExit(vector<pair<int, int>> & visNum, int num){
    for(pair<int, int> &p: visNum){
        if(p.first == num){
            return true;
        }
    }
    return false;
}
// 找到某個數在隊列中的索引
int findIdx(vector<pair<int, int>> & visNum, int num){
    for (int i = 0; i < visNum.size(); ++i) {
        pair<int, int> p = visNum[i];
        if(p.first == num){
            return i;
        }
    }
    return -1;
}

// 找到 freq 最小的在 pre 中的位置
int findMinIdx(vector<pair<int, int>> visNum, vector<int> pre){

    int id = -1;
    int min = (1 << 31) - 1;

    for (int i = 0; i < pre.size(); ++i) {
        for (int j = 0; j < visNum.size(); ++j) {
            pair<int, int> p = visNum[j];
            if(pre[i] == p.first && p.second < min){
                id = i;
                min = p.second;
            }
        }
    }
    return id;
}

void LFU(){

    vector<pair<int, vector<int>>> res;
    vector<int> pre;

    // 記錄通路頻率<數, 頻率>
    vector<pair<int, int>> visNum;
    int lackPageNum = 0;

    for (int num: v) {

        bool flag = true;
        rightMove(visNum);

        for (int i = 0; i < pre.size(); ++i) {
            if(pre[i] == num){
                flag = false;
            }
        }

        if(!flag){
            int idx = findIdx(visNum, num);
            setToOne(visNum[idx].second, 30);
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        bool isEx = isExit(visNum, num);

        if(pre.size() < size){
            pre.push_back(num);
            visNum.push_back({num, (1 << 30)});
        }else{

            if(!isEx){
                visNum.push_back({num, (1 << 30)});
            }else{
                int idx = findIdx(visNum, num);
                setToOne(visNum[idx].second, 30);
            }

            int idx = findMinIdx(visNum, pre);

            pre.erase(pre.begin() + idx);
            pre.push_back(num);
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("LFU(最少使用)置換算法：\n");
    print(res, lackPageNum, t);

    puts("");
    puts("");
}

// 1 3 4 2 5 6 3 4 7
void CLK(){

    vector<pair<int, vector<int>>> res;

    vector<int> pre;
    int vis[t + 5];

    int lackPageNum = 0;
    bool flag;

    // 指針
    int idx = 0;

    for (int num: v) {
        flag = true;
        for (int i = 0; i < pre.size(); ++i) {
            if(pre[i] == num){
                vis[i] = 1;
                flag = false;
            }
        }

        if(!flag){
            res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end())));
            continue;
        }

        lackPageNum++;

        if(pre.size() < size){
            pre.push_back(num);
            vis[pre.size()-1] = 1;
        }else{

            while (true){

                if(!vis[idx]){
                    pre.erase(pre.begin() + idx);
                    pre.insert(pre.begin() + idx, num);
                    vis[idx] = 1;
                    idx = (idx + 1) % size;
                    break;
                }

                vis[idx] = 0;
                idx = (idx + 1) % size;
            }
        }

        res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end())));
    }

    printf("NRU(最近未用)置換算法：\n");
    print(res, lackPageNum, t);

    puts("");
    puts("");
}


void init1(){

    printf("可用實體塊大小：");
    scanf("%d", &size);
    printf("調入序列長度：");
    scanf("%d", &t);

    int num;

    printf("請輸入調入頁面序列：");

    printf("");
    for (int i = 0; i < t; ++i) {
        scanf("%d", &num);
        v.push_back(num);
    }
}

void init2(){

    ifstream df("../data.txt");

    if (!df.is_open()){

        cout << "Error opening file";
        exit (1);
    }
    df >> size;
    df >> t;
    int num;
    for (int i = 0; i < t; ++i) {
        df >> num;
        v.push_back(num);
    }

    df.close();
}

void init3(){

    int a = 1, b = 10;
    size = 3;
    t = 20;
    int num;

    for (int i = 0; i < t; ++i) {
        num = random(a, b);
        v.push_back(num);
    }
}

int main(){

//    int num = 1;
//    setToOne(num, 4);
//    cout << num;

//    init1();
    init2();
//    init3();

    printf("\n\n\n通路序列：");
    for (int i = 0; i < v.size(); ++i) {
        printf("%d  ", v[i]);
    }

    puts("");

    FIFO();
    LRU();
    OPT();
    LFU();
    CLK();


    // Test
//    vector<pair<int, int>> vp;
//    vp.push_back({3, 8});
//    rightMove(vp);
//    setToOne(vp[0].second, 30);
//    cout << vp[0].second;

    return 0;
}
算法 c++ 作業系統 頁面置換 缺頁
上一篇: 11月8日作業參考答案
下一篇: [C語言]基于連結清單的學生管理系統(大一第一學期的課設報告及代碼)

繼續閱讀