1、齐鲁工业大学 理学院 鹿文鹏 1第三章第三章 处理机调度与死锁处理机调度与死锁n 提高处理机的利用率及改善系统性能（吞吐提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理量、响应时间），在很大程度上取决于处理机调度性能的好坏。机调度性能的好坏。n 处理机调度是操作系统设计的中心问题之一处理机调度是操作系统设计的中心问题之一。齐鲁工业大学 理学院 鹿文鹏 2第三章第三章 处理机调度与死锁处理机调度与死锁n 3.1 处理机调度的基本概念处理机调度的基本概念n 3.2 调度算法调度算法n 3.3 实时调度实时调度n 3.4 多处理机系统中的调度多处理机系统中的调度n 3.5
2、 产生死锁的原因和必要条件产生死锁的原因和必要条件n 3.6 预防死锁的方法预防死锁的方法n 3.7 死锁的检测与解除死锁的检测与解除齐鲁工业大学 理学院 鹿文鹏 33.1 处理机调度的基本概念处理机调度的基本概念n 3.1.1 高级、中级和低级调度高级、中级和低级调度n 3.1.2 调度队列模型调度队列模型n 3.1.3 选择调度方式和调度算法的若干准则选择调度方式和调度算法的若干准则齐鲁工业大学 理学院 鹿文鹏 43.1 处理机调度的基本概念处理机调度的基本概念n 作业被提交后，必须经过处理机调度后，方作业被提交后，必须经过处理机调度后，方能获得处理机执行。能获得处理机执行。n 对于批量作
3、业而言，通常需要经过对于批量作业而言，通常需要经过 作业调度作业调度（高级调度）和（高级调度）和 进程调度进程调度 （低级调度）两个（低级调度）两个过程后，方能获得处理机；对于终端型作业过程后，方能获得处理机；对于终端型作业，通常只须经过，通常只须经过 进程调度进程调度 。在较完善的。在较完善的 OS中，往往还设置了中，往往还设置了 中级调度中级调度 。n 每一级调度，都可采用不同的调度方式和调每一级调度，都可采用不同的调度方式和调度算法。度算法。齐鲁工业大学 理学院 鹿文鹏 53.1.1 高级、中级和低级调度高级、中级和低级调度n 1.高级调度高级调度n 2.低级调度低级调度n 3.中级调度
4、中级调度齐鲁工业大学 理学院 鹿文鹏 61.高级调度高级调度 (High Scheduling)n 即即 作业作业 调度或长程调度调度或长程调度 (long-Term Scheduling)，用，用于决定把外存上处于后备队列中的哪些作业调入于决定把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源，再内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。又将新创建的进程排在就绪队列上，准备执行。又称称 接纳调度接纳调度 (Admission Scheduling)。n 批处理系统中批处理系统中 ，作业进入系统后，是先驻留在外，作业进入系统后，是
5、先驻留在外存上的，因此存上的，因此 需要需要 有作业调度，以将它们分批装有作业调度，以将它们分批装入内存。入内存。n 在分时系统中在分时系统中 ，为了能及时响应，用户通过键盘，为了能及时响应，用户通过键盘输入的命令或数据等，都是直接送入内存因而输入的命令或数据等，都是直接送入内存因而 无无需需 配置作业调度。配置作业调度。 在实时系统中在实时系统中 ，通常也不需要，通常也不需要作业调度。作业调度。齐鲁工业大学 理学院 鹿文鹏 7作业调度需做的两个决定作业调度需做的两个决定n 1.接纳多少个作业接纳多少个作业作业调度每次要接纳多少个作业进入内存，作业调度每次要接纳多少个作业进入内存，取决于多道程
6、序度取决于多道程序度 (Degree of Multiprogramming)，即允许有多少个作业同，即允许有多少个作业同时在内存中运行。时在内存中运行。n 2.接纳哪些作业接纳哪些作业应将哪些作业从外存调入内存，将取决于应将哪些作业从外存调入内存，将取决于所采用的调度算法所采用的调度算法 。先来先服务调度算法；。先来先服务调度算法；短作业优先调度算法；基于作业优先权的调短作业优先调度算法；基于作业优先权的调度算法；响应比高者优先的调度算法。度算法；响应比高者优先的调度算法。齐鲁工业大学 理学院 鹿文鹏 82.低级调度低级调度 (Low Level Scheduling)n 又称又称 进程进程
7、 调度调度 或或 短程调度短程调度 (Short-Term Scheduling) ，它决定就绪队列中的哪个进，它决定就绪队列中的哪个进程将获得处理机，然后由分派程序程将获得处理机，然后由分派程序(Dispatcher)执行把处理机分配给该进程的操执行把处理机分配给该进程的操作。作。n 运行频率很高，是运行频率很高，是 最基本的一种调度最基本的一种调度 ，在三，在三种类型的种类型的 OS中都必须配置这级调度。中都必须配置这级调度。齐鲁工业大学 理学院 鹿文鹏 9进程调度的两种方式进程调度的两种方式n 1)非抢占方式非抢占方式 (Non-preemptive Mode)n 一旦分配一旦分配 CP
8、U，便让该进程一直执行，直至，便让该进程一直执行，直至该进程完成或被阻塞时。决不允许某进程抢该进程完成或被阻塞时。决不允许某进程抢占已经分配出去的处理机。占已经分配出去的处理机。n 可能引起进程调度的因素：可能引起进程调度的因素： 正在执行的进程执行完毕，或因发生某事件正在执行的进程执行完毕，或因发生某事件而不能再继续执行而不能再继续执行 执行中的进程因提出执行中的进程因提出 I/O请求而暂停执行请求而暂停执行 在进程通信或同步过程中执行了某种原语操在进程通信或同步过程中执行了某种原语操作，如作，如 wait， block等等齐鲁工业大学 理学院 鹿文鹏 10进程调度的两种方式进程调度的两种方式n 1)非抢占方式非抢占方式 (Non-preemptive Mode)n 优点：实现简单、系统开销小，适用于大多优点：实现简单、系统开销小，适用于大多数的批处理系统环境。数的批处理系统环境。n 缺点：难于满足紧急任务的要求缺点：难于满足紧急任务的要求 -立即执行立即执行。
