①传统存储管理方式的特征
传统的内存管理策略都是为了同时将多个进程保存进内存中，它们具有以下的共同特征：
-
一次性。作业必须一次性全部装入内存后，才能开始运行（静态库）。这会导致两种情况：①当作也很大而不能完全装入内存时将无法运行。②当大量作业要求运行时，由于内存不足无法容纳所有的作业，只能少数作业先运行，导致多道程序度下降。
-
驻留性。 作业被装入内存后，就一直驻留在内存中，其任何部分都不会被换出，甚至作业运行结束。运行中的进程会因等待I/O而被阻塞，可能长期处于等待状态。
②局部性原理
局部性原理：程序在一段时间内访问的地址，可能集中在一定的范围之内。因为指令通常是顺序存放、顺序执行的，数据一般也是以数组、向量等形式存放。
- 时间局部性：在程序中的某条指令一旦运行，不久后该指令可能再次执行。
- 空间局部性：一旦程序访问了某个存储单元，在不久后，其附近的存储单元也将被访问。
虚拟内存技术就是基于局部性原理，时间局部性通过将最近使用的指令和数据保存到高速缓存中；空间局部性通过使用较大的高速缓存，并将预取机制继冲到高速缓存的控制逻辑中实现。
③虚拟存储器的定义和特征
定义：基于局部性原理，在程序装入时，仅将程序当前要运行的少数页面或段先装如内存，而将其他部分暂留在外存，便可启动程序执行。
- 在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。
- 另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。
这样，系统好像为用户提供了一个比实际内存容量大得多的存储器，称为虚拟存储器。
虚拟存储器的三个主要特征：
- 多次性。 作业运行时无需一次性装入内存，而分成多次，在需要时装入内存运行。
- 对换性。 无需在作业运行时一直常驻内存，在进程运行期间，允许将那些暂时不用的程序或数据调出内存。
- 虚拟性。 从逻辑上扩充内存，使得用户看到的内存容量远远大于实际的内存容量。
④虚拟内存技术的实现
虚拟内存的实现需要建立在离散分配的内存管理方式上的基础上。
虚拟内存的是现有以下三种方式：
- 请求分页存储管理。
- 请求分段存储管理。
- 请求段页式存储管理。
不管哪种方式，都需要一定的硬件支持。一般需要的支持有以下几个方面：
- 一定容量的内存和外存
- 页表机制（或段表机制）作为主要数据结构。
- 中断机构，每当用户程序要访问的部分尚未调入内存时，则产生中断。
- 地址变址机构，逻辑地址到物理地址的转换。
⑤内存分配策略
采用可变分配局部置换的策略。为每个进程分配一定数目的物理块，当某进程发生缺页时，只允许从该进程的在内存的页面中选择一页换出，因此不会影响其他进程的运行。
若进程在运行中频繁的发生缺页中断，则系统再为该进程分配若干物理块，直至该进程的缺页趋于适当；反之，则少给该进程分配物理块。
⑥如何调入页面
当进程所访问的页面不在内存中时，便向CPU发出缺页中断，中断响应后便转入缺页中断处理程序。通过寻找页表找出该页的物理块，若内存未满，则调入内存中。如果内存已满，按照页面置换算法从内存中调出一个页面置换。
2.页面置换算法进程运行时，如果访问页面不在内存中则需要从将其调入内存。但内存如果已经无空闲空间，则需要从内存中调出一页程序或数据，选择调出页面的算法就称为页面置换算法。
常见的页面置换算法有4种。
①最佳（OPT）置换算法
这是一种理想算法，无法实现，因为系统无法预判将要出现的页面。
具体来说，最佳置换算法选择的被淘汰的页面时以后永不使用的页面，或者最长时间内不再被访问的页面。
②先进先出页面置换算法（算法性能差）
优先淘汰**最早进入内存的页面，即淘汰再内存中驻留时间最久的算法。**但该算法与实际运行时的规律不适应，因为在进程种有的页面经常被访问。
会发生贝拉比异常：分配物理块变多时，缺页频率会变多。
③最近最久未使用置换算法（LRU算法）
选择最近最长时间未被访问过的页面给予淘汰，它认为过去一段时间为访问过的页面，在最近的将来也不会被访问。
LRU算法性能较好，但需要寄存器和栈的硬件支持。
贴一道leetcode经常面试的题：
https://leetcode.cn/problems/lru-cache/
146. LRU 缓存难度中等2279
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
- LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
- int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
- void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
LRU缓存用**一个双向链表和一个哈希表数据结构（哈希链表）**来实现。
- 链表存放的是页面（本题中是键值对），作为存放页面的容器；
- 哈希表则根据键值对来查询所要查找的页面在容器（双向链表）中的位置。链表从左往右为最近使用->最久不使用。
主要有三个操作：
- 缓存初始化 ：设置缓存能存放页面的数量（_capacity）,当前缓存中页面的数量（设置为0）.
- 查找页面是否在缓存中操作int get(int key)： 如果要查找的页面不在缓存中返回-1；如果在页面中，则把要查找的页面变成最近使用的页面。
- 页面置换操作void put(int key, int value) ： 如果要置换的页面key在缓存中，则改变页面的内容，并将其变成最近使用的页面；如果要置换的页面key不在缓存中：并且如果缓存已经满，需要将最近最少使用的页面调出内存，再调入最新的页面，否则直接调入最新的页面。
【使用自带list容器版本】
//链表头存放的是最近使用的页面，链表末尾存放的是最近最长不使用的页面
class LRUCache {
private:
int _size; //lru缓存中已存在的页数
int _capacity; //lru缓存中可容纳的页数
list> _lru; //用双向链表作为lru缓存的容器
unordered_map>::iterator> _map; //哈希表用来存放键值key的页面在缓存中的位置
public:
LRUCache(int capacity) : _size(0), _capacity(capacity) {}
int get(int key) {
auto it = _map.find(key);
//要访问的键值为key的页面在缓存中
if (it != _map.end()) {
//list中的splice(pos1, list2, pos2)函数的作用是剪切：将list2中pos2位置元素剪切，并粘贴到当前list中的pos1位置
_lru.splice(_lru.begin(), _lru, it->second);
return it->second->second;
}
return -1;
}
void put(int key, int value) {
auto it = _map.find(key);
//想要添加的页面在缓存中
if (it != _map.end()) {
_lru.splice(_lru.begin(), _lru, it->second);
it->second->second = value;
return;
}
//要添加的页面不在缓存中
if (_size == _capacity) {
--_size;
_map.erase(_lst.back().first);
_lru.pop_back();
}
_lru.emplace_front(key, value);
_map[key] = _lru.begin();
++_size;
}
};
【自写双向链表版本】
//双向链表头位置放的是最近最长不使用的页面，尾位置放的是最近使用的页面
class Node {
public:
Node() = default;
Node(int key, int val) :key(key), val(val), prev(nullptr), next(nullptr) {}
int key = 0;
int val = 0;
Node* prev = nullptr;
Node* next = nullptr;
};
//LRUCache
class LRUCache {
private:
Node* _head, * _tail; //头尾哨兵
int _size;
int _capacity;
unordered_map _map;
public:
LRUCache(int capacity) :_capacity(capacity), _size(0) {
_head = new Node;
_tail = new Node;
_head->next = _tail;
_tail->prev = _head;
}
int get(int key) {
auto it = _map.find(key);
if (it != _map.end()) {
Node *node = moveToTail(key, it);
return node->val;
}
return -1;
}
void put(int key, int val) {
auto it = _map.find(key);
if (it != _map.end()) {
Node* node = moveToTail(key, it);
node->val = val;
return;
}
if (_size == _capacity) {
--_size;
Node* tmp = _head->next;
_map.erase(tmp->key);
_head->next = tmp->next;
tmp->next->prev = _head;
delete tmp;
}
pushBack(key, val);
}
Node* moveToTail(int key, unordered_map::iterator it) {
Node* node = it->second;
Node* pre = node->prev;
Node* next = node->next;
pre->next = next;
next->prev = pre;
node->prev = _tail->prev;
node->next = _tail;
_tail->prev->next = node;
_tail->prev = node;
return node;
}
void pushBack(int key, int value) {
Node* node = new Node(key, value);
Node* pre = _tail->prev;
pre->next = node;
node->prev = pre;
node->next = _tail;
_tail->prev = node;
_map[key] = node;
++_size;
}
};
④时钟（clock）置换算法
LRU算法性能接近OPT算法，但实现起来开销大。因此，操作系统试图用比较小的开销来接近LRU算法，这类算法都是clock算法的变体。
