单核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集群调度

搭建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集群方案的应用、基于Red5服务器集群负载均衡调度算法研究

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

Golang进程权限调度包runtime

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

Java程序到CPU上执行 的步骤

相信很多的小伙伴在最初学习编程的时候会容易产生一个疑惑❓，那就是编写的Java代码究竟是怎么一步一步到CPU上去执行的呢？CPU又是如何执行的呢？今天跟随小编的脚步去化解开这个疑惑❓。 在学习这个过程之前，我们需要先讲解一些与本内容相关的知识点 指令 指令是指导CPU运行的命令，主要由操作码+被操作数组成。 其中操作码用来表示要做什么动作，被操作数是本条指令要操作的数据，可能是内存地址，也
阅读更多...
文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《考虑燃料电池和电解槽虚拟惯量支撑的电力系统优化调度方法》

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

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

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占用过高的线程和对应的方法

如何定位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】探索进程优先级的奥秘，解锁进程的调度与切换

目录 进程优先级： 是什么？ 为什么存在进程优先级的概念呢？ Linux为什么调整优先级是要受限制的？ PRI vs NICE Linux的调度与切换 概念准备： 那我们到底怎样完成进程的调度和切换呢？ 区分：寄存器VS寄存器的内容 Linux实现进程调度的算法，需要考虑优先级，考虑进程饥饿问题，考虑效率问题。 解决优先级问题： 解决进程饥饿问题： 解决效率的问题：
阅读更多...
CPU亲和性设置 代码示例 sched_setaffinity sched_getaffinity

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安装编译

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

https://www.cnblogs.com/hanjianjian90/p/10604926.html
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2