《计算机操作系统》汤小丹讲义课件.ppt

湘 潭 大 学,第6章虚拟存储器,6.1 虚拟存储器概述,前述的各种存储管理方式，有一个共同特点，就是要求将一个作业全部装入内存以后才能运行。于是，出现这样两种情况：有的作业很大，其要求的内存空间超过了内存总容量。有大量作业要求运行，而内存不足以容纳所有这些作业。解决的办法是从逻辑上扩充内存。,6.1.1 传统存储管理方式的特征和局部性原理,传统存储管理方式的特征一次性特征；驻留性特征。而一次性和驻留性是否是程序运行时所必须的。局部性原理：程序在执行时呈现出局部性规律，即在一较短时间内，程序的执行仅限于某个部分；相应地，其所访问的存储空间也局限于某个区域。局部性表现为时间局限性和空间局限性。虚拟存储器的基本工作情况：基于局部性原理，一个作业运行之前，没有必要全部装入内存。只需装入当前要运行的那部分页或段便可启动运行，以后利用OS的对换功能来逐步完成整个作业的运行。,6.1.2 虚拟存储器的定义和特征,虚拟存储器的定义：虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。或是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储器的逻辑容量由内存和外存容量之和所决定。其运行速度接近于内存，每位的成本接近于外存。虚拟存储技术是一种非常优越的存储器管理技术,虚拟存储器的特征多次性：是指一个作业被分成多次来调入内存，即作业运行时不需将其全部装入内存，只需将当前要运行的那部分程序和数据装入，以后运行到某些部分时再将其调入。对换性：是指允许作业中的程序和数据，在作业运行过程中换进、换出。虚拟性：是指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。虚拟性以多次性和对换性为基础，多次性和对换性以离散分配为基础。,6.1.3 虚拟存储器的实现方法,请求分页系统：这是在分页系统的基础上增加请求调页和页面置换功能形成的页式虚拟存储系统。允许只装入若干页(非全部）的用户程序和数据，便可启动运行。以后利用请求调页和页面置换功能完成作业的运行。置换时以页为单位。对此，系统须提供必要的硬件支持和相应的软件。硬件支持： （1）请求分页的页表机制。用以作为请求分页的数据结构；（2）缺页中断机构；（3）地址变换机构。实现分页的软件：实现请求调页的软件和实现页面置换的软件。,请求分段系统：这是在分段系统的基础上增加请求调段和分段置换功能后而形成的段式虚拟存储系统。同样，系统须提供必要的硬件支持：（1）请求分段的段表机制；（2）缺段中断机构；（3）地址变换机构。同样需要相应的软件。目前也有建立在段页式系统基础上的段页式虚拟存储系统。,6.2 请求分页存储管理方式,6.2.1 请求分页中的硬件支持（1）一、页表机制：在请求分页系统中的主要数据结构仍然是页表。其基本作用是将用户地址空间中的逻辑地址变换为内存空间的物理地址。页表项的结构如下：,页号 物理块号 状态位P 访问字段A 修改位M 外存地址,又称存在位，用于指示该页是否已调入内存，供程序访问时参考。,用于记录本页在一段时间内被访问的次数，或最近已有多长时间未被访问，提供给置换算法选择换出页面时参考。,指示该页在调入内存后是否被修改过。若未被修改，在置换该页时就不需将该页回写到外存，否则，就要回写到外存。,用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。,二、缺页中断机构：每当所要访问的页面不在内存时，便要产生一缺页中断，请求OS将所缺之页调入内存。缺页中断虽要经历与一般中断相同的几个步骤，但它是一种特殊的中断，与一般中断的区别主要是：（1）在指令执行期间产生和处理中断信号。通常CPU都是在一条指令执行完后去检查是否有中断请求到达。有则响应，无则继续执行下一条指令。而缺页中断是在指令执行期间，发现所要访问的指令和数据不在内存时产生和处理的。（2）一条指令在执行期间，可能产生多次缺页中断，这时硬件机构应能保存多次中断时的状态，并保证最后能返回到中断前产生缺页中断的指令处，继续执行。,10,产生缺页中断的例,Copy ATo B,例如：执行COPY A TO B这条指令时，可能要产生6次缺页中断,页面,三、地址变换机构：请求分页系统中的地址变换机构，是在分页系统的地址变换机构基础上，为实现虚拟存储器而增加某些功能所形成的，如产生和处理缺页中断，以及从内存中换出一页的功能等。 请求分页系统中的地址变换过程： (见教材的流程图）,6.2.2 请求分页中的内存分配,在为进程分配物理块时，将涉及到以下三个问题：一、最小物理块数的确定：是指能保证进程正常运行所需的最少物理块数。若系统分配给某进程的物理块数小于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。,二、物理块的分配策略：分配策略可采取固定分配和可变分配两种；置换策略可采取全局置换和局部置换两种。于是可组合出三种适用的策略：1、固定分配局部置换：为每个进程分配一固定页数的内存空间，在整个运行期间保持不变。置换时，只能从进程在内存的n个页面中选出一页换出，然后再调入一页，保证其内存空间不变。,2、可变分配全局置换：先为每个进程分配一定数目的物理块，OS本身也保持一个空闲物理块队列。任一进程发现缺页时，由系统从空闲物理块队列中取出一块分配给该进程，并将欲调入的缺页装入其中。这样，凡产生缺页的进程，都将获得新物 理块。当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，选择页的可能是系统中任一进程的页。,3、可变分配局部置换：为每个进程分配一定数目的内存空间，当某进程发生缺页时，只允许从该进程在内存中的页面中选出一页换出。若某进程在运行中频繁地发生缺页中断，则系统需再为该进程分配若干附加的物理块，直至其缺页率降低到适当程度为止；反之，若某进程的缺页率特别低，则可适当地减少分配给它的物理块数，前提是其缺页率没有明显增加。,三、物理块分配算法：采用固定分配策略时，将系统中可供分配的所有物理块分配给各个进程，可采用以下几种算法：1、平均分配算法：将系统中所有可供分配的物理块平均分配给各个进程。2、按比例分配算法：根据进程的大小按比例分配物理块。3、考虑优先权的算法：通常采用的方法是把内存中可供分配的所有物理块分成两部分，一部分按比例分配给各个进程；另一部分则根据各进程的优先权来分配。,6.2.3 页面调入策略,一、何时调入页面：可采取预调页策略或请求调页策略来确定进程运行时所缺页面调入内存的时机。预调页策略：以预测为基础，将预计在不久之后便会被访问的程序或数据所在之页，预先调入内存。目前，预调页的成功率约为50%。请求调页策略：进程在运行中提出调页请求后，系统将其所需的页面调入内存。由该策略所确定调入的页，一定会被访问，但调页时的系统开销较大，因每次请求时只调入一页。,二、从何处调入页面：请求分页系统中，外存分为用于存放文件的文件区和用于存放对换页面的对换区两部分。缺页请求时，系统调页的方法有三种：,系统有足够的对换区空间。进程运行前便将与该进程有关的文件从文件区拷贝到对换区。这样系统可从对换区调入所需页面。系统缺少足够的对换区空间。这时凡是不会被修改的文件，都直接从文件区调入，以后再调入时，仍从文件区调入。对于可能被修改的部分，将他们换出时，便调到对换区，以后需要时再从对换区调入。UNIX方式。凡是未运行过的页面，都从文件区调入。曾经运行过而又被换出的页面，放在对换区，下次调入时，从对换区调入。由于允许页面共享，故某进程所请求的页面可能已被其他进程调入，此时不需从对换区调入。,三、页面调入过程：程序要访问的页面不在内存，向CPU发出缺页中断。转入缺页中断处理程序。处理程序查找页表得到缺页所在外存的物理块号。若此时内存未满，则从外存将缺页调入内存，并修改页表。若内存已满，则按置换算法从内存选出一页准备换出，若欲换出页未修改过，可不必写入外存，否则要重写。然后将缺页调入内存，并修改页表中相应的页表项，置状态位为1，再将此表项写入快表中。缺页调入内存后，利用修改后的页表，去形成所要访问的数据的物理地址，再去访问内存数据。页面的调入全过程对用户是透明的。,6.3 页面置换算法,通常,把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms).置换算法的好坏将直接影响系统的性能,不适当的算法可能导致进程发生“抖动”(Thrashing).即刚被换出的页很快又被访问,需重新调入,为此,又需再选一页调出;而此刚被换出的页,很快又被访问,因而又需将它调入,如此频繁地更换页面,以至一个进程在运行中,将把大部分时间花在完成页面置换的工作上,我们称该进程发生了“抖动”.一个好的算法,应具有较低的页面更换频率.理论上讲，应将那些以后不再被访问的页面换出，或把那些在较长时间内不会再访问的页面调出。,缺页率,把一个作业（包括程序和数据）的运行始末所访问的页的序列Z记为： P1，P2，Pt，PZ Pt为在时刻t访问的页，PZ 为最后一次访问的页。序列Z称为作业运行时的页面踪迹，或页面走向，即作业访问地址空间的规律。假设系统分配给该作业的内存空间为m个物理块，在任何时刻t，若所访问的页已在主存，称此次访问成功，若不在，则称此次访问失败，并产生缺页中断。若在作业运行过程中，访问成功的次数为S，失败次数为F，设访问页面的总次数为Z，则Z=S+F，则f=F/Z为缺页中断率。经常以此来衡量一个页面置换算法的优劣。,缺页次数的计算,假设页面调入采用请求调页策略，则在进程被创建时，并不分配内存块，直到进程运行时，由于缺页，引起缺页中断，才调入进程的第一个页面至内存，紧接着调入进程访问的第二个页面，显然，进程运行初期，缺页率是很高的。如果页面分配采取固定分配局部置换策略，则进程运行初期将很快占满分配给它的内存块，使缺页率保持在一个适当的水平，以后的缺页将引起页面置换。计算缺页次数时，是从第一次产生缺页开始，直至运行结束时总的缺页次数。计算页面置换次数，是从第一次进行页面置换，直至运行结束时总的页面置换次数。,22,6.3.1 最佳置换算法和先进先出算法（1）,一、最佳(Optimal)置换算法：是一个理论上的算法，具有最好的性能，但难以实现。该算法所选择的被淘汰页面，将是永不使用的或者是在最长时间内不再被访问的页面。对于固定分配页面方式，采用该算法可保证获得最低的缺页率。由于目前人们还无法预知一个进程在内存中的若干个页面中，谁是未来最长时间内不再被访问的，因此该算法无法实现。 最佳置换算法的例子：,7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1,7,70,701,201,203,243,203,201,701,页面的编号,系统采用固定分配局部置换策略，为某进程分配的三个物理块（页框）,进程运行时先后将7，0，1三个页面装入内存，此时内存已满，若进程要访问新的页面，则需淘汰三者之一,进程访问页面2，此时产生缺页中断，将页面2调入内存，但调入之前须将内存中的某页换出。,OS根据最佳置换算法，将页面7淘汰，因页面0将在第5次被访问，页面1在第14次被访问，而页面7要在第18次时被访问才需调入。,进程访问访问页面3，引起页面1被淘汰，因在内存中的1，2，0三个页面中，页面1将是以后最晚才被访问的，要在第14次才被访问。,采用最佳置换算法，只发生6次页面置换,进程在运行过程中共发生9次缺页中断,二、先进先出（FIFO）页面置换算法：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰。该算法实现简单，只须把一个进程已调入内存的页面，按先后次序链接成一个队列，并设置一个替换指针，使它总是指向最老的页面。但该算法与进程运行的实际规律不符，有可能使一些被经常访问的页面，如含有全局变量、常用函数等这样的页面被频繁地换入换出。 对于前述的例子，采用FIFO算法时，共要进行12次页面置换，而最佳置换算法才6次。,24,6.3.2 最近最久未使用和最少使用置换算法,最近最久未使用置换算法一、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 1,7,70,701,201,这时淘汰页面7，换入页面2。因页面7是最先进入内存且被使用，在这之后至今未使用，是最近最久未使用的页面,进程访问页面2，但它不在内存，系统需将它调入。,203,403,402,432,032,132,102,107,进程访问页面3，但它不在内存，系统需将它调入。,进程访问页面0，但其不在内存。淘汰页面4，换入页面0。,这时页面1是最近最久未使用的页面，淘汰页面1，换入页面3。,发生9次页面置换,二、LRU算法的硬件支持：LRU算法作为页面置换算法是比较好的，但实现的难度相当大，需要较多的硬件支持来解决两个问题，一是一个进程在内存中的各个页面个有多长时间未被进程访问，二是如何快速地知道最近最久未使用的页面。为此须利用两类硬件之一的支持：1、寄存器：为每个在内存中的页面配置一个移位寄存器，用于记录某进程在内存中的各页的使用情况。2、栈：每当进程访问某页面时，便将该页面的页号压入栈顶。因此，栈顶始终是最新被访问的页面的页面号，栈底是最近最久未使用页面的页面号。,最少使用(Least Frequently Used)算法：该算法是选择在最近时期使用最少的页面作为淘汰页。采用该算法时，应为内存中的每个页面设置一移位寄存器，用来记录页面被访问的次数。每次访问某页面时，便对该页面移位寄存器的最高位置1，再每隔一定时间寄存器右移一次。这样在最近一段时间内使用最少的页面将是寄存器数值最小的页面 。,6.3.3 Clock算法,Clock算法是LRU的一种近似算法。一、简单的Clock置换算法：利用该算法时，须为每页设置一访问位，再将内存中的所有页面都通过链接指针链成一循环队列。当某页被访问时，其访问位置1。 Clock算法在选择一页淘汰时，只须检查其访问位，若为0，就选择该页换出；若为1，则将其复为0，暂不换出，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面，若其访问为仍为1，则返回到队首再去检查第一个页面。因该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出，故该算法又称为最近未用算法NRC(Not Recently Used)。,28,二、改进型Clock置换算法：该算法除考虑页面的使用情况外，还考虑到页面置换代价的因素，在选择换出页面时，既要是未访问过的页面，又要是未修改过的页面。把同时满足这两个条件的页面作为首选页面。由访问位A和修改位M可以组合成四种类型的页面。 1类(A=0,M=0).最佳淘汰页面. 2类(A=0,M=1).不是很好的淘汰页. 3类(A=1,M=0),可能再被访问的页. 4类(A=1,M=1),可能再被访问的页. 内存中的每个页面必定是这四种类型之一,页面置换时,采用与简单Clock算法相类似的方法,差别是须同时检查访问位和修改位.,改进型Clock算法的执行过程可分成三步:(1)从指针指示的当前页面开始扫描循环队列，所示 页面的A=0且M=0否?是，则将该页作为淘汰页， 否，则检查下一个页面。直到整个队列扫描完毕， 这期间不修改访问位A。 (2)若在执行(1)时未淘汰页面，则开始第二轮扫描。若指针所示的页面的A=0且M=1，则将该页作为 淘汰页，否则继续扫描。这期间，所有扫描过的 页面的访问位A置0。 (3)若在执行(2)时未淘汰页面，则将指针返回到开始 位置。然后重复执行(1),必要时再重复执行(2)。此时一定能找到被淘汰的页。,6.3.4 页面缓冲算法,在请求分页系统中，页面换进换出的开销对系统性能有重大影响。影响页面换进换出的因素包括：页面置换算法。写回磁盘的频率。读入内存的频率。页面缓冲算法的特点是：显著降低页面换进换出的频率。采用较简单的置换策略。,VMS/VAX系统的页面缓冲算法(Page Buffering Algorithm)该算法采用了可变分配和局部置换方式，置换算法则采用FIFO。该算法规定将一个被淘汰的页放入两个链表中的一个，若页面未被修改，就将它直接放入空闲链表中，否则放入已修改页面链表中。这种方式使得已修改和未修改的页面都仍然留在内存中，当进程以后再次访问这些页面时，只需花较小的开销，使这些页面又返回到该进程的驻留集中。 当被修改页面达到一定数量时，才一次性地将他们写回到外存，这样就显著地减少了外存的I/O次数。,6.4 “抖动”与工作集,请求分页系统是目前最常用的一种存储管理方式。但程序在运行中所产生的缺页情况，会影响程序的运行速度即系统性能；而缺页率的高低又将直接与每个进程所占用的物理块数目有关。为此，应分析缺页率对系统性能的影响，以及应为每个进程所分配的物理块数目，使得缺页率保持在一个合理的水平上。,缺页率对有效访问时间的影响,有效访问时间可表示为： 有效访问时间=(1-p)ma+ptd=ma+(td-ma)P p:出现缺页的概率; ma:存储器访问时间,一般在10ns到数百ns之间; td :缺页中断时间，主要由缺页中断服务,缺页读入和进程重新执行三部分时间构成. 设:ma=10ns; td =25ms 假设希望在缺页时,有效访问时间延长不超过10%,则有0.1+24999.9p0.11 即: p0.0000004 这说明,要求在250万次访问中,才发生1页缺页,即应保持非常低的缺页率,否则程序的执行速度将受到严重影响.,工作集（1）,缺页率，或者缺页的时间间隔与进程分得的物理块数目密切相关（如图所示）。 之所以会形成图示曲线的原因，是由于缺页率的大小与进程运行时的工作集有关。工作集理论由Denning提出并推广。他认为程序在运行时对页面的访问是不均匀的，若能预知程序在某段时间间隔内要访问哪些页面，并将他们提前调入内存，就会大大降低缺页率。,缺页率,上限,下限,物理块数n,所谓工作集是指在某段时间间隔内，进程实际要访问的页面的集合。虽然程序只需少量的几页在内存就可运行，但为使程序能有效运行，较少地产生缺页，就必须使程序的工作集全部在内存。由于无法预知程序在不同时刻将访问哪些页面，故只能利用程序过去某段时间内的行为，作为程序将来某段时间内的行为的近似设某进程在时间t的工作集为w(t,)，称为工作集窗口尺寸。w(t,)是二元函数，与时间t和窗口尺寸有关，工作集w是工作集窗口的非降函数，即w(t,) w(t,+1)。正确选择工作集窗口的大小，对存储器的有效利用和系统吞吐量的提高，都将产生重要的影响。,36,产生抖动的原因和预防方法,一、产生抖动的原因 在系统中，运行进 程的大部分时间都用 于进行页面的换入换 出，而几乎不能完成 任何有效的工作。称 这时的进程是处于抖 动状态。,CPU利用率,多道程序度,二、抖动的预防：目前预防抖动的方法有多种，这些方法的共同点都是通过调节多道程序度来实现的。1、采用局部置换策略：某进程发现缺页后，仅在自己的内存空间范围内置换页面，不允许从其他进程获得新的物理块。2、在CPU调度程序中引入工作集算法：仅当每个进程在内存中都有足够大的驻留集时，方能再从外存上调入新的作业。3、L=S准则：产生缺页的平均时间L等于系统处理进程缺页的平均时间。此时的CPU利用得最好。4、挂起若干进程：以便腾出内存空间来分配给抖动的进程。,6.5 请求分段存储管理方式,在分页系统基础上建立的虚拟存储器，是以页面为单位进行换入换出的。在分段的基础上实现的虚拟存储器，则是以分段为单位进行换入换出的。在请求分段系统中，程序运行之前只需调入若干个分段，便可启动运行。当所访问的段不在内存时可请求OS将所缺的段调入内存。,39,1 请求分段中的硬件支持,一、段表机制：段表是请求分段式管理中所需的主要的数据结构，为适应程序在运行过程中，对段的调进调出，需在段表的原有结构上增加若干项。段表项的结构如下：,段名,段长,段的基址,存取方式,访问字段A,修改字段M,存在位p,增补位,外存起址,用于标识本分段的存取属性是只执行、只读、还是允许读写,用于记录本段被访问的频繁程度,用于表示本段进入内存后是否被修改过。,指示本段是否已调入内存,用于表示本段在运行过程中，是否进行过动态增长,指示本段在外存的起始地址，即起始盘块号。,二、缺段中断机构：在请求分段系统中，采用的是请求调段策略。即每当进程所要访问的段尚未调入内存时，便由缺段中断机构产生一缺段中断信号，进入OS后由缺段中断处理程序将所需的段调入内存。对缺段中断的处理要比对缺页中断的处理复杂。三、地址变换机构：请求分段系统中的地址变换机构，是在分段系统地址变换机构的基础上形成的。因为被访问的段并非全在内存，在地址变换时，若发现所要访问的段不在内存时，必须先将所缺的段调入内存，并修改了段表之后，才能再利用段表进行地址变换。,2、分段共享与保护,分段存储管理方式便于实现分段的共享与保护。实现分段共享的方法是只须在每个进程的段表中，用相应的表项来指向共享段在内存的起始地址即可。一、共享段表：为实现分段共享，可在系统中配置一张表，所有各共享段都在共享段表中占有一表项。表项中记录了共享段的段号、段长、内存始址、存在位等信息，并记录了共享此分段的每个进程的情况。共享段表如下图。,段名 段长 内存始址 状态 外存始址,状态 进程名 进程号 段号 存取控制,共享进程记数count, ,共享段表项, ,共享段表,用于记录需要共享该分段的进程数目。因为非共享段仅为一个进程所需要，当进程不再需要该段时，可立即释放该段，并由系统回收该段所占用的空间。而共享段为多个进程所需要，当某进程不再需要而释放它时，系统并不回收该段所占内存区。只有当所有共享该段的进程全部都不再需要它时，才由系统回收该段所占内存区。,用于标识该进程对所访问的共享段的存取权限。对于一共享段，应给不同的进程以不同的存取权限。例如，对于文件主，通常允许其读和写，而其他进程则可能只允许读，甚至只执行。,对于同一个共享段，不同的进程可以使用不同的段号去共享该段。,43,2、分段共享与保护,二、共享段的分配与回收1、共享段的分配：分配共享段的内存时，对第一个请求使用共享段的进程，由系统为该段分配一物理区，再把这共享段调入该区，同时将该区的始址填入该进程的段表相应项中，还要在共享段表中增加一表项，填写有关数据，count置1。以后，当有其他进程调用该共享段时，由于该段已在内存，故只需在调用进程的段表中增加一表项，填入该共享段的物理地址，在共享段表中填上调用进程名等，再执行count的加1操作。,2、共享段的回收：当某进程不再需要共享段时，应将该段释放，包括取消在该进程段表中共享段所对应的表项，以及执行count的减1操作。若减1后为0，则需由系统回收该共享段的物理内存，取消在共享段表中该段所对应的表项， 这表明此时已没有进程使用该段；若减1后不为 0，则只取消调用者进程在共享段表中的有关记录。,44,2 分段共享与保护,三、分段保护：在分段系统中，由于每个分段在逻辑上是独立的，因而较易实现信息保护。目前常采用的措施有以下几种：1、越界检查：2、存取控制检查：利用进程段表中的存取方式字段，执行对该段规定的访问，通常的访问方式有：(1)只读。只允许程序对该段中的程序或数据进行读访问。(2)只执行。只允许程序调用该段去执行，不准去读或写该段的内容。(3)读/写。允许程序对该段进行读和写。 对于共享段来说，存取控制尤为重要。,3、环保护机构：该机制规定：低编号的环具有高优先权，OS核心处于0环内；一些重要的实用程序和操作系统服务占居中间环；一般的应用程序安排在外环。 在环系统中，程序的访问和调用应遵循的规则： （1）一个程序可以访问驻留在相同环或较低特权环中的数据。 （2）一个程序可以调用驻留在相同环或较高特权环中的服务。,