趣谈Linux操作系统
刘超
网易杭州研究院云计算技术部首席架构师
立即订阅
19393 人已学习
课程目录
已完结 72 讲
0/4登录后,你可以任选4讲全文学习。
入门准备篇 (3讲)
开篇词 | 为什么要学习Linux操作系统?
免费
01 | 入学测验:你究竟对Linux操作系统了解多少?
02 | 学习路径:爬过这六个陡坡,你就能对Linux了如指掌
核心原理篇:第一部分 Linux操作系统综述 (3讲)
03 | 你可以把Linux内核当成一家软件外包公司的老板
04 | 快速上手几个Linux命令:每家公司都有自己的黑话
05 | 学会几个系统调用:咱们公司能接哪些类型的项目?
核心原理篇:第二部分 系统初始化 (4讲)
06 | x86架构:有了开放的架构,才能打造开放的营商环境
07 | 从BIOS到bootloader:创业伊始,有活儿老板自己上
08 | 内核初始化:生意做大了就得成立公司
09 | 系统调用:公司成立好了就要开始接项目
核心原理篇:第三部分 进程管理 (10讲)
10 | 进程:公司接这么多项目,如何管?
11 | 线程:如何让复杂的项目并行执行?
12 | 进程数据结构(上):项目多了就需要项目管理系统
13 | 进程数据结构(中):项目多了就需要项目管理系统
14 | 进程数据结构(下):项目多了就需要项目管理系统
15 | 调度(上):如何制定项目管理流程?
16 | 调度(中):主动调度是如何发生的?
17 | 调度(下):抢占式调度是如何发生的?
18 | 进程的创建:如何发起一个新项目?
19 | 线程的创建:如何执行一个新子项目?
核心原理篇:第四部分 内存管理 (7讲)
20 | 内存管理(上):为客户保密,规划进程内存空间布局
21 | 内存管理(下):为客户保密,项目组独享会议室封闭开发
22 | 进程空间管理:项目组还可以自行布置会议室
23 | 物理内存管理(上):会议室管理员如何分配会议室?
24 | 物理内存管理(下):会议室管理员如何分配会议室?
25 | 用户态内存映射:如何找到正确的会议室?
26 | 内核态内存映射:如何找到正确的会议室?
核心原理篇:第五部分 文件系统 (4讲)
27 | 文件系统:项目成果要归档,我们就需要档案库
28 | 硬盘文件系统:如何最合理地组织档案库的文档?
29 | 虚拟文件系统:文件多了就需要档案管理系统
30 | 文件缓存:常用文档应该放在触手可得的地方
核心原理篇:第六部分 输入输出系统 (5讲)
31 | 输入与输出:如何建立售前售后生态体系?
32 | 字符设备(上):如何建立直销模式?
33 | 字符设备(下):如何建立直销模式?
34 | 块设备(上):如何建立代理商销售模式?
35 | 块设备(下):如何建立代理商销售模式?
核心原理篇:第七部分 进程间通信 (7讲)
36 | 进程间通信:遇到大项目需要项目组之间的合作才行
37 | 信号(上):项目组A完成了,如何及时通知项目组B?
38 | 信号(下):项目组A完成了,如何及时通知项目组B?
39 | 管道:项目组A完成了,如何交接给项目组B?
40 | IPC(上):不同项目组之间抢资源,如何协调?
41 | IPC(中):不同项目组之间抢资源,如何协调?
42 | IPC(下):不同项目组之间抢资源,如何协调?
核心原理篇:第八部分 网络系统 (7讲)
43 预习 | Socket通信之网络协议基本原理
43 | Socket通信:遇上特大项目,要学会和其他公司合作
44 | Socket内核数据结构:如何成立特大项目合作部?
45 | 发送网络包(上):如何表达我们想让合作伙伴做什么?
46 | 发送网络包(下):如何表达我们想让合作伙伴做什么?
47 | 接收网络包(上):如何搞明白合作伙伴让我们做什么?
48 | 接收网络包(下):如何搞明白合作伙伴让我们做什么?
核心原理篇:第九部分 虚拟化 (7讲)
49 | 虚拟机:如何成立子公司,让公司变集团?
50 | 计算虚拟化之CPU(上):如何复用集团的人力资源?
51 | 计算虚拟化之CPU(下):如何复用集团的人力资源?
52 | 计算虚拟化之内存:如何建立独立的办公室?
53 | 存储虚拟化(上):如何建立自己保管的单独档案库?
54 | 存储虚拟化(下):如何建立自己保管的单独档案库?
55 | 网络虚拟化:如何成立独立的合作部?
核心原理篇:第十部分 容器化 (4讲)
56 | 容器:大公司为保持创新,鼓励内部创业
57 | Namespace技术:内部创业公司应该独立运营
58 | CGroup技术:内部创业公司应该独立核算成本
59 | 数据中心操作系统:上市敲钟
实战串讲篇 (9讲)
60 | 搭建操作系统实验环境(上):授人以鱼不如授人以渔
61 | 搭建操作系统实验环境(下):授人以鱼不如授人以渔
62 | 知识串讲:用一个创业故事串起操作系统原理(一)
63 | 知识串讲:用一个创业故事串起操作系统原理(二)
64 | 知识串讲:用一个创业故事串起操作系统原理(三)
65 | 知识串讲:用一个创业故事串起操作系统原理(四)
66 | 知识串讲:用一个创业故事串起操作系统原理(五)
67 | 期末测试:这些操作系统问题,你真的掌握了吗?
结束语 | 永远别轻视任何技术,也永远别轻视自己
免费
专栏加餐 (2讲)
学习攻略(一):学好操作系统,需要掌握哪些前置知识?
“趣谈Linux操作系统”食用指南
免费
趣谈Linux操作系统
登录|注册

15 | 调度(上):如何制定项目管理流程?

刘超 2019-05-01
前几节,我们介绍了 task_struct 数据结构。它就像项目管理系统一样,可以帮项目经理维护项目运行过程中的各类信息,但这并不意味着项目管理工作就完事大吉了。task_struct 仅仅能够解决“看到”的问题,咱们还要解决如何制定流程,进行项目调度的问题,也就是“做到”的问题。
公司的人员总是有限的。无论接了多少项目,公司不可能短时间增加很多人手。有的项目比较紧急,应该先进行排期;有的项目可以缓缓,但是也不能让客户等太久。所以这个过程非常复杂,需要平衡。
对于操作系统来讲,它面对的 CPU 的数量是有限的,干活儿都是它们,但是进程数目远远超过 CPU 的数目,因而就需要进行进程的调度,有效地分配 CPU 的时间,既要保证进程的最快响应,也要保证进程之间的公平。这也是一个非常复杂的、需要平衡的事情。

调度策略与调度类

在 Linux 里面,进程大概可以分成两种。
一种称为实时进程,也就是需要尽快执行返回结果的那种。这就好比我们是一家公司,接到的客户项目需求就会有很多种。有些客户的项目需求比较急,比如一定要在一两个月内完成的这种,客户会加急加钱,那这种客户的优先级就会比较高。
另一种是普通进程,大部分的进程其实都是这种。这就好比,大部分客户的项目都是普通的需求,可以按照正常流程完成,优先级就没实时进程这么高,但是人家肯定也有确定的交付日期。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《趣谈Linux操作系统》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(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
收起评论
35
返回
顶部