本文主要是介绍单核CPU调度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
CPU MLFQ 调度
MLFQ即多级反馈队列调度。在给定时间片中,任务存在不同优先队列之中等待被执行,MLFQ根据优先级去决定哪个任务在该时间片执行
Round Robin
Round Robin即RR,是基于时间片的轮询调度算法。给每个任务分配一个时间片,当任务时间片用完之后,会中断当前任务,切换到下一个
改变优先级的第一次尝试
初始规则如下
- 若任务A优先级高于任务B,则调度A
- 若任务A、B优先级一致,则根据RR调度A、B
根据上述两条规则,若存在任务C优先级低于A和B,那么C就会一直不被执行,导致饥饿。因此引入第三条规则
第四条规则则是考虑到对于需要高响应的任务多是短执行的,所以会频繁让出CPU,因此为了保证响应时间,就保持现有优先级
而对于CPU密集型,则不太需要高响应,所以可以降低优先级
-
当新任务到达之后放置最高优先级队列
-
如果任务A运行了一个时间片都没有主动让出CPU(比如I/O操作),则优先级降低一级
如果任务A在时间片用完之前,有主动让出CPU,则优先级保持不变
在上面的尝试中仍然存在以下问题
- 仍然存在饥饿问题。若存在大量短执行任务,就会导致长执行任务无法得到执行
- 被利用导致某些任务一直处于高优先级。
公平还是公平
为了解决饥饿问题,可以引入一个很简单的规则
- 系统运行S时长后,将所有任务放到最高优先级
这就确保所有的任务都会最终处于一个优先级中,那么所有任务即使是最低优先级的都有可能被调用,所以至少此时,众生平等
不要被利用
在解决了饥饿问题之后,恶意利用还是存在。
这样必须对规则4进行改变
- 给每个优先级分配一个时间片,当任务用完该优先级的时间片后,优先级降一级
最终尘埃落定
最终规则如下
- 若任务A优先级高于任务B,则调度A
- 若任务A、B优先级一致,则根据RR调度A、B
- 当新任务到达之后放置最高优先级队列
- 给每个优先级分配一个时间片,当任务用完该优先级的时间片后,优先级降一级
- 系统运行S时长后,将所有任务放到最高优先级
流程如下
-
新进程插入到最高优先队列尾
-
一段时间后,进程到达队列头并分配CPU
-
如果进程在给定时间片内完成,将离开调度系统
如果进程自愿放弃CPU执行,则会在再次就绪时,插入原放弃队列尾部
如果进程使用所有配额CPU时间,则会被抢占并插入到下一个较低队列尾部
低级别队列CPU配额比高级别队列低
调度器总是从高级别队列头开始选择进程进行分配,在高级别队列为空之后,才会接管低级别队列。
进程在队列的迁移总是插入到目标队列尾部,并且进程在给定队列级别只有一次完成任务的机会,然后就会被下放到较低级别的队列
Linux CFS调度
CFS代表完全公平的调度器。CFS的设计理念是在真实硬件上实现理想的、精确的多任务CPU。CFS调度器和以往的调度器不同之处在于没有时间片的概念,而是分配cpu使用时间的比例。例如:2个相同优先级的进程在一个cpu上运行,那么每个进程都将会分配50%的cpu运行时间。这就是要实现的公平
调度类
调度类是表示一种特定的调度策略和算法,定义了如何选择下一个要运行的任务,如何将任务插入到运行队列中,以及如何处理任务的唤醒和睡眠等
在Linux内核中有以下调度类
- CFS调度类(SCHED_NORMAL): 默认的调度类,用于大多数普通的非实时任务。它使用完全公平调度器(CFS)算法,以实现公平和高效的CPU调度
- 实时调度类: 用于实时任务
- SCHED_FIFO: 先进先出。
- SCHED_RR: 处于runqueue中的线程轮流获取时间片
- Deadline调度类(SCHED_DEADLINE): 针对有明确截止时间要求的实时任务的调度类。它使用EDF(最早截止时间优先)算法和CBS(恒定带宽服务器)算法,以确保所有的实时任务都能在截止时间之前完成
- Idle调度类(SCHED_IDLE): 优先级最低的调度类,只有当系统中没有其他任何任务需要运行时,才会运行属于这个调度类的任务。
核心结构
-
vruntime: 表示进程在所有CPU的总执行时间
v r u n t i m e + = 实际运行时间 ∗ 1024 / 进程权重 vruntime += 实际运行时间*1024/进程权重 vruntime+=实际运行时间∗1024/进程权重
-
runqueue: 每个CPU上的可运行进程队列
-
基于时序的红黑树: 每个CPU上根据vruntime组织所有进程
CFS调度策略
常规调度分为
- SCHED_NORMAL: 用于常规任务的调度策略
- SCHED_BATCH: 运行长,能更好利用缓存,但损失响应性
- SCHED_IDLE: 并不是一个真正的空闲定时器调度器,以避免优先级反转问题,防止机器死锁。
其中CFS属于SCHED_NORMAL
CFS调度利用红黑树优先调度执行总时间更低的,在每次时间片执行完会对执行的进程累加执行时间,并重新选择最低执行时间的进程进行执行
这也就意味着执行越久,执行优先级越低。那么计算密集型执行优先级低,IO密集型执行优先级高
当然这样的调度也会使得同一个进程连续执行多次,不过这也不是坏事,毕竟之前用的上下文还能接着用
SCHED_RR与SCHED_NORMAL对比
sched_RR | Sched_normal | |
---|---|---|
调度进程类型 | 实时进程 | 普通进程 |
时间片 | 静态 | 动态。根据系统进程数量变化 |
下一个进程的选择 | 从runqueue选择下一个 | 从红黑树选择vruntime最小的 |
CPU限额问题
配额机制限制了每个容器的摊销CPU使用率,但它没有限制任务在任何给定时刻可以使用多少个内核。相反,如果一个任务“想”在一个配额的时间片上使用更多的内核,它就会在短时间内使用多于配额的内核,然后进入节流状态,也就是说基本上进入睡眠状态,以保持它的摊销内核使用量低于配额,这对于尾延迟来说是灾难性的
比如垃圾回收器,可能在一次GC期间,所有这些GC线程将同时运行,迅速耗尽cpu配额,从而导致节流。由此产生的效果是,次秒级的GC暂停可能需要数秒的时间才能完成。
Ref
- https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf
- https://en.wikipedia.org/wiki/Multilevel_feedback_queue
- https://github.com/torvalds/linux/blob/v5.10/Documentation/scheduler/sched-design-CFS.rst
- https://arthurchiao.art/blog/linux-cfs-design-and-implementation-zh/
- https://danluu.com/cgroup-throttling/
这篇关于单核CPU调度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!