北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷处理机调度处理机调度处理机调度处理机调度?调度的类型与模型调度的类型与模型?调度算法调度算法?实时系统中的调度实时系统中的调度?多处理机调度多处理机调度北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷问题问题问题问题?处理机管理的工作是对处理机管理的工作是对CPU资源进行合理的分 配使用，以提高处理机利用率，并使各用户公 平地得到处理机资源。这里的主要问题是处理 机调度算法和调度算法特征分析。资源进行合理的分 配使用，以提高处理机利用率，并使各用户公 平地得到处理机资源。这里的主要问题是处理 机调度算法和调度算法特征分析。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷调度的类型调度的类型调度的类型调度的类型?高级调度高级调度?中级调度中级调度?低级调度低级调度北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷高级调度高级调度高级调度高级调度?高级调度：又称为高级调度：又称为“宏观调度宏观调度”、“作业调度作业调度”。 从用户工作流程的角度，一次提交的若干个作 业，对每个作业进行调度。时间上通常是分钟 、小时或天。 从用户工作流程的角度，一次提交的若干个作 业，对每个作业进行调度。时间上通常是分钟 、小时或天。?接纳多少个作业接纳多少个作业?接纳那些作业接纳那些作业北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷中级调度中级调度中级调度中级调度?内外存交换：又称为内外存交换：又称为“中级调度中级调度”。从存储器资 源的角度。将进程的部分或全部换出到外存上 ，将当前所需部分换入到内存。指令和数据必 须在内存里才能被。从存储器资 源的角度。将进程的部分或全部换出到外存上 ，将当前所需部分换入到内存。指令和数据必 须在内存里才能被CPU直接访问。直接访问。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷低级调度低级调度低级调度低级调度?低级调度：又称为低级调度：又称为“微观调度微观调度”、“进程或线程 调度进程或线程 调度”。从。从CPU资源的角度，执行的单位。时 间上通常是毫秒。因为执行频繁，要求在实现 时达到高效率。资源的角度，执行的单位。时 间上通常是毫秒。因为执行频繁，要求在实现 时达到高效率。?非抢占式非抢占式?抢占式抢占式 时间片原则时间片原则 优先权原则优先权原则 短作业（进程）优先短作业（进程）优先北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷AdmitRunningReady SuspendExitReadyBlockedDispatch TimeoutEvent WaitEvent OccursReleaseBlocked SuspendSuspendNewEvent OccursActivateSuspendActivateAdmitSuspend宏观调度微观调度中级调度北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷调度的性能准则调度的性能准则调度的性能准则调度的性能准则?从不同的角度来判断处理机调度算法的性能， 如用户的角度、处理机的角度和算法实现的角 度。实际的处理机调度算法选择是一个综合的 判断结果。从不同的角度来判断处理机调度算法的性能， 如用户的角度、处理机的角度和算法实现的角 度。实际的处理机调度算法选择是一个综合的 判断结果。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷面向用户的调度性能准则面向用户的调度性能准则面向用户的调度性能准则面向用户的调度性能准则1 1?周转时间：作业从提交到完成（得到结果）所 经历的时间。包括：在收容队列中等待，周转时间：作业从提交到完成（得到结果）所 经历的时间。包括：在收容队列中等待，CPU 上执行，就绪队列和阻塞队列中等待，结果输 出等待批处理系统上执行，就绪队列和阻塞队列中等待，结果输 出等待批处理系统 外存等待时间、就绪等待时间、外存等待时间、就绪等待时间、CPU执行时间、执行时间、 I/O操作时间操作时间 平均周转时间、带权平均周转时间（平均周转时间、带权平均周转时间（T/Ts)?响应时间：用户输入一个请求（如击键）到系 统给出首次响应（如屏幕显示）的时间分 时系统响应时间：用户输入一个请求（如击键）到系 统给出首次响应（如屏幕显示）的时间分 时系统北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷面向用户的调度性能准则面向用户的调度性能准则面向用户的调度性能准则面向用户的调度性能准则2 2?截止时间：开始截止时间和完成截止时间 实时系统，与周转时间有些相似。截止时间：开始截止时间和完成截止时间 实时系统，与周转时间有些相似。?优先级：可以使关键任务达到更好的指标。优先级：可以使关键任务达到更好的指标。?公平性：不因作业或进程本身的特性而使上述 指标过分恶化。如长作业等待很长时间。公平性：不因作业或进程本身的特性而使上述 指标过分恶化。如长作业等待很长时间。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷面向系统的调度性能准则面向系统的调度性能准则面向系统的调度性能准则面向系统的调度性能准则?吞吐量：单位时间内所完成的作业数，跟作业 本身特性和调度算法都有关系批处理系统吞吐量：单位时间内所完成的作业数，跟作业 本身特性和调度算法都有关系批处理系统 平均周转时间不是吞吐量的倒数，因为并发执行的 作业在时间上可以重叠。如：在平均周转时间不是吞吐量的倒数，因为并发执行的 作业在时间上可以重叠。如：在2小时内完成小时内完成4个作 业，而每个周转时间是个作 业，而每个周转时间是1小时，则吞吐量是小时，则吞吐量是2个作业个作业/ 小时小时?处理机利用率：大中型主机处理机利用率：大中型主机?各种资源的均衡利用：如各种资源的均衡利用：如CPU繁忙的作业和繁忙的作业和 I/O繁忙（指次数多，每次时间短）的作业搭 配大中型主机繁忙（指次数多，每次时间短）的作业搭 配大中型主机北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷调度算法本身的调度性能准则调度算法本身的调度性能准则调度算法本身的调度性能准则调度算法本身的调度性能准则?易于实现易于实现?执行开销比执行开销比北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷调度算法调度算法调度算法调度算法?通常将作业或进程归入各种就绪或阻塞队列。 有的算法适用于作业调度，有的算法适用于进 程调度，有的两者都适应。通常将作业或进程归入各种就绪或阻塞队列。 有的算法适用于作业调度，有的算法适用于进 程调度，有的两者都适应。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷先来先服务先来先服务先来先服务先来先服务(FCFS, First Come First (FCFS, First Come First Service)Service)?这是最简单的调度算法，按先后顺序调度。这是最简单的调度算法，按先后顺序调度。 按照作业提交或进程变为就绪状态的先后次序，分 派按照作业提交或进程变为就绪状态的先后次序，分 派CPU； 当前作业或进程占用当前作业或进程占用CPU，直到执行完或阻塞，才 出让，直到执行完或阻塞，才 出让CPU（非抢占方式）。（非抢占方式）。 在作业或进程唤醒后（如在作业或进程唤醒后（如I/O完成），并不立即恢复 执行，通常等到当前作业或进程出让完成），并不立即恢复 执行，通常等到当前作业或进程出让CPU。最简单 的算法。最简单 的算法。?FCFS的特点的特点 比较有利于长作业，而不利于短作业。比较有利于长作业，而不利于短作业。 有利于有利于CPU繁忙的作业，不利于繁忙的作业，不利于I/O繁忙的作业。繁忙的作业。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷短作业优先短作业优先短作业优先短作业优先(SJF, Shortest Job First)(SJF, Shortest Job First)?又称为又称为“短进程优先短进程优先”SPN(Shortest Process Next)；这 是对；这 是对FCFS算法的改进，其目标是减少平均周转时间。算法的改进，其目标是减少平均周转时间。 对预计执行时间短的作业（进程）优先分派处理机 。通常后来的短作业不抢先正在执行的作业。对预计执行时间短的作业（进程）优先分派处理机 。通常后来的短作业不抢先正在执行的作业。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷SJFSJF的特点的特点的特点的特点?优点：优点： 比比FCFS改善平均周转时间和平均带权周转时间， 缩短作业的等待时间；改善平均周转时间和平均带权周转时间， 缩短作业的等待时间； 提高系统的吞吐量；提高系统的吞吐量；?缺点：缺点： 对长作业非常不利，可能长时间得不到执行；对长作业非常不利，可能长时间得不到执行； 未能依据作业的紧迫程度来划分执行的优先级；未能依据作业的紧迫程度来划分执行的优先级； 难以准确估计作业（进程）的执行时间，从而影响 调度性能。难以准确估计作业（进程）的执行时间，从而影响 调度性能。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷时间片轮转时间片轮转时间片轮转时间片轮转(Round Robin)(Round Robin)算法算法算法算法?前两种算法主要用于宏观调度，本算法主要用 于微观调度，设计目标是提高资源利用率。其 基本思路是通过时间片轮转，提高进程并发性 和响应时间特性，从而提高资源利用率；前两种算法主要用于宏观调度，本算法主要用 于微观调度，设计目标是提高资源利用率。其 基本思路是通过时间片轮转，提高进程并发性 和响应时间特性，从而提高资源利用率；北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷时间片轮转算法时间片轮转算法时间片轮转算法时间片轮转算法?将系统中所有的就绪进程按照将系统中所有的就绪进程按照FCFS原则，排 成一个队列。原则，排 成一个队列。?每次调度时将每次调度时将CPU分派给队首进程，让其执行 一个时间片。时间片的长度从几个分派给队首进程，让其执行 一个时间片。时间片的长度从几个ms到几百到几百 ms。?在一个时间片结束时，发生时钟中断。在一个时间片结束时，发生时钟中断。?调度程序据此暂停当前进程的执行，将其送到 就绪队列的末尾，并通过上下文切换执行当前 的队首进程。调度程序据此暂停当前进程的执行，将其送到 就绪队列的末尾，并通过上下文切换执行当前 的队首进程。?进程可以未使用完一个时间片，就出让进程可以未使用完一个时间片，就出让CPU（ 如阻塞）。如阻塞）。北京航空航天大学计算机科学与工程系北京航空航天大学计算机科学与工程系王雷王雷王雷王雷时间片长度的确定时间片长度的确定时间片长度的确定时间片长度的确定?时间片长度变化的影响时间片长度变化的影响 过长过长退化为退化为FCFS算法，进程在一个时间片内都 执行完，响应时间长。算法，进程在一个时间片内都 执行完，响应时间长。 过短过短用户的一次请求需要多个时间片才能处理 完，上下文切换次数增加，响应时间长。用户的一次请求需要多个时间片才能处理 完，上下文切换次数增加，响应时间长。?对响应时间的要求：对响应时间的要求：T(响应时间响应时间)=N(进程数目进程数目 )*q(时间片时间片)?就绪进程