[工学]chapter3_处理机调度与死锁1.ppt

课程主要内容 操作系统引论（1章） 进程管理（2-3章） 存储管理（4章） 设备管理（5章） 文件管理（6章） Process Management 进程管理 进程的基本概念与控制 进程的基本概念 进程控制 线程的基本概念 UNIX中进程的描述与控制 进程同步与通信 进程同步 经典进程的同步问题 管程机制 进程通信 UNIX中进程的同步与通信 处理机调度与死锁（第3章） 第3章 处理机调度与死锁 第3章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度 10.2.4 UNIX系统中进程的调度 3.1 处理机调度的基本概念 在多道程环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。它是操作系统设计的中心问题之一。 一、调度的层次 二、调度队列模型 三、选择调度方式和算法的若干准则 作业的相关概念 作业(job): 是把命令、程序和数据按照预先确定的次序结合在一起，并提交给系统的一个组织单位。 或者：作业是用户交给系统的具有独立功能的任务。 作业：程序和数据+作业说明书 在批处理系统中，是以作业为基本单位从外存调入内存的。 作业在系统中是动态的，从作业产生到作业消失的整个过程中，作业的状态跟随系统的运作而发生变化。 作业能自动完成任务而无需人工干预。 作业的相关概念 作业流 若干个作业进入系统后，被依次存放在外存上，这便形成了输入的作业流；在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。 每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，其中的每一个加工步骤称为一个作业步。 一个典型的作业可分成三个作业步：① “编译”作业步；② “连结装配”作业步；③ “运行”作业步。 作业控制块Job Control Block 在多道批处理系统中通常有上百个作业，为了管理和调度作业，系统为每个作业设置了一个作业控制块（JCB），它记录该作业的有关信息。不同系统的JCB的组成内容有所区别。 JCB是作业在系统中存在的唯一标志。作业进入系统时由系统为每个作业建立一个JCB；当作业退出系统时，则它的JCB也一起被撤消。 作业控制块的主要内容 补充：作业的状态(1) 根据所处的不同位置，作业被分为四种状态 (1)提交状态：当用户正在通过输入设备向计算机提交作业时，作业处于提交状态。 处于提交状态的作业，因为它的信息尚未全部进入系统，故不能被调度程序选中。 (2)后备状态：当用户完成作业的提交，作业已存在于辅助存储器中，则在它还未被调度去执行前，称该作业处于后备状态。 处于后备状态的作业具有完整的作业描述信息。 处于后备状态的作业有资格进入主存储器，但何时进入主存储器，还需要看有否这样的时机。 补充：作业的状态(2) (3)执行状态：作业被调度进入主存储器，并以进程的形式存在，其状态就是执行状态。 处于执行状态的作业并不意味着一定在CPU上运行，是否运行依赖于进程控制。 处于执行状态的作业可以有多个。 (4)停止状态：当作业已经完成其指定的功能，等待着与之相关的进程、资源，及其他描述信息的撤消，作业便进入停止状态。 一、调度的层次 一个作业从提交开始，往往要经历三级调度：高级调度、低级调度、中级调度。 1、高级调度（长程/作业/宏观调度） ①从外存后备队列中选择作业进入内存就绪队列或挂起就绪。 ②在批处理系统中，大多配有作业调度，但在分时系统及实时系统中,一般不配置。 ③作业调度执行频率很低，时间尺度通常是分钟、小时或天。 一、调度的层次（续） 高级调度需解决的问题 （1）接纳作业数（内存驻留数） 即多道程序的“道” 太多则可能会影响系统的服务质量（如周转时间太长），太少又将导致系统资源利用率和吞吐量的下降 根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度 （2）接纳策略（应将哪些作业从外存调入内存） 取决于采用何种调度算法（先来先服务、短作业优先等） 一、调度的层次（续） 2、低级调度（短程/CPU/进程/微观调度） （1）任务是从就绪队列中选择一个进程来执行并由分派程序（Dispatcher）分配处理机。 （2）是OS中最基本的调度。 （3）时间尺度通常是毫秒级的，由于低级调度算法的频繁使用，要求在实现时做到高效。 （4）常采用非抢占（非剥夺）方式和抢占（剥夺）方式两种。 一、调度的层次（续） （5）引起进程调度的因素： 进程正常终止或异常终止 正在执行的进程因某种原因而阻塞 在引入时间片的系统中，时间片用完 在抢占调度方式中，就绪队列中某进程的优先权变得比当