4.5 虚拟存储管理
4.5.1 虚拟存储管理的概念
问题：作业提交时,先全部进入辅助存储器,作业投入运行时,能否不把作业的全部信息同时装入主存储器,而是将其中当前使用部分先装入主存储器,其余暂时不用的部分先存放在作为主存扩充的辅助存储器中,待用到这些信息时,再由系统自动把它们装入到主存储器中,这就是虚拟存储器的基本思路 。
解决,部分装入、部分对换,问题
那么当主存空间小于作业需要量时，这个作业也能执行 ;
多个作业存储总量超出主存总容量时,也可以把它们全部装入主存,实现多道程序运行。
允许用户的逻辑地址空间大于主存储器的绝对地址空间 。 对于用户来说,好象计算机系统具有一个容量很大的主存储器,我们把它称作为,虚拟存储器,(virtual
memory)。
虚拟存储器的定义如下：
具有部分装入和部分对换功能,能从逻辑上对内存容量进行大幅度扩充,使用方便的一种存储器系统。
作业信息不全部装入主存的情况下能否保证作业的正确运行？
回答是肯定的,早在 1968年 P.Denning就研究了程序执行时的局部性原理，
指程序在执行过程中的一个较短时间内,所执行的指令地址或操作数地址分别局限于一定的存储区域中 。 又可细分时间局部性和空间局部性 。
1)程序中大部分是顺序执行的指令,仅用少量转移和过程调用
2)过程调用时,执行程序范围不超过这组过程
3)程序含有较多循环结构,它们由少量指令组成,却被多次执行
4) 程序含有较多数据结构操作,如动态数组,往往局限在较小存储区域
5)程序中有些部分是彼此互斥的,不是每次运行时都用到的实现虚拟存储器必须解决好以下有关问题：
主存辅存统一管理问题,
逻辑地址到物理地址的转换问题,
部分装入和部分对换问题 。
虚拟存储管理主要采用以下几种技术实现请求分页式请求分段式段页式虚拟存储管理
4.5.2分页式虚拟存储系统
4.5.2.1 分页式虚拟存储系统的基本原理分页式虚拟存储系统是将作业信息的副本存放在磁盘这一类辅助存储器中，当作业被调度投入运行时，并不把作业的程序和数据全部装入主存，而仅仅装入立即使用的那些页面，在执行过程中访问到不在主存的页面时，再把它们动态地装入请页式 (demand Paging)
当需要执行某条指令或使用某个数据,而发现它们并不在主存时,产生一个缺页中断,系统从辅存中把该指令或数据所在的页面调入内存 。
请页式虚存管理
仅让作业或进程当前使用部分放在主存中，所以，执行过程中必然会发生某些页面不在内存中的情况，那么，怎样才能发现页面不在内存中呢?怎样处理这种情况呢?采用的办法是：扩充页表的内容,
增加驻留标志位和页面辅存的地址等信息,扩充后的页表页式虚拟存储管理的页表扩展
页号
┅
┅
┅
┅
┅
┅
辅存地址 其它标志
┅
┅
┅
┅
┅
┅
驻留标志 块号第 0页第 1页
┅
驻留标志位 (又称中断位 )
修改位（ Modified）
引用位（ Renferenced）
禁止缓存位
访问位，
查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无请求页式存储管理
IBM/370系统的 VS/1,VS/2和 VM/370，
Honeywell 6180的 MULTICS
UNIVAC系列 70/64的 VMS
请求页式虚拟存储系统有以下优点：
作业的程序和数据可以按页分散存放在内存中,减少了移动的开销,有效地解决了碎片问题 ;由于采用请页式管理,用户可用的主存空间大大扩展,
既有利于改进主存利用率,又有利于多道程序运行 。
主要缺点是：
要有一定硬件支持,要进行缺页中断处理,因而机器成本增加,系统开销加大,此外页内会出现碎片,
如果页面较大,则主存的损失仍然很大 。
4.5.2.2页面装入策略和清除策略页面装入主存,有两种策略可供选择：
请页式调度预调式调度 。
请页式调度
仅当需要访问程序和数据时,才把所在页面装入主存 。 那么当某个进程第一次执行时,开始会有许多缺页中断,随着越来越多的页面装入主存,根据局部性原理,大多数未来访问的程序和数据都在最近被装入主存的页面中,一段时间之后,缺页中断就会下降到很低的水平,程序进入相对平稳阶段 。
这种策略的主要缺点是处理缺页中断和调页的系统开销较大,由于每次仅调一页,增加了磁盘
I/O次数 。
预调式调度
由操作系统预测进程将要使用的那些页面,在使用入之前预先调入主存,每次调入若干个页面,
而不是像请页式那样仅调一个页面 。 由于进程的页面大多数连续存放在辅存储中器,一次调入多个页面能减少磁盘 I/O启动次数,节省了寻道和搜索时间 。 但是如果调入的一批页面中多数未被使用,则效率就很低了,可见预调页要建立在预测的基础上,目前所用预调页的成功率在 50%左右 。
预调式调度和进程的对换当一个进程挂起被换出主存时,
它的常驻页面统统移出 ;当该进程继续执行时,先前移出的页面都会重新调入主存,但不是由预调页调度来完成的 。
清除策略
它要考虑何时把一个修改过的页面写回辅存储器,常用的两种方法是,请页式清除和预清除。
请页式清除是仅当一页选中被替换,且之前它又被修改过,才把这个页面写回辅助存储器。预清除方法对更改过的页面，在需要之前就把它们都回辅助存储器,因此可以成批进行。
两个方法的缺点
预清除,写出的页仍然在内存中,直到页页替换算法选中一页从内存中移出,它允许成批地把页面写出,但如若刚刚写出了很多页面,在它们被替换前,其中大部分又被更改,那么,预清除就毫无意义 。
请页式清除,写出一页是在读进一个新页之前进行的,它要成双操作,它仅需要写出一页,但引起进程不得不等待两次 I/O操作完成,可能会降低 CPU使用效率 。
页缓冲策略
其策略如下,仅清除淘汰的页面,并使清除操作和替换操作不必成双进行 。 在页缓冲中,淘汰了的页面进入两个队列中,
修改页面和非修改页面队列 。 在修改页面队列中的页的不时地式批写出并加入到非修改页面队列 ; 非修改页面队列中的页面,当它被再次引用时回收,或者淘汰掉以作替换 。
4.5.2.3 页面分配策略
在分页式虚拟存储管理中,不可能也不必要把一个进程的所有页面调入主存,那么操作系统决定为某进程分配多大的主存空间,需要考虑以下因素,① 分配给一个进程的空间越小,同一时间处于内存的进程就越多,于是至少有一个进程处于就绪态的可能性就越大,从而可减少进程交换的时间 。 ② 如果进程只有一小部分在入主存里,
即使它的局部性很好,缺页中断率还会相当高 。
③ 因为程序的局部性原理,分配给一个进程的内存超过一定限度后,再增加内存空间,也不会明显降低进程的缺页中断率 。 基于这些因素,
在请页式系统中,可采用两种策略分配页框给进程,固定分配和可变分配 。
分配页框给进程策略
在请页式系统中,可采用两种：
固定分配可变分配 。
如果进程生命周期中,保持页框数固定不变,称页面分配为固定分配 ;通常在进程创建时,根据进程类型和程序员的要求决定页框数,只要有一个缺页中断产生,进程就会有一页被替换。
如果进程生命周期中,分得的页框数可变,
称页面分配为可变分配 ;当进程执行的某一阶段缺页率较高,说明进程程序目前的局部性较差，系统可多分些页框以降低缺页率，反之说明进程程序目前的局部性较好,可以减少分给进程的页框数。
固定分配策略缺少灵活性,而可变分配的性能会更好些,被许多操作系统所采用 。
采用可变分配策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况,这会增加操作系统的开销 。
页面替换两种策略：
局部替换和全局替换
如果页面替换算法的作用范围是整个系统，称为全局页面替换算法,它可以在可运行进程之间动态地分配页框。
如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法,它实际上需要为每个进程分配固定的页框。
固定分配和局部替换策略配合使用每个进程运行期间分得的页框数不再改变,如果发生缺页中断,只能从进程在内存的页面中选出一页替换,
以保证进程的页框总数不变 。 这种策略的主要难点在于,应给每个进程分配多少个页框?给少了,缺页中断率高 ;给多了,会使内存中能同时执行的进程数减少,
进而造成处理器空闲和其它设备空闲 。 采用固定分配算法时,系统把可供分配的页框分配给进程,可采用下列方式,① 平均分配,不论进程大小,每个进程得到的页框数相等,会造成大进程缺页中断率高 。
② 按比例分配,大进程获得页框多,小进程获得页框少 。 ③ 优先权分配,可以把页框分成两类,一类按上比例分配,另一类根据进程优先权适当增加份额 。
可变分配和全局替换策略配合使用这种分配和替换算法,先为系统中的每个进程分配一定数目的页框,操 作系统自己保留若干空闲页框,当一个进程发生缺页中断时,从系统空闲页框中选一个给进程,于是可把缺页调入这个页框中,这样产生缺页中断的进程的内存空间会逐渐增大 。 凡是产生缺页中断的进程都能获得新的页框,有助于减少系统的缺页中断次数 。 直到系统拥有的空闲页框耗尽,才会从内存中选择一页淘汰,该页可以是内存中任一进程的页面,这样又会使那个进程的页框数减少,缺页中断率上升 。
可变分配配合局部替换可以克服可变分配全局替换的缺点,其实现要点如下,① 新进程装入主存时,根据应用类型,程序要求,分配给一定数目页框,可用请页式或预调式完成这个分配 。
② 当产生缺页中断时,从产生缺页中断的进程的常驻集中选一个页面替换 。 ③ 不时重新评价进程的分配,增加或减少分配给进程的页框以改善系统性能 。
4.5.1 虚拟存储管理的概念
问题：作业提交时,先全部进入辅助存储器,作业投入运行时,能否不把作业的全部信息同时装入主存储器,而是将其中当前使用部分先装入主存储器,其余暂时不用的部分先存放在作为主存扩充的辅助存储器中,待用到这些信息时,再由系统自动把它们装入到主存储器中,这就是虚拟存储器的基本思路 。
解决,部分装入、部分对换,问题
那么当主存空间小于作业需要量时，这个作业也能执行 ;
多个作业存储总量超出主存总容量时,也可以把它们全部装入主存,实现多道程序运行。
允许用户的逻辑地址空间大于主存储器的绝对地址空间 。 对于用户来说,好象计算机系统具有一个容量很大的主存储器,我们把它称作为,虚拟存储器,(virtual
memory)。
虚拟存储器的定义如下：
具有部分装入和部分对换功能,能从逻辑上对内存容量进行大幅度扩充,使用方便的一种存储器系统。
作业信息不全部装入主存的情况下能否保证作业的正确运行？
回答是肯定的,早在 1968年 P.Denning就研究了程序执行时的局部性原理，
指程序在执行过程中的一个较短时间内,所执行的指令地址或操作数地址分别局限于一定的存储区域中 。 又可细分时间局部性和空间局部性 。
1)程序中大部分是顺序执行的指令,仅用少量转移和过程调用
2)过程调用时,执行程序范围不超过这组过程
3)程序含有较多循环结构,它们由少量指令组成,却被多次执行
4) 程序含有较多数据结构操作,如动态数组,往往局限在较小存储区域
5)程序中有些部分是彼此互斥的,不是每次运行时都用到的实现虚拟存储器必须解决好以下有关问题：
主存辅存统一管理问题,
逻辑地址到物理地址的转换问题,
部分装入和部分对换问题 。
虚拟存储管理主要采用以下几种技术实现请求分页式请求分段式段页式虚拟存储管理
4.5.2分页式虚拟存储系统
4.5.2.1 分页式虚拟存储系统的基本原理分页式虚拟存储系统是将作业信息的副本存放在磁盘这一类辅助存储器中，当作业被调度投入运行时，并不把作业的程序和数据全部装入主存，而仅仅装入立即使用的那些页面，在执行过程中访问到不在主存的页面时，再把它们动态地装入请页式 (demand Paging)
当需要执行某条指令或使用某个数据,而发现它们并不在主存时,产生一个缺页中断,系统从辅存中把该指令或数据所在的页面调入内存 。
请页式虚存管理
仅让作业或进程当前使用部分放在主存中，所以，执行过程中必然会发生某些页面不在内存中的情况，那么，怎样才能发现页面不在内存中呢?怎样处理这种情况呢?采用的办法是：扩充页表的内容,
增加驻留标志位和页面辅存的地址等信息,扩充后的页表页式虚拟存储管理的页表扩展
页号
┅
┅
┅
┅
┅
┅
辅存地址 其它标志
┅
┅
┅
┅
┅
┅
驻留标志 块号第 0页第 1页
┅
驻留标志位 (又称中断位 )
修改位（ Modified）
引用位（ Renferenced）
禁止缓存位
访问位，
查快表有登记无登记查页表登记入快表发缺页中断在主存在辅存形成绝对地址继续执行指令重新执行被中断指令恢复现场调整页表和主存分配表装入所需页面主存有空闲块保护现场有选择调出页面该页是否修改未修改已修改把该页写回辅存相应位置操作系统硬件逻辑地址无请求页式存储管理
IBM/370系统的 VS/1,VS/2和 VM/370，
Honeywell 6180的 MULTICS
UNIVAC系列 70/64的 VMS
请求页式虚拟存储系统有以下优点：
作业的程序和数据可以按页分散存放在内存中,减少了移动的开销,有效地解决了碎片问题 ;由于采用请页式管理,用户可用的主存空间大大扩展,
既有利于改进主存利用率,又有利于多道程序运行 。
主要缺点是：
要有一定硬件支持,要进行缺页中断处理,因而机器成本增加,系统开销加大,此外页内会出现碎片,
如果页面较大,则主存的损失仍然很大 。
4.5.2.2页面装入策略和清除策略页面装入主存,有两种策略可供选择：
请页式调度预调式调度 。
请页式调度
仅当需要访问程序和数据时,才把所在页面装入主存 。 那么当某个进程第一次执行时,开始会有许多缺页中断,随着越来越多的页面装入主存,根据局部性原理,大多数未来访问的程序和数据都在最近被装入主存的页面中,一段时间之后,缺页中断就会下降到很低的水平,程序进入相对平稳阶段 。
这种策略的主要缺点是处理缺页中断和调页的系统开销较大,由于每次仅调一页,增加了磁盘
I/O次数 。
预调式调度
由操作系统预测进程将要使用的那些页面,在使用入之前预先调入主存,每次调入若干个页面,
而不是像请页式那样仅调一个页面 。 由于进程的页面大多数连续存放在辅存储中器,一次调入多个页面能减少磁盘 I/O启动次数,节省了寻道和搜索时间 。 但是如果调入的一批页面中多数未被使用,则效率就很低了,可见预调页要建立在预测的基础上,目前所用预调页的成功率在 50%左右 。
预调式调度和进程的对换当一个进程挂起被换出主存时,
它的常驻页面统统移出 ;当该进程继续执行时,先前移出的页面都会重新调入主存,但不是由预调页调度来完成的 。
清除策略
它要考虑何时把一个修改过的页面写回辅存储器,常用的两种方法是,请页式清除和预清除。
请页式清除是仅当一页选中被替换,且之前它又被修改过,才把这个页面写回辅助存储器。预清除方法对更改过的页面，在需要之前就把它们都回辅助存储器,因此可以成批进行。
两个方法的缺点
预清除,写出的页仍然在内存中,直到页页替换算法选中一页从内存中移出,它允许成批地把页面写出,但如若刚刚写出了很多页面,在它们被替换前,其中大部分又被更改,那么,预清除就毫无意义 。
请页式清除,写出一页是在读进一个新页之前进行的,它要成双操作,它仅需要写出一页,但引起进程不得不等待两次 I/O操作完成,可能会降低 CPU使用效率 。
页缓冲策略
其策略如下,仅清除淘汰的页面,并使清除操作和替换操作不必成双进行 。 在页缓冲中,淘汰了的页面进入两个队列中,
修改页面和非修改页面队列 。 在修改页面队列中的页的不时地式批写出并加入到非修改页面队列 ; 非修改页面队列中的页面,当它被再次引用时回收,或者淘汰掉以作替换 。
4.5.2.3 页面分配策略
在分页式虚拟存储管理中,不可能也不必要把一个进程的所有页面调入主存,那么操作系统决定为某进程分配多大的主存空间,需要考虑以下因素,① 分配给一个进程的空间越小,同一时间处于内存的进程就越多,于是至少有一个进程处于就绪态的可能性就越大,从而可减少进程交换的时间 。 ② 如果进程只有一小部分在入主存里,
即使它的局部性很好,缺页中断率还会相当高 。
③ 因为程序的局部性原理,分配给一个进程的内存超过一定限度后,再增加内存空间,也不会明显降低进程的缺页中断率 。 基于这些因素,
在请页式系统中,可采用两种策略分配页框给进程,固定分配和可变分配 。
分配页框给进程策略
在请页式系统中,可采用两种：
固定分配可变分配 。
如果进程生命周期中,保持页框数固定不变,称页面分配为固定分配 ;通常在进程创建时,根据进程类型和程序员的要求决定页框数,只要有一个缺页中断产生,进程就会有一页被替换。
如果进程生命周期中,分得的页框数可变,
称页面分配为可变分配 ;当进程执行的某一阶段缺页率较高,说明进程程序目前的局部性较差，系统可多分些页框以降低缺页率，反之说明进程程序目前的局部性较好,可以减少分给进程的页框数。
固定分配策略缺少灵活性,而可变分配的性能会更好些,被许多操作系统所采用 。
采用可变分配策略的困难在于操作系统要经常监视活动进程的行为和进程缺页中断率的情况,这会增加操作系统的开销 。
页面替换两种策略：
局部替换和全局替换
如果页面替换算法的作用范围是整个系统，称为全局页面替换算法,它可以在可运行进程之间动态地分配页框。
如果页面替换算法的作用范围局限于本进程，称为局部页面替换算法,它实际上需要为每个进程分配固定的页框。
固定分配和局部替换策略配合使用每个进程运行期间分得的页框数不再改变,如果发生缺页中断,只能从进程在内存的页面中选出一页替换,
以保证进程的页框总数不变 。 这种策略的主要难点在于,应给每个进程分配多少个页框?给少了,缺页中断率高 ;给多了,会使内存中能同时执行的进程数减少,
进而造成处理器空闲和其它设备空闲 。 采用固定分配算法时,系统把可供分配的页框分配给进程,可采用下列方式,① 平均分配,不论进程大小,每个进程得到的页框数相等,会造成大进程缺页中断率高 。
② 按比例分配,大进程获得页框多,小进程获得页框少 。 ③ 优先权分配,可以把页框分成两类,一类按上比例分配,另一类根据进程优先权适当增加份额 。
可变分配和全局替换策略配合使用这种分配和替换算法,先为系统中的每个进程分配一定数目的页框,操 作系统自己保留若干空闲页框,当一个进程发生缺页中断时,从系统空闲页框中选一个给进程,于是可把缺页调入这个页框中,这样产生缺页中断的进程的内存空间会逐渐增大 。 凡是产生缺页中断的进程都能获得新的页框,有助于减少系统的缺页中断次数 。 直到系统拥有的空闲页框耗尽,才会从内存中选择一页淘汰,该页可以是内存中任一进程的页面,这样又会使那个进程的页框数减少,缺页中断率上升 。
可变分配配合局部替换可以克服可变分配全局替换的缺点,其实现要点如下,① 新进程装入主存时,根据应用类型,程序要求,分配给一定数目页框,可用请页式或预调式完成这个分配 。
② 当产生缺页中断时,从产生缺页中断的进程的常驻集中选一个页面替换 。 ③ 不时重新评价进程的分配,增加或减少分配给进程的页框以改善系统性能 。
