操作系统：内存页的替换

问题：虚拟页被分配使用之后，在页表中一定有到相应的物理页的映射吗？答案是否定的。

举个例子：电脑只有4g内存，但是要同时打开一个占用3g内存和一个2g内存的游戏，怎么办呢？这里面就涉及到了换页(page swapping)机制。

换页的设计思想

换页的基本思想就是当物理内存不够时，操作系统将若干物理页的内容写到类似于磁盘这种更大更便宜的存储设备中，然后就可以回收物理页并继续使用了。

换页的步骤：

当操作系统希望从应用程序A那里回收物理页P（对于应用程序中的虚拟页V）时，操作系统需要将P写入到磁盘中的一个位置，然后再应用程序A的页表中去除对虚拟页V的映射，同时记录该物理页被换到磁盘上的对应位置。该过程称为P的换出(swap out)，物理页P就可以被操作系统回收，并且分配给别的应用程序使用。此时，虚拟页V就处于已分配但未映射至物理内存的状态。

缺页异常

当应用程序访问已分配但未映射的页时，就会触发缺页异常。此时CPU会运行操作系统预先设置的缺页异常处理函数，该函数就会找到一个空闲的物理页然后把之前的内容加载到这个物理页中，并在页表中增加虚拟地址到这一物理页的映射。这个过程称为换入。然后CPU可以回到发生缺页异常的地方继续运行。

预取(prefetching)机制

由于换页过程涉及到耗时的磁盘io，因此在发生换入操作时，操作系统就设计了预取机制。预测还有哪些页将要被访问，也将它们一并换入物理内存，减少发生缺页异常的次数。

按需页分配

当应用程序申请分配内存时，操作系统可选择将新分配的虚拟页标记为已分配但未映射至物理内存的状态。当应用程序访问这个虚拟页的时候，会触发缺页异常，于是操作系统才真正为这个虚拟页分配对应的物理页。

页替换策略

当需要分配物理页时，若空闲的内存已经用完或者小于某个阈值，就需要通过页替换策略将某些物理页换出，以腾出物理内存的空间。

MIN/OPT策略

MIN(Minimum)策略又称为OPT策略(Optimal策略，最优策略），是一种理想化的换页策略。在选择被换出的页时，优先选择未来不会再访问的页，或者在最长时间内不会再访问的页。这个策略是理论最优的页替换策略，在实际场景中很难实现。因为页访问的顺序取决于应用程序。但是它可以作为一个标准来衡量其他替换策略的优劣。

FIFO策略

FIFO是先进先出的策略。其策略直观、开销低，但是在实际使用中往往表现不好，因为页换入换出顺序与使用是否频繁通常没有关联。

Second Chance策略

这个是FIFO的改进版本，为每个物理页号维护一个访问标志位，如果访问的页号已经在队列中，则为其置上标志位。在寻找要换出的页时，优先寻找队头的页号，如果它的标志位没有被置上，就换出，否则将其标志位清零，放到队尾。那么最坏情况下（初始时全部页都已经被访问过），它会暂时退化为FIFO，把队头的页面换出。

Belady异常

通常来说，系统分配给一个应用程序的物理页数量越多，换页次数越少。但是有的时候更多的可用物理内存会导致更多的换页、更低的性能，这就是Belady异常。可能在操作系统采用FIFO或者Second Chance等页替换策略时发生。

然后，我写了这么一个程序去随机生成访问序列，找到了一个序列，会出现Belady异常

其中，红色三角形代表的是缺页，白色圆形代表页面命中。

代码如下：

import random
import time
random.seed(time.time())
q = []

size = 12 # 页面访问数量
kinds = 5 # 页面种数
queue_max_size = kinds - 1 # 页框的最大大小

# 记录缺页次数
times = []

def check_page_swap():
    for i in range(1, len(times)):
        if times[i] > times[i-1]:
            return True
    return False

rows = []
seq = []
js = 0


while not check_page_swap():
    js += 1
    if js % 10000 == 0:
        print("正在计算...第{}次".format(js))
    times.clear()
    # 页面访问顺序
    seq.clear()
    # 随机生成页面访问顺序
    for _ in range(0, size):
        seq.append(random.randint(1, kinds))

    rows.clear()

    for sz in range(1, queue_max_size+1):
        row = ''
        q.clear()
        ans = 0
        for s in seq:
            if not s in q:
                if len(q) >= sz:
                    q.pop(0)
                q.append(s)
                # 换页次数+1
                ans += 1
                row += "🔺"
            else:
                row += "⚪"
        times.append(ans)
        rows.append(row)

print("页框大小\t", end='')
for s in seq:
    print("%s" % str(chr(ord('A')-1 +s)), end='')
print('\t缺页次数')
for i in range(1, queue_max_size + 1):
    print("{}\t{}\t{}".format(i, rows[i-1], times[i-1]))

LRU策略

LRU(Least Recently Used)策略在选择被换出的页时，优先选择最久未被访问的页。该策略的出发点在于：过去数条指令很可能在后续的数条指令种被频繁访问。

MRU策略

MRU(Most Recently Used)策略在替换内存页时，优先换出最近访问的内存页。该策略基于的假设是：程序不会反复的访问相同的地址，如视频播放器。

时钟算法策略

时钟算法是将换入的物理内存页号排成时钟的形状，时钟有一个针臂，指向新换入内存的页号的后一个。同时也为每个页号维护一个访问标志位。每次选择要换出的页号时，从针臂开始检查。如果当前页号的访问位没有设置，则将其替换。如果已经被置上访问位，那就将其清空，并且针臂移动到下一个页号。这个与Second Chance有相似之处，但是在确实还是有区别的。比如插入的位置不同、不需要将页号移到队尾。

工作集模型

如果选择的内存替换策略与实际的工作负载不匹配，就可能导致颠簸(thrashing)现象，造成严重的性能损失。

工作集模型能有效地避免颠簸现象的发生。

工作集是“一个程序在时间t的工作集W为它在时间区间[t-x,t]使用的内存页集合，也被视为它在未来（下一段x时间内）会访问的内存页集合”。该模型认为应当将应用程序的工作集同时保持在物理内存中，优先将非工作集中的页换出。

如何高效地追踪工作集？

常见的方法是工作集时钟算法。操作系统设置一个定时器，每经过固定的时。间间隔，一个设置好的工作集追踪函数就会被就会被调用。该追踪函数为每个内存页维护两个状态：上次使用时间和访问位，均被初始化为0.每次调用，该函数都会检查每个内存页的状态。如果访问位为1，则说明在此次时间间隔内该页被访问过，于是该函数会把当前系统时间赋值给该内存页的上次使用时间。该方法的前提是CPU会在访问内存页的时候自动把对应的访问位设置为1.如果访问位为0，则说明在该时间间隔内没有被访问，于是该函数就会计算该页的年龄（当前系统时间-该页上次使用时间），若该页的年龄超过了预设的时间间隔，就不再属于工作集。检查完一个页的状态后，该工作集追踪函数将其访问位设置为0。

参考资料 《现代操作系统：原理与实现》

转载请注明来源：https://www.longjin666.top/?p=1177