FIFO和LRU算法实现操作系统中主存管理

🕗 发布于 2024-11-22 13:23 算法

FIFO，用数组实现

1和2都是使用nextReplace实现新页面位置的更新

1、不精确时间：用ctime输出运行时间都是0.00秒

#include <iostream>
#include <iomanip>
#include<ctime>//用于计算时间
using namespace std;

// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };

// FIFO算法
void fifo(int n) {
    int memory[5] = { -1, -1, -1, -1, -1 };  // 用于存储主存块，初始化为 -1 表示空
    int table[5][20] = { -1 };               // 用于记录每次访问的内存状态，初始化为 -1 表示空
    bool status[20];                         // 记录是否缺页

    int pageFaults = 0;                      // 缺页次数
    int nextReplace = 0;                     // 记录下一个要替换的位置

    // 获取开始时间（时钟周期数）
    clock_t start = clock();

    // 遍历每个页面访问
    for (int j = 0; j < 20; j++) {
        int page = pages[j];
        bool found = false;

        // 检查页面是否已在内存中
        for (int i = 0; i < n; i++) {
            if (memory[i] == page) {
                found = true;
                break;
            }
        }

        if (!found) {  // 缺页情况
            memory[nextReplace] = page;       // 替换页面
            nextReplace = (nextReplace + 1) % n; // 更新替换位置
            status[j] = false;                // 标记缺页
            pageFaults++;
        }
        else {
            status[j] = true;                 // 标记命中
        }

        // 记录当前内存状态到表格
        for (int i = 0; i < n; i++) {
            table[i][j] = memory[i];
        }
    }

    // 获取结束时间（时钟周期数）
    clock_t end = clock();

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  ";  // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        if (status[j]) {
            cout << "\u221A ";  // Unicode "√"
        }
        else {
            cout << "\u00D7 ";  // Unicode "×"
        }
    }
    cout << endl;

    cout << "FIFO 缺页率: " << fixed << setprecision(2) << (float)pageFaults / 20 * 100 << "%" << endl;
    cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl; // 输出运行时间
}

int main() {
    cout << "内存容量为 3 块:\n";
    fifo(3);
    cout << endl;

    cout << "内存容量为 4 块:\n";
    fifo(4);

    return 0;
}

2、精确时间：用chrono输出运行时间都是xx微秒，输出时间不定

#include <iostream>
#include <iomanip>
#include <chrono> // 引入chrono库

using namespace std;
using namespace std::chrono; // 使用chrono命名空间

// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };

// FIFO算法
void fifo(int n) {
    int memory[5] = { -1, -1, -1, -1, -1 };  // 用于存储主存块，初始化为 -1 表示空
    int table[5][20] = { -1 };               // 用于记录每次访问的内存状态，初始化为 -1 表示空
    bool status[20];                         // 记录是否缺页

    int pageFaults = 0;                      // 缺页次数
    int nextReplace = 0;                     // 记录下一个要替换的位置

    // 获取开始时间
    auto start = high_resolution_clock::now();

    // 遍历每个页面访问
    for (int j = 0; j < 20; j++) {
        int page = pages[j];
        bool found = false;

        // 检查页面是否已在内存中
        for (int i = 0; i < n; i++) {
            if (memory[i] == page) {
                found = true;
                break;
            }
        }

        if (!found) {  // 缺页情况
            memory[nextReplace] = page;       // 替换页面
            nextReplace = (nextReplace + 1) % n; // 更新替换位置
            status[j] = false;                // 标记缺页
            pageFaults++;
        }
        else {
            status[j] = true;                 // 标记命中
        }

        // 记录当前内存状态到表格
        for (int i = 0; i < n; i++) {
            table[i][j] = memory[i];
        }
    }

    // 获取结束时间
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  ";  // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        if (status[j]) {
            cout << "\u221A ";  // Unicode "√"
        }
        else {
            cout << "\u00D7 ";  // Unicode "×"
        }
    }
    cout << endl;

    cout << "FIFO 缺页率: " << fixed << setprecision(2) << (float)pageFaults / 20 * 100 << "%" << endl;
    cout << "运行时间: " << duration.count() << " 微秒" << endl; // 输出运行时间
}

int main() {
    cout << "内存容量为 3 块:\n";
    fifo(3);
    cout << endl;

    cout << "内存容量为 4 块:\n";
    fifo(4);

    return 0;
}

3、数组模拟队列、类似滑动窗口

#include <iostream>
#include <iomanip>
#include <chrono>
#include <cstring>

using namespace std;
using namespace std::chrono;

const int N = 1010;
int memory[N];//每次查找页面进行记录的滑动窗口
int table[5][20]; // 最终输出的表格状态
// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };

// FIFO算法
void fifo(int n) {
    memset(memory, 0x3f, sizeof memory);
    bool status[20];  // 记录是否缺页

    int pageFaults = 0;       // 缺页次数
    int hh = 0, tt = -1;      // 队首和队尾指针
    auto start = high_resolution_clock::now(); // 获取开始时间

    for (int j = 0; j < 20; j++) {
        int page = pages[j];
        bool found = false;

        // 检查页面是否已在内存中
        for (int i = hh; i <= tt; i++) {
            if (memory[i] == page) {
                found = true;
                break;
            }
        }

        if (!found) {  // 缺页情况
            memory[++tt] = page; // 新页面加入队尾

            // 控制滑动窗口大小为 n
            if (tt - hh + 1 > n) {
                hh++; // 超过容量，队首出队
            }

            status[j] = false;  // 标记缺页
            pageFaults++;
        }
        else {
            status[j] = true;   // 标记命中
        }

        // 记录当前内存状态到表格
        for (int i = 0; i < n; i++) {
            //如果只写memory[hh]的话不就移动队首指针了吗，不可以，现在是赋值阶段，只需要控制负责赋值的滑动指针首先不能超过队尾指针，确保在滑动窗口范围内，
            //因为有可能这个滑动窗口不足n长，你就会多余赋值本来不能存在的页面号赋值成0x3f，其次需要满足当前检查是否缺页的一次记录memory，该位置是否有值
            if (i + hh <= tt && memory[i + hh] != 0x3f) {
                table[i][j] = memory[i + hh];
            }
            else {
                table[i][j] = -1; // 空位显示为 -1
            }
        }
    }

    auto stop = high_resolution_clock::now(); // 获取结束时间
    auto duration = duration_cast<microseconds>(stop - start);

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  ";  // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        cout << (status[j] ? "\u221A " : "\u00D7 ");//unicode编码，前者代表true则不缺页是√标识，后者代表false是缺页×表示
    }
    cout << endl;

    cout << "FIFO 缺页率: " << fixed << setprecision(2) << (float)pageFaults / 20 * 100 << "%" << endl;
    cout << "运行时间: " << duration.count() << " 微秒" << endl;
}

int main() {
    cout << "内存容量为 3 块:\n";
    fifo(3);
    cout << endl;

    cout << "内存容量为 4 块:\n";
    fifo(4);

    return 0;
}

朴素版算缺页率

#include <iostream>
#include <ctime>
#include <cstring>

using namespace std;


const int N = 1010;
int memory[N];//每次查找页面进行记录的滑动窗口
int table[5][20]; // 最终输出的表格状态
// 页访问顺序
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };

// FIFO算法
void fifo(int n) {
    memset(memory, 0x3f, sizeof memory);
    bool status[20];  // 记录是否缺页

    int pageFaults = 0;       // 缺页次数
    int hh = 0, tt = -1;      // 队首和队尾指针
    clock_t start=clock(); // 获取开始时间

    for (int j = 0; j < 20; j++) {
        int page = pages[j];
        bool found = false;

        // 检查页面是否已在内存中
        for (int i = hh; i <= tt; i++) {
            if (memory[i] == page) {
                found = true;
                break;
            }
        }

        if (!found) {  // 缺页情况
            memory[++tt] = page; // 新页面加入队尾

            // 控制滑动窗口大小为 n
            if (tt - hh + 1 > n) {
                hh++; // 超过容量，队首出队
            }

            status[j] = false;  // 标记缺页
            pageFaults++;
        }
        else {
            status[j] = true;   // 标记命中
        }

        // 记录当前内存状态到表格
        for (int i = 0; i < n; i++) {
            //如果只写memory[hh]的话不就移动队首指针了吗，不可以，现在是赋值阶段，只需要控制负责赋值的滑动指针首先不能超过队尾指针，确保在滑动窗口范围内，
            //因为有可能这个滑动窗口不足n长，你就会多余赋值本来不能存在的页面号赋值成0x3f，其次需要满足当前检查是否缺页的一次记录memory，该位置是否有值
            if (i + hh <= tt && memory[i + hh] != 0x3f) {
                table[i][j] = memory[i + hh];
            }
            else {
                table[i][j] = -1; // 空位显示为 -1
            }
        }
    }

    clock_t end = clock(); // 获取结束时间

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  ";  // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        cout << (status[j] ? "\u221A " : "\u00D7 ");//unicode编码，前者代表true则不缺页是√标识，后者代表false是缺页×表示
    }
    cout << endl;

    cout << "FIFO 缺页率: " << (float)pageFaults / 20 * 100 << "%" << endl;
    cout << "运行时间: " << (double)(end-start)/CLOCKS_PER_SEC << " 秒" << endl;

}

int main() {
    cout << "内存容量为 3 块:\n";
    fifo(3);
    cout << endl;

    cout << "内存容量为 4 块:\n";
    fifo(4);

    return 0;
}

FIFO，用链表实现

LRU，用计数器实现

#include <iostream>
#include <ctime>
#include <cstring>
#include <unordered_map>

using namespace std;

const int N = 1010;
int table[5][20]; // 最终输出的表格状态
unordered_map<int, int> m; // 键为page号，值为count值
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };

void lru(int n) {
    memset(table, -1, sizeof table);
    m.clear();
    bool status[20]; // 记录是否缺页

    int pageFaults = 0; // 缺页次数

    clock_t start = clock(); // 获取开始时间

    for (int j = 0; j < 20; j++) {
        int page = pages[j];

        if (!m.count(page)) { // 没命中就要加入或者替换页面
            if (m.size() >= n) {
                // 找到count最大的页面进行替换
                int maxpage = -1, maxcounts = -1;
                for (auto p : m) {
                    if (p.second > maxcounts) {
                        maxpage = p.first;
                        maxcounts = p.second;
                    }
                }
                m.erase(maxpage);
            }
            m[page] = 0;//没命中且主存没满则直接加入页面
            pageFaults++;
            status[j] = false; // 标记缺页
        }
        else {
            status[j] = true; // 标记命中
            m[page] = 0;
        }

        // 更新所有页面的count值：命中则置0，没命中加入新页面——满足条件则不加1即可，不管加不加入新页面，其他没中的页面都是要count+1的
        for (auto& p : m) {
            if (p.first != page) {
                p.second += 1;
            }
        }

        // 更新当前主存块内存在的页面
        int i = 0;
        for (auto p : m) {
            if (i < n) {//用一个i去便利贮存块，而不用for
                table[i][j] = p.first;
                i++;
            }
        }
        //一开始写错了：
        /*for (int i = 0; i < n; i++) {
            for (auto p : m) {
                table[i][j] = p.first;
            }
        }*/
    }

    clock_t end = clock(); // 获取结束时间

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  "; // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        cout << (status[j] ? "\u221A " : "\u00D7 ");
    }
    cout << endl;

    cout << "LRU 缺页率: " << (float)(pageFaults) / 20 * 100 << "%" << endl;
    cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;
}

int main() {
    cout << "内存容量为 3 块:\n";
    lru(3);
    cout << endl;

    cout << "内存容量为 4 块:\n";
    lru(4);

    return 0;
}

LRU，用堆栈实现

两个算法综合在一起看运行速率

#include <iostream>
#include <ctime>
#include <cstring>
#include <unordered_map>
#include <chrono> // 引入chrono库

using namespace std;
using namespace std::chrono; // 使用chrono命名空间

const int N = 1010;
int table[5][20]; // 最终输出的表格状态
unordered_map<int, int> m; // 键为page号，值为count值
int pages[20] = { 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 };
int memory[N];//每次查找页面进行记录的滑动窗口

// FIFO算法
void fifo(int n) {
    memset(memory, 0x3f, sizeof memory);
    memset(table, -1, sizeof table);
    bool status[20];  // 记录是否缺页

    int pageFaults = 0;       // 缺页次数
    int hh = 0, tt = -1;      // 队首和队尾指针
    //clock_t start = clock(); // 获取开始时间
     // 获取开始时间
    auto start = high_resolution_clock::now();

    for (int j = 0; j < 20; j++) {
        int page = pages[j];
        bool found = false;

        // 检查页面是否已在内存中
        for (int i = hh; i <= tt; i++) {
            if (memory[i] == page) {
                found = true;
                break;
            }
        }

        if (!found) {  // 缺页情况
            memory[++tt] = page; // 新页面加入队尾

            // 控制滑动窗口大小为 n
            if (tt - hh + 1 > n) {
                hh++; // 超过容量，队首出队
            }

            status[j] = false;  // 标记缺页
            pageFaults++;
        }
        else {
            status[j] = true;   // 标记命中
        }

        // 记录当前内存状态到表格
        for (int i = 0; i < n; i++) {
            //如果只写memory[hh]的话不就移动队首指针了吗，不可以，现在是赋值阶段，只需要控制负责赋值的滑动指针首先不能超过队尾指针，确保在滑动窗口范围内，
            //因为有可能这个滑动窗口不足n长，你就会多余赋值本来不能存在的页面号赋值成0x3f，其次需要满足当前检查是否缺页的一次记录memory，该位置是否有值
            if (i + hh <= tt && memory[i + hh] != 0x3f) {
                table[i][j] = memory[i + hh];
            }
            else {
                table[i][j] = -1; // 空位显示为 -1
            }
        }
    }

    //clock_t end = clock(); // 获取结束时间
    // 获取结束时间
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  ";  // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        cout << (status[j] ? "\u221A " : "\u00D7 ");//unicode编码，前者代表true则不缺页是√标识，后者代表false是缺页×表示
    }
    cout << endl;

    cout << "FIFO 缺页率: " << (float)pageFaults / 20 * 100 << "%" << endl;
    //cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;
    cout << "运行时间: " << duration.count() << " 微秒" << endl; // 输出运行时间

}
void lru(int n) {
    memset(table, -1, sizeof table);
    m.clear();
    bool status[20]; // 记录是否缺页

    int pageFaults = 0; // 缺页次数

    //clock_t start = clock(); // 获取开始时间
     // 获取开始时间
    auto start = high_resolution_clock::now();

    for (int j = 0; j < 20; j++) {
        int page = pages[j];

        if (!m.count(page)) { // 没命中就要加入或者替换页面
            if (m.size() >= n) {
                // 找到count最大的页面进行替换
                int maxpage = -1, maxcounts = -1;
                for (auto p : m) {
                    if (p.second > maxcounts) {
                        maxpage = p.first;
                        maxcounts = p.second;
                    }
                }
                m.erase(maxpage);
            }
            m[page] = 0;//没命中且主存没满则直接加入页面
            pageFaults++;
            status[j] = false; // 标记缺页
        }
        else {
            status[j] = true; // 标记命中
            m[page] = 0;
        }

        // 更新所有页面的count值：命中则置0，没命中加入新页面——满足条件则不加1即可，不管加不加入新页面，其他没中的页面都是要count+1的
        for (auto& p : m) {
            if (p.first != page) {
                p.second += 1;
            }
        }

        // 更新当前主存块内存在的页面
        int i = 0;
        for (auto p : m) {
            if (i < n) {//用一个i去便利贮存块，而不用for
                table[i][j] = p.first;
                i++;
            }
        }
        //一开始写错了：
        /*for (int i = 0; i < n; i++) {
            for (auto p : m) {
                table[i][j] = p.first;
            }
        }*/
    }

    //clock_t end = clock(); // 获取结束时间
    // 获取结束时间
    auto stop = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop - start);

    // 输出结果表格
    cout << "主存块号 ";
    for (int j = 0; j < 20; j++) {
        cout << pages[j] << " ";
    }
    cout << endl;

    for (int i = 0; i < n; i++) {
        cout << "   " << i << "     ";
        for (int j = 0; j < 20; j++) {
            if (table[i][j] == -1) {
                cout << "  "; // 空块显示为空格
            }
            else {
                cout << table[i][j] << " ";
            }
        }
        cout << endl;
    }

    // 输出缺页标记
    cout << "是否缺页 ";
    for (int j = 0; j < 20; j++) {
        cout << (status[j] ? "\u221A " : "\u00D7 ");
    }
    cout << endl;

    cout << "LRU 缺页率: " << (float)(pageFaults) / 20 * 100 << "%" << endl;
    //cout << "运行时间: " << (double)(end - start) / CLOCKS_PER_SEC << " 秒" << endl;
    cout << "运行时间: " << duration.count() << " 微秒" << endl; // 输出运行时间
}

int main() {
    cout << "内存容量为 3 块:\n";
    fifo(3);
    cout << endl;
    lru(3);
    cout << endl;

    cout << "内存容量为 4 块:\n";
    fifo(4);
    cout << endl;
    lru(4);

    return 0;
}

1）主存块数越多的，不论哪个算法，运行时间都更长一些，用的时chrono精确时间微妙

但是同样的，运行每次的时间不定

2）主存块数越多的，不论哪个算法，缺页率都更低一些

原文地址：https://blog.csdn.net/yyt_cdeyyds/article/details/143485384

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：操作系统进程和线程——针对实习面试
下一篇：k8s篇之flannel网络模型详解

云计算-华为HCIA-学习笔记
平均时间：平均寻道时间，平均等待时间，平均寻道时间指的是磁头切换到目标磁道所需要的时间，平均等待时间指的是磁头到达指定磁道之后，切换到目标扇区的时间。SCSI卡是SCSI控制卡的简称。所有的服务器都可
阅读更多2024-11-25
【Linux】基础-文件系统
文件系统介绍，ext2文件系统，文件系统函数，递归遍历函数，虚拟文件系统
阅读更多2024-11-25
气膜场馆照明设计：科技与环保的完美结合—轻空间
气膜场馆的照明设计，选用高效节能的400瓦LED灯具，结合现代节能技术，提供强大而均匀的光照。科学的照明设计不仅提升了气膜场馆的实用性，还满足了日常训练、体育比赛和大型文艺活动的多样化需求。无论是专业
阅读更多2024-11-25
python-docx -- 读取word页眉、页脚
基于python-docx解析word文档的页眉、页脚；
阅读更多2024-11-25
Python操作neo4j库py2neo使用之创建和查询（二）
【代码】## Python操作neo4j库py2neo使用之创建和查询（二）
阅读更多2024-11-25
使用flink编写WordCount
1. env-准备环境2. source-加载数据转换4. sink-数据输出5. execute-执行。
阅读更多2024-11-25
Ros2 操作指令记录
ros2 pkg create --build-type {cmake,ament_cmake,ament_python} --dependencies
阅读更多2024-11-25
详细描述一下Elasticsearch搜索的过程?
详细描述一下Elasticsearch搜索的过程?
阅读更多2024-11-25
编程中的字节序问题
字节序（Endianness）是指计算机以二进制格式存储和处理多字节数据时，字节的排列顺序。它主要决定了在存储和传输过程中，数据的高字节和低字节如何被排列。字节序是计算机体系结构中非常重要的一个概念，
阅读更多2024-11-25
#渗透测试#SRC漏洞挖掘#网络运维# 黑客脚本编写终章之重定向与脚本调用
免责声明本教程仅为合法的教学目的而准备，严禁用于任何形式的违法犯罪活动及其他商业行为，在使用本教程前，您应确保该行为符合当地的法律法规，继续阅读即表示您需自行承担所有操作的后果，如有异议，请立即停止
阅读更多2024-11-25