5.3. 虚拟存储管理

1. 进程运行过程中，访问的页面不在内存，调入时内存已无空闲空间，需要将内存中的一页程序或数据调到外存。

页面置换算法(page replacement algorithms)：选择换出哪些页面的算法，其好坏直接影响系统的性能。

1. 应具有较低的缺页率：

1. 最佳Optimal置换算法
2. 先进先出FIFO置换算法
3. 最近最久未使用(LRU)置换算法
4. CLOCK置换算法
5. 其他

1. 最佳（Optimal）置换算法

1. Belady，1966年提出的一种理论上的算法
   • 换出以后永不再用的，或在最长(未来)时间内不再被访问的页面。

优点：保证获得最低的缺页率

不足：无法实现，因为无法预知一进程将来的运行情况

作用：作为参照标准，评价其他算法。

1. 例1：假设一个作业，运行中依次使用的页面情况如下，分配给该进程的内存物理块只有3个，按最佳置换算法，内存中的页面如何变化，缺页率是多少？

2）先进先出置换算法（FIFO）

1. 先进入的先淘汰，即选择内存中驻留时间最久的页面予以淘汰。
   • 优点：实现简单，把一进程已调入内存的页面按先后次序组织成一个队列，并设置一个指针(替换指针)，使它总是指向队首最老的页面。
   • 不足：与进程实际运行规律不相适应（较早调入的页往往是经常被访问的页，频繁被对换造成运行性能降低）

*Belady 现象

1. Belady现象：出现分配的页面数增多，缺页率反而提高的异常现象。
2. 描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。
3. Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征矛盾，即被置换的页面并不是进程不会访问的。

3）最近最久未使用(LRU)置换算法

1. 无法预测将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法选择最近最久未使用（least recently used）的页面予以淘汰。
2. 对例1用LRU算法计算：

1. 不足：
   • 有时页面过去和未来的走向之间并无必然的联系。
   • 相应的需较多的硬件支持：记录每个页面自上次被访问以来所经历的时间t，淘汰时选择页面t值最大的；以及需要快速地知道哪一页是最近最久未使用的页面，用寄存器或栈。

• 寄存器记录时间的原理

1. 一进程有8个页面，每个页面需配备一个8位的（移位）寄存器。

       移位寄存器表示为

            R=Rn-1Rn-2Rn-3…R2R1R0

1. 页面被访问后的操作：
   • 将该页对应的寄存器的Rn-1位置为1
2. 如何记时：
   • 由系统发出定时信号，每隔一定时间将所有寄存器右移1位。
   • 某一时刻，比较各寄存器的值，被用到的标志1逐渐往低位上积累，若高位上没有1，就说明最近没用过。所以最近最久未使用的就是寄存器值最小的那个页。

1. 某页面被访问，便将该页面的页面号从栈中移出，将它压入栈顶。因此：栈顶始终是最新被访问页面的编号，越久未使用，页面越被压在栈底。

练习：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。

试分别利用OPT、FIFO及LRU算法计算缺页次数。

4）轮转算法(clock)
又称最近未使用算法(NRU, Not Recently Used)，

1. LRU(最近最久未使用算法)近似算法
   • 折衷FIFO

1. 每个页设一个使用标志位(use bit)，若该页被访问则将其置为1。
2. 设置一个指针，从当前指针位置开始按地址先后检查各页，寻找use bit=0的页面作为被置换页。
3. 若指针经过的页use bit=1，修改use bit=0（暂不凋出，给被用过的页面驻留的机会 ），指针继续向下。到所有页面末尾后再返回队首检查。

时钟算法示例

改进CLOCK

1. 改进：主要考虑对没访问过的页面再细分是否修改过的不同情况，减少因修改造成的频繁I/O操作。
2. 每页除记录是否用过A，还记录是否修改的标志M。置换时根据两个标志的值有4种不同情况的处理。

5）其他置换算法

• 最少使用 (LFU, Least Frequently Used)
  • 关键在次数记录上
  • 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；缺页中断时，淘汰计数值最小的页面，并将所有计数清零；
  • 计数的实现类似LRU，用移位寄存器，但比较时不是简单比较寄存器的值，而是比较寄存器每位的和∑Ri。

1. LRU与LFU

1000101

0001111

1. • LFU置换次数少的。程序局部性会导致一个页面在一段时间内使用次数很多。但使用次数多并不能说明将来被用到的可能性大
   • 而LRU置换最近最久未用的，对未来的预计一般会更好些。
2. 所有，LRU相对得到较好的应用。

• 页面缓冲算法PBA(page buffering algorithm)
  • 对FIFO算法的发展，弥补了FIFO可能造成的I/O开销，又不需要LRU等算法的硬件支持。
  • 仍用FIFO算法选择被置换页
  • 但并不将其马上换入外存。
  • 系统将页面放入两个链表之一：如果页面未被修改，就将其归入到空闲页面链表的末尾；否则将其归入到已修改页面链表。
  • 需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除（从空闲链表摘下）。
  • 空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。
  • 当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。

2012考研试题

某请求分页系统的局部页面置换策略如下： 系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。

进程P依次访问的<虚拟页号，访问时刻>是：

<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>。

请回答下列问题:

 1）访问<0,4>时，对应的页框号是什么？

 2）访问<1,11>时，对应的页框号是什么？说明理由。

 3）访问<2,14>时，对应的页框号是什么？说明理由。

 4）该策略是否适合于时间局部性好的程序？说明理由。

解答：

（1）页框号为21。（1 分）

理由：因为起始驻留集为空，而0 页对应的页框为空闲链表中的第三个空闲页框（21），其对应的页框号为21。（1 分）

（2）页框号为32。（1 分）

理由：因11>10 故发生第三轮扫描，页号为1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。（1 分）

（3）页框号为41。（1 分）

理由：因为第2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。（1 分）

（4）合适。（1 分）

理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。（1 分）

2013考研题

若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是  B

     I. 处理越界错        II. 置换页         III. 分配内存

1.   仅 I、II         B. 仅 II、III        
2.   仅 I、III        D. I、II和 III

2009年考研题

请求分页管理系统中，假设某进程的页表内容如下表所示。  

1. 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。
2. 假设①TLB初始为空；
          ②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；
          ③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。
3. 设有虚地址访问序列2362H、1565H、25A5H，请问：  

(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。

(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

解答

（1）

1. 根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。
2. 页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。

可得三个虚地址的页号P如下：2    1    2

1.  2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
2.  1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，重新执行指令，访问快表命中10ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+10ns+100ns=100000220ns。 
3.  25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。

（2）

1. 当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

2010年考研试题

设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）。

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：

（1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。

（3）若采用时钟（CLOCK）置换算法，设搜索下一页的指针沿顺时针方向移动，当前指向2号页框，示意图如下。该逻辑地址对应的物理地址是多少？要求给出计算过程。

解答：

17CAH=(0001 0111 1100 1010)2

（1）页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以第一问的解为：5

（2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为：
(0001 1111 1100 1010)2---1FCAH

（3）CLOCK,则被置换的页面所在页框为2，所以对应的物理地址为:
(0000 1011 1100 1010)2---OBCAH

作业：

1. 简述OPT、FIFO、LRU三种页面置换算法的基本思想。
2. 缺页次数与置换次数是同一个概念吗？
3. 考虑下面的页面访问串：
   1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
   当分配给该作业4个物理块时，分别采用OPT、 LRU 、 FIFO三种页面置换算法计算缺页次数及缺页率。假定4个物理块初始均为空，每个页面均请求调入方式。

1. 假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…15。设某作业有4页，其页号为0，1，2，3，被分别装入主存的2、4、1、6块。试问：
   1. 该作业的总长度是多少字节？
   2. 写出该作业每一页在主存中的起始地址；
   3. 对多个逻辑地址[0，100]、[1，50]、[2，0]、[3，60]，试计算出相应的内存地址。

※ 虚拟存储管理下访问内存的有效时间

1. 请求分页管理方式下，存在三种方式的内存访问
   • 页在内存，且快表检索命中
     • EAT= l + t
   • 页在内存，但快表检索没有命中
     • EAT= 快表检索时间+访问页表时间+修改更新快表时间+访问页面物理内存时间
     • l +t+ l +t=2*(l +t)

• • 页面不在内存
    • EAT=快表检索时间+访问页表时间+缺页中断处理时间+修改更新快表时间+访问页面物理内存时间

• l + t + e + l  + t

• • 加入概率的综合公式(a是快表命中率，f是缺页率)
    • EAT= l  + a*t +(1-a)*{    }

• l  +a*t +(1-a)*{t + f*(e+l+t)  +(1-f)*(l+ t) }

1. 练习：

              现有一请求调页系统，其页表保存在寄存器中；若有一个可用的空页或被替换的页未被修改，则它处理一个缺页中断需要8ms；若被替换页已被修改，则它处理一个缺页中断需要20ms；内存存储时间为1μs，访问页表的时间可忽略不计；假定70%被替换页被修改过，为保证有效存取时间不超过2μs，可接受的最大缺页率是多少？

解答：

1. 设最大缺页率为p,则：

(1-p)*1μs+p(0.3*8ms+0.7*20ms+ 1μs) <=2μs

2400p+14000p+1-p<=2

16400p<=1

p<=0.006%

※ 影响缺页率的主要因素

（1）分配给作业的主存块数:

       多则缺页率低，反之则高。

(2)页面大小：

       大则缺页率低；反之则高。

(3)页面调度算法：

       对缺页中断率影响很大，但不可能找到一种最佳算法。

(4)程序编制方法：

       以数组运算为例，如果每一行元素存放在一页中，则按行处理各元素缺页中断率低；反之，按列处理各元素，则缺页中断率高。

。

思考题

1. 在一个页式虚存系统中，每页可容纳200个整数。有一个对二维数组int  a（100，100） 操作的程序。
2. 若系统分给该进程3个内存块，其中1块装入程序和变量i，j，另外两块存放数组页面来存储数组数据。数组存放时是按行存放的。

设程序段已经调入内存，请分别计算下列程序的缺页次数。

5.3. 虚拟存储管理

1. 进程运行过程中，访问的页面不在内存，调入时内存已无空闲空间，需要将内存中的一页程序或数据调到外存。

页面置换算法(page replacement algorithms)：选择换出哪些页面的算法，其好坏直接影响系统的性能。

1. 应具有较低的缺页率：

1. 最佳Optimal置换算法
2. 先进先出FIFO置换算法
3. 最近最久未使用(LRU)置换算法
4. CLOCK置换算法
5. 其他

1. 最佳（Optimal）置换算法

1. Belady，1966年提出的一种理论上的算法
   • 换出以后永不再用的，或在最长(未来)时间内不再被访问的页面。

优点：保证获得最低的缺页率

不足：无法实现，因为无法预知一进程将来的运行情况

作用：作为参照标准，评价其他算法。

1. 例1：假设一个作业，运行中依次使用的页面情况如下，分配给该进程的内存物理块只有3个，按最佳置换算法，内存中的页面如何变化，缺页率是多少？

2）先进先出置换算法（FIFO）

1. 先进入的先淘汰，即选择内存中驻留时间最久的页面予以淘汰。
   • 优点：实现简单，把一进程已调入内存的页面按先后次序组织成一个队列，并设置一个指针(替换指针)，使它总是指向队首最老的页面。
   • 不足：与进程实际运行规律不相适应（较早调入的页往往是经常被访问的页，频繁被对换造成运行性能降低）

*Belady 现象

1. Belady现象：出现分配的页面数增多，缺页率反而提高的异常现象。
2. 描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。
3. Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征矛盾，即被置换的页面并不是进程不会访问的。

3）最近最久未使用(LRU)置换算法

1. 无法预测将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法选择最近最久未使用（least recently used）的页面予以淘汰。
2. 对例1用LRU算法计算：

1. 不足：
   • 有时页面过去和未来的走向之间并无必然的联系。
   • 相应的需较多的硬件支持：记录每个页面自上次被访问以来所经历的时间t，淘汰时选择页面t值最大的；以及需要快速地知道哪一页是最近最久未使用的页面，用寄存器或栈。

• 寄存器记录时间的原理

1. 一进程有8个页面，每个页面需配备一个8位的（移位）寄存器。

       移位寄存器表示为

            R=Rn-1Rn-2Rn-3…R2R1R0

1. 页面被访问后的操作：
   • 将该页对应的寄存器的Rn-1位置为1
2. 如何记时：
   • 由系统发出定时信号，每隔一定时间将所有寄存器右移1位。
   • 某一时刻，比较各寄存器的值，被用到的标志1逐渐往低位上积累，若高位上没有1，就说明最近没用过。所以最近最久未使用的就是寄存器值最小的那个页。

1. 某页面被访问，便将该页面的页面号从栈中移出，将它压入栈顶。因此：栈顶始终是最新被访问页面的编号，越久未使用，页面越被压在栈底。

练习：某程序在内存中分配三个页面，初始为空，页面走向为4，3，2，1，4，3，5，4，3，2，1，5。

试分别利用OPT、FIFO及LRU算法计算缺页次数。

4）轮转算法(clock)
又称最近未使用算法(NRU, Not Recently Used)，

1. LRU(最近最久未使用算法)近似算法
   • 折衷FIFO

1. 每个页设一个使用标志位(use bit)，若该页被访问则将其置为1。
2. 设置一个指针，从当前指针位置开始按地址先后检查各页，寻找use bit=0的页面作为被置换页。
3. 若指针经过的页use bit=1，修改use bit=0（暂不凋出，给被用过的页面驻留的机会 ），指针继续向下。到所有页面末尾后再返回队首检查。

时钟算法示例

改进CLOCK

1. 改进：主要考虑对没访问过的页面再细分是否修改过的不同情况，减少因修改造成的频繁I/O操作。
2. 每页除记录是否用过A，还记录是否修改的标志M。置换时根据两个标志的值有4种不同情况的处理。

5）其他置换算法

• 最少使用 (LFU, Least Frequently Used)
  • 关键在次数记录上
  • 每页设置访问计数器，每当页面被访问时，该页面的访问计数器加1；缺页中断时，淘汰计数值最小的页面，并将所有计数清零；
  • 计数的实现类似LRU，用移位寄存器，但比较时不是简单比较寄存器的值，而是比较寄存器每位的和∑Ri。

1. LRU与LFU

1000101

0001111

1. • LFU置换次数少的。程序局部性会导致一个页面在一段时间内使用次数很多。但使用次数多并不能说明将来被用到的可能性大
   • 而LRU置换最近最久未用的，对未来的预计一般会更好些。
2. 所有，LRU相对得到较好的应用。

• 页面缓冲算法PBA(page buffering algorithm)
  • 对FIFO算法的发展，弥补了FIFO可能造成的I/O开销，又不需要LRU等算法的硬件支持。
  • 仍用FIFO算法选择被置换页
  • 但并不将其马上换入外存。
  • 系统将页面放入两个链表之一：如果页面未被修改，就将其归入到空闲页面链表的末尾；否则将其归入到已修改页面链表。
  • 需要调入新的物理页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第一项删除（从空闲链表摘下）。
  • 空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，只需较小开销，而被访问的页面可以返还作为进程的内存页。
  • 当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表，这样能大大减少I/O操作的次数。

2012考研试题

某请求分页系统的局部页面置换策略如下： 系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集（扫描时间忽略不计），本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。

假设不考虑其它进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。

进程P依次访问的<虚拟页号，访问时刻>是：

<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>。

请回答下列问题:

 1）访问<0,4>时，对应的页框号是什么？

 2）访问<1,11>时，对应的页框号是什么？说明理由。

 3）访问<2,14>时，对应的页框号是什么？说明理由。

 4）该策略是否适合于时间局部性好的程序？说明理由。

解答：

（1）页框号为21。（1 分）

理由：因为起始驻留集为空，而0 页对应的页框为空闲链表中的第三个空闲页框（21），其对应的页框号为21。（1 分）

（2）页框号为32。（1 分）

理由：因11>10 故发生第三轮扫描，页号为1 的页框在第二轮已处于空闲页框链表中，此刻该页又被重新访问，因此应被重新放回驻留集中，其页框号为32。（1 分）

（3）页框号为41。（1 分）

理由：因为第2 页从来没有被访问过，它不在驻留集中，因此从空闲页框链表中取出链表头的页框41，页框号为41。（1 分）

（4）合适。（1 分）

理由：如果程序的时间局部性越好，从空闲页框链表中重新取回的机会越大，该策略的优势越明显。（1 分）

2013考研题

若用户进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作是  B

     I. 处理越界错        II. 置换页         III. 分配内存

1.   仅 I、II         B. 仅 II、III        
2.   仅 I、III        D. I、II和 III

2009年考研题

请求分页管理系统中，假设某进程的页表内容如下表所示。  

1. 页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。
2. 假设①TLB初始为空；
          ②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；
          ③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。
3. 设有虚地址访问序列2362H、1565H、25A5H，请问：  

(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。

(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

解答

（1）

1. 根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。
2. 页面大小为4KB，即212，则得到页内位移占虚地址的低12位，页号占剩余高位。

可得三个虚地址的页号P如下：2    1    2

1.  2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。
2.  1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，重新执行指令，访问快表命中10ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+10ns+100ns=100000220ns。 
3.  25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。

（2）

1. 当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

2010年考研试题

设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页（Page）数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框（Page Fame）。

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据，请问答下列问题：

（1）该逻辑地址对应的页号是多少？

（2）若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。

（3）若采用时钟（CLOCK）置换算法，设搜索下一页的指针沿顺时针方向移动，当前指向2号页框，示意图如下。该逻辑地址对应的物理地址是多少？要求给出计算过程。

解答：

17CAH=(0001 0111 1100 1010)2

（1）页大小为1K，所以页内偏移地址为10位，于是前6位是页号，所以第一问的解为：5

（2）FIFO，则被置换的页面所在页框为7，所以对应的物理地址为：
(0001 1111 1100 1010)2---1FCAH

（3）CLOCK,则被置换的页面所在页框为2，所以对应的物理地址为:
(0000 1011 1100 1010)2---OBCAH

作业：

1. 简述OPT、FIFO、LRU三种页面置换算法的基本思想。
2. 缺页次数与置换次数是同一个概念吗？
3. 考虑下面的页面访问串：
   1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6
   当分配给该作业4个物理块时，分别采用OPT、 LRU 、 FIFO三种页面置换算法计算缺页次数及缺页率。假定4个物理块初始均为空，每个页面均请求调入方式。

1. 假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…15。设某作业有4页，其页号为0，1，2，3，被分别装入主存的2、4、1、6块。试问：
   1. 该作业的总长度是多少字节？
   2. 写出该作业每一页在主存中的起始地址；
   3. 对多个逻辑地址[0，100]、[1，50]、[2，0]、[3，60]，试计算出相应的内存地址。

※ 虚拟存储管理下访问内存的有效时间

1. 请求分页管理方式下，存在三种方式的内存访问
   • 页在内存，且快表检索命中
     • EAT= l + t
   • 页在内存，但快表检索没有命中
     • EAT= 快表检索时间+访问页表时间+修改更新快表时间+访问页面物理内存时间
     • l +t+ l +t=2*(l +t)

• • 页面不在内存
    • EAT=快表检索时间+访问页表时间+缺页中断处理时间+修改更新快表时间+访问页面物理内存时间

• l + t + e + l  + t

• • 加入概率的综合公式(a是快表命中率，f是缺页率)
    • EAT= l  + a*t +(1-a)*{    }

• l  +a*t +(1-a)*{t + f*(e+l+t)  +(1-f)*(l+ t) }

1. 练习：

              现有一请求调页系统，其页表保存在寄存器中；若有一个可用的空页或被替换的页未被修改，则它处理一个缺页中断需要8ms；若被替换页已被修改，则它处理一个缺页中断需要20ms；内存存储时间为1μs，访问页表的时间可忽略不计；假定70%被替换页被修改过，为保证有效存取时间不超过2μs，可接受的最大缺页率是多少？

解答：

1. 设最大缺页率为p,则：

(1-p)*1μs+p(0.3*8ms+0.7*20ms+ 1μs) <=2μs

2400p+14000p+1-p<=2

16400p<=1

p<=0.006%

※ 影响缺页率的主要因素

（1）分配给作业的主存块数:

       多则缺页率低，反之则高。

(2)页面大小：

       大则缺页率低；反之则高。

(3)页面调度算法：

       对缺页中断率影响很大，但不可能找到一种最佳算法。

(4)程序编制方法：

       以数组运算为例，如果每一行元素存放在一页中，则按行处理各元素缺页中断率低；反之，按列处理各元素，则缺页中断率高。

。

思考题

1. 在一个页式虚存系统中，每页可容纳200个整数。有一个对二维数组int  a（100，100） 操作的程序。
2. 若系统分给该进程3个内存块，其中1块装入程序和变量i，j，另外两块存放数组页面来存储数组数据。数组存放时是按行存放的。

设程序段已经调入内存，请分别计算下列程序的缺页次数。