处理机调度与死锁课件

《处理机调度与死锁课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章处理机调度与死锁第三章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4产生死锁的原因和必要条件3.5预防死锁的方法3.6死锁的检测与解除3.1处理机调度的基本概念3.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）将外存作业调入内存，创建PCB等，插入就绪队列。一般用于批处理系统，分/实时系统一般直接入内存，无此环节。3.1处理机调度的基本概念3.1高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）在每次执行作业调度时，都须做出以下两个决定。1)接纳多少个作业2)接纳哪些作业3.1处理机调度的基本概念3.1

2、高、中、低三级调度1、高级调度（作业调度、长程调度、接纳调度）调度特性1.接纳作业数（内存驻留数）太多―――>周转时间T长太少―――>系统效率低2.接纳策略：即采用何种调度算法：FCFS、短作业优先等2.低级调度(LowLevelScheduling)1)非抢占方式(Non-preemptiveMode)可能引起进程调度的因素可归结为这样几个：①正在执行的进程执行完毕，或因发生某事件而不能再继续执行；②执行中的进程因提出I/O请求而暂停执行；③在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语、Wakeup原语等。处理机调度的基本概念（2

3、）2.低级调度(LowLevelScheduling)1)非抢占方式(Non-preemptiveMode)这种调度方式的优点是实现简单、系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。显然，在要求比较严格的实时系统中，不宜采用这种调度方式。处理机调度的基本概念（2）处理机调度的基本概念（2）2、低级调度（进程调度，短程调度）主要是由分派程序（Dispatcher）分派处理机。2.抢占方式（1）时间片原则（2）优先权原则（3）短作业优先原则。处理机调度的基本概念（2）3、中级调度（中程调度）为提高系统吞吐量和

4、内存利用率而引入的一内--外存对换功能（换出时，进程为挂起或就绪驻外状态）运行频率：低>中>高。3.1.2调度的队列模型一、仅有进程调度的队列模型就绪队列CPU阻塞队列交互用户时间片完进程调度进程完成等待事件事件出现图3-1仅具有进程调度的调度队列模型3.1.2调度的队列模型二、具有高/低级模型就绪队列CPU阻塞队列时间片完进程调度进程完成等待事件1事件1出现后备队列阻塞队列等待事件2事件2出现作业调度图3-2具有高、低两级调度的调度队列模型(1)就绪队列的形式。(2)设置多个阻塞队列。图3-2示出了具有高、低两级调度的调度队列模型。该模型与上一模型的主要区别在于如下两个

5、方面。三.同时具有三级调度的调度队列模型图3-3具有三级调度时的调度队列模型3.1.3选择调度方式和算法的若干准则一、面向用户的准则1．周转时间短（常用于批处理系统）概念：作业从提交――>完成的时间.分为：（1）驻外等待调度时间（2）驻内等待调度时间（3）执行时间（4）阻塞时间一、面向用户的准则1．周转时间短平均周转时间:平均带权周转时间:Ts为实际服务时间，作业的周转时间Ti。可见带权w越小越好。3.1.3选择调度方式和算法的若干准则一、面向用户的准则2．响应时间快：（对交互性作业）概念：键盘提交请求到首次响应时间（1）输入传送时间（2）处理时间（3）响应传送时间3．截

6、止时间的保证（特别于实时系统）4．优先权准则：（即需要抢占调度）3.1.3选择调度方式和算法的若干准则二、面向系统的准则1．吞吐量高（特别于批处理）：单位时间完成作业数2．处理机利用率好：（因CPU贵，特别于大中型多用户系统）3．各类资源的平衡利用。3.1.3选择调度方式和算法的若干准则3.2调度算法——是一个资源分配问题3.2.1先来先服务和短作业（进程）优先调度算法1.FCFS特点：简单，有利于长作业,即CPU繁忙性作业可以分别用于作业调度和进程调度先来先服务调度算法例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100先来先

7、服务调度算法例进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A010111B110011011001C21101102100100D31001022021991.992.短作业(进程)优先调度算法短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。3.2调度算法2.短作业(进程)优先调度算法短作业优先(SJF)的调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选出一估