操作系统2002--存储管理(2).ppt

五、分段存储管理,1、基本原理,引入分段存储管理方式，主要是为了满足用户的下述要求：方便编程分段共享分段保护动态链接动态增长,A、分段在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。每个段的逻辑地址都是从0开始。段内地址是连续的，但段与段之间不一定是连续的。,分段的基本原理,作业的逻辑地址由段号与段内地址所组成，结构如下：,如果机器的地址有m位，其中段内地址占n位，则每个作业最多可分为2(m-n)个段。,B、段表,为使程序能够正常运行，亦即能从物理内存中找出每个逻辑段所对应的位置，应象分页系统那样，在系统中为每个作业建立一张段的映射表，简称段表。在配置了段表后，程序在执行过程中可通过查找段表，找到每个段所对应的内存区。,2、主存空间的分配与去配,段式存储管理分配主存空间的方法及回收存储空间的方法与可变分区管理方式所采用的方法相同。,3、地址转换与存储保护,地址变换机构和变换过程,段表始址,段表长度,1K,6K,600,4K,500,8K,200,9200,位移量,段号,段号,0,1,2,3,2,100,+,+,控制寄存器,8292,基址,段长,越界,逻辑地址,物理地址,主存,例题:某分段管理中采用下表所示的段表：,给定段号和段内地址，说明分段管理中的地址变换过程；计算0，430，1，10，2，500，3，400，4，20，5，100的内存地址，其中方括号内的第一个元素是段号，第二个元素是段内地址；说明存取主存的一条指令或数据至少要访问几次内存。,解答：0，430的物理地址是：219+430=6491，10的物理地址是：3300+10=33102，500的物理地址是：500100，越界3，400的物理地址是：1237+400=16374，20的物理地址是：1952+20=19725，100的物理地址是：54，段号越界存取主存的一条指令或数据至少要访问2次内存,分段的共享,与分页系统相比较，分段系统对段的保护更加简单易行。假定有一文本编辑程序，程序区500K，数据区100K，两个用户作业同时进行文本编辑，对于分页系统，假定每个页面大小为1K。对于分页系统，每个用户作业需建立一个页表，其中，500个页表项对应程序区，100个页表项对应数据区。而如果采用分段系统，则每个段表只需两个段表项，系统的开销要小的多，而且管理也会更加简单。,分页和分段的主要区别,1、页是信息的物理单位，而段是信息的逻辑单位；2、页的大小固定且由系统决定，而段的长度不固定，决定于用户编写的程序；3、分页的作业地址空间是一维的，而分段的地址空间是二维的。4、分段系统便于动态链接，存储保护，便于增长、修改和信息共享。,4、可分页的段式存储管理,A、基本原理先将作业分为若干个段，再把每个段划分为若干页。,段表控制寄存器,0号段页表,1号段页表,主存,B、地址变换过程再获得逻辑地址后，根据段表的控制寄存器，得到段表的首地址；首先利用段号，将它与段表长度进行比较，如段号大于段表长度，表示段号越界；根据段号求得对应该段的页表的首地址；再根据段内页号得到该页对应的物理块的地址；最后将物理块的首地址和页内地址相加构成最后的物理地址。,1、基本概念,虚拟存储器为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间、乃至n维空间），并没有容量的限制。现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。虚拟存储器需要大容量的外存储器的支持，或称物资基础。,五、虚拟存储器,2、虚拟存储器的工作原理,1、局部性原理程序执行时的局部性规律：程序在执行时，除了少部分的转移和过程调用指令外，在大多数情况下，仍然是顺序执行的。过程调用将会使程序的执行轨迹从一部分内存区域转到另一部分区域，但在大多数情况下，过程调用的深度都不超过5。程序中存在许多循环结构，它们虽由少数指令构成，但可以多次执行程序中的许多数据结构，如数组，在被操作时，往往局限于一个很小的范围内。,局部性原理表现在：时间局限性是指某个位置最近被访问了，那么往往很快又要被再次访问。空间局限性是指一旦某个位置最近被访问了，那么它附近的位置也要被访问。,3、虚拟存储器的定义,所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。,4、虚拟存储器的实现方式：页式虚拟存贮段式虚拟存储,页式虚拟存储它是在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的虚拟存储系统。系统必须提供的硬件支持：请求分页的页表机构缺页中断机构地址变换机构,段式虚拟存储这是在分段系统的基础上，增加了请求调段功能及分段置换功能后，所形成的段式虚拟存储系统。系统必须提供的硬件支持：请求分段的段表机构缺段中断机构地址变换机构,虚拟存储器的特征：,离散性指内存分配时采用离散分配方式多次性指一个作业被分成多次的调入内存运行对换性指允许在作业运行过程中在内存和磁盘间换进、换出虚拟性指能够从逻辑上扩充内存容量。,1、问题的提出,在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术,页式虚拟存储管理,需要解决的问题,如何发现执行的程序或访问的数据不在内存；程序或数据什么时候调入内存，调入策略；当一些页调入内存时，内存没有空闲内存时，将淘汰哪些页，采用什么淘汰策略。,2、基本原理,页式虚拟存储中的页表项组成：,状态位：用于指示该页是否已调入内存；访问字段：用于记录该页在一段时间内被访问的次数；修改位：表示该页在调入内存后是否被修改过；外存地址：用于指出该页在外存上的地址。,3、页式虚拟存储中的缺页中断机构,缺页中断与一般中断的区别：在指令执行期间产生和处理中断信号在一条指令执行期间，可能产生多次中断。,4、页式虚拟存储中的地址变换机构在分页系统地址变化机构的基础上，再增加某些虚拟存储器的功能而形成的。,地址变换过程,5、页面调度,主存的分配与置换策略固定分配局部置换：基于进程的类型（交互型或批处理型），或根据程序员、系统管理员的建议，为进程分配一固定页数的内存空间。可变分配全局置换：先为系统中的每一个进程分配一定数目的物理块，OS本身保留一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个进行分配。可变分配局部置换：同样基于进程的类型或根据程序员的要求，为每个进程分配一定数量的内存空间。当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其它进程的运行。,6、分配算法,在采用固定分配算法时，如何将系统中可供分配的所有物理块分配给各个进程，可采取下述方法：平均分配算法：将系统中所有可供分配的物理块，平均分配各个进程。按比例分配算法：根据进程的大小按比例分配物理块。例如：如果各进程页面数的总和是：,同时，假定系统中可用物理块总数为m，则每个进程所能分到的物理块bi为：,考虑优先权的分配算法：把内存中可供分配的物理块分成两个部分：一部分按比例分配给各个进程；另一部分则根据各进程的优先权，适当地增加其相应份额后，分配给各进程。,7、页面调入策略,何时调入页面：预调页策略：将那些预计在不久之后便会被访问的程序和数据所在的页面，预先调入内存。请求调页策略：当发现所需要的页面不再内存时，立即提出请求，由系统将所需页面调入内存。,从何处调入页面对于不同的系统，所采用的方法也不相同，可分成三种情况：,如果系统拥有足够的内存空间，可以全部从对换区调入页面，以提高调页速度。如果系统缺少足够的内存空间，则可以对不被修改的部分，直接从文件区调入；对于那些可能被修改的部分，将它们换出时，便需调到对换区，以后需要时再从对换区调入。UNIX方式：凡是未运行过的页面，都从文件区调入，对于曾经运行过而又被换出的页面，由于是放在对换区的，因此在下次调入时，应从对换区调入。,常用到的几个术语：抖动：刚刚被淘汰出去的页面，不久又被调入主存，这种现象，称为抖动（也称为颠簸）。页面走向：用引用串来表示。页面失效率：缺页中断次数占全部访问页面数的百分比，即：失效率=（失效次数/访问页面总数）100%,在讨论页面淘汰算法前假设：引用串：对进程逻辑地址空间的访问所涉及到的页面号序列。仅考虑页面号，不需考虑其页内位移。如连续两次对页面P进行访问，则至少第二次访问不会产生缺页中断。随着可用块数量的增加，产生缺页中断的次数将会减少。,8、页面置换算法先进先出页面置换算法该算法总是在淘汰最先进入内存的页面，即选择在内存中驻留最久的页面予以淘汰，即先进入主存的页，先退出储存。,FIFO（3块）,共进行了12次页面置换,假定系统分配给某进程3个存储块，并考虑如下引用串：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,FIFO（4块）,共进行了6次页面置换,例题：在请求分页存储管理中，若采用先进先出页面淘汰算法，会产生一种奇怪的现象：分配给作业的物理块越多，作业执行时的缺页率反而升高。试举一例说明这种现象。解答：若在作业运行过程中地址访问的引用串为：4，3，2，1，4，3，5，4，3，2，1，5。下面是为作业分配3个和4个物理块时的页面访问过程：,FIFO（3块）,FIFO（4块）,可见，3块时缺页中断次数为9，而4块时为10,最佳页面置换算法所选择的被淘汰的页面，将是以后永不被使用的，或者是在最长时间内不再被访问的页面。,OPT（3块）,共进行了6次页面置换。,最近最久未使用置换算法选择最近最久未使用过的页面进行淘汰，是用作业执行过程中过去的页面踪迹来推测未来的行为。,LRU（3块）,共发生9次置换,例题：近代计算机系统常采用请求页式存储管理方案来管理自己的主存。用简图说明它的地址变换方法；假定某作业J所涉及的页面依次为：0，1，0，2，0，1，0，1，3，0，并已知主存中有3个可供作业J使用的空闲存储块。试说明采用FIFO和LRU两种不同淘汰算法时，缺页中断率各是多少？,FIFO（3块）,缺页中断次数为5次,LRU（3块）,缺页中断次数为4次,注意，计算缺页次数和缺页率时，要注意初始时刻所有物理块为空。此时，虽然不发生页面的淘汰，但却需要引起缺页中断。,CLOCK置换算法简单的CLOCK置换算法为每页设置一个访问位，将内存中所有被使用的页面通过链接指针链成一个循环队列。当某页被访问时，其访问位被置1。置换算法再选择一页被淘汰时，只需按链查找，如果检查到链中的某页访问位是0，则选择该页换出，若为1，则重新将它置为0，然后检查下一页。,队首指针,页面访问位为0,置页面访问位为0,入口,选择该页面淘汰,是,否,查询指针前进一步，指向下一表目,返回,改进的CLOCK置换算法除了考虑页面的使用情况外，还考虑置换代价，即同时检查访问位A和修改位M。1类A=0，M=0，表示该页最近既未被访问，也未被修改，是最佳淘汰页；2类A=0，M=1，表示该页最近既未被访问，但已被修改，并不是很好的淘汰页；3类A=1，M=0，最近已被访问，但未被修改，该页有可能再被访问；4类A=1，M=1，最近已被访问，也被修改，该页有可能再被访问；,改进型CLOCK算法的执行过程：第一步，从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的页面，如找到，则淘汰之。在这遍扫描中不改变访问位A。第二步，如果第一步失败，则开始第二遍扫描，寻找A=0且M=1的页面，将所遇到的第一个这样的页面作为淘汰页，在此遍扫描中将所有经过的页面的访问位置为0。第三步，如果第二步也没有找到所要淘汰的页面，则将指针返回到开始的位置，并将所有页面的访问位置为0。然后重复第一步。,9、缺页中断率,假定，出现缺页的概率为p，主存的有效访问时间为MA，则页式虚拟存储管理的有效访问时间：有效访问时间=（1p）MAp缺页中断时间其中，缺页中断时间主要由三部分组成：缺页中断服务时间将缺页读入的时间作业重新执行时间可见，有效访问时间正比于缺页率。,影响缺页中断率的因素：分配给作业的的物理块数：一般地说，分配给作业的物理块数越多，则缺页中断率越低；页面的大小：页面越大，装入页面的信息量就越多，越可能降低缺页中断率；程序的编制方法：程序编制的方法不同，对缺页中断的次数有很大的影响；页面的调度算法：页面的调度算法对缺页中断率的影响也很大。,例子：设有二维数组VarA:array1128ofarray1128ofinteger;在一个页式虚拟存储系统中，采用LRU页面淘汰算法，一个进程有2页内存空间，每页可以存放128个整数。其中第一页存放程序，且假定程序已经在内存。请分别就下面程序A和B的执行过程计算缺页次数。,程序Afori:=1to128doforj:=1to128doAi,j:=0;,程序Bforj:=1to128dofori:=1to128doAi,j:=0;,对于程序A，会产生(128-1)次缺页对于程序B，会产生(128*128)-1次缺页中断,抖动产生的的原因和预防的方法1、抖动产生的的原因2、抖动的预防方法采用局部置换策略：作业运行中发现缺页时，仅在自己的内存空间范围内置换页面，而不允许从其它作业获得物理块；在CPU调度中引入工作集算法：在调度程序将作业调入内存之前，还必须检查作业在内存的驻留集是否足够大。L=S准则：产生缺页的平均时间等于系统处