校招基础知识详解——计算机操作系统（内存管理）

文章目录

虚拟内存
分页系统地址映射
页面置换算法
- 最佳页面置换算法(OPT, Optimal replacement algorithm)
- 先进先出置换算法（FIFO, First In First Out）
- 最近最久未使用的置换算法（LRU, Least Recently Used）
- 最不常用算法
- 最近未使用（NRU, Not Recently Used）
- 第二次机会算法
- 时钟页面置换算法（Clock）
分段
段页式
分页与分段的比较
Linux 内存管理

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

在这里插入图片描述

虚拟内存可以让每个进程以为自己独占整个内存

虚拟内存可以在逻辑上扩充物理内存，比如GTA5这个游戏，本身有游戏大小60G，而内存只有8G，没有虚拟内存话，那么就无法将60G的游戏从硬盘放到8G的内存中，即无法运行GTA5

而有了虚拟内存，就可以运行GTA5了，将需要运行的部分程序代码放入内存，需要用到什么就判断内存有没有，没有就载入，不需要用的就替换出去放回硬盘。

分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为（110 000000000100）。

在这里插入图片描述

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

最佳页面置换算法(OPT, Optimal replacement algorithm)

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。

是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：

7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

在这里插入图片描述

先进先出置换算法（FIFO, First In First Out）

选择换出的页面是最先进入的页面。

该算法会将那些经常被访问的页面换出，导致缺页率升高。

在这里插入图片描述

最近最久未使用的置换算法（LRU, Least Recently Used）

虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

在这里插入图片描述

对应 Leetcode—146. LRU 缓存【中等】

struct Node {
    int key;
    int val;
};

class LRUCache {
public:
    LRUCache(int capacity) : m_capacity(capacity) {
        
    }
    
    int get(int key) {
        const auto & it = mp.find(key);
        // key 不存在
        if(it == mp.cend()) {
            return -1;
        }
        // key 存在
        const auto& lsNode = it->second;
        lst.splice(lst.begin(), lst, lsNode);
        return lsNode->val;
    }
    
    void put(int key, int value) {
        // key 存在, 变更val
        if(const auto it = mp.find(key); it != mp.cend()) {
            const auto& lsNode = it->second;
            lst.splice(lst.begin(), lst, lsNode);
            lsNode->val = value;
            return;
        }

        // key 不存在
            // 容量已满
        if(m_capacity == mp.size()) {
            auto & item = lst.back();
            mp.erase(item.key);
            lst.pop_back();
        }
            // 容量有余
        lst.emplace_front(key, value);
        mp[key] = lst.begin();
    }
private:
    const int m_capacity;
    list<Node> lst;
    unordered_map<int, list<Node>::iterator> mp;
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */