产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除
教学重点和难点 • 处理机调度算法 • 死锁概念、必要条件，银行家算法
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
• 多道程序系统中，作业提交后，要想获得处理机而执 行，必须要经过处理机调度。
• 一个批处理作业，可能经历三级调度：
– 高级调度、中级调度、低级调度
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
• 高级调度（High Scheduling）
– 又称作业调度、长程调度、接纳调度 – 作用：决定把外存处于后备队列中的哪些作业调入内存， 并为它们创建进程、分配必要的资源，再将新创建的进 程排在就绪队列中，准备执行。 – 高级调度控制了多道程序的程度 为了给当前的进程集提供满意服务，长程调度程序可能 限制多道程序的程度 当处理器的空闲时间超过一定程度，则可启动长程调度 程序（装入一个或多个新作业）
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
• 调度队列模型
（1）仅有低级调度的调度队列模型
时 间 片 完 进 程 调 度 进 程 完 成
交 互 用 户 事 件 出 现
就绪队列
C P U
阻塞队列
等 待 事 件
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
（2）具有高级和低级调度的调度队列模型
3.2 调度算法
（2）短作业（进程）优先 SJ（P）F
• 属于非抢占策略 • 运行时间最短的进程将被选中 • 短进程会在长进程之前运行
0 5 10 15 20
A B C D E
第三章 处理机调度与死锁
3.2 调度算法
• 短作业（进程）优先 SJ（P）F
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
（2）面向系统的准则 – 系统吞吐量高（可评价批处理系统性能）
– 处理机利用率好 – 各类资源的平衡利用
第三章 处理机调度与死锁
• • • • • • • 3.1 3.2 3.3 3.4 3.5 3.6 3.7 处理机调度的基本概念 调度算法
实时调度 多处理机系统中的调度
产生死锁的原因和必要条件 预防死锁的方法 死锁的检测与解除
第三章 处理机调度与死锁
3.2 调度算法
调度算法
– 根据系统的资源分配策略所规定的资源分配算法。 – 不同类型的系统和系统目标，采用不同的调度算法 – 调度算法有的使用高级调度，有的使用低级调度， 有的既可用于高级调度，也可用于低级调度。
第三章 处理机调度与死锁
作 业 调 度 后 备队 列 时 间 片 完 进 程 调 度 进 程 完 成
就绪 队 列
CPU
事 件 1出 现
等 待 事 件 1
事 件 2出 现
等 待 事 件 2
…
事 件 n出 现
…
…
…
等 待 事 件 n
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
（3）同时具有三级调度的调度队列模型
作业调度 后备队列 批量作业 交互型作业 中级调度 时间片完 就绪队列
教学内容安排
• • • • • • 第一章 第二章 第三章 第四章 第五章 第六章 操作系统引论 进程管理 处理机调度与死锁 存储器管理 设备管理 文件管理
第三章 处理机调度与死锁
• • • • • • • 3.1 3.2 3.3 3.4 3.5 3.6 3.7 处理机调度的基本概念 调度算法
实时调度 多处理机系统中的调度
进程 到达时间 服务时间 A B 0 2 3 6
C
D E
4
6 8
4
5 2
第三章 处理机调度与死锁
3.2 调度算法
（1）先来先服务（FCFS， First-Come-First-Served ）
非抢占策略 • 每一个进入系统的进程都放入就绪队列Ready queue • 当当前运行的进程结束时，将选择就绪队列中等待最久的进程投 入运行
进程调度
CPU
进程完成
就绪，挂起队列 事件出现
阻塞，挂起队列 事 件 出 现 阻塞队列 等待事件 挂起
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
• 选择调度方式和调度算法的若干准则
（1）面向用户的准则 – 周转时间短（可评价批处理系统性能） – 响应时间快（可评价分时系统性能） – 截止时间保证（可评价实时系统性能） – 优先权准则
一旦进程处于运行状态，它就不断执行直到终止或因为等待 I/O而阻塞
• 抢占方式（ Preemptive Mode ）
当前运行的进程可能被OS中断并被放到就绪状态。 可提供较好的服务：避免了任何一个进程独占处理器太长时间
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
• 中级调度（ Intermediate-Level Scheduling ）
– 又称作中程调度 – 作用：将那些暂时不能运行的进程调至外存上等待 （此时进程状态称为挂起状态），当这些进程重又 具备运行条件、且内存又稍有空闲时，由中级调度 来决定把外存上的哪些又具备运行条件的就绪进程， 重新调入内存，并修改其状态为就绪状态，挂在就 绪队列上等待进程调度。 – 属于对换功能的一部分
3.2 调度算法
• 常用的调度算法
– – – – – – 先来先服务 短作业（进程）优先 优先权 高响应比优先 时间片轮转法 多级反馈队列（不作重点）
• 几。 （2）周转时间T：进程从 进入系统 到 运行结束所 经历的全部时间。 （3）带权周转时间T/Ts： 周转时间/服务时间。
0 5 10 15 20
A B C D E
第三章 处理机调度与死锁
3.2 调度算法
• 先来先服务（FCFS， First-Come-First-Served ）
进程 到达时间 服务时间 完成时间 周转时间 带权周转时间 平均
– 有利于长作业（进程），不利于短作业（进程）。
第三章 处理机调度与死锁
第三章 处理机调度与死锁
3.1 处理机调度的基本概念
• * 低级调度（ Low Level Scheduling ） – 又称作进程调度、短程调度 – 作用：用来决定就绪队列中的哪个进程应获得处理机， 然后再由分派程序执行把处理机分配给该进程的具体 操作。
– 两种调度方式 • 非抢占方式（ Non-preemptive Mode ）