操作系统之内存管理_页面置换算法(C++实现LRU)

╰半橙微兮° 2022-12-19 03:50 172阅读 0赞

一、问题描述  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]  
**场景**：  
假定系统为某进程分配了**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)选用的数据结构  
①由于需要**查找**物理块中是否已有要访问的页面，选用map(内部用红黑树实现)，其查找元素的时间复杂度为O( log ⁡ 2 N \\log\_2N log2N)；

map<int, CacheNode *> mp; //int，页面号；CacheNode *, 对应结点的地址

②由于需要插入和删除，若选用单链表将结点链接起来，删除结点的时候需要从表头开始遍历查找，时间复杂度为O(n)；而采用双链表，时间复杂度为O(1)

struct CacheNode {
        
                int key;
                int value;
                CacheNode *pre, *next;
                CacheNode(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {
        }
            };

> 故选择**map** \+ **双链表**实现**LRU**

(3)涉及的操作  
①新插入的结点应放置在双链表的头部(setHead函数)  
②成功访问双链表的结点，需将该结点移至双链表的头部(remove函数 + setHead函数)  
③若链表已满，则丢弃链表尾部结点(remove函数)

**setHead函数的代码：**

void setHead(CacheNode *node) {
        
                node->next = head;
                node->pre = nullptr;
                if(head != nullptr) 
                    head->pre = node;
                head = node;
                if(tail == nullptr)
                    tail = head;
            }

**remove函数的代码：**

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) {
        
                map<int, CacheNode *>::iterator 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) {
        
                        map<int, CacheNode *>::iterator it = mp.find(tail->key);
                        remove(tail);
                        mp.erase(it);
                    }
                    setHead(newNode);
                    mp[key] = newNode;
                }
            }

三、完整代码及运行结果  
**1.完整代码**

//C++实现LRU
    #include <map>
    #include <iostream>
    #include <cstdio>
    using namespace std;
    typedef unsigned int UI;
    class LRUCache {
        
        private:
            struct CacheNode {
        
                int key;
                int value;
                CacheNode *pre, *next;
                CacheNode(int k, int v) : key(k), value(v), pre(nullptr), next(nullptr) {
        }
            };  
            UI size;
            CacheNode *head, *tail;
            map<int, CacheNode *> 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) {
        
                map<int, CacheNode *>::iterator 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) {
        
                        map<int, CacheNode *>::iterator it = mp.find(tail->key);
                        remove(tail);
                        mp.erase(it);
                    }
                    setHead(newNode);
                    mp[key] = newNode;
                }
            }
            //本次模拟无需get函数
            int get(int key) {
        
                map<int, CacheNode *>::iterator it = mp.find(key);
                if(it != mp.end()) {
        
                    CacheNode *node = it->second;
                    remove(node);
                    setHead(node);
                    return node->value;
                }
                else
                    return -1;
            }   
    };
    
    int main() {
        
        //测试 3个物理块 访问页面 : 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
        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; //页面内容，非模拟重点，都设为7；
        int len = sizeof(sequence) / sizeof(sequence[0]);
        int count = 0;
        for (int i = 0; i < len; i++) {
        
            if(lruCache->get(sequence[i]) == -1) {
        
                //缺页
                count++;
                printf("%d号页面缺失\n", sequence[i]);
                lruCache->set(sequence[i], value);
            }
            else {
        
                printf("%d号页面命中\n", sequence[i]);
            }
        }
        printf("总共缺页次数为%d\n", count);
        return 0;
    }

**2.运行结果**  
![在这里插入图片描述][2020110512283079.png_pic_left]  
四、参考文献  
[常见缓存算法和LRU的c++实现][LRU_c]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzQ3NzAwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/a07cf98974ef48aa975e5dfe4e592ef1.png
[2020110512283079.png_pic_left]: https://img-blog.csdnimg.cn/2020110512283079.png#pic_left
[LRU_c]: https://www.cnblogs.com/cpselvis/p/6272096.html