计算机操作系统（第二版）课件：进程调度算法

10月14日,鸿蒙新里程碑！美的发布物联网操作系统1.010月22日,HarmonyOS3.0.0开发者预览版全新发布Harmony设计系统ArkUI3.0ArkCompiler3.0DevEcoStudio3.0TS/JSAPI操作系统实验室：探索下一代云网端融合架构下的未来操作系统，以及着力于新一代移动计算平台的研究XR实验室：拓展在智能计算技术领域以及交互领域的研究布局。阿里达摩院增设两大实验室进程调度先来先服务调度算法（FCFS）

短作业优先调度算法（SJF）

高响应比优先调度算法（HRRF）时间片轮转调度算法

优先级调度算法多级队列调度算法多级反馈队列调度算法3.5.2进程调度算法先来先服务调度算法（FCFS）

短作业优先调度算法（SJF）

高响应比优先调度算法（HRRF）时间片轮转调度算法

优先级调度算法

说明优先级调度的两种方式、性能特点优先级设计：静态、动态

案例分析（讲授+讨论）多级队列调度算法多级反馈队列调度算法3.5.2进程调度算法3.5进程调度基本概念实现思路性能分析如何改进1.先来先服务调度算法（FCFS）作业名提交时间要求执行时间开始执行时间完成时间周转时间带权周转时间ABCD1.01.21.41.52.03.01.20.31.03.06.07.23.06.07.27.52.04.85.86.01.01.64.820.0平均周转时间：T＝（2.0+4.8+5.8+6.0）/4=4.65平均带权周转时间：W＝(1+1.6+4.8+20)/4=6.85优点：实现简单；缺点：对长作业有利，对短作业不利；平均周转时间可能较长；没有考虑任务的紧迫性3.5.2进程调度算法3.5进程调度=周转时间/

要求执行时间=完成时间－

提交时间总结其优点、缺点？2.短作业（进程）优先调度算法3.5.2进程调度算法3.5进程调度作业名提交时间要求执行时间开始时间完成时间周转时间带权周转时间ABCD1.01.21.41.52.03.01.20.3算法分类：

--非抢占式调度：--抢占式调度算法：按估计运行时间抢占按剩余运行时间抢占非抢占式调度：A、B、C、D四个作业的调度顺序应该是怎样的？算法的基本概念、如何实现？2.短作业（进程）优先调度算法非抢占式调度：3.5.2进程调度算法作业名提交时间要求执行时间开始时间完成时间周转时间带权周转时间ADCB1.01.51.41.22.00.31.23.01.03.03.34.53.03.34.57.52.01.83.16.31.06.02.62.1平均周转时间：T＝（2.0+1.8+3.1+6.3）/4=3.3平均带权周转时间：W＝(1+6+2.6+2.1)/4=2.93FCFS:T=4.65;W=6.852.短作业（进程）优先调度算法抢占式调度：按剩余时间抢占作业名提交时间要求执行时间开始时间完成时间周转时间带权周转时间ABCD1.01.21.41.52.03.01.20.3平均周转时间：平均带权周转时间：1.01.0

AB1.2

C1.4

D1.5

ACDDC1.8

C2.9

A4.5

B7.5

AB4.53.51.754.57.56.32.11.42.91.51.251.51.80.31.0T＝（3.5+6.3+1.5+0.3）/4=2.9

W＝(1.75+2.1+1.25+1)/4=1.533.5.2进程调度算法2.短作业（进程）优先调度算法优缺点：优点：使作业的平均周转时间最短；证明：考察4个作业A、B、C、D，同时到达系统，其运行时间分别为a、b、c、d，且abcd

D时间ACaa+ba+b+ca+b+c+dBA、B、C、D的周转时间分别为a、a+b、a+b+c和a+b+c+d，因此平均周转时间为：(4a+3b+2c+d)/4，显然，当abcd时，平均周转时间最小。缺点：对长作业不利（饥饿状态）；对紧迫作业不利；估计运行时间不准，难以真正做到短作业（进程）优先。

总结其优点、缺点？3.5.2进程调度算法3.高响应比优先调度算法（HRRF）作业名提交时间要求执行时间ABCD1.01.21.41.52.03.01.20.3顺序：A,D,C,B3.3s3.5.2进程调度算法按高响应比优先调度算法进行调度，给出下述作业的调度顺序，并计算平均周转时间及带权周转时间。要求写出计算过程。小组讨论（7分钟）基本概念？选择非强占式or抢占式？如何实现？3.高响应比优先调度算法（HRRF）

优点：

首先照顾了短作业；

同时也考虑了长作业的等待时间，相对比较公平。

缺点：

每次调度都需要重新计算所有作业或就绪进程的响应比，系统开销较大；常采用非抢占调度方式。

不能保证紧迫型任务得到及时处理。总结该算法的优点、缺点？3.5.2进程调度算法时间片太大或太小有什么不好？交互型系统就绪队列，FCFS交互型请求CPU进程调度运行完成时间片到，未完成时间片大小的确定：T=Nq系统的响应时间就绪进程的数量进程调度及切换开销CPU的运行速度4、

时间片轮转调度算法3.5.2进程调度算法算法的基本概念、如何实现？时间片轮转调度算法的改进将固定时间片改为可变时间片：每当一轮开始时，系统根据响应时间及当前就绪进程数目重新计算时间片：q=T/N将单就绪队列改为多就绪队列：

如按优先级组建多个就绪队列。4、

时间片轮转调度算法有哪些改进思路呢？3.5.2进程调度算法5、优先级调度算法优先级进程调度算法的类型非强占式优先级调度算法强占式优先级调度算法批处理系统、要求不严格的实时系统非强占式优先级调度算法要求严格的实时系统哪个小组分析下这两种调度方式的概念、性能特点及适用场景？解决复杂问题：

折中！5、优先级调度算法优先级设计进程类型静态优先级进程对资源的需求进程的估计运行时间如何确定进程的静态优先级呢？静态优先级有什么不好呢？“饥饿”问题1973年工作人员关闭MIT的IBM7094时，发现一个1967年提交的低优先级进程一直未得到运行动态优先级如何设计动态优先级呢？随等待时间延长而提升随占用CPU时间延长而降低随剩余运行时间缩短而提升完成I/O操作后提升5、优先级调度算法Win2000的优先级策略基于动态优先级抢占的多处理机线程调度系统进程静态优先级实时高级中上中级中下空闲

③进程与线程优先级的关系

进程优先级实时24高级13中上10中级8中下6空闲4Time_critical311515151515Highest2615121086Above_normal251411975Normal241310864Below_normal23129753Lowest22118642Idle2111111Win2000的优先级策略5、优先级调度算法线程优先级5、优先级调度算法Win2000的优先级策略线程I/O操作完成线程信号量或事件等待结束前台进程中的线程完成一个等待操作

线程动态优先级提升策略线程处于就绪状态超过一定时间降低策略线程在CPU上运行完一个时间配额哪个小组来分析下每种优先级调整策略的目的是什么？5、优先级调度算法

linux及华为openEuler系统的调度策略调度类表示一个具体实现的调度器停机调度类调度停机进程，如迁移线程限期调度类调度限期进程实时调度类调度实时进程公平调度类调度普通进程空闲调度类调度空闲线程，即0号线程优先级逐级降低5、优先级调度算法

linux及华为openEuler系统的调度策略CFS调度器调度普通进程虚拟运行时间VTi当两个进程实际运行时间T相等时，nice值小的进程，其VTi越大还是越小？将nice值转换为Wi5、优先级调度算法团队自主研发：HDU-edge-OS无人车、无人机、无人船等实时控制系统基于静态优先级抢占的多处理器进程调度算法关于优先级大小的论述中，正确的是（）计算型作业的优先级，应高于I/O型作业的优先级用户进程的优先级，应高于系统进程的优先级在动态优先级中，随着作业等待时间的增加，其优先级降低在动态优先级中，随着进程执行时间的增加，其优先级降低ABCD提交单选题10分下列调度算法中，不可能导致饥饿现象的是（）静态优先级调度非抢占式短作业优先时间片轮转抢占式短作业优先ABCD提交单选题10分下列选项中，提升进程优先级的合理时机有（

）进程时间片用完进程刚完成I/O操作，进入就绪队列进程长期处于就绪队列中进程从就绪状态转为运行状态ABCD提交刚创建完成的新进程E刚被V操作唤醒的进程F当进行进程调度时，提升就绪队列中进程的优先级G多选题10分若某单处理机多进程系统中有多个就绪进程，则下列关于处理机调度的叙述中，错误的是（）在进程结束时能进行处理机调度创建新进程后能进行处理机调度在进程处于临界区时不能进行处理机调度在系统调用完成并返回用户态时能进行处理机调度ABCD提交单选题10分系统中设置多个就绪队列，每个队列优先级不同；每个队列有自己独立的进程调度算法；

一个进程依据其属性固定位于某个就绪队列中。实时进程队列系统进程队列交互式进程队列批处理进程队列

……进程队列最高优先级最低优先级CPU各队列分别采用什么调度算法更合适呢？6、

多级队列调度算法进程采用静态优先级如果采用非抢占式调度，该如何实现？如果采用抢占式调度，该如何实现？按调度级别（优先级）设置多个就绪进程队列按优先级（或就绪队列）设置不同时间片各级就绪队列按FCFS组织，按时间片调度，每个进程被调度后运行一个当前队列的时间片长度最后一级按时间片轮转方式组织调度各队列间按抢占式优先级算法调度新进程运行完成运行完成CPU第二个就绪队列，FCFSS2时间片到，未完成运行完成时间片到，未完成CPU第n个就绪队列，FCFSSn时间片到，未完成（时间片：S1<S2<Sn）CPU第一个就绪队列，FCFSS1分析该算法的性能优缺点？7、

多级反馈队列调度算法8.调度算法设计举例

运行首先选择

100ms

因I∕O

而等待

高优先就绪

低优先就绪进程调度进程调度时间片到请求I/OI/O完成其次选择

500ms分析：1）进程状态设置？调度队列设置？2）这个算法实现的思路是怎样的？3）调度效果是怎样的8.调度算法设计举例

运行首先选择

100ms

因I∕O

而等待

高优先就绪

低优先就绪进程调度进程调度时间片到请求I/OI/O完成其次选择

500ms105①进程状态运行状态就绪状态因I/O而等待状态②队列结构低优先就绪队列高优先就绪队列因I/O而等待队列③进程调度算法：优先调度与时间片调度相结合的调度算法

ⅰ当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。ⅱ当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。④调度效果：

优先照顾I∕O量大的进程；适当照顾计算量大的进程。3.5.1进程调度基本概念各种调度算法的基本概念、性能特点本节知识小结哪个小组来总结下？3.5进程调度3.5.3多处理器调度多处理器调度的背景CPU缓存内存总线鲲鹏920处理器架构8个集群计算DIE8个集群计算DIE8个集群I/ODIEChip3.5进程调度3.5.3多处理器调度多处理器调度的背景CPU缓存内存总线CPU0缓存CPU1缓存内存总线两者间的核心差别在于对硬件缓存的使用、多处理器间的数据共享缓存一致性问题CPU间数据共享问题负载均衡问题缓存亲和性问题3.5进程调度3.5.3多处理器调度多处理器调度策略CPU0P1缺乏可扩展性违背缓存亲和性P2P3P4P5CPU1单队列调度存在的问题违背缓存亲和性P1P2P3P4P5单队列运行情况引入亲和度机制后的单队列运行情况3.5.3多处理器调度3.5.3多处理器调度多处理器调度策略CPU0P1初期均衡，后期可能不均衡P3P2P4CPU1多队列调度存在的问题就绪进程跨CPU迁移解决思路分析下这种方式的性能优缺点？3.5.3多