华东理工815操作系统第17讲精要.ppt

地址变换例题 二、请求分页中的内存分配策略和分配算法 在请求分页系统中，为进程分配内存时，将涉及以下三个问题： 1、最小物理块数的确定 最小物理块数指能保证进程正常运行所需的最小的物理块数，与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。 2、物理块的分配策略 3、物理块分配算法 2、物理块的分配策略 （1）固定分配局部置换：为每个进程分配固定数目n的物理块，在整个运行中都不改变。如出现缺页，则从中置换一页。 （2）可变分配全局置换：分配固定数目的物理块，但OS自留一空闲块队列，若发现缺页，则从空闲块队列中分配一空闲块与该进程，并调入缺页于其中。当空闲块队列用完时，OS才从内存中选择一页置换。 （3）可变分配局部置换：分配一定数目的物理块，若发现缺页，则从该进程的页面中置换一页，根据该进程缺页率高低，则可增加或减少物理块。 3、物理块分配算法 在采用固定分配策略时，将系统中可供分配的所有物理块分配给各个进程，可采用以下几种算法： （1）平均分配算法：平均分配给各个进程。 （2）按比例分配算法：根据进程的大小按比例分配给各个进程。 （3）考虑优先权的分配算法：将系统提供的物理块一部分根据进程大小先按比例分配给各个进程，另一部分再根据各进程的优先权适当增加物理块数。 三、请求分页中的页面调入策略 调入策略决定什么时候将一个页面由外存调入内存，从何处将页面调入内存。 何时调入页面（1） 预调页策略：将那些预计在不久便被访问的页预先调入内存。这种调入策略提高了调页的效率，减少了I/O次数。但由于这是一种基于局部性原理的预测，若预调入的页面在以后很少被访问，则造成浪费，故这种方式常用于程序的首次调入。 三、请求分页中的页面调入策略 何时调入页面（2） 请求调页策略：当进程运行中访问的页不在内存时，则发出缺页中断，提出请求调页，由OS将所需页调入内存。这种策略实现简单，应用于目前的虚拟存储器中，但易产生较多的缺页中断，且每次调一页，系统开销较大，容易产生抖动现象。 三、请求分页中的页面调入策略 从何处调入页面（1） 在请求分页系统中，通常将外存分成了文件区和对换区，文件区按离散分配方式存放文件，对换区按连续分配方式存放对换页。 对换区：系统有足够的对换区空间，运行前可将与进程相关的文件从文件区复制至对换区，以后缺页时，全部从对换区调页。 三、请求分页中的页面调入策略 从何处调入页面（2） 文件区：系统没有足够的对换区空间，凡是不会被修改的文件，每次都直接从文件区调页，换出时不必换出。 文件区、对换区：系统没有足够的对换区空间，对可能会修改的文件第一次调页直接从文件区，换出时换至对换区，以后从对换区调页。 UNIX方式：凡未运行过的页面均从文件区调页，运行过的页面和换出的页面均从对换区调页。 三、请求分页中的页面调入策略 页面调入过程 4.8 请求分页中的页面置换算法 页面置换算法也称为页面淘汰算法，是用来选择换出页面的算法。页面置换算法的优劣直接影响到系统的效率，若选择不合适，可能会出现以下现象： 刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不久又再次被淘汰出内存，然后又要访问它，如此反复，使得系统把大部分时间用在了页面的调进换出上，而几乎不能完成任何有效的工作，这种现象称为抖动（又称颠簸）。 4.8 请求分页中的页面置换算法 常用的页面置换算法： 最佳置换算法：选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。 先进先出置换算法FIFO：选择先进入内存的页面予以淘汰。 最近最久未使用置换算法LRU：选择最近一段时间最长时间没有被访问过的页面予以淘汰。 Clock置换算法 *其它算法 最佳置换算法例 先进先出置换算法例题 先进先出置换算法例题 先进先出置换算法例题 先进先出置换算法_注（1）： 先进先出置换算法_注（2）： 最近最久未使用算法例 最近最久未使用算法_注（1） 最近最久未使用算法_注（2） Clock置换算法 （1）简单Clock置换算法 该算法是LRU和FIFO的折衷。该算法要求为每页设置一个访问位，并将内存中的所有页链接成一个循环队列。 当某页被访问时，系统将其访问位设置为1。 置换时采用一个指针，从当前指针位置开始按序检查各页，若访问位为0则选择该页换出，若访问位为1则将其设置为0，最后指针停留在被置换页的下一页上。 （2）改进型Clock置换算法 该算法要求除须考虑页面的使用