物联网
您现在所在的位置:首页>企业动态>物联网

进程调度

编辑:学到牛牛IT培训    发布日期: 2023-08-14 09:27:54  

关于进程调度需要先了解什么是进程,进程可以简单理解为正在运行的程序。而进程调度的两个关键性指标则是:响应时间与周转时间。


1691976655572.jpg


响应时间:

进程未运行到下次被选中运行的时间间隔。如:创建进程到第一次调度到进程的时间。再比如:进程切换后到下一次调度到该进程的时间间隔。

响应时间体现了交互感,如:敲下键盘到屏幕上出现对应的字符,自然是时间越短越好。即响应时间越短,交互性越好。


周转时间:

进程从启动开始到执行结束的时间间隔。周转时间可以体现性能,周转时间越短,从进程执行到结束所等待的时间越短。

性能和公平往往是互相矛盾的,优化性能必然会降低公平性,反之亦然。进程调度就是不断去平衡两者之间的关系,去权衡利弊。

进程的调度算法分为:先进先出(FIFO)调度算法、最短任务优先(SJF)调度算法、最短完成时间优先(STCF)调度算法、Round—Robin调度算法、高响应比优先调度算法、多级反馈队列调度算法。


先进先出(FIFO)调度算法:

设:有三个进程A、B、C,当他们的运行时间一致(10s)时:

平均周转时间: (10 + 20 + 30)/ 3 = 20s

平均响应时间: (0 + 10 + 10)/ 3 = 6.67s


当A进程运行时间为100s时:

平均周转时间: (100 + 110 + 120)/ 3 = 110s

平均响应时间: (0 + 100 + 110)/ 3 = 70s


此时,FIFO的缺点就很明显了。若耗时较短的进程放在耗时更长的进程之后,那么短进程将做出无谓的等待。

就像去超市买东西结账时,假如我们只买了一件商品,前面的人购物车堆满了商品。此时,我们都想让我们先结账,因为在我们看来,我们的结账速度很快。因此,这种效率很低。但如果超市开通一个新的零散结账通道给购买商品很少的客户,就可以提高效率。但很显然这是不可能的,因为超市无法对用户的商品购买量进行限制。

但这种零散结账的模式正是下一种算法:最短任务优先,让购买量较小的客户先结账。


最短任务优先(SJF)调度算法:

顾名思义,最短的进程先执行。按照上面的例子,如果A进程执行时间为100s,B、C不变仍为10s;A最长,所以最后执行。

平均周转时间: (10 + 20 + 120)/ 3 = 50s

平均响应时间: (0 + 10 + 20)/ 3 = 10s


但如果不是所有进程同时启动,而是随机启动,则此时最坏的情况就是A进程先执行,这时就又回到了最糟糕的情况:

平均周转时间: (100+(110-10) + (120 - 10))/ 3 = 103.3s

平均响应时间: (0 + (100-10) + (110-10))/ 3 = 63.3s


最短完成时间优先(STCF)调度算法:

在上一种算法中,仍然有可能回到最糟糕的情况。因此,我们假设进程的调度是可以抢占的,谁抢到优先权谁就先运行。那么短任务就可以在开始的时候直接运行,不需要等待很长时间,这就是最短完成时间优先调度算法。

因此,先进先出和最短任务优先都是非抢占式的,而最短完成时间是抢占式的调度算法。


关于抢占式,可能会有一些容易误解的地方。抢占式并不是说进程抢到CPU资源了,而是指优先级。进程调度实际上大部分都是由操作系统决定的,所谓抢占,只是表明该进程优先级要高一些,可能马上就会调度到它,下一个就是,同时也有可能除它以外还有优先级更高的进程或者和它同级的进程。

平均周转时间: (120 + (20-10) + (30-10))/ 3 = 50s

平均响应时间: (0 + 0 + 10)/ 3 = 3.3s

此算法在两项指标上都已经达到了最佳效果,这归功于抢占式。只要是抢占式,平均时间就不会比非抢占式的差。


Round—Robin调度算法:

其实,抢占式的响应时间还可以优化。在最短完成时间的基础上添加一个条件:指定每个进程最多运行固定的一段时间,轮询调度每一个进程,这就是“轮询调度”或“时间片轮转”。

这种“固定的时间段”就是“时间片”。如果要使用时间片的功能,就必然需要时间中断,并且时间片的长度必须是时钟周期的倍数。如: 时间中断是5s一次,那么时间片就是5s、10s、15s、20s ... ...

在上个算法的基础上添加2s的时间片,且三个进程同时启动:

平均周转时间: (120 + (30-2) + 30)/ 3 = 59.3s

平均响应时间: (0 + 2 + 4)/ 3 = 3s

高响应比优先调度算法:

高响应比优先调度算法(Highest Reponse Ratio First, HRRF)是非抢占式的,它同时考虑了每个进程的响应时间与周转时间。每次调度时,从所有进程中选出响应比最高的进程进行调度。

响应比 = (周转时间 + 响应时间)/ 周转时间


多级反馈队列调度算法:

多级反馈队列调度算法不需要事先知道各进程所需要的执行时间,实施过程如下:

1.设置多个就绪队列,并为其赋予不同的优先级。


2.赋予各队列中进程的时间片各不相同,优先级越高,时间片越小。


3.当一个新进程进入内存后,放入第一级队列末尾,按照FCFS原则等待调度。轮到该进程执行时,若能在该时间片内完成,便可以准备撤离系统;若在一个时间片结束时未能完成,则将其转入第二级队列末尾继续等待调度;若再不行则转入第三级队列末尾,以此类推。


4.当第一级队列为空时,才调度第二级队列;若在处理第n级队列中的某进程时,有一个新进程进入较高级队列中,则系统讲正在运行的进程放回第n级队列末尾,先执行较高级队列中的进程。


免费试学
课程好不好,不如实地听一听

封闭学习

2

1

联系我们

电话:028-61775817

邮箱:1572396657@qq.com

地址:成都市金牛区西城国际A座8楼

  • 物联网_物联网专题新闻_物联网IOT资讯-学到牛牛
    物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

    扫一扫,免费咨询

  • 物联网_物联网专题新闻_物联网IOT资讯-学到牛牛
    物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

    微信公众号

  • 物联网_物联网专题新闻_物联网IOT资讯-学到牛牛
物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

学一流技术,找高薪工作

物联网_物联网专题新闻_物联网IOT资讯-学到牛牛

7-24小时服务热线:

028-61775817

版权声明 网站地图

蜀ICP备2021001672号

课程问题轻松问