第六章 虚拟 存储器 (Virtual Memory)
教学目的,
为了在内存空间运行超过内存总容量的大作业，或者同时运行大量作业，解决的方法是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。 本课要介绍虚拟存储技术实现的各种方案，每种方案所需的硬件和软件支持。
教学要求：
掌握 虚拟存储器的 理论基础和定义,熟悉虚拟存储 器 实现方式和 特征。
掌握请求分页的页表机制、缺页中断机构和地址变换机构，
熟悉 页面的分配和置换策略、页面的分配的算法。
熟练掌握最佳置换算法、先进先出（ FIFO）置换算法、最近最久未使用置换算法 LRU，掌握 Clock置换算法和 页面缓冲算法； 掌握有效访问时间计算,熟悉 工作集概念。
掌握请求分段的段表机制、缺段中断机构和地址变换机构，
熟悉 分段的共享和保护。
6.1 虚拟 存储器 (Virtual Memory)的基本概念问题的提出物理存储器的结构是个一维的线性空间,容量是有限的 。
用户程序结构：
一维空间一个用户程序就是一个程序,并且程序和数据是不分离的；
二维空间 程序由主程序和若干个子程序 （ 或函数 ） 组成,并且程序 与数据是分离的；
n维空间 即一个大型程序,由一个主模块和多个子模块组成,其中,各子模块又由主程序和子程序 （ 或函数 ） 组成 。
用户程序的大小,可能比内存容量小,也可能比内存容量大,有时候要大得多 。
如何将大于物理内存容量的用户程序装入运行？ 这就是提出研究虚拟存储器的原因,或称为虚拟存储技术发展的原动力 。
虚拟存储器的基本思想：程序,数据,堆栈的大小可以超过内存的大小,
OS把程序当前使用的部分保留在内存,而把其它部分保留在磁盘上,并在需要时在内存和磁盘之间动态交换 。 同时支持多道程序设计技术 。
6.1 虚拟存储器的基本概念一次性及驻留性的必要性？
6.1.1 虚拟存储器的引入
1,局部性原理早在 1968年 P,Denning就指出过,程序在执行时在时间和空间上将呈现出局部性规律,即在一段时间内,程序的执行仅局限于某个部分；相应地,它所访问的存储空间也局限于某个区域内 。 那么程序为什么会出现局部性规律呢？ 原因可以归结为以下 4点：
程序在执行时,除了少部分的转移和过程调用指令外,大多数仍是顺序执行的 。
子程序调用将会使程序的执行由一部分内存区域转至另一部分区域 。 但在大多数情况下,过程调用的深度都不超过 5。
程序中存在许多循环结构,循环体中的指令被多次执行 。
程序中还包括许多对数据结构的处理,如对连续的存储空间 ——数组的访问,往往局限于很小的范围内 。
虚拟存储器的引入 -1
所以局限性表现为：
时间局限性,如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
空间局限性,一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。
2。 虚拟存储技术虚存,把内存与外存结合起来使用，从而得到一个容量很大的内存，这就是虚存。其逻辑容量由内存和外存容量之和决定。
虚拟存储器的引入 -2
实现思想：
根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。程序在运行时，由请求调入或置换完成执行。这样，
可使一个大用户程序在较小内存空间运行；也可使内存中有更多进程并发执行。
请求调入：
程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；
但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用 OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。
置换：
如果此时内存已满,无法再装入新的页 （ 段 ）,则还须再利用页 （ 段 ） 的置换功能,将内存中暂时不用的页 （ 段 ） 调出至磁盘上,腾出足够的内存空间后,再将所要访问的页 （ 段 ） 调入内存,使程序继续执行下去 。
从用户角度看,该系统所具有的内存容量,将比实际内存容量大得多,人们把这样的存储器称为虚拟存储器 。
3 虚拟存储 器 实现方式
1。 请求分页系统,
它是在分页系统的基础上,增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统 。 它允许只装入若干页 （ 而非全部程序 ） 的用户程序和数据,就可以启动运行,以后再通过调页功能和页面置换功能,陆续把将要运行的页面调入内存,同时把暂不运行的页面置换到外存上,置换时以页面为单位 。
2。 请求分段系统,
它是在分段系统的基础上,增加了请求调段和分段置换功能所形成的段式虚拟存储系统 。 它允许只装入若干段 （ 而非全部段 ） 的用户程序和数据,就可以启动运行,以后再通过调段功能和置换功能将不运行的段调出,同时调入将要运行的段,置换以段为单位 。
3。 请求段页式系统,它是在段页式系统的基础上,增加了请求调页和页面置换功能所形成的段页式虚拟存储系统 。
虚拟存储 器
4 虚拟存储器的特征
离散性,指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。
多次性,指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。
对换性,指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。
虚拟性,指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
6.2 请求分页存储管理方式
1,基本工作原理
请求分页技术当一个用户程序要调入内存时,不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行,在运行的过程中，如果 发现要运行的程序或要访问数据不在内存,则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存,该程序继续运行 。
2 请求分页中的硬件支持
1） 请求分页的页表机制它是在纯分页的页表机制上形成的,由于只将应用程序的一部分调入内存,还有一部分仍在磁盘上,故需在页表中再增加若干项,供程序 (数据 )在换进,换出时参考 。 在请求分页系统中的每个页表项如图所示 。
页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址请求分页中的硬件支持 -1
其中各字段说明如下：
状态位 （存在位 P）：用于指示该页是否已调入内存，供程序访问时参考。 1—在内存； 0—不在内存。
访问字段 A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。页面访问频度。
修改位 M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
外存地址,用于指出该页在外存上的地址，通常是物理块号，
供调入该页时使用。
请求分页中的硬件支持 -2
2,缺页中断机构在请求分页系统中,每当所要访问的页面不在内存时,便要产生一缺页中断,请求 OS将所缺页调入内存 。 与一般中断的主要区别在于：
缺页中断在指令执行期间产生和处理中断信号,而一般中断在一条指令执行完后检查和处理中断信号 。
缺页中断返回到该指令的开始重新执行该指令,而一般中断返回到该指令的下一条指令执行 。
一条指令在执行期间,可能产生多次缺页中断 。 P169图 6-1。
3,地址变换机构请求分页系统中的地址变换机构,是在分页系统的地址变换机构的基础上,再为实现虚拟存储器而增加了某些功能所形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等等,下图 给 出了请求分页系统的地址变换过程 。
缺页中断处理是否否是是 否产生缺页中 否是 断请求调页 是开始 （ 程序请求访问一页 )
越界中断
CPU检索快表页表项是否在快表中？
访问页表页是否在内存中？
修改快表修改访问位和修改位形成物理地址地址变换结束保留 CPU现场从外存中找到缺页页号 > 页 表长度？
内存满否？
选择一页换出该页是否被修改？
将该页写回外存将一页从外存换入内存修改页表
CPU从外存读缺页启动 I/O硬件
6.2.2页面分配
1.最少物理块数在为进程分配物理块时,首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数 （ 称为最小物理块数 ） 。
若系统为某进程所分配的物理块数少于此值时,进程将无法运行,这取决于指令的格式,功能和寻址方式 。 p169
2,页面的分配和置换策略在请求分页系统中,可采取两种分配策略 ——固定和可变分配策略 。 在进行置换时,也可采取两种策略 ——全局置换和局部置换 。 于是可组合成以下三种策略 。
固定分配局部置换策略,它基于进程的类型 （ 交互型或批处理型等 ）,或根据程序员,系统管理员的建议,为每个进程分配一固定页数的内存空间,在整个运行期间都不再改变 。
如果进程在运行中发现缺页,则只能从该进程在内存的固定页面中选出一页换出,然后再调入另一页,保证分配给该进程的内存空间不变 。
页面分配 -1
可变分配全局置换策略,
系统为每个进程分配一定数目的物理块，而 OS本身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。当空闲物理块队列中的物理块用完时,OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。
可变分配局部置换,
根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，而不影响其它进程的运行。若该进程缺页率太高,OS可为其追加若干物理块。
页面分配 -2
3．页面分配算法在采用固定分配策略时,可采用以下 3种物理块分配方法：
平均分配算法,将系统中所有可供分配的物理块,平均分配给各个进程 。
按比例分配算法,这是根据进程的大小按比例分配物理块 。
考虑优先权的分配算法,该方法是把内存中可供分配的所有物理块分成两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程 。
6.2.3 页面调入策略为能使进程运行,必须事先将一部分要执行的程序和数据调入内存 。
1,调入页面的时机为了将进程运行时所缺的页面调入内存,可采取策略有：
预调页策略 是一种主动的缺页调入策略,即将那些预计在不久的将来会被访问的程序或数据所在的页面,预先调入内存 。 由于预测的准确率不高 （ 50%）,所以这种策略主要用于进程的首次调入 。 有的系统将预调页策略用于请求调页,例如在
VAX/VMS操作系统中,采用了一种称为群页式的调页策略,当系统将进程所请求的页面调入内存时,也同时将其相邻的几个页面调入内存 。
请求调页策略是指当进程在运行中发生缺页时,就立即提出请求,由系统将缺页调入内存 。 目前的虚拟存储器中,大多采用此策略 。 但这种策略在调页时须花费较大的系统开销,如需频繁启动磁盘 I/O。
页面调入策略 -1
2。从何处调入页面每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？
1）对换区中调入：系统有足够大的对换区空间，全部从对换区调入，淘汰页面 ---对换区。
2）系统缺少足够大的对换区，代码从文件区调入，淘汰代码直接从内存淘汰；可变页面从对换区调入，数据从内存淘汰到对换区，以备再用。
3） UNIX方式,在 UNIX系统中，对于从未运行过的页面，都应从硬盘 文件区调入；对于曾经运行过而又被换出的页面，可以从 对换区 调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。
在虚拟存储系统中，外存（硬盘）
常常被分成两部分,
文件区（用于存放文件）
对换区（用于存放对换页面）
通常，对换区的磁盘 I/O速度比文件区要高。
系统文件区工作区 /对换区页面调入策略 -2
对换进程就是 0号进程，它一个永远处于核心态的进程。其任务是将进程的映象在内存和对换区之间传递。
系统盘的结构：
页面调入策略 -3
（一）进程换入
当内存空闲时,0号进程将对换区中处于就绪状态的进程的映象调入内存，直到内存满，或者是对换区中已经没有处于就绪状态的进程。
（二）进程换出
当内存空间不足时,0号进程将内存中的某些进程换到对换区。
不能换出的进程是核心态的进程（ UNIX核心）、处于创建状态的进程、上锁的进程，在内存中驻留时间不足两分钞钟的就绪进程。
换出的顺序是：处于睡眠状态的进程、暂停状态的进程。
若无以上这两类进程，就是处于就绪状态的进程。
按就绪状态的进程在内存中驻留时间从长到短的顺序依次调入内存，直到内存中无进程可调出为止。
3、页面调入过程
P170
6.3页面置换算法（ Page Replacement Algorithms）
在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的对换区。但将哪个页面调出，则须根据一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生,抖动,
（ Thrashing)。 即刚被换出的页很快又被访问，需重新调入，
导致系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在完成页面置换的工作上，我们称该进程发生了
,抖动,。
从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访问的页面换出。下面介绍几种常用的置换算法。
页面置换算法 -1
6.3.1 最佳（ Optimal）置换算法它是一种理想化的算法，性能最好，但在实际上难于实现。 即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去 。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。
例,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串,7,0,l,2,0,3,0,4,2,3,0,3,2，
l,2,0,l,7,0,1。如下图 所示,进程运行时先将 7,0，
1三个页面装入内存。当进程访问页面 2时，产生缺页中断，
此时 OS根据最佳置换算法，页面 7将在第 18次才被访问，是三页中将最久不被访问的页面，所以被淘汰 (在 UNIX中称为偷页 )。 接着访问页面 0时，发现已在内存中，而不会产生缺页中断，以此类推。 从 图可以看出，采用最佳置换算法，只发生了 6次页面置换。
最佳（ Optimal）置换算法 -1
页面引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
物理块
1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
缺页 x x x x x x x x x
发生了 6 次面置换,9 次缺页 中断。
6.3.2先进先出（ FIFO）置换算法该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针即可。它是一种最直观，性能最差的算法，它有 B E L A D Y 异常现象：对页面访问序列 A B C D A B E A B C D E,物理块从
3 块增加到 4 块，缺页次数增加。
页面引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1
7 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 0
物理块
7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7
缺页 x x x x x x x x x x x x x x x
发生了 12 次页面置换,缺页次数 15 次。
6.3.3最近最久未使用置换算法
LRU（ Least Recently Used）
该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间
T,当要淘汰一个页面时，选择 T 最大的页面。但在实现时需要硬件的支持 （寄存器或栈）。利用 LRU 算法对上例进行页面置换的结果如下：
页 面 引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
物理块
7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7
缺页 x x x x x x x x x x x x
发生了 9 次面置换,缺页次数 12 次
6.3.3 最少使用置换算法（ LFU）
1、基本方法记录每个页面的访问次数，最少访问的页面首先考虑淘汰。
2、实际采取方法为页面设置移位寄存器。
与 LRU的区别,R1=10000000
R2=01110100
LRU----------淘汰 R2
LFU----------淘汰 R1
6.3.4 页面缓冲算法（ Page Buffering Algorithm）
该算法在页面分配时，采用可变分配和局部置换的方式 。首先为每个作业分配一个工作集（进程在一段时间内运行，要用到的部分页面的集合），每个工作集的块数相对固定的
（在一段时间内），块号是可变的。系统自己也保留一部分存储块作为页面缓冲，并把页面缓冲组织成两个队列：空闲队列和已修改的页面队列。
经过一段时间的运行,OS把一些暂时不访问的页面（在每个工作集采用 FIFO算法进行选择）放入页面缓冲，如果页面未被修改，就将它直接放入空闲队列中；否则，便放入已修改的页面队列中。注意，这时页面在内存中并未做物理上的移动，而只是将页表中的表项移到上述两个队列之一中。图中是页面缓冲算法的某个状态，有三个作业（ A,B,C）的工作集和页面缓冲的两个队列。
页面缓冲算法 -1
A
B
C
页面缓冲已修改的页面队列 空闲队列页面修改位 =“1” 页面修改位 =“0”
当进程要访问页面时,先到工作集中去找,如果找到就可以直接访问 。 否则,到页面缓冲的两个队列中去找,如果找到也可以直接访问,并将该页在页表中的表项链接到工作集队列的末尾,而把工作集队列的队首的页表表项链入页面缓冲的两个队列中 。
40 3 19 22 61 20
24 41 5 23
7 12 13 30 10
1 32 14 9 43 39 8 16
工作集页面缓冲算法 -2
如果还是没找到,则启动磁盘 I/O,将缺页读入空闲队列第一个物理块中 （ 利用 FIFO）,并将该页在页表中的表项链接到工作集队列的末尾 。
利用这种方法可使已修改的页面和未修改的页面,都仍留在内存中 。 当该进程要再次访问这些页面时,便只须花较小的开销就可以使这些页面又返回到该进程的工作集中 。 当在页面缓冲的已修改页面达到一定数量时,例如 64个页面,可以将它们一起写回到磁盘,从而显著地减少了磁盘 I/O的操作次数 。
页面缓冲算法是一个较简单的近似于 LRU页面缓冲算法,它与 LRU置换算法相比,无需硬件的支持,又大大减少了页面置换的开销 。 在性能上又比 FIFO要好,有效地改善了请求式分页系统的性能 。 著名的 VAX／ VMS和 Windows NT便是使用这种算法,而在 MACH操作系统实现中,只是它没有区分已修改页面和末修改页面 。
(6)性能分析
1.缺页率对有效访问时间的影响在请求分页系统中,假设存储器的访问时间 ma为 100ns（ 一般为 10ns～几百 ns）,缺页率为 p,缺页中断时间为 25ms,则有效访问时间就可以表示为：
有效访问时间 =（ 1一 p） × ma十 p× 缺页中断时间
=（ 1一 p） × 0.1十 p× 25000 = 0.1十 24999.9 p
由上式可以看出,有效访问时间与缺页率成正比 。 如果缺页率为 0.1%,则有效访问时间约为 25μ s,与直接访问存储器的有效访问时间 （ 0.1μ s ） 相比的时间,程序执行的性能将受到严重的影响 。 如果希望在缺页时,仅使有效访问时间延长不超过 10%,则可计算出缺页率 p=0.0000004,由此得出,要求在 2500000次的访问中才发生一页缺页,即请求分页方式应保持非常低的缺页率；否则,将使程序执行速度受到严重影响 。 此外,提高磁盘 I/O的速度,对改善请求分页系统的性能至关重要 。 为此,应选用高速磁盘和高速磁盘接口 。
性能分析 -1
2,工作集
程序在运行中所产生的缺页情况，会影响程序的运行速度及系统性能，而缺页率的高低又将是与每个进程所占用的物理块数目有关。这里我们简单地分析一下应为每个进程分配多少个物理块，才能把缺页率保持在一个合理的水平上。
缺页率与进程所分得的物理块数目有密切关系。下图 说明了的缺页率与进程分得的物理块数目 N之间的关系曲线。从图中可以看出，缺页率随着所分得的物理块数目的减少而递增，
并在所分到的物理块数目较少处，出现一个拐点。在拐点上限以左时，随着分到的物理块数目的增加，缺页率明显地减少；而过了拐点，在下限以右时，随着分到的物理块数目的增加，却对缺页率的改善并不明显。所以，为进程分配的物理块数，应取在该曲线的拐点左右。
性能分析 -2
缺页率拐点所分得的物理块数
工作集的理论是在 1968年由 Denning提出来的 。 他认为,程序在运行时对页面的访问是不均匀的,即往往在某段时间内的访问仅局限于较少的若干个页面,如果能够预知程序在某段时间间隔内要访问哪些页面,并能将它们提前调入内存,将会大大地降低缺页率,从而减少置换工作,提高 CPU的利用率 。
性能分析 -3
所谓工作集是指，在某段时间间隔（ Δ ）里，进程实际要访问的页面的集合。 Denning认为，虽然程序只需有少量的几页在内存就可以运行，但为了使程序能够有效地运行，较少地产生缺页、就必须使程序的工作集全部在内存中。把某进程在时间 t的工作集记为 w（ t,Δ ），把变量 Δ 称为工作集
,窗口尺寸,（ Windows Size）。正确选择工作集窗口（ Δ ）
的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。
抖动产生的原因？
1）页面置换算法不合理。
2）分配给进程的物理页面数太少。
例,A,B,C进程之间的换页。
6.4 请求分段存储管理方式请求分段系统在分段系统的基础上实现的虚拟存储器,是以分段为单位进行换入,换出的 。 在程序运行之前只要先调入若干个分段 （ 不必调入所有的分段 ）,便可启动运行 。 当所访问的段不在内存时可请求 OS将所缺的段调入内存 。 为实现请求分段存储管理方式,同样需要一定的硬件支持和相应的软件,有段表机制,缺段中断机构以及地址变换机构 。
（ 1） 请求分段中的硬件支持
1,段表机制在请求分段式管理中在段表中增加若干项,以供程序在调进,
调出时参考 。 请求分段的段表项如下：
段 段 段的 存取 访问 修改 存在 增补 外存名 长 基址 方式 字段 A 位 M 位 P 位 起址请求分段中的硬件支持 -1
在段表项中，除了段名 (号 )、段长、段在内存的起始地址外，
还增加了以下几项：
存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读／写。
访问字段 A：用于记录该段被访问的频繁程度。
修改位 M：用于表示该段进入内存后，是否已被修改过。
存在位 P：说明本段是否已调入内存。
增补位：用于表示本段在运行过程中，是否进行过动态增长。
外存起址：指示本段在外存中的起始地址，即起始盘块号。
2.缺段中断机构在请求分段系统中，采用的是请求调段策略。即当进程所要访问的段未调入内存时，便由缺段中断机构产生一缺段中断信号，由缺断中断处理程序将所需的段调入内存。缺段中断的处理过程如下图：
请求分段中的硬件支持 -1
拼接后形成合适大小的空闲区淘汰一个或几个段以形成合适大小的空闲区虚段不在内存中阻塞请求的进程内存中有合适的空闲区？
从外存读入段修改段表和内存空闲链唤醒请求进程返回空闲区大小总和能否满足？
N
N
请求分段中的硬件支持 -2
3。 地址变换机构请求分段系统中的地址变换机构,是在分段系统地址变换机构的基础上形成的 。 由于被访问的段并非全在内存,所以在地址变换时,若发现所要访问的段不在内存时,必须先将所缺的段调入内存,并修改了段表之后,才能再利用段表进行地址变换 。 为此,在地址变换机制中又增加了某些功能,如缺段中断的请求及其处理等 。
请求分段中的硬件支持 -3
4。段的动态链接经过编释或汇编得到的一组目标程序需经链接程序，连接装配成一个一维的线性连续地址空间，这一过程称为 静态链接,但是这种连接装配过程既复杂又费时，还经常发生许多被连接好的摸块在作业运行过程中根本不用，而造成连接时的机时和主存空间的浪费，所以最好能采用什么时候用到那一段责连接该段的方法，这种方法称为动态连接方法。 段的动态链接是指“在一个程序运行开始时，只将主程序装配好并调入主存，其它各段的装配是在主程序段运行过程中逐步进行的，每当需要调用一个新段时，再将该段装配好，并与主程序段连接。 在分段存储管理环境中，由于逻辑地址空间是二维的，每段有自己的段名，因而实现动态连接比较容易。
（ 2） 分段共享与保护分段存储管理方式实现分段的共享和保护只须在每个进程的段表中,用相应的表项来指向共享段在内存中的起始地址 。
为了实现分段共享,应配置相应的共享段表,用来对共享段进行操作 。
在系统中,用共享段表来记录了每一个共享段的段号和段长,
内存始址,存在位等信息,并记录共享此分段的每个进程的情况 。 共享段表如下图所示 。
分段共享与保护 -1
其中：
共享进程计数 器 COUNT：记录有多少个进程需要共享该分段。
存取控制字段：说明不同的进程对该分段不同的存取权限。
段号：对于同一个共享段，不同的进程可以使用不同的段号去共享该段。
段名 段长 内存起址 状态 外存起址共享进程计数器 COUNT
状态 进程名 进程号 段号 存取控制
教学目的,
为了在内存空间运行超过内存总容量的大作业，或者同时运行大量作业，解决的方法是从逻辑上扩充内存容量，这正是虚拟存储技术所要解决的主要问题。 本课要介绍虚拟存储技术实现的各种方案，每种方案所需的硬件和软件支持。
教学要求：
掌握 虚拟存储器的 理论基础和定义,熟悉虚拟存储 器 实现方式和 特征。
掌握请求分页的页表机制、缺页中断机构和地址变换机构，
熟悉 页面的分配和置换策略、页面的分配的算法。
熟练掌握最佳置换算法、先进先出（ FIFO）置换算法、最近最久未使用置换算法 LRU，掌握 Clock置换算法和 页面缓冲算法； 掌握有效访问时间计算,熟悉 工作集概念。
掌握请求分段的段表机制、缺段中断机构和地址变换机构，
熟悉 分段的共享和保护。
6.1 虚拟 存储器 (Virtual Memory)的基本概念问题的提出物理存储器的结构是个一维的线性空间,容量是有限的 。
用户程序结构：
一维空间一个用户程序就是一个程序,并且程序和数据是不分离的；
二维空间 程序由主程序和若干个子程序 （ 或函数 ） 组成,并且程序 与数据是分离的；
n维空间 即一个大型程序,由一个主模块和多个子模块组成,其中,各子模块又由主程序和子程序 （ 或函数 ） 组成 。
用户程序的大小,可能比内存容量小,也可能比内存容量大,有时候要大得多 。
如何将大于物理内存容量的用户程序装入运行？ 这就是提出研究虚拟存储器的原因,或称为虚拟存储技术发展的原动力 。
虚拟存储器的基本思想：程序,数据,堆栈的大小可以超过内存的大小,
OS把程序当前使用的部分保留在内存,而把其它部分保留在磁盘上,并在需要时在内存和磁盘之间动态交换 。 同时支持多道程序设计技术 。
6.1 虚拟存储器的基本概念一次性及驻留性的必要性？
6.1.1 虚拟存储器的引入
1,局部性原理早在 1968年 P,Denning就指出过,程序在执行时在时间和空间上将呈现出局部性规律,即在一段时间内,程序的执行仅局限于某个部分；相应地,它所访问的存储空间也局限于某个区域内 。 那么程序为什么会出现局部性规律呢？ 原因可以归结为以下 4点：
程序在执行时,除了少部分的转移和过程调用指令外,大多数仍是顺序执行的 。
子程序调用将会使程序的执行由一部分内存区域转至另一部分区域 。 但在大多数情况下,过程调用的深度都不超过 5。
程序中存在许多循环结构,循环体中的指令被多次执行 。
程序中还包括许多对数据结构的处理,如对连续的存储空间 ——数组的访问,往往局限于很小的范围内 。
虚拟存储器的引入 -1
所以局限性表现为：
时间局限性,如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。
空间局限性,一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。 即程序在一段时间内所访问的地址，可能集中在一定的范围内，其典型原因是程序是顺序执行的。
2。 虚拟存储技术虚存,把内存与外存结合起来使用，从而得到一个容量很大的内存，这就是虚存。其逻辑容量由内存和外存容量之和决定。
虚拟存储器的引入 -2
实现思想：
根据局部性原理，一个作业在运行之前，没有必要把全部作业装入内存，而仅将那些当前要运行的那部分页面或段，先装入内存便可启动运行，其余部分暂时留在磁盘上。程序在运行时，由请求调入或置换完成执行。这样，
可使一个大用户程序在较小内存空间运行；也可使内存中有更多进程并发执行。
请求调入：
程序在运行时如果它所要访问的页（段）已调入内存，便可继续执行下去；
但如果程序所要访问的页（段）尚未调入内存（称为缺页或缺段），此时程序应利用 OS所提供的请求调页（段）功能，将它们调入内存，以使进程能继续执行下去。
置换：
如果此时内存已满,无法再装入新的页 （ 段 ）,则还须再利用页 （ 段 ） 的置换功能,将内存中暂时不用的页 （ 段 ） 调出至磁盘上,腾出足够的内存空间后,再将所要访问的页 （ 段 ） 调入内存,使程序继续执行下去 。
从用户角度看,该系统所具有的内存容量,将比实际内存容量大得多,人们把这样的存储器称为虚拟存储器 。
3 虚拟存储 器 实现方式
1。 请求分页系统,
它是在分页系统的基础上,增加了请求调页功能和页面置换功能所形成的页式虚拟存储系统 。 它允许只装入若干页 （ 而非全部程序 ） 的用户程序和数据,就可以启动运行,以后再通过调页功能和页面置换功能,陆续把将要运行的页面调入内存,同时把暂不运行的页面置换到外存上,置换时以页面为单位 。
2。 请求分段系统,
它是在分段系统的基础上,增加了请求调段和分段置换功能所形成的段式虚拟存储系统 。 它允许只装入若干段 （ 而非全部段 ） 的用户程序和数据,就可以启动运行,以后再通过调段功能和置换功能将不运行的段调出,同时调入将要运行的段,置换以段为单位 。
3。 请求段页式系统,它是在段页式系统的基础上,增加了请求调页和页面置换功能所形成的段页式虚拟存储系统 。
虚拟存储 器
4 虚拟存储器的特征
离散性,指在内存分配时采用离散的分配方式，它是虚拟存储器的最基本的特征。
多次性,指一个作业被分成多次调入内存运行，即在作业运行时没有必要将其全部装入，只须将当前要运行的那部分程序和数据装入内存即可。多次性是虚拟存储器最重要的特征。
对换性,指允许在作业的运行过程中在内存和外存的对换区之间换进、换出。
虚拟性,指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。
6.2 请求分页存储管理方式
1,基本工作原理
请求分页技术当一个用户程序要调入内存时,不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行,在运行的过程中，如果 发现要运行的程序或要访问数据不在内存,则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存,该程序继续运行 。
2 请求分页中的硬件支持
1） 请求分页的页表机制它是在纯分页的页表机制上形成的,由于只将应用程序的一部分调入内存,还有一部分仍在磁盘上,故需在页表中再增加若干项,供程序 (数据 )在换进,换出时参考 。 在请求分页系统中的每个页表项如图所示 。
页号 物理块号 状态位 P 访问字段 A 修改位 M 外存地址请求分页中的硬件支持 -1
其中各字段说明如下：
状态位 （存在位 P）：用于指示该页是否已调入内存，供程序访问时参考。 1—在内存； 0—不在内存。
访问字段 A：用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。页面访问频度。
修改位 M：表示该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一份副本，因此，若未被修改，在置换该页时就不需将该页写回到外存上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写到外存上，以保证外存中所保留的始终是最新副本。
外存地址,用于指出该页在外存上的地址，通常是物理块号，
供调入该页时使用。
请求分页中的硬件支持 -2
2,缺页中断机构在请求分页系统中,每当所要访问的页面不在内存时,便要产生一缺页中断,请求 OS将所缺页调入内存 。 与一般中断的主要区别在于：
缺页中断在指令执行期间产生和处理中断信号,而一般中断在一条指令执行完后检查和处理中断信号 。
缺页中断返回到该指令的开始重新执行该指令,而一般中断返回到该指令的下一条指令执行 。
一条指令在执行期间,可能产生多次缺页中断 。 P169图 6-1。
3,地址变换机构请求分页系统中的地址变换机构,是在分页系统的地址变换机构的基础上,再为实现虚拟存储器而增加了某些功能所形成的,如产生和处理缺页中断,以及从内存中换出一页的功能等等,下图 给 出了请求分页系统的地址变换过程 。
缺页中断处理是否否是是 否产生缺页中 否是 断请求调页 是开始 （ 程序请求访问一页 )
越界中断
CPU检索快表页表项是否在快表中？
访问页表页是否在内存中？
修改快表修改访问位和修改位形成物理地址地址变换结束保留 CPU现场从外存中找到缺页页号 > 页 表长度？
内存满否？
选择一页换出该页是否被修改？
将该页写回外存将一页从外存换入内存修改页表
CPU从外存读缺页启动 I/O硬件
6.2.2页面分配
1.最少物理块数在为进程分配物理块时,首先应该考虑的问题是：能保证进程能正常运行所需的最少物理块数 （ 称为最小物理块数 ） 。
若系统为某进程所分配的物理块数少于此值时,进程将无法运行,这取决于指令的格式,功能和寻址方式 。 p169
2,页面的分配和置换策略在请求分页系统中,可采取两种分配策略 ——固定和可变分配策略 。 在进行置换时,也可采取两种策略 ——全局置换和局部置换 。 于是可组合成以下三种策略 。
固定分配局部置换策略,它基于进程的类型 （ 交互型或批处理型等 ）,或根据程序员,系统管理员的建议,为每个进程分配一固定页数的内存空间,在整个运行期间都不再改变 。
如果进程在运行中发现缺页,则只能从该进程在内存的固定页面中选出一页换出,然后再调入另一页,保证分配给该进程的内存空间不变 。
页面分配 -1
可变分配全局置换策略,
系统为每个进程分配一定数目的物理块，而 OS本身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中，取出一物理块分配给该进程，并将欲调入的缺页装入其中。当空闲物理块队列中的物理块用完时,OS才能从内存中选择一页调出，该页可能是系统中任一进程的页。
可变分配局部置换,
根据进程的类型或程序员的要求，为每个进程分配一定数目的内存空间；但当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，而不影响其它进程的运行。若该进程缺页率太高,OS可为其追加若干物理块。
页面分配 -2
3．页面分配算法在采用固定分配策略时,可采用以下 3种物理块分配方法：
平均分配算法,将系统中所有可供分配的物理块,平均分配给各个进程 。
按比例分配算法,这是根据进程的大小按比例分配物理块 。
考虑优先权的分配算法,该方法是把内存中可供分配的所有物理块分成两部分：一部分按比例分配给各进程；另一部分则根据各进程的优先权,适当地增加其相应份额后,分配给各进程 。
6.2.3 页面调入策略为能使进程运行,必须事先将一部分要执行的程序和数据调入内存 。
1,调入页面的时机为了将进程运行时所缺的页面调入内存,可采取策略有：
预调页策略 是一种主动的缺页调入策略,即将那些预计在不久的将来会被访问的程序或数据所在的页面,预先调入内存 。 由于预测的准确率不高 （ 50%）,所以这种策略主要用于进程的首次调入 。 有的系统将预调页策略用于请求调页,例如在
VAX/VMS操作系统中,采用了一种称为群页式的调页策略,当系统将进程所请求的页面调入内存时,也同时将其相邻的几个页面调入内存 。
请求调页策略是指当进程在运行中发生缺页时,就立即提出请求,由系统将缺页调入内存 。 目前的虚拟存储器中,大多采用此策略 。 但这种策略在调页时须花费较大的系统开销,如需频繁启动磁盘 I/O。
页面调入策略 -1
2。从何处调入页面每当进程发出缺页请求时，系统应从何处将缺页调入内存呢？
1）对换区中调入：系统有足够大的对换区空间，全部从对换区调入，淘汰页面 ---对换区。
2）系统缺少足够大的对换区，代码从文件区调入，淘汰代码直接从内存淘汰；可变页面从对换区调入，数据从内存淘汰到对换区，以备再用。
3） UNIX方式,在 UNIX系统中，对于从未运行过的页面，都应从硬盘 文件区调入；对于曾经运行过而又被换出的页面，可以从 对换区 调入；对于共享页面，该页面可能已由其它进程调入内存，此时就无须再从对换区调入。
在虚拟存储系统中，外存（硬盘）
常常被分成两部分,
文件区（用于存放文件）
对换区（用于存放对换页面）
通常，对换区的磁盘 I/O速度比文件区要高。
系统文件区工作区 /对换区页面调入策略 -2
对换进程就是 0号进程，它一个永远处于核心态的进程。其任务是将进程的映象在内存和对换区之间传递。
系统盘的结构：
页面调入策略 -3
（一）进程换入
当内存空闲时,0号进程将对换区中处于就绪状态的进程的映象调入内存，直到内存满，或者是对换区中已经没有处于就绪状态的进程。
（二）进程换出
当内存空间不足时,0号进程将内存中的某些进程换到对换区。
不能换出的进程是核心态的进程（ UNIX核心）、处于创建状态的进程、上锁的进程，在内存中驻留时间不足两分钞钟的就绪进程。
换出的顺序是：处于睡眠状态的进程、暂停状态的进程。
若无以上这两类进程，就是处于就绪状态的进程。
按就绪状态的进程在内存中驻留时间从长到短的顺序依次调入内存，直到内存中无进程可调出为止。
3、页面调入过程
P170
6.3页面置换算法（ Page Replacement Algorithms）
在进程运行过程中，如果发生缺页，此时内存中又无空闲块时，为了保证进程能正常运行，就必须从内存中调出一页程序或数据送磁盘的对换区。但将哪个页面调出，则须根据一定的页面置换算法来确定。置换算法的好坏将直接影响系统的性能，不适当的算法可能会导致进程发生,抖动,
（ Thrashing)。 即刚被换出的页很快又被访问，需重新调入，
导致系统频繁地更换页面，以致一个进程在运行中把大部分时间花费在完成页面置换的工作上，我们称该进程发生了
,抖动,。
从理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再被访问的页面换出。下面介绍几种常用的置换算法。
页面置换算法 -1
6.3.1 最佳（ Optimal）置换算法它是一种理想化的算法，性能最好，但在实际上难于实现。 即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去 。但是要确定哪一个页面是未来最长时间内不再被访问的，目前来说是很难估计的，所以该算法通常用来评价其它算法。
例,假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串,7,0,l,2,0,3,0,4,2,3,0,3,2，
l,2,0,l,7,0,1。如下图 所示,进程运行时先将 7,0，
1三个页面装入内存。当进程访问页面 2时，产生缺页中断，
此时 OS根据最佳置换算法，页面 7将在第 18次才被访问，是三页中将最久不被访问的页面，所以被淘汰 (在 UNIX中称为偷页 )。 接着访问页面 0时，发现已在内存中，而不会产生缺页中断，以此类推。 从 图可以看出，采用最佳置换算法，只发生了 6次页面置换。
最佳（ Optimal）置换算法 -1
页面引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 2 7 7 7
0 0 0 0 0 0 4 4 4 0 0 0 0 0 0 0 0 0 0
物理块
1 1 1 3 3 3 3 3 3 3 3 1 1 1 1 1 1 1
缺页 x x x x x x x x x
发生了 6 次面置换,9 次缺页 中断。
6.3.2先进先出（ FIFO）置换算法该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针即可。它是一种最直观，性能最差的算法，它有 B E L A D Y 异常现象：对页面访问序列 A B C D A B E A B C D E,物理块从
3 块增加到 4 块，缺页次数增加。
页面引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 2 3 0 4 2 3 0 0 0 1 2 2 2 7 0 1
7 0 1 1 2 3 0 4 2 3 3 3 0 1 1 1 2 7 0
物理块
7 0 0 1 2 3 0 4 2 2 2 3 0 0 0 1 2 7
缺页 x x x x x x x x x x x x x x x
发生了 12 次页面置换,缺页次数 15 次。
6.3.3最近最久未使用置换算法
LRU（ Least Recently Used）
该算法是选择最近最久未使用的页面予以淘汰，系统在每个页面设置一个访问字段，用以记录这个页面自上次被访问以来所经历的时间
T,当要淘汰一个页面时，选择 T 最大的页面。但在实现时需要硬件的支持 （寄存器或栈）。利用 LRU 算法对上例进行页面置换的结果如下：
页 面 引用
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0
物理块
7 0 1 2 2 3 0 4 2 2 0 3 3 1 2 0 1 7
缺页 x x x x x x x x x x x x
发生了 9 次面置换,缺页次数 12 次
6.3.3 最少使用置换算法（ LFU）
1、基本方法记录每个页面的访问次数，最少访问的页面首先考虑淘汰。
2、实际采取方法为页面设置移位寄存器。
与 LRU的区别,R1=10000000
R2=01110100
LRU----------淘汰 R2
LFU----------淘汰 R1
6.3.4 页面缓冲算法（ Page Buffering Algorithm）
该算法在页面分配时，采用可变分配和局部置换的方式 。首先为每个作业分配一个工作集（进程在一段时间内运行，要用到的部分页面的集合），每个工作集的块数相对固定的
（在一段时间内），块号是可变的。系统自己也保留一部分存储块作为页面缓冲，并把页面缓冲组织成两个队列：空闲队列和已修改的页面队列。
经过一段时间的运行,OS把一些暂时不访问的页面（在每个工作集采用 FIFO算法进行选择）放入页面缓冲，如果页面未被修改，就将它直接放入空闲队列中；否则，便放入已修改的页面队列中。注意，这时页面在内存中并未做物理上的移动，而只是将页表中的表项移到上述两个队列之一中。图中是页面缓冲算法的某个状态，有三个作业（ A,B,C）的工作集和页面缓冲的两个队列。
页面缓冲算法 -1
A
B
C
页面缓冲已修改的页面队列 空闲队列页面修改位 =“1” 页面修改位 =“0”
当进程要访问页面时,先到工作集中去找,如果找到就可以直接访问 。 否则,到页面缓冲的两个队列中去找,如果找到也可以直接访问,并将该页在页表中的表项链接到工作集队列的末尾,而把工作集队列的队首的页表表项链入页面缓冲的两个队列中 。
40 3 19 22 61 20
24 41 5 23
7 12 13 30 10
1 32 14 9 43 39 8 16
工作集页面缓冲算法 -2
如果还是没找到,则启动磁盘 I/O,将缺页读入空闲队列第一个物理块中 （ 利用 FIFO）,并将该页在页表中的表项链接到工作集队列的末尾 。
利用这种方法可使已修改的页面和未修改的页面,都仍留在内存中 。 当该进程要再次访问这些页面时,便只须花较小的开销就可以使这些页面又返回到该进程的工作集中 。 当在页面缓冲的已修改页面达到一定数量时,例如 64个页面,可以将它们一起写回到磁盘,从而显著地减少了磁盘 I/O的操作次数 。
页面缓冲算法是一个较简单的近似于 LRU页面缓冲算法,它与 LRU置换算法相比,无需硬件的支持,又大大减少了页面置换的开销 。 在性能上又比 FIFO要好,有效地改善了请求式分页系统的性能 。 著名的 VAX／ VMS和 Windows NT便是使用这种算法,而在 MACH操作系统实现中,只是它没有区分已修改页面和末修改页面 。
(6)性能分析
1.缺页率对有效访问时间的影响在请求分页系统中,假设存储器的访问时间 ma为 100ns（ 一般为 10ns～几百 ns）,缺页率为 p,缺页中断时间为 25ms,则有效访问时间就可以表示为：
有效访问时间 =（ 1一 p） × ma十 p× 缺页中断时间
=（ 1一 p） × 0.1十 p× 25000 = 0.1十 24999.9 p
由上式可以看出,有效访问时间与缺页率成正比 。 如果缺页率为 0.1%,则有效访问时间约为 25μ s,与直接访问存储器的有效访问时间 （ 0.1μ s ） 相比的时间,程序执行的性能将受到严重的影响 。 如果希望在缺页时,仅使有效访问时间延长不超过 10%,则可计算出缺页率 p=0.0000004,由此得出,要求在 2500000次的访问中才发生一页缺页,即请求分页方式应保持非常低的缺页率；否则,将使程序执行速度受到严重影响 。 此外,提高磁盘 I/O的速度,对改善请求分页系统的性能至关重要 。 为此,应选用高速磁盘和高速磁盘接口 。
性能分析 -1
2,工作集
程序在运行中所产生的缺页情况，会影响程序的运行速度及系统性能，而缺页率的高低又将是与每个进程所占用的物理块数目有关。这里我们简单地分析一下应为每个进程分配多少个物理块，才能把缺页率保持在一个合理的水平上。
缺页率与进程所分得的物理块数目有密切关系。下图 说明了的缺页率与进程分得的物理块数目 N之间的关系曲线。从图中可以看出，缺页率随着所分得的物理块数目的减少而递增，
并在所分到的物理块数目较少处，出现一个拐点。在拐点上限以左时，随着分到的物理块数目的增加，缺页率明显地减少；而过了拐点，在下限以右时，随着分到的物理块数目的增加，却对缺页率的改善并不明显。所以，为进程分配的物理块数，应取在该曲线的拐点左右。
性能分析 -2
缺页率拐点所分得的物理块数
工作集的理论是在 1968年由 Denning提出来的 。 他认为,程序在运行时对页面的访问是不均匀的,即往往在某段时间内的访问仅局限于较少的若干个页面,如果能够预知程序在某段时间间隔内要访问哪些页面,并能将它们提前调入内存,将会大大地降低缺页率,从而减少置换工作,提高 CPU的利用率 。
性能分析 -3
所谓工作集是指，在某段时间间隔（ Δ ）里，进程实际要访问的页面的集合。 Denning认为，虽然程序只需有少量的几页在内存就可以运行，但为了使程序能够有效地运行，较少地产生缺页、就必须使程序的工作集全部在内存中。把某进程在时间 t的工作集记为 w（ t,Δ ），把变量 Δ 称为工作集
,窗口尺寸,（ Windows Size）。正确选择工作集窗口（ Δ ）
的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。
抖动产生的原因？
1）页面置换算法不合理。
2）分配给进程的物理页面数太少。
例,A,B,C进程之间的换页。
6.4 请求分段存储管理方式请求分段系统在分段系统的基础上实现的虚拟存储器,是以分段为单位进行换入,换出的 。 在程序运行之前只要先调入若干个分段 （ 不必调入所有的分段 ）,便可启动运行 。 当所访问的段不在内存时可请求 OS将所缺的段调入内存 。 为实现请求分段存储管理方式,同样需要一定的硬件支持和相应的软件,有段表机制,缺段中断机构以及地址变换机构 。
（ 1） 请求分段中的硬件支持
1,段表机制在请求分段式管理中在段表中增加若干项,以供程序在调进,
调出时参考 。 请求分段的段表项如下：
段 段 段的 存取 访问 修改 存在 增补 外存名 长 基址 方式 字段 A 位 M 位 P 位 起址请求分段中的硬件支持 -1
在段表项中，除了段名 (号 )、段长、段在内存的起始地址外，
还增加了以下几项：
存取方式：用于标识本分段的存取属性是只执行、只读，还是允许读／写。
访问字段 A：用于记录该段被访问的频繁程度。
修改位 M：用于表示该段进入内存后，是否已被修改过。
存在位 P：说明本段是否已调入内存。
增补位：用于表示本段在运行过程中，是否进行过动态增长。
外存起址：指示本段在外存中的起始地址，即起始盘块号。
2.缺段中断机构在请求分段系统中，采用的是请求调段策略。即当进程所要访问的段未调入内存时，便由缺段中断机构产生一缺段中断信号，由缺断中断处理程序将所需的段调入内存。缺段中断的处理过程如下图：
请求分段中的硬件支持 -1
拼接后形成合适大小的空闲区淘汰一个或几个段以形成合适大小的空闲区虚段不在内存中阻塞请求的进程内存中有合适的空闲区？
从外存读入段修改段表和内存空闲链唤醒请求进程返回空闲区大小总和能否满足？
N
N
请求分段中的硬件支持 -2
3。 地址变换机构请求分段系统中的地址变换机构,是在分段系统地址变换机构的基础上形成的 。 由于被访问的段并非全在内存,所以在地址变换时,若发现所要访问的段不在内存时,必须先将所缺的段调入内存,并修改了段表之后,才能再利用段表进行地址变换 。 为此,在地址变换机制中又增加了某些功能,如缺段中断的请求及其处理等 。
请求分段中的硬件支持 -3
4。段的动态链接经过编释或汇编得到的一组目标程序需经链接程序，连接装配成一个一维的线性连续地址空间，这一过程称为 静态链接,但是这种连接装配过程既复杂又费时，还经常发生许多被连接好的摸块在作业运行过程中根本不用，而造成连接时的机时和主存空间的浪费，所以最好能采用什么时候用到那一段责连接该段的方法，这种方法称为动态连接方法。 段的动态链接是指“在一个程序运行开始时，只将主程序装配好并调入主存，其它各段的装配是在主程序段运行过程中逐步进行的，每当需要调用一个新段时，再将该段装配好，并与主程序段连接。 在分段存储管理环境中，由于逻辑地址空间是二维的，每段有自己的段名，因而实现动态连接比较容易。
（ 2） 分段共享与保护分段存储管理方式实现分段的共享和保护只须在每个进程的段表中,用相应的表项来指向共享段在内存中的起始地址 。
为了实现分段共享,应配置相应的共享段表,用来对共享段进行操作 。
在系统中,用共享段表来记录了每一个共享段的段号和段长,
内存始址,存在位等信息,并记录共享此分段的每个进程的情况 。 共享段表如下图所示 。
分段共享与保护 -1
其中：
共享进程计数 器 COUNT：记录有多少个进程需要共享该分段。
存取控制字段：说明不同的进程对该分段不同的存取权限。
段号：对于同一个共享段，不同的进程可以使用不同的段号去共享该段。
段名 段长 内存起址 状态 外存起址共享进程计数器 COUNT
状态 进程名 进程号 段号 存取控制
