第5章虚拟存储器

1、v 5.1 虚拟存储器概述虚拟存储器概述v 5.2 请求分页存储管理方式请求分页存储管理方式v 5.3 页面置换算法页面置换算法v 5.4 “抖动抖动”与工作集与工作集v 5.5 请求分段存储管理方式请求分段存储管理方式1v 物理存储器的结构是个一维的线性空间，容量是有限的。物理存储器的结构是个一维的线性空间，容量是有限的。v 物理存储器管理方式的特征：物理存储器管理方式的特征： 一次性一次性：程序要全部一次性装入内存后才能运行：程序要全部一次性装入内存后才能运行 驻留性驻留性：程序装入内存后，一直驻留在内存中，直至作：程序装入内存后，一直驻留在内存中，直至作业运行结速。业运行结速。v 用户程

2、序的大小，可能比内存容量小，也可能比内存容用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。量大，有时候要大得多。v 如何将大于物理内存容量的用户程序装入运行？这就是如何将大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。的原动力。2 指程序在执行过程中的一个较短时间内，所执行指程序在执行过程中的一个较短时间内，所执行的指令地址或操作数地址分别局限于一定的存储区域的指令地址或操作数地址分别局限于一定的存储区域中。又可细分时间局部性和空间局部性。中。又可细分时间局部性和空间局部性

3、。v时间局限性时间局限性 一条指令被执行了，则在不久的将来它可能再被一条指令被执行了，则在不久的将来它可能再被执行。执行。v空间局限性空间局限性 若某一存储单元被使用，则在一定时间内，与该若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用。存储单元相邻的单元可能被使用。3v 虚拟存储器虚拟存储器 是采用是采用请求调入功能请求调入功能和和置换功能置换功能，把内存与外存把内存与外存有机的结合起来使用，从逻辑上有机的结合起来使用，从逻辑上为用户提供一个比物为用户提供一个比物理主存容量大得多的，可寻址的一种理主存容量大得多的，可寻址的一种“主存储器主存储器” ，这就是虚存。这就是虚

4、存。v 虚拟存储器的容量虚拟存储器的容量 是有限的；是有限的； 由内存容量和外存容量之和所决定，受计算机的由内存容量和外存容量之和所决定，受计算机的地址结构限制。地址结构限制。 以以CPU时间和外存空间换取昂贵内存空间，这是时间和外存空间换取昂贵内存空间，这是操作系统中的资源转换技术。操作系统中的资源转换技术。4v常规存储器的特征常规存储器的特征 一次性一次性 驻留性驻留性v虚拟存储器特征虚拟存储器特征 多次性多次性 对换性对换性 虚拟性虚拟性5v实现虚拟存储器必须解决好以下有关问题实现虚拟存储器必须解决好以下有关问题 主存辅存统一管理问题主存辅存统一管理问题 逻辑地址到物理地址的转换问题逻辑

5、地址到物理地址的转换问题 部分装入和部分对换问题部分装入和部分对换问题v虚拟存储管理主要采用以下技术实现虚拟存储管理主要采用以下技术实现 请求分页存储管理请求分页存储管理 请求分段存储管理请求分段存储管理6v 基本原理基本原理 在进程开始运行之前，不是装入全部页面，而是装在进程开始运行之前，不是装入全部页面，而是装入部分页面，之后根据进程运行的需要，动态装入其它入部分页面，之后根据进程运行的需要，动态装入其它页面。页面。 当内存空间已满，而又需要装入新的页面时，则根当内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。据某种算法淘汰某个页面，以便装入新的页面。

6、例例v 怎样才能发现页面不在内存中呢怎样才能发现页面不在内存中呢? ?怎样处理这种情况呢怎样处理这种情况呢? ? 采用的办法是：扩充页表的内容，增加驻留标志位采用的办法是：扩充页表的内容，增加驻留标志位和页面辅存的地址等信息。通过产生缺页中断来处理和页面辅存的地址等信息。通过产生缺页中断来处理. .7前进前进82022-5-8151413121110987654321060K-64K56K-60K52K-56K48K-52K44K-48K40K-44K36K-40K32K-36K28K-32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K28K-

7、32K24K-28K20K-24K16K-20K12K-16K 8K-12K 4K-8K 0K-4K虚地址空间虚地址空间物理地址空间物理地址空间 虚页虚页页框页框返回返回v 页号、内存块号、状态位、外存地址、访问位、修改位页号、内存块号、状态位、外存地址、访问位、修改位 状态位（中断位）：表示该页是在内存还是在外存状态位（中断位）：表示该页是在内存还是在外存 访问位：根据访问位来决定淘汰哪页（由不同的算法访问位：根据访问位来决定淘汰哪页（由不同的算法决定）决定） 修改位：查看此页是否在内存中被修改过修改位：查看此页是否在内存中被修改过9页号页号状态位状态位辅存地址辅存地址访问位访问位 修改位修

8、改位物理块号物理块号101 11 10 00 01 11 11 10 00 00 00 00 00 01 11 1状态位状态位 在地址映射过程中，在页表中发现所要访问的页不在地址映射过程中，在页表中发现所要访问的页不在内存，则产生在内存，则产生缺页中断缺页中断。操作系统接到此中断信号。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外后，就调出缺页中断处理程序，根据页表中给出的外存地址，准备将该页调入内存。存地址，准备将该页调入内存。此时应将缺页的进程挂起（调页完成唤醒）此时应将缺页的进程挂起（调页完成唤醒）如果内存中有空闲块，则分配一个块，将要调入的如果内存中有空闲块，则分

9、配一个块，将要调入的页装入该块，并修改页表中相应页表项目的驻留位页装入该块，并修改页表中相应页表项目的驻留位及相应的内存块号及相应的内存块号若此时内存中没有空闲块，则要淘汰某页（若被淘若此时内存中没有空闲块，则要淘汰某页（若被淘汰页在内存期间被修改过，则要将其写回外存）汰页在内存期间被修改过，则要将其写回外存）11 缺页中断和一般中断都是中断。缺页中断和一般中断都是中断。v 相同点：相同点： 保护现场保护现场 、中断处理、中断处理、 恢复现场恢复现场v 不同点：不同点： 一般中断是一般中断是一条指令完成后一条指令完成后检查和处理中断信号，缺页检查和处理中断信号，缺页中断是中断是一条指令执行时一

10、条指令执行时产生和处理中断信号。产生和处理中断信号。 缺页中断缺页中断返回到该指令的开始返回到该指令的开始重新执行该指令，而一般重新执行该指令，而一般中断返回到该指令的中断返回到该指令的下一条指令下一条指令执行。执行。 一条指令执行时可能产生多个缺页中断。如指令可能访一条指令执行时可能产生多个缺页中断。如指令可能访问多个内存地址，这些地址在不同的页中。问多个内存地址，这些地址在不同的页中。 12v 内存分配策略分为两种内存分配策略分为两种 进程保持页框数固定不变，称进程保持页框数固定不变，称固定分配固定分配; ;进程分得进程分得的页框数可变，称的页框数可变，称可变分配可变分配。v 固定分配固定

11、分配 进程创建时，根据进程类型和程序员的要求决定进程创建时，根据进程类型和程序员的要求决定页框数，只要有一个缺页中断产生，进程就会有一页页框数，只要有一个缺页中断产生，进程就会有一页被替换。即使内存中有空闲的物理块，也不分配给该被替换。即使内存中有空闲的物理块，也不分配给该进程。进程。v 可变分配可变分配 先为每个进程分配一定数目的物理块，进程执行先为每个进程分配一定数目的物理块，进程执行的某阶段缺页率较高，说明目前局部性较差，系统可的某阶段缺页率较高，说明目前局部性较差，系统可多分些页框以降低缺页率，反之说明进程目前局部性多分些页框以降低缺页率，反之说明进程目前局部性较好，可减少分给进程的页

12、框数。较好，可减少分给进程的页框数。13v 固定分配缺少灵活性，而可变分配的性能会更好些，固定分配缺少灵活性，而可变分配的性能会更好些，被许多操作系统采用。被许多操作系统采用。v 采用可变分配策略的困难在于操作系统要经常监视采用可变分配策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况，会增加活动进程的行为和进程缺页中断率的情况，会增加系统的开销。系统的开销。14v全局置换全局置换 如果页面置换算法的作用范围是整个系统，称全局如果页面置换算法的作用范围是整个系统，称全局页面置换算法，它可以在运行进程间动态地分配页页面置换算法，它可以在运行进程间动态地分配页框。被置换的页可以是

13、内存中任一进程的页。框。被置换的页可以是内存中任一进程的页。v局部置换局部置换 如果页面置换算法的作用范围局限于本进程，称为如果页面置换算法的作用范围局限于本进程，称为局部页面置换算法，它实际上需要为每个进程分配局部页面置换算法，它实际上需要为每个进程分配固定的页框。始终保持分配给该进程的物理块数不固定的页框。始终保持分配给该进程的物理块数不变。变。15v 固定分配局部置换策略固定分配局部置换策略 进程分得的页框数不变，发生缺页中断，只能从进程分得的页框数不变，发生缺页中断，只能从进程的页面中选页置换，保证进程的页框总数不变。进程的页面中选页置换，保证进程的页框总数不变。v 策略难点策略难点

14、应给每个进程分配多少页框应给每个进程分配多少页框? ? 给少了，缺页中断率给少了，缺页中断率高；给多了，使内存中能同时执行的进程数减少，进高；给多了，使内存中能同时执行的进程数减少，进而造成处理器和其它设备空闲。而造成处理器和其它设备空闲。v 采用固定分配算法，系统把页框分配给进程，采用采用固定分配算法，系统把页框分配给进程，采用 平均分配平均分配 按比例分配按比例分配 优先权分配优先权分配16v 先每个进程分配一定数目页框，先每个进程分配一定数目页框，osos保留若干空闲页保留若干空闲页框，进程发生缺页中断时，从系统空闲页框中选一框，进程发生缺页中断时，从系统空闲页框中选一个给进程，这样产生

15、缺页中断进程的内存空间会逐个给进程，这样产生缺页中断进程的内存空间会逐渐增大，有助于减少系统的缺页中断次数。渐增大，有助于减少系统的缺页中断次数。v 系统拥有的空闲页框耗尽时系统拥有的空闲页框耗尽时 ，会从内存中选择一，会从内存中选择一页淘汰，该页可以是内存中任一进程的页面，这样页淘汰，该页可以是内存中任一进程的页面，这样又会使那个进程的页框数减少，缺页中断率上升。又会使那个进程的页框数减少，缺页中断率上升。17 其实现要点如下其实现要点如下: :v 新进程装入主存时，根据应用类型、程序要求，新进程装入主存时，根据应用类型、程序要求，分配给一定数目页框。分配给一定数目页框。v 产生缺页中断时，

16、从该进程驻留集中选一个页面产生缺页中断时，从该进程驻留集中选一个页面替换。替换。v 不时重新评价进程的分配，增加或减少分配给进不时重新评价进程的分配，增加或减少分配给进程的页框以改善系统性能。程的页框以改善系统性能。18v何时页面装入主存何时页面装入主存 请求调页策略请求调页策略: :需要访问程序和数据时，才把所在页面装需要访问程序和数据时，才把所在页面装入主存。缺点是每次只调入一页，处理缺页中断和调页入主存。缺点是每次只调入一页，处理缺页中断和调页的系统开销较大，增加磁盘的系统开销较大，增加磁盘I/OI/O启动频率。启动频率。 预调页策略预调页策略: :系统系统预测预测进程将要使用的页面，使

17、用前预先进程将要使用的页面，使用前预先调入主存，每次调入若干页面，而不是仅调一页。缺点调入主存，每次调入若干页面，而不是仅调一页。缺点是如果调入的一批页面中多数未被使用，则效率就很低是如果调入的一批页面中多数未被使用，则效率就很低了，可见预调页要建立在预测的基础上。了，可见预调页要建立在预测的基础上。19v 缺页中断率缺页中断率 假定作业假定作业p p共计共计n n页，系统分配给它的主存块只有页，系统分配给它的主存块只有m m块（块（mnmn）。如果作业）。如果作业p p在运行中成功的访问次数在运行中成功的访问次数为为s s， 不成功的访问次数为不成功的访问次数为F F，则总的访问次数为：，则

18、总的访问次数为： A = S + FA = S + F 又定义：又定义：f = F / Af = F / A，称，称f f为缺页中断率。为缺页中断率。v 影响缺页中断率影响缺页中断率f f的因素有：的因素有： (1)(1)主存物理块数主存物理块数 (2)(2)页面大小页面大小 (3)(3)程序的编制方法程序的编制方法 (4)(4)页面置换算法页面置换算法20 程序要将程序要将128128的数组置的数组置“0”。分给的主存只一块，页。分给的主存只一块，页面尺寸为每页面尺寸为每页128个字，数组中的元素每行存放在一页中。若程个字，数组中的元素每行存放在一页中。若程序如下：序如下： Var A: a

19、rray1.128 of array 1.128 of integer; for j := 1 to 128 do for i := 1 to 128 do Aij:=0 总共产生（总共产生（128*1281）次缺页中断。）次缺页中断。 如果重新编制程序如下：如果重新编制程序如下： Var A: array1.128 of array1.128 of integer; for i := 1 to128 do for j:= 1 to 128 do Aij := 0 总共产生（总共产生（1281）次缺页中断。）次缺页中断。21 当要索取一页面并送入到全满的内存中时，必当要索取一页面并送入到全满的

20、内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。一页的规则叫做置换算法。v最佳置换算法（最佳置换算法（OPT）v先进先出页面置换算法（先进先出页面置换算法（FIFO）v最近最久未使用算法（最近最久未使用算法（LRU）22 基本思想：淘汰以后不再需要的或最远的将来才会基本思想：淘汰以后不再需要的或最远的将来才会用到的页面。可用来作为衡量各种具体算法的标准。用到的页面。可用来作为衡量各种具体算法的标准。 【例例】采用固定分配局部置换策略，某程序在内存采用固定分配局部置换策略，某程序在内存中分配三个块，访问页的走向为中分配三

21、个块，访问页的走向为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 4 4 4 4 4 4 4 4 2 1 1块块2 3 3 3 3 3 3 3 3 3 3 3块块3 2 1 1 1 5 5 5 5 5 5 x x x x x x x 共缺页中断共缺页中断7次次缺页中断率缺页中断率=7/12=58.33%23 基本思想：淘汰最先调入主存的那一页，或者说在主基本思想：淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那

22、一页（常驻的除外）。存中驻留时间最长的那一页（常驻的除外）。 【例例】采用固定分配局部置换策略，某程序在内存中采用固定分配局部置换策略，某程序在内存中分配三个块，访问页的走向为分配三个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，计算缺页次数，假设开始时所有页均不在，计算缺页次数，假设开始时所有页均不在内存。内存。FIFO 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 1 1 1 5 5 5 5 5 5块块2 3 3 3 4 4 4 4 4 2 2 2块块3 2 2 2 3 3 3 3 3 1 1 x x x x x x x x x 共缺页中断共缺页中断

23、9次，缺页中断率次，缺页中断率=9/12=75%24这种算法实现简单，但会淘汰经常使用的页面这种算法实现简单，但会淘汰经常使用的页面 基本思想：根据程序局部性原理，那些刚被使用过的页面，可能基本思想：根据程序局部性原理，那些刚被使用过的页面，可能马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使马上还要被使用，而在较长时间里未被使用的页面，可能不会马上使用到。用到。当需要淘汰某一页时，算法选择离当前时间最近的一段时间内当需要淘汰某一页时，算法选择离当前时间最近的一段时间内最久没有使用过的页先淘汰。最久没有使用过的页先淘汰。LRU 4 3 2 1 4 3 5 4 3 2 1 5块块1 4 4 4 1 1 1 5 5 5 2 2 2块块2 3 3 3 4 4 4 4 4 4 1 1块块3 2 2 2 3 3 3 3 3 3 5 x x x x x x x x x x共缺页中断共缺页中断10次次缺页中断率缺页中断率=10/12=83.33%25v基本原理基本原理 分段式虚拟存储系统把作业的所有分段的副本分段式虚拟存储系统把作业的所有分段的副本都存放