操作系统3讲义

《操作系统3讲义》由会员分享，可在线阅读，更多相关《操作系统3讲义（74页珍藏版）》请在金锄头文库上搜索。

1、第三章 处理机调度与死锁,3.1 处理机调度的基本概念（掌握） 3.2 调度算法（理解） 3.3 实时调度（理解） 3.4 多处理系统的调度(自学) 3.5 产生死锁的原理和必要条件（理解） 3.6 预防死锁的方法（掌握） 3.7 死锁的检测与解除,3.1 处理机调度的基本概念,一、高、中、低级调度 二、调度队列模型 三、选择调度方式和调度算法的准则,一、高、中、低级调度,分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，因此处理机调度性能直接决定处理机的利用率及系统性能。 处理机的调度问题是操作系统的核心问题。其调度过程与OS类型、作业类型、内存组织密切有关。 一个基

2、于虚拟存储的批处理型作业要经历作业调度（高）、进程调度（低）、存储对换（中）三个过程，而一个终端型作业或实时作业只须经过进程调度,1. 高级调度（又称作业调度）,主要作用：把外存上处于后备队列中的作业调人内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行 。 涉及的主要问题： 调入多少作业？ 调入哪些作业？,取决于系统最多允许多少作业同时运行。,取决于所采用的调度算法，是先来先服务、短作业优先还是优先高者优先。,课堂提问：分时或实时系统是否需要作业调度？,2. 低级调度（又称进程调度）,主要作用：用来决定就绪队列中的哪个进程应获得处理机，再由分派程序把处理机分配给

3、该进程的具体操作。 解决方案： 非抢占方式 抢占方式,(1) 非抢占式方式(Non-preemptive Mode) 定义：进程一旦获得处理机，则一直执行，直至该进程完成或发生某事件而被阻塞时，才释放处理机，决不允许其他进程抢占已分配的处理机。 特点：实现简单、系统开销小，适合批处理系统，但不适合实时系统。 (2) 抢占式方式（Preemptive Mode) 定义：允许调度程序根据某种原则，去暂停正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。 抢占原则：优先权原则、短作业优先原则、时间片原则 特点：调度程序的运行频率高，要求其算法不能太复杂。,3. 中级调度（又称中程调度）,引

4、入目的： 为了提高内存利用率和系统吞吐量。 基本手段： 当进程挂起时将它们调到外存中等待，激活时重新调入内存，进入就绪状态 可见，中级调度的实质为虚拟存储管理,二、调度队列模型,1. 仅有进程调度的调度队列模型,2. 具有高级和低级调度的调度队列模型,外存,内存,阻塞队列,就绪队列的形式可以是优先级队列，也可以是无序链表,思考：无序链表方式能否实现优先级调度？,3. 同时具有三级调度的调度队列模型,外存,内存,外存,外存,内存,三、选择调度方式和调度算法的准则,1. 面向用户的准则 周转时间短 响应时间快 截止时间的保证 优先级准则 2. 面向系统的准则 系统吞吐量高 处理机利用率高 各类资源

5、的平衡利用,周转时间是作业被提交系统开始到完成为止的时间间隔，包括作业在后备队列上等待调度的时间、进程在就绪队列上等待调度的时间、在CPU上执行的时间、等待I/O操作完成的时间。 用于评价多道批处理系统。,响应时间是从用户提交请求开始，直到系统产生响应为止的时间，包括传送键盘输入的时间、处理键盘输入的时间、回送响应信息的时间。 用于评价分时系统。,截止时间是一个任务必须开始执行的最迟时间，或者必须完成的最迟时间。 用于评价分时系统。,系统吞吐量是指在单位时间内系统所完成的作业数。 用于评价批处理系统。,3.2 调度算法,一、先来先服务和短作业优先调度算法 二、高优先权优先调度算法 三、基于时间

6、片的轮转调度算法,一、先来先服务和短作业优先调度算法,1. 先来先服务调度算法FCFS 应用：既可用于作业调度，也可用于进程调度。 特点：有利于长作业（进程），不利用短作业（进程） 2. 短作业优先调度算法SJ(P)F 应用：既可用于作业调度，也可用于进程调度。 特点：对长作业不利、未考虑作业的紧迫性、作业执行时间长短只能进行估计,示例1,以下A、B、C、D四个作业按FCFS算法调度，它们分别到达系统的时间、要求服务的时间、开始执行的时间、各自的完成时间，周转时间和带权周转时间，见下表：,注：周转时间=完成时间-到达时间 带权周转时间=周转时间/服务时间,示例2,以下A、B、C、D、E五个进程

7、按FCFS或SJF算法调度，其周转时间和带权周转时间分别见下表：,二、高优先权优先调度算法,可用于批处理系统和实时系统，可用于作业调度和进程调度 1. 优先权调度算法的类型 非抢占式优先权算法：处理机只分配给在就绪队列中优先权最高的进程，直到进程完成或阻塞。 抢占式优先权算法：处理机只分配给在就绪队列中优先权最高的进程，但在该进程执行过程中允许重新分配给更高优先权的进程。,2. 优先权的类型,(1)静态优先权：在创建进程时确定的，且在进程的整个运行期间保持不变 (2)动态优先权：在创建进程时赋予优先权初始值，之后随进程执行或阻塞等待时间而动态改变。,特点：简单易行、系统开销小，但不够精确。,特

8、点：调度性能更好，但算法复杂，系统开销大。,思考：依据什么来确定进程的优先权？,答：根据以下三个方面确定进程的优先权 进程类型：系统进程的优先权用户进程的优先权 进程对资源的需求：需求内存少的进程优先 用户要求：考虑进程的紧迫程序或用户所承担的费用,3. 高响应比优先调度算法,该算法优缺点： 既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。 利用该算法时，每次调度之前，都须先做响应比的计算，会增加系统开销。,三、基于时间片的轮转调度算法,可用于分时系统 1. 时间片轮转法 算法如下： S1：所有进程按FCFS的原则进入就绪队列等待调度； S2：把CPU分配给队首进程，并

9、令其执行一个时间片； S3：若在时间片内该进程执行完成，则该进程从就绪队列中移除；否则计时器发出时钟中断请求； S4：停止执行该进程，并将它送入就绪队列的队尾； S5：重复S2S4，直到就绪队列所有进程执行完成。,2. 多级反馈队列调度算法,算法如下： S1：设置多个就绪队列，且分别赋予不同的优先级； S2：新进程先放入第一队列的末尾，根据FCFS原则等待调度； S3：把CPU分配给队首进程，并令其执行一个时间片； S4：该进程若在时间片内执行完成，则从所在就绪队列中移除；否则计时器发出时钟中断请求； S5：将该进程送入第二队列的队尾，同样地按FCFS原则等待调度执行； S6：如果该进程在第二

10、队列中运行一个时间片后仍未完成，再依次将它放入第三队列，； S7：当第i-1队列的所有进程完成时，继续执行第i队列中的进程。,多级反馈队列调度算法原理图,3多级反馈队列调度算法的性能,多级反馈队列调度算法具有较好的性能，能较好地满足各种类型用户的需要。 (1) 终端型作业用户：只要能在第一队列所规定的时间片内完成，可使终端型作业用户都感到满意。 (2) 对短作业有利，周转时间较短。 (3) 对长作业，将依次在第1，2,，n个队列中运行，然后再按轮转方式运行，因此不必担心其作业长期得不到处理。,3.3 实时调度,一、实现实时调度的基本条件 二、实时调度算法的分类 三、常用的几种实时调度算法,一、

11、实现实时调度的基本条件,因为实时系统的任务往往对截止时间有明确要求，因此实现实时调度必须具备以下条件： 1. 提供必要的信息 2. 系统处理能力强 3. 采用抢占式调度机制 4. 具有快速切换机制,包括就绪时间、开始截止时间或完成截止时间、处理时间、资源要求、优先级。,当需要处理多个实时任务时，若处理机的处理能力不足，则有可能让某些实时任务不能得到及时处理。,让优先级高者分配处理器，以满足对截止时间的要求。,系统处理能力问题,假设有m个周期性的硬实时任务，其处理时间为Ci，周期时间为Pi，处理机个数为N，则必须满足以下要求系统才可调度：,思考：在单处理机系统中，若有6个实时任务，其周转时间均为

12、50ms，每次的处理时间为10ms，请问该系统是否可调度？,二、实时调度算法的分类,1. 非抢占式调度算法 非抢占式轮转调度算法 非抢占式优先调度算法 2. 抢占式调度算法 基于时钟中断的抢占式优先权调度算法 立即抢占的优先权调度算法,调度程序每次选择队列中的第一个任务投入运行。当该任务完成后，便把它挂在轮转队列的末尾，等待下次调度运行,如果在系统中存在着实时要求较为严格的任务，则用该算法，为这些任务赋予较高的优先级。当这些实时任务到达时，把它们安排在就绪队列的队首，等待当前任务自我终止或运行完成后，才能被调度执行。,某实时任务到达后，如果该任务的优先级高于当前任务的优先级，这时并不立即抢占当

13、前任务的处理机，而是等到时钟中断到来时，调度程序才剥夺当前任务的执行，将处理机分配给新到的高优先权任务。,一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。,实时调度算法示意图,三、常用的几种实时调度算法,1. 最早截止时间优先调度算法 2. 最低松驰度优先调度算法,1. 最早截止时间优先调度算法 EDF(Earliest Deadline First),基本要点：该算法要求在系统中保持一个实时任务就绪队列，该队列各任务按开始截止时间的早晚排序；具有最早截止时间的任务排在队列的最前面。调度程序总是选择就绪队列中的第一个任务，为之分配处理机

14、，使之投入运行。,非抢占式最早截止时间优先调度示例图,2. 最低松驰度优先调度算法 LLF(Least Laxity First),(1) 基本思想 根据任务紧急程度（或松驰程度）来确定作务的优先级。 (2) 算法要点 首先将就绪队列中的各实时任务按松弛度排序，松弛度值最小的任务排在队列最前面，然后由调度程序选择队首任务执行。,松驰度L=必须完成时间-其本身的运行时间-当前时间,例：设两个实时任务A和B，A要求每20ms执行一次，执行时间为10ms；任务B只要求每50ms执行一次，执行时间为25ms。,LA1=20-10-0=10ms LB1=50-25-0=25ms,LA2=40-10-10

15、=20ms LB1=50-25-10=15ms,LA2=40-10-30=0ms LB1=50-5-30=15ms,LA3=60-10-40=10ms LB1=50-5-40=5ms,LA3=60-10-45=5ms LB2=100-25-45=30ms,LA4=80-10-70=0 LB2=100-10-70=20,3.4 多处理系统的调度,多处理系统分为紧密耦合型和松散耦合型。前者通过高速总线实现多个处理机间的互连，共享主存和I/O设备，由操作系统实施统一的调度和控制。后者通过网络技术实现多台计算机的互连，达到分布式存储和分布式运算的目的。 多处理系统又分为对称型和非对称型。前者的各处理机

16、的结构和功能相同，称为同构系统；后者各处理机的结构和功能不相同，称为异构系统。,3.4.1 多处理机系统中的进程分配方式,1. 对称多处理机系统中的进程分配方式 静态分配：一个进程固定分配给一个处理机 动态分配：一个进程可动态分配给任一处理机 2. 非对称多处理机系统中的进程分配方式 采用主-从操作系统 进程调度由主机运行 用户程序由从机执行。,3.4.2 进程的调度方式,1. 自调度方式 2. 成组调度方式 3. 专用处理机分配,1. 自调度方式,调度机制：设置一个公共就绪队列，所有的处理器在空闲时都从该队列中获取进程来运行。 优点：沿用单处理机系统的就绪队列和调度算法就可实现，因此简单；只要就绪队列不空，就不会出现处理机空闲的情况，因此有利用提高处理机的利用率。 缺点：各处理机互斥地共享就绪队列，易形成瓶颈；进程在整个生命期中可能因更换处理机而造成 Cache效率低；同属一个进程的各线程因很难同时获得处理机而造成切换频繁。,2. 成组调度方式,调度机制：将一个进程中的一组线程，分配到一组处理器上执行。 具体办法： 面向所有应用程序平均分配处理器时间。 面向所有线