第8章_虚拟存储管理.

8．1．2虚拟存储器实现方法：一个进程在运行之时，没有必要全部装入内存，而只把当前运行所需要的页（段）装入内存便可启动运行，而其余部分则存放在磁盘上。程序在运行时，如果所需要的页（段）已经调入内存，便可以继续执行下去。如果所需要的页（段）不在内存，此时程序应利用操作系统所提供的请求调页（段）功能，将该页（段）调入内存，以使程序能够运行下去。如果此时分配给该程序的内存已全部占用，不能装入新的页（段），则需要利用系统的置换功能，把内存中暂时不用的页（段）调出至磁盘上，腾出足够的内存空间，再将所要装入的页（段）调入内存，使程序能够继续运行下去。8．1．2虚拟存储器虚拟存储器的定义：是指仅把进程的一部分装入内存便可运行的存储器系统，它具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。虚拟存储器的逻辑容量：虚拟存储器的逻辑容量由系统的寻址能力和外存容量之和所决定。8．2请求分页式存储管理方式请求分页式存储管理是在分页式存储管理的基础上，增加了请求调页功能、页面置换功能而形成的页式虚拟存储系统。它是目前常用的一种虚拟存储器的方式。8．2．1请求分页式存储管理的基本概念基本原理：在请求分页式存储管理系统中，进程运行之前将一部分页面装入内存，另外一部分页面则装入外存。在进程运行过程中，如果所访问的页面不在内存中，则发生缺页中断，进入操作系统，由操作系统进行页面的动态调度。其方法如下：找到被访问页面在外存中的地址；在内存中找一个空闲块，如果没有，则按照淘汰算法选择一个内存块，将此块内容写回外存，修改页表；读入所需的页面，修改页表；重新启动进程，执行被中断的指令。8．2．1请求分页式存储管理的基本概念页表机制：纯分页的页表只有两项：页号和物理块。而请求分页存储管理增加了调入功能和置换功能，故需在页表中增加若干项，供程序在换进换出时参考。下面所示是一请求分页系统中的页表：页号物理块号状态位P访问字段A修改位M外存地址状态位P：用于指示该页是否已调入内存，0表示该页已在内存，1表示该页不在内存，供程序访问时参考；访问字段A：用于记录该页在一段时间内被访问的次数，或最近已有多长时间未被访问，供置换算法选择页面时参考；8．2．1请求分页式存储管理的基本概念修改位M：用于记录该页在调入内存后是否被修改过。由于内存中的每一页都在外存上保留一个副本，因此，若未被修改，在置换该页时就不需将该页写回到磁盘上，以减少系统的开销和启动磁盘的次数；若已被修改，则必须将该页重写回磁盘上，以保证磁盘上所保留的始终是最新副本。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。8．2．2页面分配策略内存页面分配策略：平均分配：将内存中的所有可供分配的物理块，平均分配给各个进程。这是最简单的分配方式，它看起来很公平，但实际上很不公平，因为它没有考虑进程的大小等因素。按进程大小比例分配：系统按进程的大小按比例分配物理块。若m为可用物理块总和，S为各进程页面总和，si为第i个进程的页面数，则为第i个进程分配的页面数为：按进程优先级比例分配：为照顾重要的、紧迫的进程，使其能够尽快的完成，可以为其分配较多的内存物理块。)(mSsINTaii8．2．2页面分配策略外存块的分配策略：静态分配：一个进程在运行前，将其所有页面全部装入外存。当某一外存页面被调入内存时，所占用外存页面并不释放。这样，当该页面以后被淘汰时，如果它在内存中未被修改过，则不必写回外存，因为外存中有一个和它完全相同的副本，这可以减少因页面调度而引起的系统开销，代价是牺牲一定的外存空间。动态分配：一个进程在运行前，仅将未装入内存的那部分页面装入外存。当某一外存页面被调入内存，释放所占用的外存空间。这样，当该页面以后被淘汰时，不管它在内存中是否被修改过，都必须重新为其申请外存物理块，将该页重新写回外存。这种方法的优点是节省外存空间，但会增加由页面调度而引起的系统开销。8．2．3页面调入时机请求调页策略：当发生缺页中断时进行调度，即当访问某一页而该页不在内存时，立即提出请求，由系统将所需页面调入内存。显然，采用纯请求调页策略，被调入内存的页面一定会被用到，不会发生无意义的页面调度。但是，请求调页策略也有一个缺点，从缺页中断发生到页面被调入内存，发生缺页中断的进程必须等待，影响了进程的推进速度。预调页策略：由于在外存上查找所缺的页，须经历较长的时间。如果一个进程存放在外存中的许多页在一个连续的区域中，每次调入若干个页会比每次调入一页更高效些。但如果调入的一批页面中的大多数都未被访问，则这种调入又是低效的。可见，如果预测比较准确，会大大降低缺页中断率，从而提高进程的推进速度。8．2．4页面置换算法最佳置换算法（OPT，Optimal）：最佳置换算法置换那些以后永不再使用的或者在最长的时间以后才会用到的页面。显然，这种算法的缺页率最低。然而，该算法只是一种理论上的算法，因为很难估计哪一个页面是以后永远不再使用或在最长时间以后才会用到的页面，所以，这种算法是不能实现的。尽管如此，该算法仍然是有意义的，可以把它作为衡量其它算法优劣的一个标准。8．2．4页面置换算法【例8-1】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最佳置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501500000223332220100115122233222000101100511304440331222555++++-+-+--+--+---+--缺页中断次数=9缺页中断率=9/20=45%8．2．4页面置换算法先进先出置换算法（FIFO，First-InFirst-Out）：先进先出置换算法总是置换最先进入内存的页面。该算法实现简单，只须把一个进程已调入内存的页面，按照进入内存的先后顺序排成一个队列，当一个页面由外存调入内存时排入队尾，需要淘汰时取队首的页面。8．2．4页面置换算法【例8-2】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用先进先出置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501501223042300012225015011230423330111250500123042223000125++++-++++++--++--+++缺页中断次数=15缺页中断率=15/20=75%8．2．4页面置换算法Belady异常现象：一般而言，分配给进程的物理块越多，运行时的缺页次数应该越少。但是Belady在1969年发现了一个反例，使用FIFO算法时，四个物理块时的缺页次数比三个物理块时的多，这种反常的现象称为Belady异常。如下面两表所示，一个进程有5个页面，页面访问序列如下：Belady异常现象（3个物理块的FIFO现象）页面访问序列012301401234012301444233012301114220123000144九次缺页+++++++--++-8．2．4页面置换算法Belady异常现象（4个物理块的FIFO现象）页面访问序列012301401234012333401234012223401230111234012000123401十次缺页++++--++++++由表中可见，3个物理块时缺页次数是9次，缺页中断率为9/12=75%；而4个物理块时的缺页次数是10次，缺页中断率为10/12≈83.3%。8．2．4页面置换算法最近最久未使用置换算法（LRU，LeastRecentlyUsed）：该算法的基本思想是：如果某一页面被访问了，那么它很可能马上又被访问；反之，如果某一页面很久没有被访问，那么最近也不会再次被访问。因此，该算法为每一个页面设置一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面予以淘汰。LRU的实现：记时法：系统为每一页面增设一个记时器。每当一个页面被访问时，当时的绝对时钟内容被拷贝到对应的记时器中，这样系统记录了内存所有页面最后一次被访问的时间。淘汰页面时，选取记时器中值最小的页面淘汰。8．2．4页面置换算法LRU的缺点：虽然LRU在理论上是可以实现的，但代价太高。为了实现LRU，需要在内存维持一个包含所有页的链表，最近使用的页面在表头，最近未使用的页面在表尾。而每次访问页面时都需要对链表进行更新。在链表中找到所需的页，将它移动到表头是一个非常费时的操作，即使使用硬件实现也是一样。8．2．4页面置换算法【例8-3】假定系统为某进程分配了3个物理块，页面访问序列为：5、0、1、2、0、3、0、4、2、3、0、3、2、1、2、0、1、5、0、1。采用最近最久未使用置换算法，计算缺页中断次数和缺页中断率。解：页面置换过程如下表所示：页面访问序列50120304230321201501501203042303212015015012030423032120150501223042203312015++++-+-++++--+-+-+--缺页中断次数=12缺页中断率=12/20=60%8．2．4页面置换算法最近未使用置换算法（NRU，NotRecentlyUsed）：为了克服LRU的缺点，最近未使用置换算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置1。在选择一页淘汰时，检查其访问位，如果是0，则淘汰该页；若为1，则把其置0，暂不换出该页，再按照FIFO算法检查下一个页面。当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回队首再去检查第一个页面。事实上，NRU算法不但希望淘汰最近未使用的页，而且还希望被挑选的页在内存驻留期间，其页面内的数据未被修改过。淘汰该页时，由于该页未被修改过，因此不必写盘，从而减少了磁盘的I/O操作次数。为此，要为每页增设两个硬件位：访问位和修改位：8．2．4页面置换算法访问位A=0：该页尚未被访问过=1：该页已经被访问过修改位M=0：该页尚未被修改过=1：该页已经被修改过访问位和修改位的组合有以下四种：1类（A=0，M=0）：表示该页最近既未被访问，又未被修改，是最佳淘汰页；2类（A=0，M=1）：表示该页最近未被访问，但已被修改，并不是很好的淘汰页；3类（A=1，M=0）：最近已被访问，但未被修改，该页有可能再次被访问；4类（A=1，M=1）：最近已被访问且被修改，该页可能再次被访问。8．2．4页面置换算法开始时，所有页的访问位、修改位都置为0。当访问某页时，将该页访问位置1。当某页的数据被修改，则该页的修改位置1。当要选择一页淘汰时，挑选内存中现有的类别最低的页淘汰。8．2．4页面置换算法Clock置换算法：最近未使用置换算法是一种比较合理的算法，但它经常要在链表中移动页面，大大降低了系统效率。为了克服这个缺陷，把所有的页面保存在一个类似时钟表面的环形链表中，用一个表针指向可能淘汰的页面，如下图所示ABCDEFGHIJK8．2．4页面置换算法当发生缺页时，该算法首先检查表针指向的页面，如果其访问位是0，则淘汰该页，并把新的页面插入到这个位置，然后把表针前移一个位置；如果访问位是1则把其置0，并把表针前移一个位置，重复这个过程直到找到一个访问位为0的页为止。了解了这个算法的工作方式，我们就知道这种算法为什么被称为Clock算法了。它与最久未使用置换算法的区别仅仅是实现方法上的不同。8．2．5请求分页系统的性能分析请求分页式存储管理系统的性能优越，较好地解决了存储扩充问题。因此，它是目前最常用的存储管理方式。但进程在运行时所产生的缺页中断，会影响程序的运行速度及系统性能。而缺页率的高低又与分配给进程的物理块数直接相关。因