操作系统-虚拟内存管理

CPU访存

虚拟地址空间：不同的可执行文件所映射的虚拟地址空间大小一样，地址空间中的区域划分结构也相同

页可以分为3种状态：

1. 未分配页：没有任何内容相关联的页
2. 缓存页：已调入主存而被缓存在DRAM中的页面
3. 未缓存页：未调入主存而存在硬盘上的页面

操作系统使用页表将虚拟页转换成物理页，页表具有一下属性：

装入位：该页是否存在DRAM中

存放位置：指向物理页号，若为0，则没有被调入内存

脏位：该页是否被修改

使用位：配合替换策略来设置

访问权限位：说明页面访问权限

禁止缓存位：说明页面是否可以装入cache

快表：后背转换缓冲器，高速缓存，存储了最活跃的几个页表项。快表比页表小得多，为提高命中率，快表通常具有较高的关联度，大多采用全相联或者组相联的方式

CPU访存的过程如下：

页面替换算法

先进先出算法（FIFO）

基本思路：选择在内存中驻留时间最长的页面并淘汰之。具体来说：OS维护着一个链表，记录了所有内存当中的逻辑页面。从链表的排序顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个页面中断时，把链首页面淘汰出局，把新的页面添加到链表的末尾。

最近最久未使用算法（LRU）

思路：当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。

它是对最优置换算法的近似，以过去推未来。根据程序的局部性原理，即在最近一小段时间（最近几条指令），如果某些页面被频繁访问，那么在将来的一小段时间内，它们还可能再一次被频繁访问。反之，如果在过去某些页面长时间未被访问，那么将来它们还可能会长时间地得不到访问。

算法实现模拟：（使用哈希链表实现）

#include<iostream>
#include<list>
#include<unordered_map>
using namespace std;

// key: page, int
class LRU
{
public:
    const int max_size = 3;
    unordered_map<int, list< int >::iterator > h;
    list< int > ls;

    void visit(int pg)
    {
        // pg in h:
        if(h.count(pg) > 0)
        {
            // put to head
            auto tmp = *h[pg];
            ls.erase(h[pg]);
            ls.push_front(tmp);
            h[pg] = ls.begin();
        }
        else  // pg not in h
        {
            // cur size < max size
            // put to front, add to h
            if(h.size() < max_size)
            {
                ls.push_front(pg);
                h[pg] = ls.begin();
            }
            else
            {
                // swap the last, del in h
                h.erase(ls.back());
                ls.pop_back();
                // put to front, add to h
                ls.push_front(pg);
                h[pg] = ls.begin();
            }
        }
    }

    void output()
    {
        cout << "~~~~~~~~~~~~~~~~~~~~\n";
        cout << "hash table:\n";
        for(auto& pr : h)
        {
            cout << pr.first << endl;
        }
        cout << "list: \n";
        for(auto& v : ls)
        {
            cout << v << " ";
        }
        cout << "\n~~~~~~~~~~~~~~~~~~~~\n";
    }
};

int main()
{
    LRU lru;
    int tb[] = {1, 2, 3, 4, 2, 3, 1};
    for(auto& v : tb)
    {
        lru.visit(v);
        lru.output();
    }
    return 0;
}

时钟页面置换算法

Clock 页面置换算法——LRU的近似，对FIFO的改进

基本思路：需要用到页表项的访问位（access bit），当一个页面被装入内存时，把该位初始化为0，然后如果这个页被访问（读/写）时，硬件把它置为1.

把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最先进来）；

当发生一个缺页中断，考察指针所指向的最老的页面，若它的访问为为0，则立即淘汰。若访问为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

最不常用算法（least frequently used，LFU）

基本思路：当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰之

实现方法：对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器加1，淘汰计数值最小的那个页面

LRU/LFU区别：LRU考察的是多久未访问，时间越短越值得留在内存，LFU是访问次数/频度，次数越多越好。

反例：一个页面在进程开始时使用的很多，但以后就不使用了。此时LFU就不适用了。把时间也考虑进去，在一段时间内考察LFU。比如，定期把次数寄存器右移一位。