OS3处理机调度与死锁OS3处理机调度与死锁.ppt

第三章 处理机调度与死锁 3.1 处理机调度的层次——高、中、低三级调度 3.1.1高级调度——作业调度、长程调度、接纳调度 (Admission Scheduling) 外存→内存，创建PCB等，插入就绪队列。 用于批处理系统，分/实时系统一般直接入内存，无此环节。 调度特性 1)接纳多少（内存驻留数） 太多――― 太少――― 2)接纳哪些 即采用何种调度算法：FCFS、SJF、HRRN等 3.1.2 低级调度——进程调度、短程调度 主要是由分派程序（Dispatcher）分派处理机。 1.非抢占方式 (Nonpreemptive Mode) （1）执行完毕 （2）执行中因提出I/O请求而暂停执行 （3）在进程通信或同步过程中执行了某种原语操作 如P操作 简单，系统开销小，实时性差 2.抢占方式 (Preemptive Mode) （1）优先权原则 （2）短作业优先原则 （3）时间片原则 3.1.3 中级调度——中程调度 （ Medium-Term Scheduling ） 为提高系统吞吐量和内存利用率而引入的 内----外存对换功能（换出时，进程为挂起或就绪驻外状态） 运行频率：低中高 3.2 调度队列模型和调度准则 1.仅有进程调度的队列模型(分时系统） 3.2 调度队列模型和调度准则 2.具有高/低两级调度的队列模型(批处理系统） 3.同时具有三级调度的调度队列模型 一、面向用户的准则 1．周转时间短（常用于批处理系统） 概念：作业从提交――完成的时间 等待时间+执行时间 （1）驻外等待调度时间（后备队列） （2）驻内等待调度时间（就绪队列） （3）执行时间 （4）阻塞时间（阻塞队列） 一、面向用户的准则 平均周转时间 二、面向系统的准则 1．吞吐量高（特别于批处理） 单位时间完成作业数 2．处理机利用率好 特别于大中型多用户系统 3．均衡使用资源 合理搭配各种类型作业，最大限度发挥资源效益 3.3 调度算法 1.先来先服务调度算法 FCFS （作业、进程） 简单，只顾及等待时间，未考虑执行时间； 优待长作业（进程）不利于短作业（进程） 2.短作业（进程）优先调度算法 SJ(P)F 假定所有任务同时到达，平均等待时间最短,提高了平均（带权）周转时间（从而提高了系统吞吐量）； 忽视了等待时间； 对长作业不利，有可能得不到服务（饥饿）; 估计时间不易确定; 未考虑作业的紧迫程度 例 FCFS FCFS和SJF比较 SJF习题 在一单道批处理系统中，一组作业的提交时刻和运行时间如下，试计算SJF调度算法的平均周转时间T和平均带权周转时间W 3.3.2 高优先权优先调度算法（Highest Priority First, HPF） 1.优先权调度算法的类型 非抢占式优先权算法 （批处理） 抢占式优先权算法，实时性更好 2.优先权类型 1）静态优先权：整个运行期间不变 确定优先权依据 类型 对资源的需求 根据用户需求 特点：简单，但低优先权作业可能长期不被调度 2）动态优先权 优先权随执行时间而下降，随等待时间而升高。 3.3.2 高优先权优先调度算法 3.高响应比优先算法 (Highest Response-ration Next ,HRRN) 特点:引入动态优先权,保证长作业运行 响应比: Rp = 响应时间/服务时间 =（Tw+Ts）/Ts = 1+Tw/Ts Tw相同， Ts相同， 即使Ts很长， 优点：长短兼顾 缺点：需计算Rp 3.3.3 基于时间片的轮转调度算法 1.时间片轮转法(Round Robin,RR) （进程） 时间片大小的确定 太大：退化为FCFS； 太小：系统开销过大（时钟中断、调度、分派） 2. 多级反馈队列调度 （ Round Robin With Multiple Feed back ） 性能： （1）终端型作业一次完成； （2）短批处理作业周转时间不长； （3）大型作业不会长期不处理。 3.5 死锁 (deadlock) 3.5.1 产生死锁的原因 1.竞争资源 可剥夺（CPU、内存）和非剥夺性（打印机、磁带机）资源 可供多个进程共