《调度与死锁操作系统进程管理》由会员分享，可在线阅读，更多相关《调度与死锁操作系统进程管理（138页珍藏版）》请在金锄头文库上搜索。
1、课程主要内容,操作系统引论（1章） 进程管理（2-3章） 存储管理（4章） 设备管理（5章） 文件管理（6章） 操作系统接口（7章）,Ch2 进程管理,进程的基本概念与控制 进程的基本概念 进程控制 线程的基本概念 UNIX中进程的描述与控制 进程同步与通信 进程同步 经典进程的同步问题 管程机制 进程通信 UNIX中进程的同步与通信,Ch3 处理机调度与死锁,调度是多道程序的关键 在多道程序环境下，一个作业从提交到执行，通常都要经历多级调度，如高级调度、低级调度、中级调度等，而系统的运行性能在很大程度上取决于调度 死锁的产生 在多道程序环境下，由于多个进程的并发执行，改善了系统资源的利用率并
2、提高了系统的处理能力 多个进程的并发执行也带来了新的问题死锁,Ch3 处理机调度与死锁,3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 UNIX系统中进程的调度,3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除 本章作业,3.1 处理机调度的基本概念,处理机资源管理需要解决的问题 依照什么原则分配处理机,即确定处理机调度算法 什么时候分配处理机,即需要确定处理机调度时机 如何分配处理机,即需要给出处理机调度过程 调度的层次 调度队列模型 选择调度方式和算法的若干准则,提交,输入管理系统,作业调度,SPOOLING 输出,后备,退出,完
3、成,就绪,阻塞,交换调度,进程调度（线程调度）,1. 调度的层次,1. 调度的层次（高级调度）,高级调度（High Scheduling） 长程/作业/宏观调度 从外存后备队列中选择作业进入就绪队列或挂起就绪 在批处理系统中，大多配有作业调度，但在分时系统及实时系统中，一般不配置 作业调度执行频率很低，通常为几分钟一次，甚至更久,补充：作业的相关概念,作业是用户交给计算机的具有独立功能的任务 在联机系统中，从用户登录系统到用户退出系统的整个过程，可以多次形成作业，用户每输入一条命令或运行一段程序都代表着一个作业步 作业在系统中也是动态的，从作业产生到作业消失的整个过程中，作业的状态跟随系统的运
4、作而发生变化 作业和进程相等同吗？,补充：作业的状态,提交状态 当用户正在通过输入设备向计算机提交作业时，作业处于提交状态 处于提交状态的作业，因为它的信息尚未全部进入系统，故不能被调度程序选中 后备状态 当用户完成作业的提交，作业已存在于辅助存储器中，在还未被调度执行前，称该作业处于后备状态 处于后备状态的作业具有完整的作业描述信息 处于后备状态的作业有资格进入主存储器，但何时进入主存储器，还需要看有否这样的时机,补充：作业的状态,执行状态 作业被调度进入主存储器，并以进程的形式存在，其状态就是执行状态 处于执行状态的作业并不意味着一定在CPU上运行，是否运行依赖于进程控制 处于执行状态的作
5、业可以有多个 停止状态 当作业已经完成其指定的功能，等待着与之相关的进程、资源，及其他描述信息的撤消，作业便进入停止状态,Process Management进程管理-processes 进程,高级调度需解决的问题 接纳作业数（内存驻留数） 即多道程序的“道或度” 太多: 可能会影响系统的服务质量(如周转时间太长) 太少: 将导致系统资源利用率和吞吐量的下降 应根据系统的规模和运行速度来确定，同时要求I/O型进程与CPU型进程中和调度 接纳策略（应将哪些作业从外存调入内存） 取决于采用何种调度算法(FCFS、短作业优先等),1. 调度的层次(高级调度),1. 调度的层次（低级调度）,低级调度(
6、Low Level Scheduling) 短程/CPU/进程/微观调度 进程调度任务 保存处理机的现场信息：在进行调度时首先需要保存当前进程的处理机的现场信息，如程序计数器、多个通用寄存器中的内容等 按某种算法选取进程：调度程序按某种算法，从就绪队列中选取一个进程，将其状态改为运行状态，并准备把处理机分配给它 把处理器分配给进程：由分派程序把处理器分配给进程,1. 调度的层次（低级调度）,进程调度机制 排队器：事先将系统中的所有就绪进程，按照一定的策略，排成一个或多个队列，每当有进程转变为就绪状态时，排队器便将它插入到相应的就绪队列 分派器：依据进程调度程序所选定的进程，将其从就绪队列中取出
7、，然后进行进程间的上下文切换，将处理机分配给新选出的进程 上下文切换器：在对处理机进行切换时，会发生： OS将保存当前进程的上下文，装入分派程序的上下文，以便分派程序运行 移出分派程序的上下文，装入新选进程上下文,进程调度机制,1. 调度的层次（低级调度）,进程调度方式 非抢占方式：一旦把处理机分配给某进程后，便让该进程一直执行，直到该进程完成或因某事件而被阻塞，才再把处理机分配给其它进程，决不允许某进程抢占已分配出去的处理机 实现简单，系统开销小，常用于批处理系统 实时性差，不利于处理紧急任务，故实时、分时系统不宜采用,1. 调度的层次（低级调度）,进程调度方式 抢占方式: 允许调度程序根据
8、某种原则（时间片、优先权、短进程优先），停止正在执行的进程，而将处理机重新分配给另一进程 有利于处理紧急任务，故实时与分时系统中常采用 “抢占” 必须遵循的原则 优先权原则 短进程优先原则 时间片原则,1. 调度的层次（中级调度）,中级调度 中程/交换调度 在内存和外存对换区之间按照给定的原则和策略选择进程对换，以解决内存紧张问题，从而提高内存的利用率和系统吞吐量 常用于分时系统或具有虚拟存储器的系统中,2. 调度队列模型,在OS中的任何一种调度中，都将涉及到进程队列 仅有进程调度的调度队列模型 具有高级和低级调度的调度队列模型 同时具有三级调度的调度队列模型,仅有进程调度的调度队列模型,进程
9、调度,时间片完,具有高级和低级调度的调度队列模型,时间片完,同时具有三级调度的调度队列模型,时间片完,进程调度,CPU,进程完成,等待事件,作业调度,中程调度,3. 选择调度方式和算法的若干准则,面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先权准则 面向系统的准则 系统吞吐量 处理机利用率好 各类资源平衡利用,最优准则 最大的CPU利用率 最大的吞吐量 最短的周转时间 最短的等待时间 最短的响应时间,周转时间（常用于批处理系统）定义：作业从提交 完成的时间时间组成： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间,周转时间不具有区分实际运行时间长短
10、的性质,3. 选择调度方式和算法的若干准则,平均周转时间带权周转时间 平均带权周转时间,平均周转时间可以衡量不同调度算法对相同任务流的调度性能,带权周转时间衡量长短任务的差别，故带权周转时间W越小越好,3. 选择调度方式和算法的若干准则,R: 提供服务时间,3. 选择调度方式和算法的若干准则,响应时间快（对交互性作业） 概念：键盘提交请求到首次响应时间 时间组成 输入传送时间 处理时间 响应传送时间 截止时间的保证（特别于实时系统） 优先权准则（即需要抢占调度）,时间片完,CPU,进程完成,事 件 出 现,等待事件,进程调度,中级调度,作业调度,回顾:具有三级调度的调度队列模型,3.2 调度算
11、法,具体考虑指标 CPU利用率：使CPU尽量处于忙碌状态 吞吐量：单位时间内所处理计算任务的数量 周转时间：从计算任务就绪到处理完毕 响应时间：从任务就绪到开始处理 系统开销：系统调度进程过程中所付出的时空代价,3.2 调度算法,衡量就绪任务处理效率的度量标准 周转时间(turnaround time): 由就绪开始时刻到处理完毕时刻的时间 平均周转时间(average turnaround time): 所有进程的周转时间之和与处理时间之和的比值得 等待时间(waiting time)：周转时间与处理时间差 平均等待时间(average waiting time)：所有进程周转时间与进程个数
12、之比值,3.2 调度算法,根据系统的资源分配策略所规定的资源分配算法 先来先服务调度算法 短作业/进程优先调度算法 时间片轮转调度算法 优先权调度算法 高响应比优先调度算法 多级反馈队列调度算法,基本思想:,对于作业调度：从后备作业队列中（按进入的时间顺序排队）选择队首一个或几个作业，调入内存，创建进程，放入就绪队列对于进程调度：从就绪队列中选择一个最先进入队列的进程，将CPU分配于它,一、先来先服务（FCFS）调度算法,一、先来先服务（FCFS）调度算法,按照进程申请CPU的次序，即进入就绪状态的次序来调度 Process Burst time P1 27ms P2 3ms P3 5ms 假
13、定进程到达次序为P1, P2, P3，CPU调度状况可用Gantt 图表示,平均等待时间=(0+27+30)/3=19毫秒,平均周转时间=(27+30+35)/3=30.67毫秒,例1： 作业名 到达时间 服务时间A 0 1B 1 100C 2 1D 3 100,一、先来先服务（FCFS）调度算法,完成时间-到达时间,开始时间+服务时间,上一个进程的完成时间,1 101 100 1,101 102 100 100,102 202 199 1.99,例2：下面三个作业几乎同时到达系统并立即进行FCFS调度：作业名 所需CPU时间作业1 28作业2 9作业3 3 假设提交顺序为1、2、3，则平均作
14、业周转时间T = 若提交顺序改为作业2、1、3，则T= 若提交顺序改为作业3、2、1，则T= FCFS调度算法的平均作业周转时间与作业提交的顺序有关,(28+37+40)/3 = 35,29,18,一、先来先服务（FCFS）调度算法,FCFS调度算法评价,简单，具有公平的优点，不会出现饿死情况 效率不高 有利于长作业（进程）不利于短作业（进程） 有时为了等待长作业的执行，而使短作业的周转时间变得很大，从而平均周转时间也变大 现在操作系统中，已很少用该算法作为主要调度策略，尤其是在分时系统和实时系统中 但FCFS常被结合在其它调度策略中使用,一、先来先服务（FCFS）调度算法,短作业优先调度算法
15、（SJF） 从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行,短进程优先调度算法（SPF） 从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它 可采用抢占或者非抢占调度方式,二、短作业/进程优先调度算法,执行顺序：,SJF/SPF（非抢占式举例）,A,0,3,3,1,0,3,A,B,C,D,E,2,4,6,8,6,4,5,2,B,3,9,7,1.17,9,11,3,1.5,11,15,11,2.75,15,20,14,2.8,E,C,D,7.6,1.84,FCFS：ABCDE SJF: ADBEC,FCFS和的SJF比较,优点 能有效降低作业/进程的平均等待时间 提高吞吐量 能有效缩短作业/进程的周转时间缺点 对长作业/进程不利 不考虑作业/进程的紧迫程度 作业执行时间仅为估计*,二、短作业/进程优先调度算法,SRT (Shortest Remaining Time First)是针对 SPF 增加了抢占机制的一种调度算法，它总是选择预期剩余时间最短的进程只要新进程就绪，且有更短的剩余时间，调度程序就可能抢占当前正在运行的进程,基本思想:,补充: 最短剩余时间调度算法（SRT）,SRT 的调度次序,
