总阅读量次

最近在做操作系统上机实验。有一个关于页置换算法的实验，实验所给的代码是先进先出调页算法，一时手痒就想着自己模拟一下LRU调页算法，就作为一个小开始吧。

1.关于LRU算法

　　算法步骤描述如下:

1. 为所有的页添加一个计数器并置0。
2. 若系统访问的页存在于内存中，为该页的计数器加一，并对内存中所有的页按计数器大小降序排列；否则执行第三步。
3. 判断系统内存页数是否已满，是则将内存中排序最后一页置换为系统访问的页，并为该页初始化计数器；否则将系统访问的页加入内存，并初始化计数器。

2.关于数据结构

　　1. 页类型可用如下结构体表示

struct page
{
    int pageNum = -1;    // 系统访问页码,默认-1为空
    int time = 0;       // 系统在内存访问总次数，默认为0次
    page() {}                                       // 空无参构造
    page(const int p): pageNum(p) {}                // 构造函数
    friend bool operator<(page &p1, page &p2)       // 排序比较器
    {
        return p1.time < p2.time;
    }
};

　　2. 可用一个最大空间为3的vector模拟内存

#define CAPACITY 3
std::vector<pageNode> mainMem;

3.调页函数

void foldPage(int page, std::vector<pageNode> &mainMem)
{
    if(CAPACITY == mainMem.size())              /* 内存存放的页满,置换最后一页*/
    {
        mainMem.back().pageNum = page;
        mainMem.back().time = 0;
    }
    else
    {
        mainMem.emplace_back(page);             /* emplace_back()直接调用其构造函数，并加在vector最后。*/
    }
}

测试结果

模拟访问页面走向
4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5, 1, 4, 3
-------------------------------------
时间  访问页   内存状态  缺页中断 调入页
0        
1       4        4           +      4
2       3        4 3         +      3
3       2        4 3 2       +      2
4       1        4 3 1       +      1
5       4        4 3 1
6       3        4 3 1
7       5        4 3 5       +      5
8       4        4 3 5
9       3        4 3 5
10      2        4 3 2       +      2
11      1        4 3 1       +      1
12      5        4 3 5       +      5
13      1        4 3 1       +      1
14      4        4 3 1
15      3        4 3 1
缺页中断次数为9
缺页率9/15=60.00%%

完整测试代码见我的Github。

————————————————————————————————————————————————我是分割线——————————————————————————-
更新于2020.2.28

上面的构想还是学生时代初期的构想，太过于理想化，只考虑到了模拟，其它一概不考虑。真是一颗傲娇的心。

最近在LeetCode上刷题，遇到了一道关于设计实现LRU算法的题，才发现当年写的LRU算法真是只有当年才能写出来。
　　真正在页置换算法应用实现中是根本不会为页设置访问次数属性并由该属性进行排序的，这效率低且浪费内存。光时间复杂度就高达O(nlogn)，更别提空间复杂度了。
下面开始分析优化：
　　在页置换算法中，没有必要对工作集内的页进行按访问次数排序，从而得到最近最少访问次数。而是因为我们只要求得到最近最少访问的页，只用将经常访问的页放到页表首部，则每次都能以O(1)的时间复杂度访问；而当调入新的页时，若OS为进程分配的页帧已用完，采用LRU算法，应删除最近最少访问的页，也就是页表尾部页；若页帧没有用完，则直接将新页加入到页表首部。这里这样描述是因为这个LRU算法实现基本就是这个思想。
由以上，要以O(1)删除尾部元素，以O(1)插入元素到表首，以O(1)查找某元素(hash)，且有顺序(list)。综上分析，形成了新的数据结构——哈希链表。
　　当时在LeetCode上接触这道题时，感觉思维被打乱了，甚至没读懂题意。后来看了题解才恍然大悟。也触摸到了分析这种题的一些诀窍。下面是cpp代码：

#include<iostream>
#include<list>
#include<unordered_map>

using namespace std;
// 哈希链表
class LRUCache
{
public:
    LRUCache(int capacity):_capacity(capacity) {}
    int get(int key)
    {
        auto it = mp.find(key);                 // C++11中迭代器类似于指针
        if(it == mp.end())
            return -1;

        int val = it->second->second;           // 取出key对应的value
        cache.erase(it->second);                //从cache中删除k-v
        cache.push_front(make_pair(key,val));   // 重新构造k-v放入cache头
        mp[key] = cache.begin();                // 更新该key hash映射的迭代器
        return val;
    }

    void put(int key, int value)
    {
        auto it = mp.find(key);
        if(mp.end() == it)                      // k-v不存在
        {
            if(cache.size() == _capacity)       // cache 已满，删除尾部，清理出空间
            {
                auto temp = cache.back();
                cache.pop_back();
                mp.erase(temp.first);           // 删除尾部的key在hash中对应的结点
            }
        }
        else   cache.erase(mp[key]);            // k-v存在,更新value,并放入cache头

        cache.push_front(make_pair(key,value)); // 将结点直接加入头部
        mp[key] = cache.begin();                // 更新该key对应的迭代器
    }
private:
    unsigned int _capacity;
    list<pair<int,int>> cache;                  // 模拟cache双链表
    unordered_map<int,list<pair<int,int>>::iterator> mp;    // hash表
};

int main()
{
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout<<cache.get(1)<<endl;       // 返回  1
    cache.put(3, 3);    // 该操作会使得密钥 2 作废
    cout<<cache.get(2)<<endl;       // 返回 -1 (未找到)
    cache.put(4, 4);    // 该操作会使得密钥 1 作废
    cout<<cache.get(1)<<endl;       // 返回 -1 (未找到)
    cout<<cache.get(3)<<endl;       // 返回  3
    cout<<cache.get(4)<<endl;       // 返回  4
    return 0;
}