物理块分配算法.ppt

在虚存中，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行的时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这种现象称为颠簸或抖动。 原因： 页面淘汰算法不合理 分配给进程的物理页面数太少 重点概念和内容提示 地址映射、虚拟地址空间、绝对地址空间、静态重定位和动态重定位、交换、虚拟存储器、缺页中断、页表和段表 可变分区的放置算法 分页存储管理的原理和地址变换 分段存储管理的原理和地址映射 请求分页的原理和页面置换算法 学习目标 理解并掌握请求分页存储管理系统中的硬件支持 理解请求分页存储管理系统中的内存分配策略和分配算法 掌握主要页面置换算法 §4.7 请求分页存储管理方式 请求分页存储管理的基本思想 请求分页存储管理方式是实现虚拟存储器的一种常用技术； 基本思想：在进程开始运行之前，仅装入当前要执行的部分页面即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的页面；当内存空间已满，而又需要装入新的页面时，者根据置换功能适当调出某个页面，以便腾出空间而装入新的页面。 为了实现页式虚存，系统需要解决下面三个问题： 1）系统如何感知进程当前所需页面不在主存（页表机制）； 2）当发现缺页时，如何把所缺页面调入主存（缺页中断机构）； 3）在置换页面时，根据什么策略选择欲淘汰的页面（置换算法）。 4.7.1 请求分页的硬件支持 状态位（中断位）：标识该页是否在内存（0或1）； 访问位：标识该页面的近来的访问次数或时间（换出）； 修改位：标识此页是否在内存中被修改过； 外存地址：记录该页面在外存上的地址，即(外存而非内存的)物理块号。 页号 状态位 物理块号 外存地址 访问位 修改位 1、页表机制 程序在执行时，首先检查页表，当状态位指示该页不在主存时，则引起一个缺页中断发生，其中断执行过程与一般中断相同： 保护现场（CPU环境）； 中断处理（中断处理程序装入页面）； 恢复现场，返回断点继续执行。 2.缺页中断机构 缺页中断与一般中断的不同点： 一般中断是一条指令完成后检查是否有中断 缺页中断是在指令执行期间产生和处理中断， 一条指令执行时可能产生多个缺页中断(如指令可能访问多个内存地址，这些地址在不同的页中)。 相应的中断处理程序把控制转向缺页中断子程序。执行此子程序，即把所缺页面装入主存。然后处理机重新执行缺页时打断的指令。这时，就将顺利形成物理地址。缺页中断的处理过程是由硬件和软件共同实现的。 缺页中断引发的连续中断 4.7.2　内存分配策略和分配算法 　　1．最小物理块数的确定 　　这里所说的最小物理块数，是指能保证进程正常运行所需的最小物理块数。当系统为进程分配的物理块数少于此值时，进程将无法运行。进程应获得的最少物理块数与计算机的硬件结构有关，取决于指令的格式、功能和寻址方式。对于某些简单的机器，若是单地址指令且采用直接寻址方式，则所需的最少物理块数为2。其中，一块是用于存放指令的页面，另一块则是用于存放数据的页面。 　　2．物理块的分配策略 　　1) 固定分配局部置换(Fixed Allocation，Local Replacement) 　　这是指基于进程的类型(交互型或批处理型等)，或根据程序员、程序管理员的建议，为每个进程分配一定数目的物理块，在整个运行期间都不再改变。采用该策略时，如果进程在运行中发现缺页，则只能从该进程在内存的n个页面中选出一个页换出，然后再调入一页，以保证分配给该进程的内存空间不变。实现这种策略的困难在于：应为每个进程分配多少个物理块难以确定。若太少，会频繁地出现缺页中断，降低了系统的吞吐量；若太多，又必然使内存中驻留的进程数目减少，进而可能造成CPU空闲或其它资源空闲的情况，而且在实现进程对换时，会花费更多的时间。 　　2) 可变分配全局置换(Variable Allocation，Global Replacement) 　　这可能是最易于实现的一种物理块分配和置换策略，已用于若干个OS中。在采用这种策略时，先为系统中的每个进程分配一定数目的物理块，而OS自身也保持一个空闲物理块队列。当某进程发现缺页时，由系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的(缺)页装入其中。这样，凡产生缺页(中断)的进程，都将获得新的物理块。仅当空闲物理块队列中的物理块用完时，OS才能从内存中选择一页调出，该页可能是系统中任一进程的页，这样，自然又会使那个进程的物理块减少，进而使其缺页率增加。 　　3) 可变分配局部置换(Variable Allocation，Local Replacement) 　　这同样是基于进程的类型或根据程序员的要求，为每个进程分配一定数目的物理块，但当某进程发现缺页时，只允许从该进程在内存的页面中选出一页换出