c第三章处理机调度与死锁解读.ppt

3.1 处理机调度的层次 3.1.1 高级调度 3.1.2 低级调度 3.1.3 中级调度 作业调度 在每次执行作业调度时,都须做出以下两个决定。 (1)接纳多少个作业 取决于多道程序度(Degree of Multiprogramming),即允许多少个作业同时在内存中运行 作业太少―――资源利用率低 作业太多―――服务质量下降 (2)接纳哪些作业 即作业调度算法 先来先服务 短作业优先 优先权高优先 3.1.2 低级调度 低级调度(Low Level Scheduling)，也称为进程调度或短程调度(Short-Term Scheduling),决定就绪队列中的哪个进程应获得处理机，然后再由分派程序（Dispatcher）执行把处理机分配给该进程的具体操作。 它所调度的对象是进程（或内核级线程）。 是最基本的一种调度，在多道批处理、分时和实时3种类型的OS中，都必须配置这级调度。 1、低级调度的功能 （1）保存处理机的现场信息。指当前进程的，存入其PCB中。 （2）按某种算法选取进程。如优先数算法、轮转法等。改变选中进程的状态，即从就绪态为运行态，准备把处理机分配给它。 （3）把处理机分配给进程。由分派程序把处理机分配给进程。 2、进程调度的三个基本机制 为了实现进程调度，应具有以下三个基本机制： （1）排队器。将系统中所有的就绪进程按照一定的方式排成一个或多个队列。 （2）分派器（分派程序）。把由进程调度所选定的进程，从就绪队列中取出，然后进行上下文切换，将处理机分配给它。 （3）上下文切换。当对处理机进行切换时，会发生两次上下文切换操作。 第一次切换时，OS将保存当前进程的上下文，而装入分派程序的上下文，以便分派程序运行； 第二次切换时，将移出分派程序，而把新选进程的CPU现场信息装入到处理机的各个相应寄存器中。 3、低级调度的方式-1 常见的低级调度有非抢占方式和抢占方式两种 (1)非抢占方式(Non-preemptive Mode)(非剥夺方式) 一旦将处理机分配给某进程,便让该进程一直执行,直至该进程完成或阻塞时再分配给其他进程 引起进程调度的因素有以下几种 正在执行的进程执行完毕,或因发生某事件而不能再继续执行 执行中的进程因提出I/O请求而暂停执行; 在进程通信或同步过程中执行了某种原语操作,如P操作(wait操作)、Block原语等 优点:简单,系统开销小 缺点:不适合时间要求严格的实时系统 三种调度总结 运行频率: 低级调度中级调度高级调度 3.4.1 调度队列模型 3.4.2 选择调度方式和调度算法的若干准则 3.4.1 调度队列模型 3.4.2 选择调度方式和调度算法的若干准则 3.4.2 选择调度方式和调度算法的若干准则 1. 面向用户的准则 周转时间短（常用于批处理系统） 概念：作业从提交―― 完成的时间.分为： （1）驻外等待调度时间 （2）驻内等待调度时间 （3）执行时间 （4）阻塞时间 在OS中调度的实质是一种资源分配,因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法 对不同的系统和系统目标,通常采用不同的算法,如短作业优先,时间片轮转等 有些算法适用于作业调度,有些适用于进程调度,有些两者皆可 3.3 调 度 算 法 3.4.1 先来先服务和短作业优先算法 3.4.2 高优先权优先调度算法 3.4.3 基于时间片的轮转调度算法 3.3 调 度 算 法 3.4.1 先来先服务和短作业优先算法 3.4.2 高优先权优先调度算法 3.4.3 基于时间片的轮转调度算法 3.3 调 度 算 法 3.4.1 先来先服务和短作业优先算法 3.4.2 高优先权优先调度算法 3.4.3 基于时间片的轮转调度算法 3.4 实时调度 3.4 实时调度 2.抢占式调度算法(根据抢占发生时间的不同) (1)基于时钟中断的抢占式优先权调度算法 某实时任务到达后,若优先级高于当前正在执行任务的优先级,并不立即抢占当前任务的处理机,而是等到时钟中断到来后调度程序才剥夺当前任务的执行(几十至几毫米) 2.抢占式调度算法(根据抢占发生时间的不同) (1)… (2)立即抢占(Immediate Preemption)的优先权调度算法 一旦有外部中断,只要当前任务不在临界区内,便立即剥夺当前任务的执行,交处理机分配给要求中断的紧迫任务(几至0.1毫米…) 3.4 实时调度 假如在一个实时系统中,有两个周期性实时任务A和B,任务A要求每 20 ms执行一次,执行时间为 10 ms;任务B只要求每50 ms执行一次,执行时间为 25 ms 处理能力需求: 作业 3.5 产生死锁的原因和必要条件 3.5.1 产生死锁的原因 3