操作系统—调度008"/>
操作系统—调度008
操作系统—调度008
- 一、调度背景
- 1、CPU调度
- 二、调度准则
- 1、调度策略
- 2、程序执行模型
- 3、比较调度算法的准则
- 4、吞吐量VS延迟
- 5、公平的目标
- 三、调度算法
- 1、调度算法1(通常操作系统桌面和服务器涉及最基本的调度算法。)
- 1. FCFS:先来先服务,最简单的算法
- 2.SPN:选择下一个最短的进程——考虑时间的进程 Priority
- 3. HRRN:最高响应比优先——最短剩余时间有限
- 4. Round Robin:CPU轮流执行进程任务。对公平有一定的考虑
- 4.1 **CPU流转任务RR的缺点:**
- 4.2 RR轮流执行和短作业优先的比较:
- 5. MFQ:强调了公平,也强调了变化。进程等待执行时间,根据动态执行过程,进程动态执行调整。
- 6. FSS:共享是指CPU的时间——等待和执行可以公平的共享
- 2、Linux调度算法(基于RR时间轮转 和 短作业优先)
- 2.1 counter的两个作用
- 3、调度算法3(嵌入式实时系统中的特殊调度的算法)
- 4、调度算法4(多CPU多核调度算法的考虑)
- 四、实时调度
- 1、实时系统
- 2、可调度性
- 3、单调速率(RM)
- 4、截止日期最早优先(EDF)
- 五、多处理器调度
- 六、优先级反转
一、调度背景
1、CPU调度
- 将程序切换到运行态,那么就可以占用CPU运行。一旦从运行态切换到其他状态,就会不能再占用CPU运行了。
- 那么什么时候切,以及切换原则呢?
- 那么就更CPU调度有关了。
在某一个时刻绝对选择让哪一个进程让CPU将要运行的下一个进程。 - 调度需要考虑两种情况:.
- 不可抢占。大部分我们调用的是应用程序,应用程序运行的时候,是以用户态的进程形式存在。这个进程从开始到结束,中间是不允许打断。早期操作系统设计的情况 ——不可抢占策略。这样其他的程序需要进行等待,效率不高。比如说运行程序中,处于堵塞状态,这时CPU是停止的。所以效率不高
- 可以抢占:用户进程程序在运行中,可能感觉不到,但是操作系统会决定某个时刻打断用户执行,让操作系统去选择另外一个进程。现在操作系统很常用的调度策略。当一个用户进程执行系统调用,在内核中不会导致进程处于等待状态,那么这时当系统访问时,内核中不会出现抢占状态。
二、调度准则
1、调度策略
进程在计算机运行时处于的状态,进程更多的是访问内存和i/o,让CPU做计算。
2、程序执行模型
在某个进程在等待I/o时,可以切换到其他进程中,可以使CPU处于一直工作状态。
3、比较调度算法的准则
- 可以用来评测分析调度算法的指标。
- CPU利用率越高,那么认为当前系统效率越好。说明进程调度很好。 CPU利用率是一方面。
- 吞吐量越高,意味着进程的效率越好。
- 周转时间:启动后需要等待一段时间才能会被CPU执行,从而完成想对的工作,才会结束。等待时间+服务时间=周转时间。时间越少越好。
- 等待时间:处于就绪态的进程,变为运行态所等待的时间。
- 响应时间:外设发出请求,到请求被进程处理完毕,为相应时间。
4、吞吐量VS延迟
什么是更快,对快的解释?
- 传输文件时的高宽带:出水量大
- 玩游戏时的低延迟:响应时间块
- 这两个因素是独立的
和“水管”类比
- 低延迟:喝水的时候想要一打开水龙头就流出来。
- 高带宽:给游泳池冲水时希望水龙头同时流出大量的水,并且不介意是否存在延迟。
对于算法来说,我们希望算法达到什么样的效果呢?
- 响应时间:及时处理用户的输出并且尽管输出提供给用户。
- 减少平均响应时间的波动:在交互系统中,可预测性比高差异低,平均更重要。
- 增加吞吐量-两个方面
1.减少开销(操作系统开销、上下文切换)
2.系统资源的高效利用(CPU、I/o设备) - 减少等待时间:减少每个进程的等待时间。等待时间越小越好,程序已启动,马上可以执行。
这四点:是有矛盾的,最小响应时间和最大吞吐量,在操作系统中设置中,不能同时顾及,只能做偏一方面或者折中。
所以在不同的应用场合,选择不同的优点。
- 低延迟调度增加了交互式表现:比如说桌面系统(鼠标键盘),更多的需要交互性。那么就是低延迟比较高。
- 操作系统需要保证吞吐量不收影响:数据的服务器,更需要吞吐量,需要提供很大带宽,比如视频等等…
- 吞吐量是操作系统的计算带宽
- 相应时间是操作系统的计算延迟
5、公平的目标
-
并不是以效率(延迟、吞吐量),而是以公平作为很重要的调度指标。
-
期望是调用算法,系统运行了每一个进程的公平得到CPU服务。也就是说“得到CPU的时间,大致是公平的”,等待CPU时间,大概也是公平的。
-
公平通常会增加平均响应时间
-
前台任务关注相应时间,一般I/o操作比较多。后台任务关注周转时间,一般长时间利用CPU,进行计算。
所以前台任务优先级高于后台任务。因为当先去执行前台任务,那么经历一小段CPU操作,就会去长时间执行I/o操作,这时就可以线程切换去执行后台任务,这样后台任务就可以进行长时间的CPU操作。这样就达成了,并行操作。
三、调度算法
实际调度算法比这几个都复杂, 但是实际调度算法对于这些基本特征都是有所体现的。
- FCFS:比较简单先来先服务。
- SPN/SRT考虑是时间短的进程,后果是:长进程一直得不到操作系统调度。
- HRRN:将等待时间考虑进去了。想对前面等待时间很长的进程,也有机会执行。
- round Robin:每个进程都有机会被执行。想对公平,但是会引入上下文切换问题
- MLFQ:动态根据执行过程(CPU、I/o密集)(根据消耗时间片)来动态调整优先级。使得操作系统根据进程的动态特点来选择优先级。
- 公平调度:强调用户请求,在不同级别公平调度。
1、调度算法1(通常操作系统桌面和服务器涉及最基本的调度算法。)
1. FCFS:先来先服务,最简单的算法
在一个队列中,先来的程序,排在前面,CPU进行先处理,后来的排在后面。按着顺序进行处理。
例子中三个进程,根据任务到达顺序,进行任务先后。
可以看出前面程序越长,那么后面程序等待的时间也就越长,从而影响整个系统的周转时间。
那么调整方法有:将最短的时间放在前面,把最长的程序放在后面。那么优先调度时间很短的进程。短进程优先的算法
- 优点:
简单 - 缺点:
平均等待时间和周转时间波动较大
花费时间少的任务可能排在花费时间长的任务后面
可能导致I/o和CPU之间的重叠处理(CPU密集型进程会导致I/o设备空闲时,I/o密集型进程也在等待)
2.SPN:选择下一个最短的进程——考虑时间的进程 Priority
将时间短的进程放在前面,可能提高效率。进程的时间决定优先级,时间越短优先级越高。
将几个进程进行排序,排序后,在调用时,根据排序结果进行执行。如果有来了新程序,不会打断当前程序。“不抢占程序。”
-
新来了程序,与前面进行比较,如果新来的程序,比前面的程序段,会进行抢占前面程序的顺序。而SPN不会进行抢占。
所以说这个平均等待时间最小的 -
缺点是:
连续的段任务流会使长任务饥饿
短任务可用时的任何长任务的CPU时间都会增加平均等待时间 -
需要预知未来
怎么预估下一个CPU突发的持续时间
简单的解决办法:询问用户
如果用户欺骗就杀死进程
如果用户不知道怎么办 -
既然不知道进程执行多长时间,可以进行预估之前执行历史,来判断什么时候结束。
-
对下一次时刻的预估,根据预估时间进行对调度排序。在操作系统很常用的方法是:根据过去预知未来。
3. HRRN:最高响应比优先——最短剩余时间有限
HRRN比前面多考虑了一个多等待时间,SPN只考虑了执行时间,没有考虑等待时间
公式:R越大,那么等待时间越长,优先调度该进程。
最高响应:综合考虑进程的执行时间和等待时间。
从而可以设计出了,交互性、相互性更好的调度算法。
4. Round Robin:CPU轮流执行进程任务。对公平有一定的考虑
让各个进程轮流占用CPU去执行。衡量效率:等待时间。
每个进程都有机会占用CPU执行。平均等待时间很大
4.1 CPU流转任务RR的缺点:
由于是CPU轮流执行任务,不停的切换线程,那么就会产生响应时间。导致相应时间太长。
由于是CPU轮流执行任务,不停的切换线程,那么就会产生时间片小,所以单位时间内通过的“车”少,所以吞吐量小。
多级队列:将进程分析成很多队列,不同队列采取不同调度算法。高级队列:最短优先
4.2 RR轮流执行和短作业优先的比较:
前台任务(word关系响应时间):用轮转任务,因为需要响应时间短,周转时间大。需要快速响应,也就是说快速让CPU去执行一小段时间,然后紧接着可能是一大段时间的I/o操作。这时CPU就可以切换线程去执行后台任务。从而达到并行。
中间需要利用优先级调度,前台任务优先级比后台任务高,那么有什么问题呢?会造成后台任务长时间得不到执行
后台任务(GCC关系周转时间):用短作业优先,因为需要周转时间小,响应时间长。这个需要的是快速的执行作业,并不需要立马执行作业。所以可以利用前台任务去执行I/o操作时,来执行后台任务,从而并行。
- RR轮流执行和短作业优先会出现的问题:
如果利用优先级会造成后台任务长时间得不到执行,也就是一些长时间利用CPU的操作得不到占用。那么如果加入时间片呢?那和RR轮流操作,就会让前台任务得不到快速响应。这该怎么办呢??
- 什么是一个好的调度呢??
好的调度应该有学习机制,1是认识前台后台任务,2是根据任务来调整优先级。
要做一个算法,1是算法自身要简单,2要认识各任务,3是考虑各种任务的特点,4是根据任务变化,算法来自适应变化。
5. MFQ:强调了公平,也强调了变化。进程等待执行时间,根据动态执行过程,进程动态执行调整。
- 多级反馈队列:反馈体现在进程执行的特征,在队列中有所反应。比如说一个进程开始是交互式,开始设为级别较高,最先执行,执行完后,做I/o交互,所以大量等待时间。时间越长优先级越高,那么占用CPU时间越长,时间片很快,一旦发现,那么就可以把优先级进行降级队列。时间片用的越多,就越降级。使得让一些交互性比较好的进程,提高优先级。从而整体提高效率。
I/o密集型的交互性高:提高优先级,让得到很快的执行。
CPU密集型的消耗很多计算机资源的:优先级降低,跑慢一点。
6. FSS:共享是指CPU的时间——等待和执行可以公平的共享
强调公平,
2、Linux调度算法(基于RR时间轮转 和 短作业优先)
调度算法是为了折中、均衡各种情况
该调度算法:考虑响应时间短和周转时间大的问题
考虑:I/O约束性、CPU约束性、前台任务、后台任务。
代码目标是:找到next下一个最合适切换的线程。
counter:就是优先级,也是时间片。所以综合了时间轮转和短作业优先这两种算法
问题1:IN_TRSKS 是什么?将P设成了最后一个地址,将PCB做成了一个数组,放在数组的末尾。
i=NR_TRSKS; 从末尾开始,一直往回移动while(){if(){}}每次往回移动时,如果数组中是就绪的状态 并且 counter 大于C, 就将counter赋值给C,
--以上循环一遍:求最大的counter,也就是优先级最大的进程,交给swith_to跳转去执行。
if(c) break; 如果C不等于0,找到了,那么将next 就是下一个切换的线程。
--典型的优先级算法。那么counter如何修改呢? 也就是说就绪状态的线程的时间片都等于0,也就是时间片都用完了,
for(所有的进程){counter = counter 右移动1位 + priority 就是counter的初值 }
-- 比如说 0010 ->0001 2变成了1 也就是说除以2。
-- priority是counter(优先级/时间片)的初值
--- 一方面:如果是就绪状态的进程,就设成了counter的初值,
--- 另一方面:如果是其他进程,比如是阻塞进程(现在执行I/o操作的进程),现在有自己的counter,先进行除以2,在加上初值。 将来阻塞的进程成了就绪状态,它的counter一定比之前的counter大。也就说执行过I/o的进程,counter一定会变大,从而优先级会变大,从而时间片也会变大。
2.1 counter的两个作用
1、时间片
既然是时间片那么在【时钟中断】里面需要更改:
每次【时钟中断】都需要修改–counter,直到为0,然后就进行切换。
vodi do_time(){if((让counter--操作,不大于0为止)){如果等于0了,那么就可以进行调度了。也就是说可以切换线程了。}}
do_time 是放在【时钟中断】的函数里边的。
2、优先级
找到counter最大值,就是在找优先级最大的线程。
而优先级是不断的进行动态调整:
I/O线程的优先级就会升高,I/O时间越长优先级就越会更大,从而响应时间越快。
是因为:只要经过了I/O的进程,就会是阻塞状态。那么就会到for循环中进行counter的重置(counter除以2,再加上初值counter)。所以一定会比只执行CPU操作的进程的时间片会多,I/O约束性操作优先级就会上来,也就是前台操作的特征。
3、关于counter的整理
算法中经历一次I/O操作的进程的counter就会增加一次。那么是counter时间片应该也有界。那么最长的时间片,其是小于初值的2倍。
3、调度算法3(嵌入式实时系统中的特殊调度的算法)
4、调度算法4(多CPU多核调度算法的考虑)
四、实时调度
实时调度和通信调度有很大区别:实时调度面临的系统不一样
1、实时系统
-
定义:正确依赖于其时间和功能 两方面的一种操作系统。比如说一些工业性质。在某一段时间内,必须完成一些任务。以进程的形式,能够满足实时实时的特征。
-
性能指标:
时间约束的及时性
速度和平均性能想对不重要 -
主要特征:时间约束的可预测性
实时系统分为两种:
-
强实时系统:需要在保证的时间内完成重要的任务,必须完成。
当系统的某一个关键任务,如果不能再规定时间完成,会引起灾难性后果。必须在强实时系统中,所有任务,在设定的时间段,必须要完成。例如:控制水坝。 -
弱实时系统:要求重要的进程的优先级更高,尽量完成,并非必须。
比如说看视频,就算出现卡顿,不会产生严重后果。 -
如何衡量一个任务能够完成实时需求呢?
Released相当于进程中的就绪态,就绪可能不会马上执行,等待一段时间。
执行时间(Execution time):这一段时间开始执行,结束时间是蓝色这一块终止时间。
最终期限(Absolute deadline):执行时间一定不能超过,此期限。
2、可调度性
静态优先级调度:在任务执行之前,将优先级确定,按着优先级在规定时间去完成,相应工作。
动态优先级调度:任务优先级,随着执行过程,优先级会动态变化。动态变化可能影响不同时刻执行顺序。所以会可能先、延长调度。
3、单调速率(RM)
静态:优先级在执行前,就已经确定了(周期和优先级)。
周期越短,优先级越高。
4、截止日期最早优先(EDF)
随着任务执行,动态调整优先级。离着Dealine越早,优先级越高。
五、多处理器调度
-
多处理器调度:在实际系统中,多核处理器和并行处理器越来越多。前面调度主要考虑一个CPU,其实现在多个CPU。
-
单处理器:进程只在一个CPU中进行。多处理器的CPU调度更加复杂
1.多个相同的处理器组成一个多处理器:那么来了一个进程后,操作系统应该考据,将进程放在哪个CPU中运行。
2.多CPU,空闲和忙碌CPU,如何均衡的运行。
3.优点:负载共享 -
对称多处理器(SMP)
1.每个处理器运行自己的调度程序
2.需要在调度程序中同步
六、优先级反转
如果第一个进程,没有及时完成的话,那么系统会认为是不稳定现象。就会重启系统。
t1虽然比t2的优先级高,t1执行时间受制于t2执行时间,t2抢占用了t3的CPU时间去执行。t1必须等着t3,导致t1的执行时间被t2延长。 从而出现了:t1不能及时完成任务,导致整个系统不稳定现象。从而重启。 低优先级任务影响高优先级任务。
更多推荐
操作系统—调度008
发布评论