15 | 调度（上）：如何制定项目管理流程？

精选留言(35)

• 

  why

  - 调度策略与调度类
  - 进程包括两类: 实时进程(优先级高); 普通进程
  - 两种进程调度策略不同: task_struct->policy 指明采用哪种调度策略(有6种策略)
  - 优先级配合调度策略, 实时进程(0-99); 普通进程(100-139)
  - 实时调度策略, 高优先级可抢占低优先级进程
  - FIFO: 相同优先级进程先来先得
  - RR: 轮流调度策略, 采用时间片轮流调度相同优先级进程
  - Deadline: 在调度时, 选择 deadline 最近的进程
  - 普通调度策略
  - normal: 普通进程
  - batch: 后台进程, 可以降低优先级
  - idle: 空闲时才运行
  - 调度类: task_struct 中 * sched_class 指向封装了调度策略执行逻辑的类(有5种)
  - stop: 优先级最高. 将中断其他所有进程, 且不能被打断
  - dl: 实现 deadline 调度策略
  - rt: RR 或 FIFO, 具体策略由 task_struct->policy 指定
  - fair: 普通进程调度
  - idle: 空闲进程调度
  - 普通进程的 fair 完全公平调度算法 CFS(Linux 实现)
  - 记录进程运行时间( vruntime 虚拟运行时间)
  - 优先调度 vruntime 小的进程
  - 按照比例累计 vruntime, 使之考虑进优先级关系
  - 调度队列和调度实体
  - CFS 中需要对 vruntime 排序找最小, 不断查询更新, 因此利用红黑树实现调度队列
  - task_struct 中有 实时, deadline 和 cfs 三个调度实体, cfs 调度实体即红黑树节点
  - 每个 CPU 都有 rq 结构体, 里面有 dl_rq, rt_rq 和 cfs_rq 三个调度队列以及其他信息; 队列描述该 CPU 所运行的所有进程
  - 先在 rt_rq 中找进程运行, 若没有再到 cfs_rq 中找; cfs_rq 中 rb_root 指向红黑树根节点, rb_leftmost指向最左节点
  - 调度类如何工作
  - 调度类中有一个成员指向下一个调度类(按优先级顺序串起来)
  - 找下一个运行任务时, 按 stop-dl-rt-fair-idle 依次调用调度类, 不同调度类操作不同调度队列
  

  2019-05-01

  

   35
• 

  青石

  # 查看当前进程的调度策略
  $ chrt -p 31636
  pid 31636 的当前调度策略：SCHED_OTHER
  pid 31636 的当前调度优先级：0
  
  # 修改31636进程的调度策略为SCHED_FIFO，优先级为10
  $ chrt -f -p 10 31636
  $ chrt -p 31636
  pid 31636 的当前调度策略：SCHED_FIFO
  pid 31636 的当前调度优先级：10

  2019-05-05

   1

   7
• 

  Keep-Moving

  本节讲的是进程的调度，那线程的调度是什么样的呢？Linux调度的基本单位是进程还是线程呢？

  作者回复: 进程和线程都是task，一起调度

  2019-05-01

  

   7
• 

  刘強

  感觉这个sched_class结构体类似面向对象中的基类啊,通过函数指针类型的成员指向不同的函数，实现了多态。

  作者回复: 是的

  2019-05-02

  

   4
• 

  拾贝壳的孩子

  如果优先队列一直有任务,普通队列的task一直得不到处理，操作系统会怎么做呢？
  -------------------------------------------------------------------------------------
  我现在知道这个问题的答案了。这种现象叫做饿死。我当时想到这个问题时其实不知道这个概念。
  为了防止这种现象的发生，操作系统在一定的时间周期会重置所有task的优先级，这样就保证
  了低优先级的task得以执行,而不被饿死。但是这个时间设置为多少合适？设置的短了会导致系统的频繁重置。设置的长了，又会使普通优先级的task切换太慢。这个时间一般是系统研究人员研究得到的，我觉得可能可以通过一些统计学上的方式来做。
  为了解决task响应时间和完成时间的平衡，现代操作系统如Windows和Linux都依赖于Multi-Level Feedback Queue, 和文章讲的正好对应起来了。首先面对的情况是：
  1. 操作系统无法知道每个task何时到来 ？
  2. 操作系统无法知道每个task运行完成实际需要多少时间 ？
  那么FIFO ShortJobFirst或者Short Time Completed First 算法，面对这两种场景将无从下手。
  面对这样的问题，为了使交互性的TASK能够得到快速的响应，提升用户的的体验，同时缩短task 的完成时间。计算机科学家提出了Multi-Level Feedback Queue的解决方案。基本思想是通过优先级保证交互性的task，能够快速响应，同时通过统计task 对CPU的使用时间以期对TASK判断，有点类似于机器学习。
  如果某个task 在其时间片里用完前释放CPU， 可以认为这是种交互式的task, 优先级保留。反之认为某个task是需要运行时间长的。同时基于对task 对cpu 时间使用的统计作为判断依据。这样经过一段时间运行后，长时间运行的队列会被逐渐降低优先级。
  而快速响应的task 能够优先使用CPU。但是这里面还有两个问题: 首先，如果优先级低的一直得不到cpu, 可能会出现饿死。其次，有人可能会利用这个漏洞编程的方式在使用完CPU时间片后释放CPU，从而控制CPU。 基于此，Multi-feedback-queue有以下5条规则：
  1. 如果A的优先级大于B， 则A先运行。
  2. 如果A的优先级等于B， 则以RR算法交互运行。
  3. 新来的 Task 会被置于最高的优先级。
  4. 如果一个task 在其当前优先级运行完被分配的时间片后，会降低其优先级，重置其放弃使用CPU的次数。（这条规则修改过，是为了防止有人利于原有规则的漏洞控制CPU, 原来的规则是如果一个task 在其时间片用完前释放cpu, 则其优先级保持不变， 这个修正增加了对task 实际使用cpu 时间统计作为判断依据）。
  5. 系统每过时钟周期的倍数，会重置所有task 的优先级。（这条规则是为了防止task被饿死的，也是我之前所疑惑的）。

  作者回复: 对的，饿死，cpu一直转，低优先级的没响应

  2019-05-12

  

   3
• 

  why

  如果是新建的进程如何处理, 它 vruntime 总是最小的, 总被调度直到与其他进程相当.

  作者回复: 每次新进程创建完毕后，都会试图先让新的抢占一次

  2019-05-01

  

   3
• 

  俩孩儿他爸

  对于CFS的这个比喻很贴切，之前看过CFS相关的内容，一直找不到如何用一个现实中的过程类比一下。大口袋和小口袋所放入的球的比例一样，对应到CFS，也就是vruntime一样，从这个角度来看，也就是做到了完全的公平！

  作者回复: 是的

  2019-08-26

  

   2
• 

  天王

  调度，1 task_struct 里面有policy和priority，任务调度的策略和优先级，项目即进程多了，干活的人即CPU个数是有限的，需要进行进程的调度，分配CPU的时间，既保证线程的快速响应，也保证公平。2 调度策略 2.1 linux里面进程分成2种，一种是实时进程，一种是普通进程，正常时间排 调度策略，task_struct里面有个policy，里面有一些枚举值，SCHED_normal 0，sched_fifo 1，sched_rr 2，sched_batch 3，sched_idle 5，sched_deadline 6。配合调度策略的还有priority，task_struct里面有prio，static_prio，normal_prio，实时进程的优先级是0到99，普通进程是100到139，优先级越小，优先级越高。2.2 调度策略分实时调度策略和普通调度策略 2.21实时调度策略有sched_rr，sched_fifo，sched_deadline，sched_fifo 是高优先级的抢占低优先级的进程，相同优先级的先进的先处理，sched_rr 是轮流着来，每个调度执行个时间片，执行完放到队列后面，sched_deadline，是哪个快到时间了，执行哪个。2.22 普通调度策略 sched_normal，sched_batch，sched_idle，sched_normal 普通进程，sched_batch 后台进程，sched_idle空闲的时候才跑的后台进程，3 policy和priority都是定义了一种策略，具体的调度类 sched_class，sched_class定义了几种实现，stop_sched_class 这个任务优先级最高，可以中断其他线程，不能被其他线程中断，dl_sched_class对应sched_deadline的调度策略，rt_sched_class对应rr算法和fifo的调度策略，fair_sched_class对应就是完全公平的调度策略，idle_sched_class对应空闲的调度策略。4 普通进程的完全公平调度算法 CFS 全称completely fair schedue CFS的原理4.1首先记录一个进程的运行时间 CPU会提供一个时钟，每隔一段时间触发一个中断，叫tick，CFS会为每个进程提供一个虚拟运行时间virtualruntime，随着进程的运行，tick的到来virtualruntime会增大，没有得到执行的virtualruntime保持不变，virtualruntime少的会补上，下次会优先分，优先级高的给一个大桶，按比例分，这样就能给优先级高的优先分配，同样的运行时间，给优先级高的算的少，这样，下次分配的时候，按照virtualruntime小的分配，优先级高的就被执行到了。5 调度队列和调度实体 平衡快速查询和更新的数据结构是红黑树，红黑树的节点是包含virtualruntime的，称为调度实体，有几种sched_entity 完全公平调度实体，sched_rt_entity 实时调度实体，sched_dl_entity deadline调度实体，进程根据自己的状况选择某一个实体，如果是普通进程，则通过sched_entity将自己挂在红黑树上，sched_entity里面包含了vruntime和load_weight，还有统计信息，所有可运行的进程通过不断的插入更新操作，都存储在以时间为顺序的红黑树中，virtualruntime最小的的在树的左侧，最大的在树的右侧，CFS策略会选择左侧最小的作为下一个要执行的任务。红黑树的位置，每个CPU有自己的struct rq结构，用于描述所有在此CPU上运行的所有进程，包括实时队列rt_mq和CFS运行队列cfs_mq，调度器首先会去实时队列rt_mq上有没有要运行的进程，没有去cfs_mq去看下是否有进程需要执行，cfs_mq里面有个rb_root指向的是红黑树的根节点，这个红黑树就像一个队列，不断取下一个要运行的进程，rb_leftmost指向最左边的节点。6 调度类如何工作 6.1 sched_class 结构 sched_class next用于指向下一个调度类，enqueue_task用于将就绪的进程加入到调度列表，dequeue用于将进程从调度列表删除，pick_next_task 用于查找下一个任务，6.2 每个CPU上都有一个大队列rq，这个队列包含多个子队列，rt_rq，cfs_rq，CPU找任务要执行的时候，按照优先级依次调度sched_class，不同的sched_class操作不同的队列，，优先rt_mq是否还有task，没有的话，调用fair_sched_class去cfs_

  2019-08-26

  

   2
• 

  kdb_reboot

  可以通过sched_setscheduler和pthread_setschedparam设置进程和线程的API

  作者回复: 赞

  2019-07-27

  

   2
• 

  garlic

  进程线程的API ： http://man7.org/linux/man-pages/man7/sched.7.html, Posix Threads API http://man7.org/linux/man-pages/man7/pthreads.7.html , 实时调度策略可以设置优先级普通调度策略设置nice值。 线程要设置指定的调度策略， 主线程 PTHREAD_EXPLICIT_SCHED 否则默认集成主线程调度策略。 网上找了个例子验证了一下： https://garlicspace.com/2019/07/16/linux-%e8%bf%9b%e7%a8%8b%ef%bc%8c%e7%ba%bf%e7%a8%8b%e7%9a%84%e8%b0%83%e5%ba%a6%e7%ad%96%e7%95%a5api/

  作者回复: 赞

  2019-07-20

  

   2
• 

  叫啥好捏

  大佬假期也不休息么

  作者回复: 写的期间，就没休息过呀

  2019-05-01

  

   2
• 

  闫循鸣

  想要cpu使用率一直100 % 进程的优先级是不是要最高 好一直占用时间片？

  作者回复: 如果创建一个rt的，是能够看到这个现象的

  2019-07-02

  

   1
• 

  Geek__WMK

  @why是小灰吧

  作者回复: 网友见面

  2019-05-27

  

   1
• 

  杨领well

  建议：
  1、源码在第一行标记出具体出处（某某文件某某行）
  2、文中出现的源码尽量将其标签（如：again）的位置标记出来。

  作者回复: 源码很多地方是混合的，重点看逻辑过程哈

  2019-05-22

  

   1
• 

  焰火

  一个task 分配给一个cpu执行后，就不会再被其他cpu 执行了吧？

  作者回复: 是的，同一个时刻同一个cpu只能给一个进程用

  2019-05-02

  

   1
• 

  安排

  讲的清晰明了，但是有个疑问，task_struct中为什么需要指向sched_class的指针呢？没想到有啥作用？

  作者回复: 调度的时候要呀

  2019-05-01

   1

   1
• 

  陈志恒

  1.要了解有哪些部分，这些部分之间的前后关系是啥（流程图）。
  2.摘抄：一个 CPU 上有一个队列，CFS 的队列是一棵红黑树，树的每一个节点都是一个 sched_entity，每个 sched_entity 都属于一个 task_struct，task_struct 里面有指针指向这个进程属于哪个调度类。
  3.这句话就讲解了流程图之间各个部分之间的关系。
  4.前几遍学习注重流程以及其中的关系！

  2019-11-25

  

  
• 

  柳长青

  我可以这么理解吗：就是所有的调度策略都是系统默认设置好了，并不能单独设置个别进程的调度策略，如果要更改系统的调度策略怎么办？

  2019-10-31

  

  
• 

  俩孩儿他爸

  “如果没有才会去 CFS 运行队列找是否有进行需要运行”

  作者回复: 进程。
  
  哈哈哈

  2019-08-26

  

  
• 

  江山未

  有个疑问，sched_class和rq这些结构，都存在内核态的哪里啊，也有一个进程负责维护他们吗，CPU怎么有他们的地址的。。抱歉问题比较多

  作者回复: 到了内核里面，就没有所谓进程不进程了，对于操作系统内核的代码，都是数据结构，随内核怎么操作都行。地址是初始化的时候，重要数据结构的起始地址都是能够找到的。

  2019-07-24

   1

  