5.3.虚拟存储管理

时间: 2023-07-11 admin IT培训

5.3.    虚拟存储管理

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

    • LFU置换次数少的。程序局部性会导致一个页面在一段时间内使用次数很多。但使用次数多并不能说明将来被用到的可能性大
    • 而LRU置换最近最久未用的,对未来的预计一般会更好些。
  1. 所有,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,另外两块存放数组页面来存储数组数据。数组存放时是按行存放的。

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