操作系统第6章虚拟存储器管理

1、内蒙古大学计算机学院内蒙古大学计算机学院2002年年8月月 传统的内存管理方式要求将一个作业全部传统的内存管理方式要求将一个作业全部 装入内存才装入内存才可以运行，由此造成了以下两种情况：可以运行，由此造成了以下两种情况：l 大作业对内存的要求超出物理内存总容量，致使其无大作业对内存的要求超出物理内存总容量，致使其无法运行法运行l内存由于容量的限制，只能装入少量的作业使其运行，内存由于容量的限制，只能装入少量的作业使其运行，而其它大量作业留在外存上而其它大量作业留在外存上怎么办？怎么办？方法一：从物理上增加内存容量方法一：从物理上增加内存容量成本高成本高方法二：从逻辑上扩充内存容量方法二：从逻

2、辑上扩充内存容量由来由来:传统思路传统思路:进程必须全部进入内存进程必须全部进入内存,直至运行结束直至运行结束“一次性一次性”全全部装入内存，部装入内存，对空间浪费对空间浪费非常大非常大在进程运行的在进程运行的过程中，始终过程中，始终“驻留驻留”在内在内存。暂时不用存。暂时不用的数据无法释的数据无法释放放l局部性原理：程序在执行过程中的一个较短时期，所局部性原理：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一执行的指令地址和指令的操作数地址，分别局限于一定区域。定区域。l引入：在程序装入时，不必将其全部读入到内存，而引入：在程序装入时，不必将其全部读入到内存，

3、而只需将当前需要执行的部分页或段读入到内存，就可只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。让程序开始执行。l在程序执行过程中，如果需执行的指令或访问的数据在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操尚未在内存（称为缺页或缺段），则由处理器通知操作系统，将相应的页或段调入到内存，然后继续执行作系统，将相应的页或段调入到内存，然后继续执行程序。程序。虚拟存储器概念虚拟存储器概念:虚拟存储器是指具有请求调入功能和置换功能，虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。能从逻辑上对内存容量进行扩

4、充的一种存储系统。它不是一个实际的物理存储器它不是一个实际的物理存储器,而是一个容量可以而是一个容量可以非常大的存储器的逻辑模型非常大的存储器的逻辑模型,在该模型的支撑下在该模型的支撑下,把把程序的一部分装入内存便可以执行。程序的一部分装入内存便可以执行。 虚拟的虚拟的: 大小由大小由OS决定决定 逻辑模型逻辑模型: 概念概念,原理原理,技术解决方案技术解决方案,具体实现具体实现 部分执行部分执行实现原理实现原理l进程运行只装入部分程序和数据进程运行只装入部分程序和数据l在外存保留完整副本在外存保留完整副本l运行中动态调整进程在内存中的部署运行中动态调整进程在内存中的部署技术难点技术难点l如何

5、确定和记录当前哪些部分在内存如何确定和记录当前哪些部分在内存l执行中访问不在内存的指令和数据时如何处理执行中访问不在内存的指令和数据时如何处理l从外存中调入某页时从外存中调入某页时,内存中空间不够如何处理内存中空间不够如何处理优点优点: 利用率高，方便用户，对多道程序运行有较强的支持利用率高，方便用户，对多道程序运行有较强的支持有两种典型虚拟存储器实现方式有两种典型虚拟存储器实现方式一、分页请求系统一、分页请求系统l基本思想基本思想分页管理分页管理,装入少量页运行装入少量页运行,缺页故障后调整缺页故障后调整l页表结构进行了调整页表结构进行了调整:页号页号 + 标志位标志位 + 块号块号 + 外

6、存地址外存地址l地址转换地址转换:正常地址转换正常地址转换缺页时缺页时:缺页中断缺页中断二、请求分段系统二、请求分段系统l基本思想基本思想 装入部分段装入部分段 动态装入或调出段动态装入或调出段l段表结构进行了扩充段表结构进行了扩充:段号段号 + 主存起址主存起址 + 长度长度 + 辅存起址辅存起址+标志位标志位 +扩充位扩充位 l缺段中断机构缺段中断机构l地址变换机构地址变换机构l离散性离散性 在内存分配时采用离散分配方式在内存分配时采用离散分配方式l多次性多次性一个作业被分成多次地调入内存运行一个作业被分成多次地调入内存运行l对换性对换性允许作业在运行过程中换进、换出允许作业在运行过程中换

7、进、换出l虚拟性虚拟性从逻辑上扩充内存容量，使用户可使用的内存空间大从逻辑上扩充内存容量，使用户可使用的内存空间大于实际物理内存。于实际物理内存。l6.2.1 6.2.1 请求分页中的硬件支持请求分页中的硬件支持l6.2.2 6.2.2 页面分配页面分配l6.2.3 6.2.3 页面调入策略页面调入策略 为了实现请求分页，系统要提供一定的硬件支持。除为了实现请求分页，系统要提供一定的硬件支持。除了一定容量的内存和外存，还需要有：页表机制、缺页了一定容量的内存和外存，还需要有：页表机制、缺页中断机构和地址变换机构。中断机构和地址变换机构。一、页表机制一、页表机制用于将用户逻辑地址空间变换为内存的

8、物理地址空间。用于将用户逻辑地址空间变换为内存的物理地址空间。在页表中增加若干项，以便于标志程序或数据的状态。在页表中增加若干项，以便于标志程序或数据的状态。页表项：页表项：请求分页系统的页表结构请求分页系统的页表结构页号页号 物理块号物理块号 状态位状态位P 访问字段访问字段 存取控制存取控制 修改位修改位M 外存地址外存地址状态位（存在位）状态位（存在位）P：表示该页是否调入内存：表示该页是否调入内存访问字段访问字段A：用于记录该页在某段时间内被访问的次数：用于记录该页在某段时间内被访问的次数修改位修改位M：表示该页在调入内存后是否被修改过。：表示该页在调入内存后是否被修改过。外存地址：该

9、页在外存上的地址，通常是物理块号。外存地址：该页在外存上的地址，通常是物理块号。二、缺页中断机构二、缺页中断机构 在地址映射过程中，在页表中发现所要访问的页不在地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，根据页表中给出的外存地址，就调出缺页中断处理程序，根据页表中给出的外存地址，将该页调入内存，使进程继续运行下去。将该页调入内存，使进程继续运行下去。 如果内存中有空闲块，则分配一页，将新调入页装如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的状

10、态位及相应的入内存，并修改页表中相应页表项目的状态位及相应的内存块号。内存块号。 若此时内存中没有空闲块，则要淘汰某页，若该页若此时内存中没有空闲块，则要淘汰某页，若该页在内存期间被修改过，则要将其写回外存。在内存期间被修改过，则要将其写回外存。三、地址变换机构三、地址变换机构 请参看请参看P170 图图6-21、在地址变换时，首先检索快表，试图从中找到要访问、在地址变换时，首先检索快表，试图从中找到要访问的页。如找到，修改其访问位。对于的页。如找到，修改其访问位。对于“写写”指令，还要指令，还要设置修改位的值。设置修改位的值。 如未找到，则转如未找到，则转3。2、利用页表项中的物理块号和页内

11、地址，形成物理地址。、利用页表项中的物理块号和页内地址，形成物理地址。3、查找页表，找到页表项后，判断其状态位、查找页表，找到页表项后，判断其状态位P，查看该，查看该页是否在内存中。如果在，则将该页写入快表（若快表页是否在内存中。如果在，则将该页写入快表（若快表已满，则应该先调出某个或某些页表项）。如果不在，已满，则应该先调出某个或某些页表项）。如果不在，则产生缺页中断，由则产生缺页中断，由OS从外存将该页调入内存。从外存将该页调入内存。 在为进程分配物理块时，要解决下列的三个问题：在为进程分配物理块时，要解决下列的三个问题：1、保证进程可正常运行所需要的最少物理块数、保证进程可正常运行所需要

12、的最少物理块数2、每个进程的物理块数，是固定值还是可变值、每个进程的物理块数，是固定值还是可变值3、不同进程所分配的物理块数，是采用平均分配算法还、不同进程所分配的物理块数，是采用平均分配算法还是根据进程的大小按照比例予以分配。是根据进程的大小按照比例予以分配。一、最小物理块数一、最小物理块数进程应获得的最少物理块数与计算机的硬件机构有关，进程应获得的最少物理块数与计算机的硬件机构有关，取决于指令的格式、功能和寻址方式。取决于指令的格式、功能和寻址方式。二、页面分配和置换策略二、页面分配和置换策略在请求分页中，可采取两种分配策略，即固定和可变分在请求分页中，可采取两种分配策略，即固定和可变分配

13、策略。在进行置换时，也可采取两种策略，即全局置配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换（置换范围不同）。于是组合出三种适用换和局部置换（置换范围不同）。于是组合出三种适用的策略：的策略：1、固定分配局部置换、固定分配局部置换思路：分配固定数目的内存空间，在整个运行期间思路：分配固定数目的内存空间，在整个运行期间都不改变都不改变策略：如果缺页，则先从该进程在内存的页面中选策略：如果缺页，则先从该进程在内存的页面中选中一页，进行换出操作，然后再调入一页。中一页，进行换出操作，然后再调入一页。特点：为每个进程分配多少页是合适的值难以确定。特点：为每个进程分配多少页是合适的值难以确

14、定。此外，在对换时会浪费比较多的时间。此外，在对换时会浪费比较多的时间。2、可变分配全局置换、可变分配全局置换思路：每个进程预先分配一定数目的物理块，同时思路：每个进程预先分配一定数目的物理块，同时OS也也保持一个空闲物理块队列。保持一个空闲物理块队列。策略：当缺页时，首先将对策略：当缺页时，首先将对OS所占有的空闲块进行分配，所占有的空闲块进行分配，从而增加了各进程的物理块数。当从而增加了各进程的物理块数。当OS的空闲块全部用完，的空闲块全部用完，将引起换出操作。将引起换出操作。3、可变分配局部置换、可变分配局部置换思路：系统根据缺页率动态调整各进程占有的物理块数思路：系统根据缺页率动态调整

15、各进程占有的物理块数目，使其保持在一个比较低的缺页率状态下。目，使其保持在一个比较低的缺页率状态下。特点：使大部分进程可以达到比较近似的性能。特点：使大部分进程可以达到比较近似的性能。三、分配算法三、分配算法在采用固定分配策略时，可使用下列方法来分配：在采用固定分配策略时，可使用下列方法来分配：1、平均分配算法：将系统中所有可供分配的物理块，平、平均分配算法：将系统中所有可供分配的物理块，平均分配给各个进程。均分配给各个进程。2、按比例分配算法：按照进程的大小比例分配物理块。、按比例分配算法：按照进程的大小比例分配物理块。3、考虑优先权的分配算法：为了对于紧迫的作业，能够、考虑优先权的分配算法

16、：为了对于紧迫的作业，能够尽快完成。可以将内存的物理块尽快完成。可以将内存的物理块 分成两部分，一部分按分成两部分，一部分按照比例分配给各进程，另一部分根据进程优先级，适当照比例分配给各进程，另一部分根据进程优先级，适当增加其相应的份额，分配给各进程。增加其相应的份额，分配给各进程。一、何时调入页面一、何时调入页面l提前取页：预先装入主存一页或几页（提前页）。提前取页：预先装入主存一页或几页（提前页）。l请求取页：当用到某页而不在主存时即缺页时取页。请求取页：当用到某页而不在主存时即缺页时取页。二、从何处调入页面二、从何处调入页面外存有两个部分：文件区和对换区。对换区外存有两个部分：文件区和对

17、换区。对换区I/O操作速度操作速度比文件区相对快一些，因此一般应当尽量使用对换区来比文件区相对快一些，因此一般应当尽量使用对换区来调入页面。对于不同情况，采用不同的策略：调入页面。对于不同情况，采用不同的策略：1、系统有足够的对换空间、系统有足够的对换空间2、系统对换空间不足、系统对换空间不足3、UNIX的调入方式的调入方式三、页面调入过程三、页面调入过程1、进程需要的页面不在内存，引起缺页中断、进程需要的页面不在内存，引起缺页中断2、中断处理程序保留现场环境，转入缺页中断处理程序、中断处理程序保留现场环境，转入缺页中断处理程序3、中断处理程序查找页表，得到对应的外存物理块号。、中断处理程序查

18、找页表，得到对应的外存物理块号。如果内存有空闲，则启动磁盘操作，将所缺的页面读入，如果内存有空闲，则启动磁盘操作，将所缺的页面读入，并修改页表。否则，到并修改页表。否则，到4。4、执行置换算法，选出要换出的页面，如果该页修改过，、执行置换算法，选出要换出的页面，如果该页修改过，应将其写入磁盘，然后将所缺页调入内存，修改相应表应将其写入磁盘，然后将所缺页调入内存，修改相应表项，将其存在位置为项，将其存在位置为1，并放入快表，并放入快表 。5、利用修改后的页表，形成物理地址，访问内存数据。、利用修改后的页表，形成物理地址，访问内存数据。可提供多个大容量的虚拟存储器：作业的地址空间可提供多个大容量的

19、虚拟存储器：作业的地址空间不再受主存大小的限制。不再受主存大小的限制。主存利用率大大提高：作业中不常用的页不会长期主存利用率大大提高：作业中不常用的页不会长期驻留在主存，当前运行用不到的信息也不必调入主驻留在主存，当前运行用不到的信息也不必调入主存。存。能实现多道作业同时运行。能实现多道作业同时运行。方便用户：大作业也无须考虑覆盖问题。方便用户：大作业也无须考虑覆盖问题。缺页中断处理增加系统开销缺页中断处理增加系统开销页面的调入调出增加页面的调入调出增加I/O系统的负担系统的负担此外页表等占用空间且需要管理，存在页内零此外页表等占用空间且需要管理，存在页内零头头.l功能：需要调入页面时，选择内

20、存中哪个物理页面被功能：需要调入页面时，选择内存中哪个物理页面被置换。置换。l目标：把未来不再使用的或短期内较少使用的页面调目标：把未来不再使用的或短期内较少使用的页面调出，通常只能在局部性原理指导下依据过去的统计数出，通常只能在局部性原理指导下依据过去的统计数据进行预测；据进行预测；l页面锁定页面锁定(frame locking)：用于描述必须常驻内存的操：用于描述必须常驻内存的操作系统的关键部分或时间关键作系统的关键部分或时间关键(time-critical)的应用进的应用进程。实现方法为在页表中加上锁定标志位程。实现方法为在页表中加上锁定标志位(lock bit)。几种页面置换算法几种页

21、面置换算法:l最佳算法最佳算法(OPT, optimal)*l最近最久未使用算法最近最久未使用算法(LRU, Least Recently Used)*l先进先出算法先进先出算法(FIFO)*l轮转算法轮转算法(clock)l最不常用算法最不常用算法(LFU, Least Frequently Used)*l页面缓冲算法页面缓冲算法(page buffering) 选择选择“未来不再使用的未来不再使用的”或或“在离当前最远位置上出现在离当前最远位置上出现的的”页面被置换。这是一种理想情况，是实际执行中无法预页面被置换。这是一种理想情况，是实际执行中无法预知的，因而不能实现。可用作性能评价的依据

22、。知的，因而不能实现。可用作性能评价的依据。例：某进程分配页数为例：某进程分配页数为3 3，其运行期间页面访问序列：，其运行期间页面访问序列：A,B,C,D,A,B,E,A,B,C,D,EA,B,C,D,A,B,E,A,B,C,D,E，分析其按照，分析其按照OPTOPT算法进行页面算法进行页面置换时的缺页情况。置换时的缺页情况。最佳置换算法最佳置换算法OPT范例范例页页面面访访问问序序列列 A B C D A B E A B C D E A A A A B A A B E E E E B B B A B B E B C D D C D D D E A A B C C + + + + + + +

23、 缺缺页页次次数数=7； 缺缺页页率率=7/12=58% 选择装入最早的页面被置换。可以通过链表来表示各选择装入最早的页面被置换。可以通过链表来表示各页的建立时间先后。性能较差。较早调入的页往往是经常被页的建立时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在访问的页，这些页在FIFO算法下被反复调入和调出。并且算法下被反复调入和调出。并且有抖动现象。有抖动现象。请参看下页的两个例子。（进程的页数分别是请参看下页的两个例子。（进程的页数分别是3和和4）页面访问序列页面访问序列 A B C D A B E A B C D E A B C D A B E E E C D D A B C

24、 D A B B B E C C A B C D A A A B E E + + + + + + + + + 缺页次数缺页次数=9； 缺页率缺页率 f=9/12=75% 页面访问序列页面访问序列 A B C D A B E A B C D E A B C D D D E A B C D E A B C C C D E A B C D A B B B C D E A B C A A A B C D E A B + + + + + + + + + + 缺页次数缺页次数=10； 缺页率缺页率 f=10/12=83% l每个页面设立移位寄存器：被访问时左边最高位置每个页面设立移位寄存器：被访问时左边最

25、高位置1，定，定期右移并且最高位补期右移并且最高位补0，于是寄存器数值最小的是最久未，于是寄存器数值最小的是最久未使用页面。使用页面。l一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是一个特殊的栈：把被访问的页面移到栈顶，于是栈底的是最久未使用页面。最久未使用页面。 选择内存中最久未使用的页面被置换。这是局部性原理的选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。但由于需要记录页面使用时间合理近似，性能接近最佳算法。但由于需要记录页面使用时间的先后关系，硬件开销太大。硬件机构可设计如下：的先后关系，硬件开销太大。硬件机构可设计如下：页页面面访访问问序序列列 A

26、B C D A B E A B C D E A B C D A B E A B C D E A B C D A B E A B C D A B C D A B E A B C + + + + + + + + + + 缺缺页页次次数数=10； 缺缺页页率率=10/12=83% l内存中所有页面通过链接指针形成一个循环队列内存中所有页面通过链接指针形成一个循环队列l每页有一个使用访问位每页有一个使用访问位(use bit)，若该页被访问则置，若该页被访问则置use bit=1。l置换时采用一个指针，从当前指针位置开始按地址先后检置换时采用一个指针，从当前指针位置开始按地址先后检查各页，寻找查各页，

27、寻找use bit=0的页面作为被置换页。的页面作为被置换页。l指针经过的指针经过的user bit=1的页都修改的页都修改user bit=0，最后指针停留，最后指针停留在被置换页的下一个页。在被置换页的下一个页。也称最近未使用算法也称最近未使用算法(NRU, Not Recently Used)，它是，它是LRU(最最近最久未使用算法近最久未使用算法)和和FIFO的折衷。的折衷。 由于由于Clock算法不考虑换出页面时，页面是否修改过算法不考虑换出页面时，页面是否修改过的问题。这样在换出的页面如果被修改过的话，则必须的问题。这样在换出的页面如果被修改过的话，则必须做拷回磁盘处理，开销比较大

28、。于是，改进型的做拷回磁盘处理，开销比较大。于是，改进型的Colck算算法为每个页又增加了一个修改位。法为每个页又增加了一个修改位。 选择页面时，尽量选择既未使用又没有修改的页面。选择页面时，尽量选择既未使用又没有修改的页面。页面：页面： （访问位（访问位A，修改位，修改位M）有四种不同情形：）有四种不同情形：1类类(A=0,M=0） 既未访问，又没有修改，最佳淘汰页既未访问，又没有修改，最佳淘汰页2类类(A=0,M=1） 未访问，但是有修改，效率低的淘汰页未访问，但是有修改，效率低的淘汰页3类类(A=1,M=0） 被访问，但没有修改被访问，但没有修改4类类(A=1,M=1） 既被访问，又有修

29、改既被访问，又有修改算法：算法：（1）指针从当前位置开始，开始第一轮扫描循环队列，）指针从当前位置开始，开始第一轮扫描循环队列，寻找未使用且没有修改过的页面（第寻找未使用且没有修改过的页面（第1类页面），找到类页面），找到则可换出。则可换出。（2）如果找不找，则开始第二轮扫描，寻找未使用但修）如果找不找，则开始第二轮扫描，寻找未使用但修改过的页面（第改过的页面（第2类页面），并且每经过一个页面时，类页面），并且每经过一个页面时，将其访问位将其访问位A设置为设置为0。如果找到一个第。如果找到一个第2类页面，则类页面，则可换出。可换出。（3） 如果仍旧未找到合适的换出页面，则此时指针回到如果仍旧未

30、找到合适的换出页面，则此时指针回到初始位置，且所有页面其访问位初始位置，且所有页面其访问位A为为0。 再转回（再转回（1）继续工作。继续工作。l目的：选择到当前时间为止被访问次数最少的页面被目的：选择到当前时间为止被访问次数最少的页面被置换；置换；l实现方法实现方法1：每个页面设立移位寄存器：被访问时左边：每个页面设立移位寄存器：被访问时左边最高位置最高位置1，定期右移并且最高位补，定期右移并且最高位补0，这样，在最近，这样，在最近一段时间内时用最少的页面将是一段时间内时用最少的页面将是RRi i 最小的页。最小的页。l实现方法实现方法2 2：每页设置访问计数器，每当页面被访问时，每页设置访问

31、计数器，每当页面被访问时，该页面的访问计数器加该页面的访问计数器加1；发生缺页中断时，淘汰计数；发生缺页中断时，淘汰计数值最小的页面，并将所有计数清零；值最小的页面，并将所有计数清零；l被置换页面的选择和处理：由操作系统中专门的页面被置换页面的选择和处理：由操作系统中专门的页面置换进程，用置换进程，用FIFO算法选择被置换页，把被置换的页算法选择被置换页，把被置换的页面放入两个链表（空闲页面链表和已修改页面链表）面放入两个链表（空闲页面链表和已修改页面链表）之一。之一。如果页面未被修改，就将其归入到空闲页面链表的如果页面未被修改，就将其归入到空闲页面链表的末尾末尾否则将其归入到已修改页面链表。

32、否则将其归入到已修改页面链表。它是对它是对FIFO算法的发展，通过被置换页面的缓冲，有机会找算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面；回刚被置换的页面；6.4.1 缺页率对有效访问时间的影响6.4.2 工作集6.4.3 抖动产生的原因和预防方法 缺页率的影响因素缺页率的影响因素分配给进程的页面数目：分配给进程的页面数目：l数目越多数目越多缺页率越低。缺页率越低。l页面数目的下限，应该是一条指令及其操作数可能涉页面数目的下限，应该是一条指令及其操作数可能涉及的页面数目的上限，以保证每条指令都能被执行。及的页面数目的上限，以保证每条指令都能被执行。 缺页率表示缺页率表示“缺页次数

33、缺页次数 / 内存访问次数内存访问次数”(比率比率)或或“缺缺页的平均时间间隔的倒数页的平均时间间隔的倒数”；假定缺页概率为假定缺页概率为P，则有效访问时间可以表示为：，则有效访问时间可以表示为： 有效访问时间有效访问时间=(1-P) * ma + P * 缺页中断时间缺页中断时间其中，其中，ma代表访问存储器的时间代表访问存储器的时间(10ns数百数百ns)。缺页中断时间由三部分组成：缺页中断时间由三部分组成：1、缺页中断服务时间、缺页中断服务时间 2、将缺页读入的时间、将缺页读入的时间:24ms3、进程重新执行时间、进程重新执行时间有效访问时间有效访问时间=（1-p)*0.1+p*2500

34、0结论：若使有效访问时间延长不超过结论：若使有效访问时间延长不超过10%，缺页中断就要，缺页中断就要小于小于0.0000004。减少缺页中断；提高。减少缺页中断；提高I/O速度。速度。25ms 实践证明实践证明, ,一个进程在一段时间内访问到的页数是比一个进程在一段时间内访问到的页数是比较确定的较确定的, ,系统只需按这个页数分配相应的页面数即可。系统只需按这个页数分配相应的页面数即可。超过这个页面数，进程的缺页次数不会减少多少，低于超过这个页面数，进程的缺页次数不会减少多少，低于这个数却会使进程的缺页次数急剧增加，称这些页面为这个数却会使进程的缺页次数急剧增加，称这些页面为工作集工作集(wo

35、rking set ) (working set ) 。 基本思想：根据程序的局部性原理，一般情况下，基本思想：根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页面，这些页面称进程在一段时间内总是集中访问一些页面，这些页面称为活跃页面，如果分配给一个进程的物理页面数太少了，为活跃页面，如果分配给一个进程的物理页面数太少了，使该进程所需的活跃页面不能全部装入内存，则进程在使该进程所需的活跃页面不能全部装入内存，则进程在运行过程中将频繁发生中断。运行过程中将频繁发生中断。如果能为进程提供与活跃页面数相等的物理页面数，如果能为进程提供与活跃页面数相等的物理页面数，则可减少缺页中断次

36、数。则可减少缺页中断次数。对于给定的访问序列选取定长的区间，称为工作集窗对于给定的访问序列选取定长的区间，称为工作集窗口，落在工作集窗口中的页面集合称为工作集。口，落在工作集窗口中的页面集合称为工作集。内容取决于页的三个因素内容取决于页的三个因素 a a 访页序列特性访页序列特性 b b 时刻时刻TiTi c c 窗口长度窗口长度( () )例： 26157775162341234443434441327 | |t1 | |t2 ws(t1)=1,2,5,6,7 ws(t2)=3,41、抖动产生的原因、抖动产生的原因 抖动现象抖动现象内存中引入过多的进程，造成多道程序度过高内存中引入过多的进程

37、，造成多道程序度过高每个进程并发执行时对内存进行访问，经常出现缺每个进程并发执行时对内存进行访问，经常出现缺页情况页情况启动置换策略将某个（某些）页面换出，调入新页启动置换策略将某个（某些）页面换出，调入新页继续访问时发现，又用到刚才调出的页面，又引起继续访问时发现，又用到刚才调出的页面，又引起缺页中断缺页中断抖动的产生：经常将调出的页再调入抖动的产生：经常将调出的页再调入2、抖动的预防、抖动的预防l采取局部置换策略采取局部置换策略 仅允许进程在自身范围内进行置换，不影响其他进程仅允许进程在自身范围内进行置换，不影响其他进程l在在CPU调度程序中引入工作集算法调度程序中引入工作集算法 调入新作

38、业时，应该检查每个进程在内存中的驻留集调入新作业时，应该检查每个进程在内存中的驻留集是否足够大是否足够大lL=S准则：产生缺页的平均时间准则：产生缺页的平均时间L=系统处理进程缺页系统处理进程缺页的平均时间的平均时间Sl挂起若干进程挂起若干进程 使某些低优先级的进程进程挂起，从而腾出内存空间使某些低优先级的进程进程挂起，从而腾出内存空间 请求分页系统建立的虚拟存储器，是以页面为单位进请求分页系统建立的虚拟存储器，是以页面为单位进行换入、换出操作的。行换入、换出操作的。 在请求分段系统中实现的虚拟存储器，以分段为单位在请求分段系统中实现的虚拟存储器，以分段为单位进行换入和换出。进行换入和换出。

39、程序在运行之前，只需要装入必要的若干个分段即可程序在运行之前，只需要装入必要的若干个分段即可运行。当访问的分段不在内存时，可由运行。当访问的分段不在内存时，可由OSOS将所缺少的段调将所缺少的段调入内存。入内存。1、段表机制、段表机制段号段号 段长段长 段的段的 存储存储 访访 问问 修修 改改 存在存在 增补位增补位 外存外存l需要在进程段表中添加若干项：需要在进程段表中添加若干项：存取方式：标记本段存取属性。如读存取方式：标记本段存取属性。如读R，写，写W，执行，执行X访问字段访问字段A：记录本段使用的频繁程度：记录本段使用的频繁程度修改位：是否在调入内存后做过修改修改位：是否在调入内存后

40、做过修改存在位：本段是否装入内存存在位：本段是否装入内存增补位增补位 ：该段是否动态增长过，在请求页式中没有该位：该段是否动态增长过，在请求页式中没有该位外存地址外存地址 基址基址 方式方式 字段字段A 字段字段M 位位p 起址起址2、缺段中断机构、缺段中断机构 要有专门的缺段中断处理程序。特点：要有专门的缺段中断处理程序。特点：指令和操作数必定不会跨越在段边界上。指令和操作数必定不会跨越在段边界上。由于段的长度是不固定的，处理比缺页系统复杂。由于段的长度是不固定的，处理比缺页系统复杂。调入一个段可能要淘汰几个内存中的段。调入一个段可能要淘汰几个内存中的段。中断处理过程请参看中断处理过程请参看

41、P185 图图6-123 3、地址变换、地址变换请求分段系统的地址变换机构，是在分段系统的请求分段系统的地址变换机构，是在分段系统的地址变换机构基础上形成的。地址变换机构基础上形成的。由于分段可能不在内存，因此会引起缺段中断。由于分段可能不在内存，因此会引起缺段中断。先将需要的段调入内存，修改段表，然后再利用段表进先将需要的段调入内存，修改段表，然后再利用段表进行地址变换。行地址变换。 地址变换过程请参看地址变换过程请参看P186 P186 图图6-136-13在多道程序系统中，尤其在分时系统中，数据共享是在多道程序系统中，尤其在分时系统中，数据共享是很重要的，在分段系统中，各共享进程应能访问

42、被共享很重要的，在分段系统中，各共享进程应能访问被共享的段，所以共享的方法是使这些共享用户的逻辑空间中的段，所以共享的方法是使这些共享用户的逻辑空间中的段指向相同的段号，在共享中必须小心处理的一个问的段指向相同的段号，在共享中必须小心处理的一个问题是共享段的保护问题。题是共享段的保护问题。一、共享段表一、共享段表为了实现共享，可在系统中配置一张段表，所有的共为了实现共享，可在系统中配置一张段表，所有的共享段都在共享段表中占有一表项。表项中记录了共享段享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录有共的段号、段长、内存始址、存在位等信息，并记录有共享

43、此分段的每个进程的情况。享此分段的每个进程的情况。共享段共享段作业作业1 1的段表的段表段名段名 段长段长 内存始址内存始址 状态状态共享本段进程数共享本段进程数 外存始址外存始址进程名进程名 进程号进程号 段号段号 存取控制存取控制进程名进程名 进程号进程号 段号段号 存取控制存取控制共享段表示意图（图中部分共享段表示意图（图中部分信息省略）信息省略）1、共享进程计数、共享进程计数记录了多少个进程在共享该记录了多少个进程在共享该分段。分段。2、存取控制字段、存取控制字段对于共享段的不同进程，应对于共享段的不同进程，应该赋予不同的存取权限。该赋予不同的存取权限。3、段号、段号不同的进程可以使用

44、不同的不同的进程可以使用不同的段号来访问相同的共享段。段号来访问相同的共享段。作业作业2 2的段表的段表二、共享段的分配和回收二、共享段的分配和回收l分配分配第一个请求的进程，由系统分配一物理块，调入共第一个请求的进程，由系统分配一物理块，调入共享段，设置相关表项信息，并置享段，设置相关表项信息，并置count=1以后的进程，在自己段表中增加一项，添入共享段以后的进程，在自己段表中增加一项，添入共享段信息；在共享段表项中做信息；在共享段表项中做count = count +1，填写进，填写进程相关信息程相关信息l回收回收做做count = count 1 如果如果count = 0 ,则将该共

45、享段回收则将该共享段回收 三、分段保护三、分段保护l越界检查越界检查 在进行存储访问时，要将逻辑地址的段号与段表长在进行存储访问时，要将逻辑地址的段号与段表长度进行比较，如果超出则发生越界中断信号；其次，将度进行比较，如果超出则发生越界中断信号；其次，将段内地址与段表中该段的长度进行比较，如果有效才进段内地址与段表中该段的长度进行比较，如果有效才进行转换，否则产生越界中断信号行转换，否则产生越界中断信号.:用于规定对该段的访问权限。通常的访用于规定对该段的访问权限。通常的访问方式有：问方式有：:允许用户对该段允许用户对该段/页内任何信息或其副本进行读页内任何信息或其副本进行读操作。操作。:允许

46、用户修改该段允许用户修改该段/页内任何信息直至撤消整个页内任何信息直至撤消整个段段/页。页。:用户可以执行该段用户可以执行该段/页程序，数据段页程序，数据段/页除外。页除外。:用户可在段用户可在段/页的末尾添加信息，但不允许修页的末尾添加信息，但不允许修改已存在于段改已存在于段/页中的信息。页中的信息。l环保护检查环保护检查是一种功能较完善的保护机制。是一种功能较完善的保护机制。思想：将所有的程序分成不同的级别，分别放置在思想：将所有的程序分成不同的级别，分别放置在不同的环上。内环（编号小，在内侧）的程序具有不同的环上。内环（编号小，在内侧）的程序具有高优先权，外环的程序优先权低。高优先权，外环的程序优先权低。操作系统核心安排在操作系统核心安排在0环内；重要程序和操作系统服环内；重要程序和操作系统服务安排在中间环；一般应用程序安排在外环。务安排在中间环；一般应用程序安排在外环。一个程序可以直接访问在相同环或低优先级环（比一个程序可以直接访问在相同环或低优先级环（比自身相对靠外的环）上