操作系统第三章调度与死锁

《操作系统第三章调度与死锁》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章调度与死锁进程调度的核心是调度算法。进程调度是实现多道程序系统的关键，直接影响到操作系统的性能，是本章讨论的主要问题。§3.1调度的基本概念(一）作业从进入系统到完成，可能要经历三级调度过程：一、调度的类型和模型1、高级调度又称为作业调度，它决定将哪些在外存上处于后备状态的作业调入主机内存，准备执行。因此，有时把它称为接纳调度。2、低级调度又称为进程调度，它决定就绪队列中哪个进程将获得处理机，并实际执行将处理机分配给进程的操作。执行分配处理机的程序称为分派程序。3、中级调度中级调度的主要作用是在内存和外存之间进行进程交换，以解决内存紧张的问题。如它将内存中处于等待状

2、态的某些进程调至外存对换区，以腾出内存空间，而将外存对换区上已具备运行条件的进程重新调入内存，准备运行。故又称为交换调度。阻塞状态就绪状态执行状态调度I/O请求进程释放时间片到后备作业队列§3.1调度的基本概念(二）CPU就绪队列内存外存阻塞队列作业调度等待事件中级调度即交换调度交换文件就绪队列阻塞队列三级调度的模型§3.1调度的基本概念(三）作业调度是确定哪些作业可以被调入内存。进程调度是确定哪个进程可以占有CPU并执行。作业调度是进程调度的基础，作业被调入内存后，是以进程的形式执行的。在一个OS中进程调度与作业调度的算法是一致的。？问题？1。进程调度与作业调度之间（功

3、能、调度算法）有何区别和联系？2。三级调度中，最核心的是那一级调度？为什么？各级调度间的关系§3.1调度的基本概念(四）作业步—将一个作业划分为若干个顺序处理的步骤，作业步相互独立又相互关联。作业—是用户请求计算机系统执行的一次独立的上机任务，是能够共享公共资源区域的一族有关进程（家族）。从静态观点看，作业由控制命令系列、程序集、数据集三部分构成。补充：关于作业的概念作业控制块—JCB（JobControlBlock）用于描述作业。定义为记录类型（作业名、优先级、建立时间、状态外存地址、大小等）。作业状态—作业在其生命期中，共有四种状态：关于作业的状态作业状态—作业在其生

4、命期中，共有四种状态：进入、后备、运行、完成完成执行就绪阻塞进入后备内存运行提交作业调度完成问题：引起进程调度的原因有哪些？§3.1调度的基本概念(五）非抢占式（非剥夺式）进程一旦被调度，就一直占有CPU，直到完成或因发生某事件而被阻塞（I/O请求）。抢占式（剥夺式）进程未执行完，可由调度程序剥夺其CPU，另分配给别的进程。抢占的原因有：优先级、时间片、短进程等。在OS中，进程调度的方式分为两类。二、进程调度的方式§3.1调度的基本概念(六）记录系统中所有进程的执行情况确定分配处理机的原则（调度算法）分配处理机给进程回收处理机、进行进程上下文切换三、进程调度的功能显然，进

5、程调度的核心问题是调度算法。§3.1调度的基本概念(七）1。周转时间短周转时间TT（TumaroundTime）对作业—从作业提交到完成。对进程—第一次进入就绪队列到运行结束。平均周转时间ATT（AverageTumaroundTime）ATT=[∑Ti]带权平均W=[∑]其中：Ti各进程的TTTri实际执行时间2.响应时间快响应时间RT（ResponseTime）—输入键盘命令到屏幕显示结果。四.调度算法准则调度算法应该尽可能提高资源利用率，减少CPU空闲时间,公平服务。可从以下方面考虑：1ni=1nTiTrii=1n1n§3.2调度算法（一）先来先服务（FCFS）

6、算法最短CPU运行期优先（SCBF）算法最高优先权（HPF）算法时间片轮转（RR）算法多级反馈队列算法思考题1、各种调度算法的特点、性能如何？适宜于哪类OS？2。最高优先权算法中，动态优先权有何实际意义？常用调度算法§3.2调度算法（二）一.、先来先服务（FCFS）算法FCFS（FirstComeFirstServer）法，又称为先进先出（FIFO）算法，就绪进程按照进入的先后次序排列，调度程序总是选择队首的进程执行。这是一种非剥夺式的调度算法，简单、易实现。对短进程易出现等待时间长，服务质量差。该算法有利于CPU繁忙型的进程，不利于I/O繁忙型的进程。该算法只能用于辅助

7、算法。§3.2调度算法（二）二、最短CPU运行期优先（SCBF）算法n+1nnt该算法优于FCFS，但长进程等待时间长，估算误差较大。SCBF（ShortestCPUBurstFirst），即调度程序总是选择CPU运行时间最短的进程执行。其中为估计的第n个CPU周期。tn为实际值。为控制值，0≤≤1，常取0.5n对最短CPU运行期的估算，依赖于系统的下一个CPU周期中，实现较困难。进程的CPU时间的估算公式：n+1§3.2调度算法（三）三、最高优先权（HPF）算法调度程序每次都将CPU分配给就绪队列中具有最高优先级（Highe