操作系统之内存管理_页面置换算法(C++实现LRU)-白红宇的个人博客

发布日期：2021-05-20 07:55:00 浏览次数：20 分类：精选文章

本文共 3035 字，大约阅读时间需要 10 分钟。

一、问题描述

系统为某进程分配了3个物理块，且考虑页面号引用串：{7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1}。若采用LRU算法进行页面置换，进程首次访问页面2时，将最近最久未被访问的页面7置换出去；接着访问页面3时，将最近最久未使用的页面1置换出去。

为了实现上述过程，我们需要编写C++代码模拟LRU算法。

二、C++实现LRU

1. 预备知识

(1) LRU（Least Recently Used）：最近最少使用的页面置换算法。

(2) 选用数据结构：

由于需要查找物理块中是否已有要访问的页面，选择使用内置于C++标准库的map（由红黑树实现），其查找元素的复杂度为O(log₂N)。

由于需要插入和删除操作，选择使用双链表来管理结点，删除操作的时间复杂度为O(1)。

2.invovle的操作

(1)新插入的结点应放置在双链表的头部，调用setHead函数。

(2)成功访问的双链表结点需移至双链表的头部，调用remove函数后再setHead函数。

(3)若链表已满，则丢弃链表尾部的结点，调用remove函数。

3.代码实现

完整代码如下：

#include #include 
    
     #include 
     
      using namespace std;typedef unsigned int UI;class LRUCache {private:    struct CacheNode {        int key;        int value;        CacheNode *pre;        CacheNode *next;        CacheNode(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {}    };    UI size;    CacheNode *head;    CacheNode *tail;    map
      
        mp;public:    LRUCache(int capacity) : size(capacity), head(nullptr), tail(nullptr) {}    void setHead(CacheNode *node) {        node->next = head;        node->pre = nullptr;        if (head != nullptr) {            head->pre = node;        }        head = node;        if (tail == nullptr) {            tail = head;        }    }    void remove(CacheNode *node) {        if (node->pre != nullptr) {            node->pre->next = node->next;        } else {            head = node->next;        }        if (node->next != nullptr) {            node->next->pre = node->pre;        } else {            tail = node->pre;        }    }    void set(int key, int value) {        auto it = mp.find(key);        if (it != mp.end()) {            CacheNode *node = it->second;            node->value = value;            remove(node);            setHead(node);        } else {            CacheNode *newNode = new CacheNode(key, value);            if (mp.size() == size) {                auto it_tail = mp.find(tail->key);                remove(tail);                mp.erase(it_tail);            }            setHead(newNode);            mp[key] = newNode;        }    }    int get(int key) {        auto it = mp.find(key);        if (it != mp.end()) {            CacheNode *node = it->second;            remove(node);            setHead(node);            return node->value;        } else {            return -1;        }    }};int main() {    LRUCache* lruCache = new LRUCache(3);    int sequence[] = {7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1};    const int value = 7;    int len = sizeof(sequence) / sizeof(sequence[0]);    int count = 0;    for (int i = 0; i < len; ++i) {        if (lruCache->get(sequence[i]) == -1) {            printf("%d号页面缺失\n", sequence[i]);            lruCache->set(sequence[i], value);            count++;        } else {            printf("%d号页面命中\n", sequence[i]);        }    }    printf("总共缺页次数为%d\n", count);    return 0;}

四、运行结果

运行程序可看到具体页面命中和缺失信息，例如：

7号页面命中0号页面命中1号页面命中2号页面命中0号页面命中3号页面命中0号页面命中4号页面命中2号页面命中3号页面命中0号页面命中3号页面命中2号页面命中1号页面命中2号页面命中0号页面命中1号页面命中7号页面命中0号页面命中1号页面命中

总共缺页次数为4。

上一篇：利用循环不变式实习二叉树的层序遍历(LeetCode 102)

下一篇：C++实现二叉树的最近公共祖先

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！