操作系统复习 第五章
# 第五章 虚拟存储器
虚拟存储器:是指具有请求调入功能和置换功能,能从逻辑.上对内存容量加以扩充的一种存储器系统。其逻辑容量由内存容量和外存容量之和所决定,其运行速度接近于内存速度，而每位的成本却接近于外存。
## 概述
- 常规处理器管理方式的特征
- 一次性
- 作业必须一次性全部装入内存后才能开始运行。
- 这会造成两个问题:
- 作业很大时,不能全部装入内存,导致大作业无法运行
- 当大量作业要求运行时,由于内存无法容纳所有作业,因此只有少量作业能运行,导致多道程序并发度下降。
- 驻留性:
- 一旦作业被装入内存,就会一直驻留在内存中,直至作业运行结束。
- 事实上,在一个时间段内,只需要访问作业的一小部分数据即可正常运行,这就导致了内存中会驻留大量的、暂时用不到的数据,浪费了宝贵的内存资源。
- 局部性
- 基于局部性原理,在程序装入时,可以将程序中很快会用到的部分装入内存,暂时用不到的部分留在外存,就可以让程序开始执行。
- 在程序执行过程中,当所访问的信息不在内存时,由操作系统负责将所需信息从外存调入内存,然后继续执行程序。
- 若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下在用户看来似乎有一个比实际内存大得多的内存,这就是虚拟内存
虚拟内存的最大容量是计算机的地址结构, CPU寻址范围决定的。
<mark>虚拟内存的实际容量是内存与外存之和, CPU寻址范围,两者的最小值</mark>
- 虚拟存储器的特征
- 多次性
- 一个作业被分成多次调入内存运行。多次性是虚拟存储器最重要的特征,与常规存储器管理的一次性相对应。
- 对换性
- 系统允许作业在运行过程中进行换进、换出操作。换进和换出能有效地提高内存利用率。
- 虚拟性
- 虚拟性是指从逻辑上扩充内存容量,并非实际存在。用户感觉到的很大的虚拟存储容量实际上是一种“假象”
<mark>虚拟存储器的实现都是建立在离散分配的存储管理方式的基础上。</mark>
## 请求分页系统
- 在分页系统的基础上,增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统。置换时以页面为单位。
- 为实现请求调页和置换功能,系统必须提供必要的支持:
- 硬件支持:
- 请求分页的页表机制
- 在请求分页系统中所需要的主要数据结构是页表。其基本作用仍然是将用户地址空间中的逻辑地址变换为内存空间中的物理地址。
- 由于只将应用程序的一部分调入内存,还有一部分仍在盘上,故需在页表中再增加若干项,供程序(数据)在换进、换出时参考。
- 
- 缺页中断机构
- 在请求分页系统中,每当要访问的页面不在内存时,便产生一缺页中断,请求OS将所缺之页调入内存。
- 缺页中断作为中断,同样需要经历诸如保护CPU环境、分析中断原因、转入缺页中断处理程序进行处理、恢复CPU环境等几个步骤。
- 但缺页中断是一种特殊的中断,与一般中断有明显区别:
- 缺页中断在指令执行期间产生和处理中断信号,而一般中断在一条指令执行完后检查和处理中断信号。
- 缺页中断返回到该指令的开始重新执行该指令，而一般中断返回到该指令的下一条指令执行。
- 一条指令在执行期间,可能产生多次缺页中断。
- 地址变换机构
- 请求分页系统中的地址变换机构,是在分页系统地址变换机构的基础上,再为实现虚拟存储器而增加了某些功能而形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等。
- 软件支持:
- 实现请求调页的软件
- 实现页面置换的软件
- 请求分页中的内存分配
- 最小物理块数的确定
- 最小物理块数,指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时,进程将无法运行。
- 进程应获得的最小物理块数与计算机的硬件结构有关,取决于指令的格式、功能和寻址方式。
- 物理块的分配策略
- 在请求分页系统中,可采取两种内存分配策略:
- 固定分配策略:为每个进程分配一定数目的物理块,在整个运行期间不再改变
- 可变分配策略:先为每个进程分配一定数量的物理块,在整个运行期间可适当增多或减少。
- 在进行置换时,也可采取两种策略
- 全局置换:发生缺页时,只选进程自己的物理块置换
- 局部置换:可以将操作系统保留的空闲物理快分配给进程,也可以将别的进程持有的物理块置换到外存,再分配给缺页进程。
- 组合出的三种策略：
- 固定分配局部置换(Fixed Allocation , Local Replacement)
- 为每个进程分配一定数目的物理块,在整个运行期间不再改变。
- 采用该策略时,如果进程在运行中发现缺页,只能从该进程在内存中的n个页面中选出一页换出,然后再调入一页。
- 困难:应为每个进程分配多少个物理块难以确定。
- 可变分配全局置换(Variable Allocation , Global Replacement)
- 在采用这种策略时,先为系统中的每个进程分配一定数目的物理块,而OS自身也保持一个空闲的物理块队列。
- 如果某进程发生缺页时,由系统从空闲的物理块队列中,取出一个物理块分配给该进程,并将欲调入的页装入其中。
- 当空闲物理块队列中的物理块用完后, OS才能从系统中的任一进程中选择一页调出。
- 可变分配局部置换(Variable Allocation , Local Replacement)
- 为每个进程分配一定数目的物理块,如果某进程发生缺页时,只允许从该进程在内存的页面中选出一页换出,不会影响其他进程执行。
- 如果进程在运行中频繁发生缺页中断,则系统再为进程分配若干物理块
- 如果进程在运行中缺页率特别低,则适当减少分配给该进程的物理块。
- 物理块的分配算法
- 在采用固定分配策略时,如何将系统中可供分配的物理块分配给各个进程，可采用以下几种算法:
- 平均分配算法:将系统中所有可供分配的物理块,平均分配给各个进程。
- 按比例分配算法:根据进程的大小按比例分配物理块。
- 设系统中共有n个进程,每个进程的页面数为Si ,则系统中各进程页面数的总和为:
$$
S=\sum_{i+1}^{n}S^i
$$
- 又假定系统中可用的物理块总数为m ,则每个进程所能分到的物理块数为bi ,将有
$$
b_i=\frac{S_i}{S}*m
$$
- bi应该取整,必须大于最小物理块数。
- 考虑优先权的分配算法:在实际应用中,为了照顾重要的、急迫的作业尽快完成,为它分配较多的内存空间
- 方法:
- 把内存中可供分配的物理块分为两部分:
- 一部分按比例分配给各进程;
- 一部分则根据各进程的优先权,适当地增加其相应份额,分配给各进程。
- 页面调入策略
- 何时调入页面
- 预调页策略
- 采用以预测为基础的预调页策略,将那些预计在不久之后便会被访问的页面,预先调入内存。
- 主要用于进程的首次调入时 ,由程序员指出应该先调入哪些页。
- 请求调页策略
- 当程序在运行中需要访问某部分程序和数据时,若发现其所在的页面不在内存,便立即提出请求,由OS将其所需要的页面调入内存。
- 优点：由请求调页策略所确定调入的页, 一定会被访问;请求调页策略比较容易实现。
- 缺点:每次仅调入一页,需花费较大的系统开销,增加了磁盘I/O的启动频率。
- 从何处调入页面
- 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面,以提高调页速度。
- 系统缺少足够的对换区空间,则将不会被修改的文件直接从文件区调入,将可能会被修改调到对换区。
- 如何进行调入
- 每当程序所要访问的页面未在内存时,便向CPU发出一缺页中断,中断处理程序首先保护CPU环境,分析中断原因后,转入缺页中断处理程序。
- 程序通过查找页表,得到该页在外存上的物理块后,如果此时内存能容纳新页则启动磁盘I/O将所缺之页调入内存,然后修改页表。
- 如果内存已满,则需按照某种置换算法从内存中选出一页准备换出;如果该页未被修改过,可不必写回磁盘;但如果此页已被修改,则必须将它写回磁盘,然后把所缺的页调入内存,并修改页表中的相应表项,置其存在位为“1" , 并将此页表项写入快表。
- 在缺页调入内存后,利用修改后的页表,形成所要访问的物理地址,再去访问内存数据。整个页面调入过程对用户是透明的
- 缺页率
- 假设一个进程的逻辑空间为n页,系统为其分配的内存物理块数为m(m≤n)。
- 如果在进程的运行过程中,访问页面成功(即所访问页面在内存中)的次数为S ,访问页面失败(即所访问页面不在内存中,需要从外存调入)的次数为F ,则该进程总的页面访问次数为A= S+ F
- 那么该进程在其运行过程中的缺页率即为
$$
缺页率=\frac{缺页次数}{访问总次数}
$$
- 影响缺页率的因素:
- 页面大小
- 进程所分配页框的数目
- 页面置换算法
- 程序固有属性
- 请求分段系统
- 在分段系统的基础.上,增加了请求调段功能和分段置换功能所形成的段式虚拟存储系统。置换时以段为单位。
- 为实现请求调段和置换功能,系统必须提供必要的支持:
- 硬件支持:
- 请求分段的段表机制
- 缺段中断机构
- 地址变换机构
- 软件支持:
- 实现请求调段的软件
- 实现段的置换的软件
## 页面置换算法
在程序执行过程中,当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存,然后继续执行程序。
若内存空间不够,由操作系统负责将内存中暂时用不到的信息换出到外存用页面置换算法决定应该换出哪个页面
页面的换入、换出需要磁盘I/O ,会有较大的开销,因此好的页面置换算法应该追求更少的缺页率
- 最佳置换算法
- 其所选择的被淘汰页面，将是以后永不再用的,或许是在最长(未来)时间内不再被访问的页面。
- 优点:保证获得最低的缺页率
- 缺点:无法预知一-个进程在内存的若干个页面,哪个在未来最长时间内不再被访问。
- 算法无法实现，但可评价其他算法。
- 先入先出页面（FIFO）置换算法
- 算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
- 算法实现简单,只需把一个进程已调入内存的页面,按先后次序链接成一个队列,并设置一个指针(替换指针) ,使它总是指向最老的页面。
- 算法与进程的实际运行规律不相适应,因为进程中的某些页面经常被访问,但先进先出置换算法不能保证这些页面不被淘汰。
- **Belady现象**
- 采用FIFO算法时,如果对一个进程未分配它所要求的全部页面,有时就会出现分配的页面数增多但缺页率反而提高的异常现象。
- Belady现象的原因是FIFO算法的置换特征与进程访问内存的动态特征是矛盾的,即被置换的页面并不是进程不会访问的,因而FIFO并不是- -个好的置换算法。
- 最近最久未使用（LeastRecently Used）算法
- 算法根据页面调入内存后的使用情况进行决策。由于无法预测各页面将来的使用情况,只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。
- 该算法赋予每个页面一个访问字段,用来记录一个页面自上次被访问以来所经历的时间t ,当需淘汰一个页面时,选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。
- 需有以下两类硬件之一的支持:
- 寄存器
- 为每个在内存中的页面配置一个移位寄存器,用来记录某进程在内存中各页的使用情况。移位寄存器表示为
- $$
R= R_{n-1}R_{n-2}R_{n-3}\cdots R_2R_1R_0
$$
- 当进程访问某物理块时,要将相应寄存器的R.1位置成1。此时,定时信号将每隔一定时间将寄存器右移一位。如果把n位寄存器的数看作一个整数,那么具有最小数值的寄存器所对应的页面,就是最近最久未使用的页面。
- 栈
- 利用一个特殊的栈来保存当前使用的各个页面的页面号
- 每当进程访问某页面时,**便将该页面的页面号从栈中移出,将它压入栈顶**。
- 栈顶始终是最新被访问页面的编号,而栈底则是最近最久未使用页面的页面号。
- 最少使用置换（Least Frequently Used)算法
- 在采用LFU算法时,应为在内存中的每个页面设置一个移位寄存器,用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。
- 简单的Clock置换算法
- 当采用简单Clock算法时,只需为每页设置一位访问位,再将内存中的所有页面都通过链接指针链接成一个循环队列。
- 当某页被访问时,其访问位被置1。
- 置换算法在选择一页淘汰时,只需检查页的访问位。如果是0 ,就选择该页换出;若为1 ,则重新将它置0 ,暂不换出,而给该页第二次驻留内存的机会
- 再按照FIFO算法检查下一个页面。
- 当检查到队列中的最后一个页面时,若其访问位仍为1 ,则再返回到队首去检查第一个页面。
- 因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描
- 改进型CLock算法
- 在将一个页面换出时,如果该页已被修改过,便须将该页重新写回到磁盘上;但如果该页未被修改过,则不必将它拷回磁盘。
- 在改进型Clock算法中,除须考虑页面的使用情况外,还须再增加一个因素,即置换代价,这样,选择页面换出时,既要是未使用过的页面,又要是未被修改过的页面。
- 把同时满足这两个条件的页面作为首选淘汰的页面。
- 由访问位A和修改位M可以组合成下面四种类型的页面:
- 1类(A=0 , M=0) :表示该页最近既未被访问,又未被修改,是最佳淘汰页。
- 2类(A=0 , M=1) :表示该页最近未被访问,但已被修改,并不是很好的淘汰页。
- 3类(A=1 , M=0) :表示该页最近已被访问,但未被修改,该页有可能再被访问。
- 4类(A=1 , M=1) :表示该页最近已被访问且被修改,该页可能再被访问。
- (1)从指针所指示的当前位置开始,扫描循环队列,寻找A=0且M=0的第一类页面,将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位A。
- (2)如果第一步失败,则开始第二轮扫描,寻找A=0且M= 1的第二类页面,将所遇到的第一个这类页面作为淘汰页。在第二轮扫描期间,将所有扫描过的页面的访问位都置0。
- (3)如果第二步也失败,则将指针返回到开始的位置,然后回到第一步重新开始,一定能找到被淘汰的页。
- 该算法与简单Clock算法比较，可减少磁盘的I/O操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之,实现该算法的开销有所增加。
- 
- 页面缓冲算法（Page Buffering Algorithm）
- 影响效率的因素
- 页面置换算法。
- 写回磁盘的频率。
- 建立了一个已修改换出页面的链表,则对每一个要被换出的页面(已修改) ,系统可暂不把它们写回磁盘,而是将它们挂在已修改换出页面的链表.上，仅当被换出页面数目达到一定值时，例如64个页面,再将它们一起写回磁盘上
- 读入内存的频率。
- 如果有进程在这批数据还未写回磁盘时需要再次访问这些页面时,就不从外存上调入,而直接从已修改换出页面链表中获取,这样也可以减少将页面从磁盘读入内存的频率,减少页面换进的开销。
- 特点
- 显著地降低了页面换进、换出的频率,使磁盘I/O的操作次数大为减少，因而减少了页面换进、换出的开销;
- 正是由于换入换出的开销大幅度减小,才能使其采用一种较简单的置换策略,如先进先出(FIFO)算法,它不需要特殊硬件的支持,实现起来非常简单。
- 空闲页面链表
- 该链表是一个空闲物理块链表。是系统掌握的空闲物理块,当进程需要读入一个页面时,便可利用空闲物理块来装入该页。
- 当有一个未被修改的页面要换出时,实际上并不将它换回到外存,而是把它们所在的物理块挂在空闲链表的末尾。这些挂在空闲链表中的物理块是有数据的,如果以后某个进程需要访问这些页面时,可以直接从空闲链表中取下,免除了从磁盘读入数据的操作,减少了页面换进的开销。
- 修改页面链表
- 该链表是由已修改的页面所形成的链表。设置该链表的目的是减少修改页面换出的次数。当进程需要将一个已经修改的页面换出时,系统并不立即将它换出到磁盘上,而是将它所在的物理块挂在修改页面链表的末尾。
- 当已修改页面的链表上的页面个数达到一定程度时,会-起将这些页面写回到磁盘。如果这些被换出的页面在写回磁盘之前,有进程需要访问其中的页面,那么可以直接从已修改页面链表.上获取该页面。所以可见,减少了磁盘I/O操作,并且减少了内存写入频率。
### 访问内存的有效时间
- 查找快表时间( λ )
- 访问实际物理地址时间( t )
- 缺页中断处理时间( ε )
- 命中率(a)
- 缺页率(f )
- 在内存,在快表
- EAT =快表时间+内存时间=λ+t
- 在内存,不在快表
- EAT =快表时间+内存时间+修改快表时间+内存时间=λ+t+λ+t
- 不在内存
- EAT =快表时间+内存时间+缺页中断时间+修改快表时间+内存时间=λ+t+ε+λ+t
- 考虑命中率与缺页率
- EAT =aX(+t)+(1-a)X [fX(+t++s+i+t)+(1-f)x(2+t+i+t)]=λ+ aXt+(1-a) X [t+f X (ε+ λ+t)+(1-f) X (1+ t)]
- 不考虑命中率,仅考虑缺页率,
- EAT=f X (t+ε+t)+ (1-f) X(t+t)=t+f X (ε+ t)+(1-f) X t
## 抖动与工作集
### 抖动
由于请求分页式虚拟存储器系统的性能优越,在正常运行情况下,它能有效地减少内存碎片,提高处理机的利用率和吞吐量,故是目前最常用的一种系统。
但如果在系统中运行的进程太多,进程在运行中会频繁地发生缺页情况,这又会对系统的性能产生很大的影响,故还须对请求分页系统的性能做简单的分析。
**刚被淘汰的页面又马.上被调回内存,调回内存不久后又被淘汰出去,如此频繁进行,这种现象称为抖动(或称颠簸)**。它使得系统中页面调度非常频繁，以致CPU大部分时间都花费在内存和外存之间的调入调出上。
发生"抖动”的根本原因是,同时在系统中运行的进程太多,由此分配给每一个进程的物理块太少,不能满足进程正常运行的基本要求。抖动是在进程运行中出现的严重问题,必须采取相应的措施解决它。
### 工作集
如果将缺页率控制在上界与下界(比如0.1%~1%) 之间,那么缺页率达到0.5%时的驻留集尺寸W将是比较适宜的。
我们无法事先预知程序在不同时刻将访问哪些页面,故仍只有像置换算法那样,用程序的过去某段时间内的行为作为程序在将来某段时间内行为的近似。
**所谓工作集,是指在某段时间间隔△里,进程实际所要访问页面的集合。**
把进程在某段时间间隔O里,在时间t的工作集记为w(t,A) ,变量△称为工作集“窗口尺寸”
对于给定的页面走向,如果△= 10次存储访问,在t1时刻的工作集是W(t1,10)=(1,2,5,6,7) ,在t2时刻,工作集是W(t2,10)=(3,4)
## 抖动的预防
- 采取局部置换策略
- 即使该进程发生了"抖动”, 也不会对其它进程产生影响,于是可把该进程”抖动”所造成的影响限制在较小的范围内
- 但在某进程发生"抖动”后,它还会长期处在磁盘I/O的等待队列中,使队列的长度增加,这会延长其它进程缺页中断的处理时间。
- 把工作集算法融入到处理机调度中
- 当调度程序发现处理机利用率低下时,它将试图从外存调入一个新作业进入内存,在从外存调入作业之前,必须检查每个进程在内存的驻留页面是否足够多。
- 如果都足够多,此时便可以从外存调入新的作业,不会因新作业的调入而导致缺页率的增加;
- 反之,如果有些进程的内存页面不足,则应首先为那些缺页率居高的作业增加新的物理块,此时将不再调入新的作业。
- 利用"L=S"准则调节缺页率
- L是缺页之间的平均时间, S是平均缺页服务时间,即用于置换一个页面所需的时间。
- 如果是L远比S大,说明很少发生缺页,磁盘的能力尚未得到充分的利用;
- 反之,如果是L比S小,则说明频繁发生缺页,缺页的速度已超过磁盘的处理能力。
- 只有当L与S接近时,磁盘和处理机都可达到它们的最大利用率。
- 理论和实践都已证明,利用"L=S"准则,对于调节缺页率是十分有效的。
- 选择暂停的进程
- 当多道程序度偏高时,已影响到处理机的利用率,为了防止发生“抖动”,系统必须减少多道程序的数目,以便腾出内存空间分配给那些缺页率偏高的进程。