单核CPU调度

2024-05-12 16:04
文章标签 cpu 调度 单核

本文主要是介绍单核CPU调度,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

CPU MLFQ 调度

MLFQ即多级反馈队列调度。在给定时间片中,任务存在不同优先队列之中等待被执行,MLFQ根据优先级去决定哪个任务在该时间片执行

Round Robin

Round Robin即RR,是基于时间片的轮询调度算法。给每个任务分配一个时间片,当任务时间片用完之后,会中断当前任务,切换到下一个

改变优先级的第一次尝试

初始规则如下

  1. 若任务A优先级高于任务B,则调度A
  2. 若任务A、B优先级一致,则根据RR调度A、B

根据上述两条规则,若存在任务C优先级低于A和B,那么C就会一直不被执行,导致饥饿。因此引入第三条规则

第四条规则则是考虑到对于需要高响应的任务多是短执行的,所以会频繁让出CPU,因此为了保证响应时间,就保持现有优先级

而对于CPU密集型,则不太需要高响应,所以可以降低优先级

  1. 当新任务到达之后放置最高优先级队列

  2. 如果任务A运行了一个时间片都没有主动让出CPU(比如I/O操作),则优先级降低一级

    如果任务A在时间片用完之前,有主动让出CPU,则优先级保持不变

在上面的尝试中仍然存在以下问题

  • 仍然存在饥饿问题。若存在大量短执行任务,就会导致长执行任务无法得到执行
  • 被利用导致某些任务一直处于高优先级。

公平还是公平

为了解决饥饿问题,可以引入一个很简单的规则

  1. 系统运行S时长后,将所有任务放到最高优先级

这就确保所有的任务都会最终处于一个优先级中,那么所有任务即使是最低优先级的都有可能被调用,所以至少此时,众生平等

不要被利用

在解决了饥饿问题之后,恶意利用还是存在。

这样必须对规则4进行改变

  1. 给每个优先级分配一个时间片,当任务用完该优先级的时间片后,优先级降一级

最终尘埃落定

最终规则如下

  1. 若任务A优先级高于任务B,则调度A
  2. 若任务A、B优先级一致,则根据RR调度A、B
  3. 当新任务到达之后放置最高优先级队列
  4. 给每个优先级分配一个时间片,当任务用完该优先级的时间片后,优先级降一级
  5. 系统运行S时长后,将所有任务放到最高优先级

流程如下

  1. 新进程插入到最高优先队列尾

  2. 一段时间后,进程到达队列头并分配CPU

  3. 如果进程在给定时间片内完成,将离开调度系统

    如果进程自愿放弃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_RRSched_normal
调度进程类型实时进程普通进程
时间片静态动态。根据系统进程数量变化
下一个进程的选择从runqueue选择下一个从红黑树选择vruntime最小的

CPU限额问题

配额机制限制了每个容器的摊销CPU使用率,但它没有限制任务在任何给定时刻可以使用多少个内核。相反,如果一个任务“想”在一个配额的时间片上使用更多的内核,它就会在短时间内使用多于配额的内核,然后进入节流状态,也就是说基本上进入睡眠状态,以保持它的摊销内核使用量低于配额,这对于尾延迟来说是灾难性的

比如垃圾回收器,可能在一次GC期间,所有这些GC线程将同时运行,迅速耗尽cpu配额,从而导致节流。由此产生的效果是,次秒级的GC暂停可能需要数秒的时间才能完成。

Ref

  1. https://pages.cs.wisc.edu/~remzi/OSTEP/cpu-sched-mlfq.pdf
  2. https://en.wikipedia.org/wiki/Multilevel_feedback_queue
  3. https://github.com/torvalds/linux/blob/v5.10/Documentation/scheduler/sched-design-CFS.rst
  4. https://arthurchiao.art/blog/linux-cfs-design-and-implementation-zh/
  5. https://danluu.com/cgroup-throttling/

这篇关于单核CPU调度的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/983084

相关文章

搭建Kafka+zookeeper集群调度

前言 硬件环境 172.18.0.5        kafkazk1        Kafka+zookeeper                Kafka Broker集群 172.18.0.6        kafkazk2        Kafka+zookeeper                Kafka Broker集群 172.18.0.7        kafkazk3

一种改进的red5集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

转自: 一种改进的red5集群方案的应用: http://wenku.baidu.com/link?url=jYQ1wNwHVBqJ-5XCYq0PRligp6Y5q6BYXyISUsF56My8DP8dc9CZ4pZvpPz1abxJn8fojMrL0IyfmMHStpvkotqC1RWlRMGnzVL1X4IPOa_  基于Red5服务器集群负载均衡调度算法研究 http://ww

Golang进程权限调度包runtime

关于 runtime 包几个方法: Gosched:让当前线程让出 cpu 以让其它线程运行,它不会挂起当前线程,因此当前线程未来会继续执行GOMAXPROCS:设置最大的可同时使用的 CPU 核数Goexit:退出当前 goroutine(但是defer语句会照常执行)NumGoroutine:返回正在执行和排队的任务总数GOOS:目标操作系统NumCPU:返回当前系统的 CPU 核数量 p

Java程序到CPU上执行 的步骤

相信很多的小伙伴在最初学习编程的时候会容易产生一个疑惑❓,那就是编写的Java代码究竟是怎么一步一步到CPU上去执行的呢?CPU又是如何执行的呢?今天跟随小编的脚步去化解开这个疑惑❓。 在学习这个过程之前,我们需要先讲解一些与本内容相关的知识点 指令 指令是指导CPU运行的命令,主要由操作码+被操作数组成。 其中操作码用来表示要做什么动作,被操作数是本条指令要操作的数据,可能是内存地址,也

文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源程序擅长文章解读,论文与完整源程序,等方面的知识,电网论文源程序关注python

win10不用anaconda安装tensorflow-cpu并导入pycharm

记录一下防止忘了 一、前提:已经安装了python3.6.4,想用tensorflow的包 二、在pycharm中File-Settings-Project Interpreter点“+”号导入很慢,所以直接在cmd中使用 pip install -i https://mirrors.aliyun.com/pypi/simple tensorflow-cpu下载好,默认下载的tensorflow

定位cpu占用过高的线程和对应的方法

如何定位cpu占用过高的线程和对应的方法? 主要是通过线程id找到对应的方法。 1 查询某个用户cpu占用最高的进程号 top -u 用户名 2 查询这个进程中占用cpu最高的线程号 top –p 进程号-H    3 查询到进程id后把进程相关的代码打印到jstack文件 jstack -l pid > jstack.txt 4 在jstack文件中通过16进制的线程id搜索到

【Linux】探索进程优先级的奥秘,解锁进程的调度与切换

目录 进程优先级: 是什么? 为什么存在进程优先级的概念呢? Linux为什么调整优先级是要受限制的? PRI vs NICE Linux的调度与切换 概念准备: 那我们到底怎样完成进程的调度和切换呢? 区分:寄存器VS寄存器的内容 Linux实现进程调度的算法,需要考虑优先级,考虑进程饥饿问题,考虑效率问题。 解决优先级问题: 解决进程饥饿问题: 解决效率的问题:

CPU亲和性设置 代码示例 sched_setaffinity sched_getaffinity

视频教程在这: cpu亲和性设置,NCCL,sched_setaffinity sched_getaffinity,CPU_ZERO、SET、ISSET、linux_哔哩哔哩_bilibili 一、CPU亲和性简介 CPU亲和性(CPU Affinity)设置是操作系统中一个重要的性能优化手段,它允许程序或进程被绑定到特定的CPU核心上运行。这样做的好处包括减少缓存未命中、降低线程迁移(co

ubuntu16.04 caffe(github源码cpu)+python3.5+opencv3.4.5安装编译

https://www.cnblogs.com/hanjianjian90/p/10604926.html