《计算机操作系统第5章要点word版本.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统第5章要点word版本.ppt（56页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 1第五章 虚 拟 存 储 器计算机操作系统第5章要点2 2第五章 虚 拟 存 储 器5.1.1 常规存储管理方式的特征和局部性原理1.常规存储器管理方式的特征我们把前一章中所介绍的各种存储器管理方式统称为传统存储器管理方式，它们全都具有如下两个共同的特征：(1)一次性(2)驻留性 3 3第五章 虚 拟 存 储 器2.局部性原理程序运行时存在的局部性现象，很早就已被人发现，但直到1968年，P.Denning才真正指出：程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。局限性又表现在下述两个方面：(1)时间局限性。程序
2、中的某条指令被执行，不久后会再次执行；某个数据被访问，不久后将再次被访问。产生时间局限性的典型原因是在程序中存在着大量的循环操作。(2)空间局限性。程序访问了某个存储单元，不久后，其附近的存储单元也将被访问。4 4第五章 虚 拟 存 储 器3.虚拟存储器的基本工作情况 基于局部性原理可知，应用程序在运行之前没有必要将应用程序在运行之前没有必要将之全部装入内存之全部装入内存，而仅须将那些当前要运行的少数页面或段当前要运行的少数页面或段先装入内存便可运行先装入内存便可运行，其余部分暂留在盘上。5 5第五章 虚 拟 存 储 器5.1.2 虚拟存储器的定义和特征1.虚拟存储器的定义当用户看到自己的程序
3、能在系统中正常运行时，他会认为，该系统所具有的内存容量一定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。虚拟存储器虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。或是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。6 6第五章 虚 拟 存 储 器2.虚拟存储器的特征与传统的存储器管理方式比较，虚拟存储器具有以下三个重要特征：(1)多次性多次性：是指一个作业被分成多次来调入内存，即作业运行时不需将其全部装入内存，只需将当前要运行的那部分程序和数据装入
4、，以后运行到某些部分时再将其调入。(2)对换性对换性：是指允许作业中的程序和数据，在作业运行过程中换进、换出。(3)虚拟性虚拟性：是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性以多次性和对换性为基础，多次性和对换性以离散分配为基础。7 7第五章 虚 拟 存 储 器5.1.3 虚拟存储器的实现方法1.分页请求系统：这是在分页系统的基础上增加请求调页和页面置换功能形成的页式虚拟存储系统。允许只装入若干页(非全部）的用户程序和数据，便可启动运行。以后利用请求调页和页面置换功能完成作业的运行。置换时以页为单位。对此，系统须提供必要的硬件支持和相应的软件。1)硬件支持主要
5、的硬件支持有：(1)请求分页的页表机制。(2)缺页中断机构。(3)地址变换机构。2)实现请求分页的软件：实现请求调页的软件和实现页面置换的软件。8 8第五章 虚 拟 存 储 器2.请求分段系统：这是在分段系统的基础上增加请求调段和分段置换功能后而形成的段式虚拟存储系统。1)硬件支持主要的硬件支持有：(1)请求分段的段表机制。(2)缺页中断机构。(3)地址变换机构。2)软件支持：实现请求调段的软件和实现段置换的软件。目前也有建立在段页式系统基础上的段页式虚拟存储系统。9 9第五章 虚 拟 存 储 器5.2 请求分页存储管理方式5.2.1 请求分页中的硬件支持为了实现请求分页，系统必须提供一定的硬
6、件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。10 10第五章 虚 拟 存 储 器1.请求页表机制在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空将用户地址空间中的逻辑地址映射为内存空间中的物理地址间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项：页号页号 物理块号物理块号 状态位状态位P P 访问字段访问字段A A 修改位修改位M M 外存地址外存地址又称存在位，用于指示该页是否已调入内存，供程序访问时参考。用于记录
7、本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。指示该页在调入内存后是否被修改过。若未被修改，在置换该页时就不需将该页回写到外存，否则，就要回写到外存。用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。11 11第五章 虚 拟 存 储 器2.缺页中断机构每当所要访问的页面不在内存时，便要产生一次缺页中断，请求OS将所缺之页调入内存。缺页中断虽要经历与一般中断相同的几个步骤，但它是一种特殊的中断，与一般中断的区别主要是：（1）在指令执行期间产生和处理中断信号在指令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后去检查是否有中断请
8、求到达。有则响应，无则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令和数据不在内存时产生和处理的。（2）一条指令在执行期间，可能产生多次缺页中断一条指令在执行期间，可能产生多次缺页中断。这时硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处，继续执行。12 12第五章 虚 拟 存 储 器B:A:Copy ATo B 例如：执行COPY A TO B这条指令时，可能要产生6次缺页中断654321页面13 13第五章 虚 拟 存 储 器3.地址变换机构请求分页系统中的地址变换机构是在分页系统地址变换机构的基础上，为实现虚拟存储器，再增加了某些功能所形
9、成的，如产生和处理缺页中断，以及从内存中换出一页的功能等等。图5-2示出了请求分页系统中的地址变换过程。14 14第五章 虚 拟 存 储 器图5-2请求分页中的地址变换过程15 15第五章 虚 拟 存 储 器5.2.2 请求分页中的内存分配在为进程分配物理块时，将涉及到以下三个问题：1.最小物理块数的确定一个显而易见的事实是，随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，从而会降低进程的执行速度。为使进程能有效地工作，应为它分配一定数目的物理块，但这并不是最小物理块数的概念。最小物理块最小物理块数数是指能保证进程正常运行所需的最少物理块数。若系统分配给某进程的物理块数小于此
10、值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。16 16第五章 虚 拟 存 储 器2.内存分配策略在请求分页系统中，可采取两种内存分配策略，即固定和可变分配策略。在进行置换时，也可采取两种策略，即全局置换和局部置换。于是可组合出以下三种适用的策略。1)固定分配局部置换(Fixed Allocation，Local Replacement)：为每个进程分配一固定页数的内存空间，在整个运行期间保持不变。置换时，只能从进程在内存的n个页面中选出一页换出，然后再调入一页，保证其内存空间不变。2)可变分配全局置换(Variable Allocat
11、ion，Global Replacement)：先为每个进程分配一定数目的物理块，OS本身也保持一个空闲物理块队列。任一进程发现缺页时，由系统从空闲物理块队列中取出一块分配给该进程，并将欲调入的缺页装入其中。这样，凡产生缺页的进程，都将获得新物理块。当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，选择页的可能是系统中任一进程 的页。3)可变分配局部置换(Variable Allocation，Local Replacement)：为每个进程分配一定数目的内存空间，当某进程发生缺页时，只允许从该进程在内存中的页面中选出一页换出。若某进程在运行中频繁地发生缺页中断，则系统需再为该进
12、程分配若干附加的物理块，直至其缺页率降低到适当程度为止；反之，若某进程的缺页率特别低，则可适当地减少分配给它的物理块数，前提是其缺页率没有明显增加。17 17第五章 虚 拟 存 储 器3.物理块分配算法在采用固定分配策略时，如何将系统中可供分配的所有物理块分配给各个进程，可采用下述几种算法：(1)平均分配算法，即将系统中所有可供分配的物理块平均分配给各个进程。(2)按比例分配算法，即根据进程的大小按比例分配物理块。(3)考虑优先权的分配算法。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额
13、。18 18第五章 虚 拟 存 储 器5.2.3 页面调入策略为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是：(1)系统应在何时调入所需页面；(2)系统应从何处调入这些页面；(3)是如何进行调入的。19 19第五章 虚 拟 存 储 器1.何时调入页面：可采取预调页策略或请求调页策略来确定进程运行时所缺页面调入内存的时机。(1)预调页策略预调页策略：以预测为基础，将预计在不久之后便会被访问的程序或数据所在之页，预先调入内存。目前，预调页的成功率约为50%。(2)请求调页策略请求调页策略：进程在运行中提出调页请求后，系统将其所需的页面调入内存。由该策略所确
14、定调入的页，一定会被访问，但调页时的系统开销较大，因每次请求时只调入一页。2020第五章 虚 拟 存 储 器2.从何处调入页面：请求分页系统中，外存分为用于存放文件的文件区和用于存放对换页面的对换区两部分。缺页请求时，系统调页的方法有三种：(1)系统拥有足够的对换区空间系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度。(2)系统缺少足够的对换区空间系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入，以后再调入时，仍从文件区调入。对于可能被修改的部分，将他们换出时，便调到对换区，以后需要时再从对换区调入。(3)UNIX方式方式。凡是未运行过的页面，都
15、从文件区调入。曾经运行过而又被换出的页面，放在对换区，下次调入时，从对换区调入。由于允许页面共享，故某进程所请求的页面可能已被其他进程调入，此时不需从对换区调入。21 21第五章 虚 拟 存 储 器3.页面调入过程(1)程序要访问的页面不在内存，向CPU发出缺页中断。转入缺页中断处理程序。(2)处理程序查找页表得到缺页所在外存的物理块号。若此时内存未满内存未满，则从外存将缺页调入内存，并修改页表。若内存已满内存已满，则按置换算法从内存选出一页准备换出，若欲欲换出页未修改过，可不必写入外存，否则要重写换出页未修改过，可不必写入外存，否则要重写。然后将缺页调入内存，并修改页表中相应的页表项，置状态
16、位为1，再将此表项写入快表中。(3)缺页调入内存后，利用修改后的页表，去形成所要访问的数据的物理地址，再去访问内存数据。2222第五章 虚 拟 存 储 器4.缺页率假设一个进程的逻辑空间为n页，系统为其分配的内存物理块数为m(mn)。如果在进程的运行过程中，访问页面成功(即所访问页面在内存中)的次数为S，访问页面失败(即所访问页面不在内存中，需要从外存调入)的次数为F，则该进程总的页面访问次数为A=S+F，那么该进程在其运行过程中的缺页率即为 缺页率的影响因素:1)页面大小；2)进程分配物理块的数目；3)页面置换算法；4)程序固有特性。2323第五章 虚 拟 存 储 器事实上，在缺页中断处理时
17、，当由于空间不足，需要置换部分页面到外存时，选择被置换页面还需要考虑到置换的代价，如页面是否被修改过。没有修改过的页面可以直接放没有修改过的页面可以直接放弃，而修改过的页面则必须进行保存，所以处理这两种情况弃，而修改过的页面则必须进行保存，所以处理这两种情况时的时间也是不同的时的时间也是不同的。假设被置换的页面被修改的概率是，其缺页中断处理时间为ta，被置换页面没有被修改的缺页中断时间为tb，那么，缺页中断处理时间的计算公式为t=ta+(1-)tb2424第五章 虚 拟 存 储 器5.3 页面置换算法通常，把选择换出页面的算法称为页面置换算法选择换出页面的算法称为页面置换算法(Page-Rep
18、lacement Algorithms)。置换算法的好坏将直接影响系统的性能，不适当的算法可能导致进程发生“抖动”(Thrash-ing)。即刚被换出的页很快又被访问，需重新调入。为此，又需再选一页调出；而此刚被换出的页，很快又被访问，因而又需将它调入。如此频繁地更换页面，以至一个进程在运行中，将把大部分时间花在完成页面置换的工作上，我们称该进程发生了“抖动抖动”。一个好的算法，应具有较低的页面更换频率。理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再访问的页面调出。2525第五章 虚 拟 存 储 器5.3.1 最佳置换算法和先进先出置换算法1.最佳(Optimal)置换
19、算法最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。25 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201203243203201701编号页面的引用顺序（页面走向）：1 2 3 4 5 6 7 8 9 10 11121314 15161718 1920页
20、面的编号系统采用固定分配局部置换策略，为某进程分配的三个物理块（页框）进程运行时先后将7，0，1三个页面装入内存，此时内存已满，若进程要访问新的页面，则需淘汰三者之一进程访问页面2，此时产生缺页中断，将页面2调入内存，但调入之前须将内存中的某页换出。OS根据最佳置换算法，将页面7淘汰，因页面0将在第5次被访问，页面1在第14次被访问，而页面7要在第18次时被访问才需调入。进程访问访问页面3，引起页面1被淘汰，因在内存中的1，2，0三个页面中，页面1将是以后最晚才被访问的，要在第14次才被访问。采用最佳置换算法，只发生6次页面置换进程在运行过程中共发生9次缺页中断缺页中断和页面置换次数是分别是多
21、少？2626第五章 虚 拟 存 储 器2.先进先出(FIFO)页面置换算法FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201231430023013702编号页面
22、的引用顺序（页面走向）：1 2 3 4 5 6 7 8 9 10 11121314 15161718 1920进程运行时已先后将7,0,1三个页面装入内存，此时内存已满。进程访问页面2，此时将产生缺页中断，将页面2调入内存，但调入之前会将7,0,1三个页面中的一个进行置换。OS根据FIFO置换算法，将页面7淘汰，因7,0,1三个页面中，页面7最先进入内存，其在内存中的驻留时间最长。230420423012712701进程访问访问页面3，引起页面0被淘汰，因在内存中的2，0，1三个页面中，页面0是最先进入内存，即在内存中驻留时间最长。总共发生15次缺页中断，12次页面置换。2727第五章 虚 拟
23、 存 储 器5.3.2 最近最久未使用和最少使用置换算法1.LRU(Least Recently Used)置换算法的描述 FIFO依据的条件是页面进入内存的时间。LRU依据的条件是页面调入内存后的使用情况。LRU置换算法选择最近最久未使用的页面予以淘汰。其作法是赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，需淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面予以淘汰。仍以前面的页面引用串作例。7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1770701201这时淘汰页面7，换入页面2。因页面7是最先进入内存且被使用，在这
24、之后至今未使用，是最近最久未使用的页面进程访问页面2，但它不在内存，系统需将它调入。203403402432032132102107进程访问页面3，但它不在内存，系统需将它调入。进程访问页面0，但其不在内存。淘汰页面4，换入页面0。这时页面1是最近最久未使用的页面，淘汰页面1，换入页面3。共发生12次缺页中断，9次页面置换2828第五章 虚 拟 存 储 器2.LRU置换算法的硬件支持1)寄存器为了记录某进程在内存中各页的使用情况，须为每个在内存中的页面配置一个移位寄存器，可表示为R=Rn-1Rn-2Rn-3 R2R1R0当进程访问某物理块时，要将相应寄存器的Rn-1位位置成1。此时，定时信号将
25、每隔一定时间(例如100 ms)将寄存器右移一位。如果我们把n位寄存器的数看作是一个整数，那么，具有最小数值的寄存器所对应的页面，就是最近最久未使用的页面。移位寄存器的最高位2929第五章 虚 拟 存 储 器图5-6 某进程具有8个页面时的LRU访问情况3030第五章 虚 拟 存 储 器2)栈可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程，它分有五个物理块，所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，631 31
26、第五章 虚 拟 存 储 器图5-7用栈保存当前使用页面时栈的变化情况3232第五章 虚 拟 存 储 器3.最少使用(Least Frequently Used，LFU)置换算法在采用LFU算法时，应为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。该置换算法选择在最近时期使用最少的页面作为淘汰页。采用该算法时，应为内存中的每个页面设置一移位寄存器，用来记录页面被访问的次数。每次访问某页面时，便对该页面移位寄存器的最高位置1，再每隔一定时间寄存器右移一次。这样在最近一段时间内使用最少的页面将是寄存器数值最小的页面。3333第五章 虚 拟 存 储 器5.3.3 Clock置换算法
27、1.简单的Clock置换算法利用该算法时，须为每页设置一访问位，再将内存中的所有页面都通过链接指针链成一循环队列。当某页被访问时，其访问位置1。Clock算法在选择一页淘汰时，只须检查其访算法在选择一页淘汰时，只须检查其访问位，若为问位，若为0，就选择该页换出；若为，就选择该页换出；若为1，则将其复为，则将其复为0，暂，暂不换出，再按照不换出，再按照FIFO算法检查下一个页面算法检查下一个页面。当检查到队列中的最后一个页面，若其访问为仍为1，则返回到队首再去检查第一个页面。因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出，故该算法又称为最近未用算法NRC(
28、Not Recently Used)。3434第五章 虚 拟 存 储 器图5-8简单Clock置换算法的流程和示例3535第五章 虚 拟 存 储 器2.改进型Clock置换算法该算法除考虑页面的使用情况外，还考虑到页面置换代价的因素，在选择换出页面时，既要是未访问过的页面，又在选择换出页面时，既要是未访问过的页面，又要是未修改过的页面要是未修改过的页面。把同时满足这两个条件的页面作为首选页面。由访问位A和修改位M可以组合成四种类型的页面。1类(A=0,M=0).最佳淘汰页面.2类(A=0,M=1).不是很好的淘汰页.3类(A=1,M=0),可能再被访问的页.4类(A=1,M=1),可能再被访问
29、的页.内存中的每个页面必定是这四种类型之一，页面置换时，采用与简单Clock算法相类似的方法，差别是须同时检查访问位和修改位。改进型Clock算法的执行过程可分成三步:(1)从指针指示的当前页面开始扫描循环队列，所示 页面的A=0且M=0否?是，则将该页作为淘汰页，否，则检查下一个页面。直到整个队列扫描完毕，这期间不修改访问位A。(2)若在执行(1)时未淘汰页面，则开始第二轮扫描。若指针所示的页面的A=0且M=1，则将该页作为 淘汰页，否则继续扫描。这期间，所有扫描过的 页面的访问位A置0。(3)若在执行(2)时未淘汰页面，则将指针返回到开始 位置。然后重复执行(1),必要时再重复执行(2)。
30、此时一定能找到被淘汰的页。3636第五章 虚 拟 存 储 器5.3.4 页面缓冲算法(Page Buffering Algorithm，PBA)1.影响页面换进换出效率的若干因素(1)页面置换算法。(2)写回磁盘的频率。对已经被修改过的页面，在换出时，应当写回磁盘。(3)读入内存的频率。如果有进程在数据还未写回磁盘时需要再次访问这些页面时，就不需从外存上调入，而直接从已修改换出页面链表中获取，这样可以减少将页面从磁盘读入内存的频率，减少页面换进的开销。3737第五章 虚 拟 存 储 器2.页面缓冲算法PBAPBA算法的主要特点是：显著地降低了页面换进、换出的频率，使磁盘I/O的操作次数大为减少
31、，因而减少了页面换进、换出的开销；正是由于换入换出的开销大幅度减小，才能使其采用一种较简单的置换策略，如先进先出(FIFO)算法，它不需要特殊硬件的支持，实现起来非常简单。1)空闲页面链表2)修改页面链表3838第五章 虚 拟 存 储 器5.3.5 访问内存的有效时间与基本分页存储管理方式不同，在请求分页管理方式中，内存有效访问时间不仅要考虑访问页表和访问实际物理地址数据的时间，还必须要考虑到缺页中断的处理时间。3939第五章 虚 拟 存 储 器5.4 5.4“抖动”与工作集 由于请求分页式虚拟存储器系统的性能优越，在正常运行情况下，它能有效地减少内存碎片，提高处理机的利用率和吞吐量，故是目前
32、最常用的一种系统。但如果在系统中运行的进程太多，进程在运行中会频繁地发生缺页情况，这又会对系统的性能产生很大的影响，故还须对请求分页系统的性能做简单的分析。4040第五章 虚 拟 存 储 器5.4.1 多道程序度与“抖动”1.多道程序度与处理机的利用率 由于虚拟存储器系统能从逻辑上扩大内存，这时，只需装入一个进程的部分程序和数据便可开始运行，故人们希望在系统中能运行更多的进程，即增加多道程序度，以提高处理机的利用率。但处理机的实际利用率却如图5-9中的实线所示。41 41第五章 虚 拟 存 储 器图5-9 处理机的利用率4242第五章 虚 拟 存 储 器2.产生“抖动”的原因发生“抖动”的根本
33、原因是，同时在系统中运行的进程同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间造成每个进程的大部分时间都用于页面的换进都用于页面的换进/换出，而几乎不能再去做任何有效的工作，换出，而几乎不能再去做任何有效的工作，从而导致发生
34、处理机的利用率急剧下降并趋于从而导致发生处理机的利用率急剧下降并趋于0的情况。我的情况。我们称此时的进程是处于们称此时的进程是处于“抖动抖动”状态状态。4343第五章 虚 拟 存 储 器5.4.2 工作集1.工作集的基本概念进程发生缺页率的时间间隔与进程所获得的物理块数有关(如图所示)。之所以会形成图示曲线的原因，是由于缺页率的大小与进程运行时的工作集有关。工作集理论由Denning提出并推广。他认为程序在运行时对页面的访问是不均匀的，若能预知程序在某段时间间隔内要访问哪些页面，并将他们提前调入内存，就会大大降低缺页率。缺页率上限下限物理块数n4444第五章 虚 拟 存 储 器2.工作集的定义
35、所谓工作集工作集，是指在某段时间间隔里，进程实际所要访问页面的集合。虽然程序只需少量的几页在内存就可运行，但为使程序能有效运行，较少地产生缺页，就必须使程序的工作集全部在内存。由于无法预知程序在不同时刻将访问哪些页面，故只能利用程序过去某段时间内的行为，作为程序利用程序过去某段时间内的行为，作为程序将来某段时间内的行为的近似将来某段时间内的行为的近似。设某进程在时间t的工作集为w(t,)，称为工作集窗口尺寸。w(t,)是二元函数，与时间t和窗口尺寸有关，工作集w是工作集窗口的非降函数，即w(t,)w(t,+1)。正确选择工作集窗口的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响
36、。4545第五章 虚 拟 存 储 器图5-11 窗口为3、4、5时进程的工作集引用页序列引用页序列窗口大小：窗口大小：3窗口大小：窗口大小：4窗口大小：窗口大小：5242424241515，2415，2415，241818，15，2418，15，2418，15，242323，18，1523，18，15，2423，18，15，242424，23，181717，24，2317，24，23，1817，24，23，18，151818，17，242418171515，17，1815，17，18，24244646第五章 虚 拟 存 储 器5.4.3 “抖动”的预防方法：目前预防抖动的方法有多种，这些方法的
37、共同点都是通过调节多道程序度来实现的。1.采用局部置换策略：某进程发现缺页后，仅在自己的内存空间范围内置换页面，不允许从其他进程获得新的物理块。2.在CPU调度程序中引入工作集算法：仅当每个进程在内存中都有足够大的驻留集时，方能再从外存上调入新的作业。3.L=S准则：产生缺页的平均时间L等于系统处理进程缺页的平均时间。此时的CPU利用得最好。4.挂起若干进程：以便腾出内存空间来分配给抖动的进程。4747第五章 虚 拟 存 储 器 5.5 请求分段存储管理方式 在分页系统基础上建立的虚拟存储器，是以页面为单位进行换入换出的。在分段的基础上实现的虚拟存储器，则是以分段为单位进行换入换出的。在请求分
38、段系统中，程序运行之前只需调入若干个分段，便可启动运行。当所访问的段不在内存时可请求OS将所缺的段调入内存。4848第五章 虚 拟 存 储 器5.5.1 请求分段中的硬件支持 1.请求段表机制 段表是请求分段式管理中所需的主要的数据结构，为适应程序在运行过程中，对段的调进调出，需在段表的原有结构上增加若干项。段表项的结构如下段名 段长段基址存取方式访问字段A修改位M存在位p增补位外存始址用于标识本分段的存取属性是只执行、只读、还是允许读写用于记录本段被访问的频繁程度用于表示本段进入内存后是否被修改过。指示本段是否已调入内存用于表示本段在运行过程中，是否进行过动态增长指示本段在外存的起始地址，即
39、起始盘块号。4949第五章 虚 拟 存 储 器2.缺段中断机构：在请求分段系统中，采用的是请求调段策略。即每当进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理程序将所需的段调入内存。对缺段中断的处理要比对缺页中断的处理复杂。3.地址变换机构：请求分段系统中的地址变换机构，是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，在地址变换时，若发现所要访问的段不在内存时，必须先将所缺的段调入内存，并修改了段表之后，才能再利用段表进行地址变换。5050第五章 虚 拟 存 储 器图5-12 请求分段系统中的中断处理过程51 51第五章 虚 拟
40、存 储 器图5-13 请求分段系统的地址变换过程5252第五章 虚 拟 存 储 器5.5.2 分段的共享与保护分段存储管理方式便于实现分段的共享与保护。实现分段共享的方法是只须在每个进程的段表中，用相应的表项来指向共享段在内存的起始地址即可。1.共享段表 为实现分段共享，可在系统中配置一张表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了共享此分段的每个进程的情况。共享段表如下图。5353第五章 虚 拟 存 储 器段名 段长 内存始址 状态 外存始址状态 进程名 进程号 段号 存取控制共享进程记数count 共享段表项 共享段表用于记录需
41、要共享该分段的进程数目。因为非共享段仅为一个进程所需要，当进程不再需要该段时，可立即释放该段，并由系统回收该段所占用的空间。而共享段为多个进程所需要，当某进程不再需要而释放它时，系统并不回收该段所占内存区。只有当所有共享该段的进程全部都不再需要它时，才由系统回收该段所占内存区。用于标识该进程对所访问的共享段的存取权限。对于一共享段，应给不同的进程以不同的存取权限。例如，对于文件主，通常允许其读和写，而其他进程则可能只允许读，甚至只执行。对于同一个共享段，不同的进程可以使用不同的段号去共享该段。5454第五章 虚 拟 存 储 器 2.共享段的分配与回收1）共享段的分配）共享段的分配：分配共享段的
42、内存时，对第一个请求使用共享段的进程，由系统为该段分配一物理区，再把这共享段调入该区，同时将该区的始址填入该进程的段表相应项中，还要在共享段表中增加一表项，填写有关数据，count置1。以后，当有其他进程调用该共享段时，由于该段已在内存，故只需在调用进程的段表中增加一表项，填入该共享段的物理地址，在共享段表中填上调用进程名等，再执行count的加1操作。2)2)共享段的回收共享段的回收：当某进程不再需要共享段时，应将该段释放，包括取消在该进程段表中共享段所对应的表项，以及执行count的减1操作。若减1后为0，则需由系统回收该共享段的物理内存，取消在共享段表中该段所对应的表项，这表明此时已没有
43、进程使用该段；若减1后不为 0，则只取消调用者进程在共享段表中的有关记录。5555第五章 虚 拟 存 储 器 3.分段保护：在分段系统中，由于每个分段在逻辑上是独立的，因而较易实现信息保护。目前常采用的措施有以下几种：1)越界检查越界检查：2)存取控制检查存取控制检查：利用进程段表中的存取方式字段,执行对该段规定的访问，通常的访问方式有：(1)只读。只允许程序对该段中的程序或数据进行读访问。(2)只执行。只允许程序调用该段去执行，不准去读或写该段的内容。(3)读/写。允许程序对该段进行读和写。对于共享段来说，存取控制尤为重要。对于共享段来说，存取控制尤为重要。3)环保护机构环保护机构：该机制规定，低编号的环具有高优先权，OS核心处于0环内；一些重要的实用程序和操作系统服务占居中间环；一般的应用程序安排在外环。在环系统中，程序的访问和调用应遵循的规则：(1)一个程序可以访问驻留在相同环或较低特权环(外环)中的数据。(2)一个程序可以调用驻留在相同环或较高特权环(内环)中的服务。5656第五章 虚 拟 存 储 器此课件下载可自行编辑修改，仅供参考！此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢感谢您的支持，我们努力做得更好！谢谢