FIFO的Belady现象
缺 页 次 数 缺 页 次 数
0 (a) 正常情况
m分配页面数
0
m分配页面数 (b) Belady现象
举例
(3)最近最久未使用页面( 当需要淘汰某一页时，选择离当前时间最近的 一段时间内最久没有使用过的页先淘汰。即当 需要淘汰一页时，选择最长时间未使用的页。 基于假设： 如果某页被访问，它可能马上还要被访问；相 反，如果某页长时间未被访问，它可能最近也 不可能被访问。 算法的实现（软件）： 为每页设置一个特定的单元，用于记录自上次 访问以来所经历的时间t，当需要置换一页时， 选择t最大的淘汰。
请求页式管理中的置换算法

目的：选出一个被淘汰的页面，该页应该是 被访问概率最低的页。 常见的置换算法有4种：
(1) 随机淘汰算法（Random Glongram） (2) 轮转法（Round Robin）和先进先出(FIFO) (3) 最近最久未使用页面置换算法（Least recent Used） (4) Clock置换算法 （Clock Algorithm） (5) 理想型淘汰算法OPT（Optimal Replacement Algorithm）

基本思想：需要淘汰某一页时，首先淘汰 到当前时间为止，被访问次数最少的那一 页。

算法的实现：修改页表 在页表中给一页增设一个访问计数器， 即可实现。每当该页被访问时，访问计 数器加1。 发生缺页中断时，淘汰计数值最小的那 一页，并将其计数器清0。
b)最近没有使用页面淘汰算法NUR

基本思想：需要淘汰某一页时，从那些最近 一个时期未被访问的页中任选一页淘汰。 算法的实现：修改页表
如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰
的页。
（2010年题）设某计算机的逻辑地址空间和物理地址空
间均为64KB，按字节编址。某进程最多需要6 页数据存 储空间，页的大小为1KB，操作系统采用固定分配局部置 换策略为此进程分配4 个页框。
当该进程执行到时刻260 时，要访问逻辑地址为 17CAH 的数据。请回答下列问题： （1）该逻辑地址对应的页号时多少？ （2）若采用先进先出(FIFO)置换算法，该逻辑地址 对应的物理地址？要求给出计算过程。



思想：先进入内存的页，先退出内存。 实质：淘汰在内存驻留时间最长的页。 理由：最早调入内存的页，不再被使用的可能性比近期 调入内存的大。 FIFO算法简单，实现容易。

由实验和测试发现FIFO算法和RR算法的内存利用 率不高。
FIFO和RR内存利用率低的原因


两种算法都是基于处理器按线性顺序访问 地址空间这一假设。事实上，许多时候， 处理器不是按线性顺序访问地址空间的。 例如，执行循环结构的程序段。 使用FIFO算法时，在未给进程或作业分配 足够它所需要的页面数时，有时会出现分 配的页面数增，缺页次数反而增加的现象 （Belady现象）。
如何淘汰——置换算法
用来选择淘汰哪一页的规则叫置换算法。
刚被淘汰出去的页，过后不久又要访问， 而调入不久又被淘汰，然后又要访问，又调入， 如此反复，使得系统把大部分时间用在了页面 的调进和调出上——抖动、颠簸 好的页面置换算法能适当降低页面的更 换频率，尽量避免系统“抖动”，评价指标— —缺页次数和缺页率
当该进程执行到时刻260 时，要访问逻辑地址为 17CAH 的数据。请回答下列问题： (3)采用时钟(Clock)置换算法，该逻辑地址对应的物理 地址是多少？要求给出计算过程。（设搜索下一页的 指针按顺时针方向移动，且指向当前2号页框，示意 图如下）
解：(1) 17CAH =0001 0111 1100 1010 B ，由于页的大小为 1KB，则页内位移有10 位，页号为00101B，所以页号为5。 (2)根据FIFO算法，需要替换装入时间最早的页，故 需要置换装入时间最早的0号页，即将5号页装入到7 号页框 中，即页框号为111，与页内位移拼接得到对应的物理地址 为0001 1111 1100 1010B = 1FCAH。 (3)根据CLOCK 算法，如果当前指针所指页框的使用 位为0 时，则替换该页；否则将使用位清0，并将指针指向 下一个页框，继续查找。根据题设和示意图，将从2 号页框 开始查找，前4次查找页框号的顺序为2->4->7->9，并将对 应页框使用位清0。在第5次查找中，指针指向2号页框，这 时2号页框的使用位为0，故置换2号页框对应的2号页，将5 号页转入2号页框中，并将对应使用位设置为1，所以对应的 物理地址为0000 1011 1100 1010B=0BCAH 。
1. 简单的Clock置换算法
入口
查寻指针前进一步，指向 下一个表目
页面访问位＝ 0? 是 选择该页面淘汰
否
置页面访 问位＝“ 0”
返回
图 简单Clock置换算法的流程
2. 改进型Clock置换算法
在将一个页面换出时，如果该页已被修改过，便须 将它重新写到磁盘上；但如果该页未被修改过，则不必将 它拷回磁盘。把同时满足两条件的页面作为淘汰的页。由 访问位A和修改位M可以组合成下面四种类型的页面： 1 类（A=0，M=0）。表示该页最近既未被访问、又 未被修改，是最佳淘汰页。 2 类（A=0，M=1）。表示该页最近未被访问，但已 被修改，并不是很好的淘汰页。 3 类（A=1，M=0）。最近已被访问，但未被修改， 该页有可能再被访问。 4 类（A=1，M=1）。最近已被访问且被修改，该页 有可能再被访问。

和纯分页的不同点：请求分页技术当一个用户程序要调
入内存时，不是将该程序全部装入内存，而是只装入部分页 到内存，就可启动程序运行，在运行的过程中，如果发现要 运行的程序或要访问数据不在内存，则向系统发出缺页中断 请求，系统在处理这个中断时，将在外存相应的页调入内存， 该程序继续运行。
请求分页要解决的问题
(1) 随机淘汰算法
在系统设计人员无法确定哪些页被访问 的概率较低时，明智的作法是随机地选择某 个用户的页并将其换出。
(2) 轮转法和先进先出法


轮转法：循环换出内存可用区内一个可以 被换出的页，无论该页是刚被换进或已换 进内存很长时间。 FIFO法：总是选择在内存驻留时间最长的 一页将其淘汰。
2. 请求页式存储管理

问题的提出
纯页式存储管理提高了内存的利用效率，但并不 为用户提供虚存，换句话说，当一个用户程序的页数 大于当前总空闲内存块数时，系统就不能将该程序装 入运行。即用户程序将受到物理内存大小的限制。为 了解决这个问题，人们提出请求分页存储管理技术。
请求分页概念

请求分页的实现思想 和纯分页的相同点：逻辑空间分页，内存空间分块。
(1) 从指针所指示的当前位置开始， 扫描循环队列， 寻找 A=0且M=0的第一类页面， 将所遇到的第一个页面作为所选中 的淘汰页。 在第一次扫描期间不改变访问位A。 (2) 如果第一步失败，即查找一周后未遇到第一类页面， 则
开始第二轮扫描，寻找A=0且M=1的第二类页面，将所遇到的第
一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过 的页面的访问位都置0。 (3) 如果第二步也失败，亦即未找到第二类页面，则将指针 返回到开始的位置，并将所有的访问位复0。 然后重复第一步，
（1）OPT （2）FIFO （3）LRU
某程序在内存中分配三个页面，初始为空，页面走向 为4，3，2，1，4，3，5，4，3，2，1，5。
OPT 4 3 2 1 4 3 5 4 3 2 1 5 页1 4 3 2 1 1 1 5 5 5 2 1 1 页2 4 3 3 3 3 3 3 3 5 5 5 页3 4 4 4 4 4 4 4 4 4 4 x x x x 3 3 x 3 3x x 3 共缺页中断7次


在页表中增设一个访问位，当某页被访问时， 访问位置1；否则，访问位置0。系统周期性地 对所有引用位清0。 当需要淘汰一页时，从那些访问位为0的页中 选一页进行淘汰。

(4) Clock置换算法

基本思想：当要调入一新页而必须淘汰一 旧页时，所淘汰的页是没有被访问过的页 面，即访问位是0的页面。
FIFO 4 3 2 1 页1 4 3 2 1 页2 4 3 2 页3 4 3 x x x x 共缺页中断9次
4 4 1 2 x
3 3 4 1 x
5 5 3 4 x
4 3 2 1 5 5 5 2 1 1 3 3 5 2 2 4 4 3 5 5 3 3x x 3
LRU 4 3 2 1 页1 4 3 2 1 页2 4 3 2 页3 4 3 x x x x 共缺页中断10次

调入策略——从何处调入页面
在请求分页系统中的外存分为两部分：用于存放文件的文
件区和用于存放对换页面的对换区。对换区的磁盘I/O速度比 文件区的高。这样，每当发生缺页请求时，系统应从何处将缺 页调入内存，可分成如下三种情况：
(1)系统拥有足够的对换区空间 ，这时可以全部从对换区
调入所需页面，以提高调页速度。为此，在进程运行前， 便 须将与该进程有关的文件，从文件区拷贝到对换区。


举例
LRU的近似算法


要完全实现LRU算法是一件十分困难的事件， 在实际系统中往往使用LRU的近似算法。 比较常用的近似算法有：
a)最不经常使用页面淘汰算法LFU（Least Frequently Used） b)最近没有使用页面淘汰算法NUR（Not Used Recently）
a)最不经常使用页面淘汰算法

采用这种技术要解决以下问题：
(1) 如何发现执行的程序或访问的数据不在内存；
(2) 程序或数据何时何处调入内存，调入策略；
(3) 当一些页调入内存时，内存没有空闲内存时， 将淘汰哪些页，淘汰策略。
数据结构
为了实现请求分页技术，页表应增加相应的内容，反映 该页是否在内存，在外存的位置，在内存的时间的长短等。