背景知识
-
局部性原理：
- 时间局限性：如果程序中某条执行被执行，则不久后该指令还可能被在次执行。如果某条数据被访问过，则不久以后该数据还可能被继续访问。产生时间局限性经典原因是存在程序中存在大量的循环操作
- 空间局限性：一旦程序访问了程序访问了某个存储单元，在不久以后其附近的存储单元也将被访问，即程序在一段时间内访问的地址可能集中在一定的范围之内，其典型情况便是程序的顺序执行（虽然存在过程调用，使程序的执行轨迹由一部分区域转向另一部分区域，，但研究表明，过程调用的深度在大多数情况下不超过5）。
虚拟存储器
虚拟存储器基本工作情况：
基于程序的局部性原理可知，应用程序在运行前没必要将作业全部装入内存，而仅将当前要运行的少数页面装入内存便可运行，其余部分暂留在盘上。程序运行时，若它所要访问的页已调入内存，便可继续执行下去，但若未调入内存（称为缺页或缺段），便发出缺页/缺段请求，此时，os将利用请求调页/段功能将它们调入内存，以便进程能继续执行下去。如果此时内存已满，无法装入新的页/段，os还需利用页/段置换功能，将内存中暂时不用的页/段调至盘上，腾出足够的内存空间后，再将要访问的页/段调入内存，是程序继续执行下去。虚拟存储器的定义：
具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种储存器系统（基于程序的局部性原理）。其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近内存，而每位成本却又接近于外存。-
虚拟存储器的实现方法：
- 分页请求系统：在分页系统的基础上增加了请求调页功能和页面置换功能所形成的页面时虚拟存储系统。置换时以页为单位。
- 请求分段系统：在分段系统的基础上，增加了请求调段及分段置换功能所形成的段式虚拟存储系统。置换时以段为单位。
页面置换算法：
最佳置换算法：所选择的被淘汰页面是以后永不使用的，或是在最长时间内不再被访问的页面。但由于目前人们无法预知哪个页面时未来最长时间内不再被访问的，因此该算法是无法实现的。
先进先出（FIFO）页面置换算法：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。实现方法为：把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针（称为替换指针），始终指向最老的页面。但是该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如含有全局变量，常用函数，例程等的页面，FIFO算法不能保证这些页面不被淘汰。不需要特定的硬件支持，实现方式简单
最近最久未使用（LRU）置换算法：选择最近最久未使用的页面予以淘汰，利用“最近的过去”，作为预测“最近的将来”的依据。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有页面中t值最大的淘汰。实现方法：可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，再将它压入栈顶。因此栈顶始终是最新访问页面的编号，栈底永远是最近最久未被访问的页，若发生缺页中断，且内存已满的情况时，应选择栈底页面予以淘汰。需要特定的硬件支持，如寄存器和栈，实现方式较FIFO复杂
LRU算法的代码实现
from collections import OrderedDict
class LruCache():
def __init__(self, size):
self.size = size
self.cache = OrderedDict()
def get(self, key):
if key in self.cache:
self.cache.move_to_end(key)
value = self.cache[key]
else:
value = None
return value
def set(self, key, value):
if key in self.cache:
self.cache[key] = value
self.cache.move_to_end(key)
else:
if self.size <= len(self.cache):
self.cache.popitem(last=False)
self.cache[key] = value
else:
self.cache[key] = value
以上算法采用了collection库中的Orderdict类，该类为dict的一个子类，详情见官网,简单来说就是该类实现了有序dict。
以下为测试用例及输出结果：
a = LruCache(5)
for i in range(0, 4):
a.set(i, i*10)
print(a.cache, a.cache.keys())
print(a.get(2))
print(a.cache, a.cache.keys())
a.set(6, 666)
print(a.cache, a.cache.keys())
a.set(8, 888)
print(a.cache, a.cache.keys())
C:\Users\19205\AppData\Local\Programs\Python\Python36-32\python.exe C:/Users/19205/Desktop/lru.py
OrderedDict([(0, 0), (1, 10), (2, 20), (3, 30)]) odict_keys([0, 1, 2, 3])
20
OrderedDict([(0, 0), (1, 10), (3, 30), (2, 20)]) odict_keys([0, 1, 3, 2])
OrderedDict([(0, 0), (1, 10), (3, 30), (2, 20), (6, 666)]) odict_keys([0, 1, 3, 2, 6])
OrderedDict([(1, 10), (3, 30), (2, 20), (6, 666), (8, 888)]) odict_keys([1, 3, 2, 6, 8])
最少使用（LFU）置换算法：该算法淘汰页面的依据是页面被访问的频率，选择在最近时期使用最少的页面作为淘汰页
Clock置换算法：
页面缓冲算法（PBA）：显著降低了页面换进换出的频率，使磁盘I/O的操作次数大为减少，因而减少了页面换进换出的开销。实现方式：在内存中设置了两个链表：空闲页面链表：实际上该链表是一个空闲物理块链表，是系统掌握的空闲物理块，用于分配给频繁发生缺页的进程，以降低该进程的缺页率 。修改页面链表：它是由已修改的页面所形成的链表。设置该链表的目的是为了减少已修改页面换出的次数。
