域名打不开原来的网站,网页开发工作室,做医院网站公司电话,湖北百度seo排名作者 | 轩辕之风O来源 | 编程技术宇宙1、任务切换现在有一块CPU#xff0c;但是有两个程序都想来执行#xff0c;我们需要开发一个任务调度程序。只有两个程序#xff0c;so easy啦#xff01;让它们交替执行就行了。为了实现切换#xff0c;我们提供一个API#xff0c;这… 作者 | 轩辕之风O来源 | 编程技术宇宙1、任务切换现在有一块CPU但是有两个程序都想来执行我们需要开发一个任务调度程序。只有两个程序so easy啦让它们交替执行就行了。为了实现切换我们提供一个API这两个程序执行一会儿就主动调用一下这个API然后在这个API内部实现任务的切换。所谓的切换其实就是把当前进程的上下文也就是CPU一堆的寄存器值保存到进程的TCB进程控制块每个进程对应的内存数据结构里。然后把另一个进程TCB里的上下文寄存器的值装载起来开始运行。这是一种主动配合式的调度。2、抢占然而理想很美好现实很骨感。这些个程序可能不是那么听话可能很久都不调用我们的API交出CPU甚至可能搞了个死循环另一个程序永远也没机会执行。看来不能依赖程序主动交出执行权调度程序需要有抢占CPU的能力怎么抢占呢我们可以利用时钟中断因为一旦有中断事件到来CPU就得去执行中断处理程序。只要在时钟中断的处理函数里面加入调度入口就能抢到CPU的执行权。为了公平起见我们决定让每个进程都执行一小段时间我们把这个叫做时间片比如100ms然后轮流执行它们就可以了差不多是这个样子我们给CPU编程让它每1ms发送一次时钟中断。在每个时钟中断到来时检查当前的线程运行时间是否足够100ms如果没有就将当前线程运行的时间1ms然后中断处理结束让它继续运行。如果检查发现时间已经到了100ms就切换另一个进程来运行。100ms对于人类几乎感知不到所以还以为两个线程是在同时运行。一个最最最简单的任务调度程序就完成了。3、阻塞渐渐地进程多了起来3个、4个、5个···我们用一个队列把它们存起来先进先出就叫做就绪队列吧意思是准备要排队执行的队列。所有就绪的进程依次排队被我们的调度程序翻牌子执行。没过多久我们发现有些进程经常占着茅坑不xx在sleep或者等待锁的时候白白霸占着CPU空转搞得队列里其他进程怨声载道。那咱们对调度程序再做一个优化吧当有进程等待锁、I/O等待或者sleep的时候调度程序也需要介入即使分配给它的时间片还没用完也要让它主动交出CPU并把它放到另一个等待队列里去等到等待的条件满足的时候再把它请回到就绪队列排队。现在我们的调度程序不再允许有占着CPU却摸鱼的现象发生。4、优先级后来进程进一步多了起来6个、7个、···、100个。每一个进程都执行100ms转一圈下来就是10000ms10s。一个打字程序按了键盘10s钟之后才反应过来这系统卡的一匹简直没法用。我们可以把每个进程执行的时间缩短为10ms转一圈下来变成了1000ms1s情况好了很多但还是有点卡。而且这一招架不住进程越来越多200个300个甚至更多转一圈的时间还是在变长。但又不好继续压缩时间否则就花太多时间在切换上了真正执行的时间变少。归根结底问题在于进程多了以后再按照顺序轮转不合时宜了。得让一些进程拥有VIP特权能够优先执行。要不这样吧给每个进程设定一个优先级从1到40总共40个优先级数字越大优先级越高。调度的时候把队列遍历一圈找出里面优先级最高的进程来执行。现在我们只需要给打字程序这样的交互式进程设定一个高优先级再次按下键盘后很快就能得到响应了。5、O(1)复杂度每次调度的时候都得去遍历所有的进程这复杂度是O(N)。进程少倒还不打紧多了以后就有些恼火了这效率太低了。让所有进程一起排在一个大的队列里不是一个明智的做法。要不我们按照优先级拆分成不同的队列吧每个优先级单独弄一个就绪队列就是40个队列分开排队找起来效率更高。调度的时候按照优先级顺序依次来看每一个队列是否有可以执行的进程找到后就从队列里取出来执行相同优先级队列里面的进程轮流执行。为了快速知道每一个优先级队列里面有没有进程咱们再弄一个位图40个bit每一位表示一个优先级队列如果是1就知道这个优先级的队列里有进程需要执行为0就没有。关于这个优先级队列差不多可以这样定义struct priority_queue {int nr_active; // 所有队列的进程总数unsigned long bitmap[BITMAP_SIZE]; // 位图struct list_head queue[MAX_PRIO]; // 队列数组
};现在找起来可方便了进程再多也没事都可以在O(1)的时间复杂度里找到要调度的进程。6、饿死问题系统运行了一段时间发现了一个重要的问题由于高优先级进程的存在低优先级的程序很难得到执行机会容易被“饿死”。除非高优先级的进程执行结束或者在睡眠等待否则只要它一直待在就绪队列里其他进程就没有机会。这可不行呀虽然你优先级高但总得给别人分口吃的吧。看来进程执行完成之后不能马上把它再放回原来的队列里去得这一轮大家都执行过后才行。不放回原队列那放哪里去呢干脆再弄一个优先级队列把它叫做expired队列并把原来的优先级队列叫做active队列。调度的时候从active队列里提取进程。完成一次调度后就把它放到expired队列等原来的队列里的进程都挨个执行完一圈active队列就空了它们都来到了这个expired队列然后交换两个队列从头再来。嗯为了避免内存拷贝。把active和expired定义成指针到时候直接交换两个指针更省事儿把原来的队列封装一下struct runqueue {struct priority_queue* active;struct priority_queue* expired;struct priority_queue array[2];
};就这样所有进程在两个队列中兜兜转转现在低优先级的进程也有机会被执行到了不会被饿死了。7、优先级与时间片到目前为止虽然进程有优先级之分但这只影响它们的调度顺序而不影响它们执行的时间所有的进程时间片依然是100ms。现在优先级高的程序提出了抗议我执行的任务很重要需要给我更长的CPU时间片于是一个新的需求来了不同优先级进程运行的时间片需要有区别。优先级高的时间片得长一点优先级低的时间片得短一些。这个需求倒也好办我们以中间优先级20为基础设定优先级为20的进程时间片是100ms优先级每增加1级时间片5ms每减少一级时间片-5ms。优先级 ---- 时间片
1 5ms
2 10ms
3 15ms
··· ···
18 90ms
19 95ms
20 100ms # base
21 105ms
··· ···
39 195ms
40 200ms现在高优先级的进程不仅能够优先被执行给它分配的运行时间也更多了。上面的时间片分配算法还不算是完美它有一个问题如果现在只有两个优先级为20和21的进程在运行时间片分别是100ms和105ms那么两个进程分别能获取到的CPU时间占比是100/(100105)48.7%和105/(100105)51.2%。优先级增加1CPU时间占比多了2.5%看起来没什么问题。现在如果换成只有两个优先级为1和2的进程在运行时间片分别是5ms和10ms那么两个进程分别能获取到的CPU时间占比是5/(510)33.3%和10/(510)66.7%。优先级2只比优先级1的进程高了一级获取的CPU时间占比就翻了一倍同样是优先级加1这差距咋就这么大呢说好的公平呢8、公平调度时间分配现在我们换个思路不用绝对时间片而用相对时间片。比如设定我们的调度周期为100ms这100ms让所有可以运行的进程来瓜分100ms之后所有就绪的进程都被执行了一圈儿。那么问题来了如何让进程们来瓜分这100ms呢当然是按照优先级来分。我们给不同优先级的进程设置不同的权重优先级高的权重值高就多分一点儿优先级越低的权重值低就少分一点儿。那这个权重值设定为多少好呢别急有人已经帮我们想好了就是下面这个数组。想知道为什么是这些数字而不是别的是有讲究的不过先不用管。const int sched_prio_to_weight[40] { 88761, 71755, 56483, 46273, 36291, 29154, 23254, 18705, 14949, 11916, 9548, 7620, 6100, 4904, 3906, 3121, 2501, 1991, 1586, 1277, 1024, 820, 655, 526, 423, 335, 272, 215, 172, 137, 110, 87, 70, 56, 45, 36, 29, 23, 18, 15,
};现在各个进程按照自己优先级对应的权重来从这100ms的调度周期里来分配时间。不知道你发现没有如果进程特别多那可能分下来的时间就会很少。咱们还得设定一个最小值不然一天天的净跑去调度切换了真正执行的时间少了。这个最小值就是进程至少得运行这么久才能切换。9、公平调度进程选择时间分配的问题解决了还有一个问题调度的时候如何挑选下一个需要执行的进程呢前面我们按照权重来给大家分配了时间但肯定有一些进程因为I/O、锁、睡眠等原因没有把分配的时间用完这一些进程应该得到补偿一旦它们符合执行条件后应该优先被执行。主动放弃了CPU的进程它们运行的时间肯定比分配的短。要不按照进程运行的时间来排个序挑选时间最短的进程来运行但是不同进程优先级不一样分配到的时间本来就有长短啊。要是能够消除因为权重造成的时间分配长短不一问题就好了就能用运行时间来排序了。要不咱们再弄一个虚拟运行时间把权重带来的影响再给修复回去比如优先级高的进程分配的时间多统计它的运行时间的时候就让它流逝的慢一些。而优先级低的进程分配的时间少统计它的运行时间的时候就让它流逝的快一些。这样所有进程在没有任何睡眠、等待、I/O的情况下大家都是用完了自己的时间消除权重后的虚拟时间都应该是一样一样的都是整个调度周期的1/N这才叫公平嘛现在只需要把所有进程按照虚拟时间来排个序排在前面的虚拟时间短调度的时候就选择它来运行。好主意那用什么样的数据结构来组织管理进程呢数组插入不方便。链表寻找插入位置的时候时间复杂度是O(N)。用二叉搜索树貌似是个不错的方案。左节点虚拟时间比父节点和右节点的虚拟时间小只要找到最左边的节点就是要调用的进程时间复杂度是O(LogN)。但二叉搜索树有个毛病一个不小心就容易变成一棵“跛脚”的树这时间复杂度就又上去了。红黑树没有这个问题它自带平衡性要不就它吧根据虚拟时间来把所有待运行的进程组织成一棵红黑树只要找到整棵树最左边的节点就是要运行的进程。不过为了更高效树调整更新导致最左边节点发生变化的时候把它给缓存起来这样调度的时候就直接拿到这个缓存节点就好了。完美总结上面讲述的进程调度模型其实就是Linux中O(1)调度算法和CFS完全公平调度算法调度算法的雏形为了便于理解文中进行了一定程度的简化。包括但不限于在实际的Linux中进程优先级有140个分为实时进程和非实时进程。在实际的Linux中进程通过一个叫nice值对其他进程的友好度nice越大越友好越谦让优先级越低的东西映射到优先级优先级数字越大优先级反而越低。在实际的Linux中进程的优先级分为静态和动态是会随着运行而变化的不是固定不变。在多核模式下为了防止加锁带来的性能损失每一个CPU核都有自己的调度队列。在实际的Linux中参与调度的是线程而不是进程。但在早期的Linux中没有线程的概念调度就是基于进程来进行引入线程后线程又称为轻量级进程。现在我们平时所说的进程和线程在语义上有所不同这一点要注意区别。看完了这篇文章再去看Linux的调度算法应该会轻松不少。往期推荐高并发下的 HashMap 为什么会死循环Docker从入门到实战过程全记录Redis 内存满了怎么办这样置才正确如何在 Kubernetes Pod 内进行网络抓包点分享点收藏点点赞点在看
