各位吴彦祖&刘亦菲，大家好！
经过深入思考，本号主决定花1-2年时间强更一个系列，暂且叫它《面霸导论》吧！
《面霸导论》有几大块内容：
嘟嘟嘟！抓紧上车了！
想深入理解操作系统的进程调度，需要先获得一些准备知识，这样后面就不懵圈啦：
科技源自生活，调度系统绝对不是计算机领域的专利，现实生活中调度无处不在：
“调度是为了解决资源和需求之间的不匹配问题，现实往往是资源少&需求多，计算机领域也是如此。
在操作系统中CPU资源是有限的，需要使用CPU的进程数量是不确定的，并且大部分情况下进程数量远大于CPU数量，如何解决不匹配问题就是进程调度核心：
操作系统的种类非常多，本身上是硬件层和应用层之间的中间层，对上与应用程序进行交互，对下实现硬件资源的管理。
“批处理是指用户将一批作业提交给操作系统后就不再干预，由操作系统控制它们自动运行，这种采用批量处理作业任务的操作系统称为批处理操作系统，不具有交互性，用户无法干预任务的运行。
“实时系统最大的特点在于计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错，强实时系统一般应用在航空航天、导弹导航制导、核工业等领域。
“分时系统将计算机系统资源（比如CPU）进行时间上的分割，每个时间段称为一个时间片，每个用户依次轮流使用时间片，由于时间间隔很短，每个用户的感觉就像他独占计算机一样，从而有效增加资源的使用率，提高用户交互体验。
Linux属于分时系统，是互联网服务器的主流操作系统，重点研究它就行！
根据进程运行时的状态，可以分为：
“在进程占用CPU期间频繁有IO操作，出现IO阻塞等待情况，比如负责监听socket的进程，真正使用CPU进行计算的时间并不多。
“在进程占用CPU期间基本都在进行计算，很少进行IO操作，期间对CPU的真实使用率很高。
进程调度器需要根据进程是IO密集型还是CPU密集型会采用不同的策略。
对进程的奖惩策略是调度器的一项核心工作，希望大家务必理解：
“交互进程往往伴随较多的IO操作，同时也是响应时间敏感的任务，鼠标点一下半天没响应，想想就很糟糕，因此属于高优先级进程。
“非交互进程往往是纯CPU计算，用户是无感知的，所以对响应时间的要求并没有那么高，属于低优先级进程。
根据进程的重要性，可以分为：
“在操作系统中有很多进程，实时进程是相对重要的，需要保证其CPU占用优先级，普通进程并不需要额外照顾。
实时进程和普通进程的进程优先级不同，调度器都会根据优先级来确定进程的CPU优先权和运行时间。
在Linux中影响优先级的两个因素：Nice谦让值和Priority权重值。
nice值也被称为谦让值，数值越大越谦让，会哭的孩子有奶吃，总谦让优先级肯定低了：
根据进程任务在占用CPU时，使用权是否会被夺取分为：
“进程任务一旦占用CPU只有当任务完成或者因为某些原因主动释放CPU，除上述两种情况外不能被其他进程夺走
“进程任务占用CPU期间可以被其他进程夺走，具体由操作系统调度器决定下一个占用CPU的进程
Linux采用抢占式调度，其可以提高CPU利用率、降低进程的响应时间等，同时也增加了切换进程时的开销，各有利弊。
有两个指标需要重视：
“进程任务从开始排队等待获取CPU资源直到任务完成的时间差，就像超市排队结账时从开始排队到结算完成离开的时间差。
“进程任务从开始排队等待获取CPU资源直到开始使用CPU的时间差，就像超市排队结账时从开始排队到轮到结算的时间差。
综合来说：
只有做到这几点，调度器才可能在周转时间和响应时间上得到一个良好的表现。
要实现一个调度器，主要包括两个核心部分：
算法更多是一种思想，调度器基于某种调度算法进行工程化实现，捋清楚二者的关系对于后续内容的理解将大有裨益。
调度算法也经历了从简单到复杂的演进，到目前为止也没有哪种调度算法是万能的，抛开场景来评判调度算法优劣并不明智。
以下介绍的主要是调度算法的思想，工程上使用的调度算法往往是其中一种或者几种的变形，更加复杂。
先来先服务First Come First Service可以说是最早最简单的调度算法，哪个进程先来就先让它占用CPU，释放CPU之后第二个进程再使用，依次类推。
最短任务优先Shortest Job First的思想是当多个进程同时出现时，优先安排执行时间最短的任务，然后是执行时间次短，以此类推。
SJF可以解决FCFS中同时到达进程执行时间不一致带来的护航效应问题：
SJF的算法思想有些理想化，但并非一无是处，升级改进下也有用武之地：
SJF算法最具启发的地方在于优先调度执行时间短的任务来解决护航效应，但是该算法属于非抢占式调度，对于先后到达且执行时间差别较大的场景也束手无策。
当向SJF算法增加抢占调度时能力就大大增强了，这就是PSJF( Preemptive Shortest Job First )算法。
PSJF算法对于进程A来说却不友好，进程A在被抢占之后只能等待B和C运行完成后，此时如果再来短任务DEF都会抢占A，就会产生饥饿效应。
PSJF算法是基于对任务运行时间长短来进行调度的，但在调度前任务的运行时间是未知的，因此首要问题是通过历史数据来预测运行时间。
时间片轮转RR(Round-Robin)将CPU执行时间按照时钟脉冲进行切割称为时间切片Time-Slice，一个时间切片是时钟周期的数倍，时钟周期和CPU的主频呈倒数关系。
“比如 CPU的主频是1000hz，则时钟周期TimeClick=1ms， Time Slice = n*Time Click，时间切片可以是2ms/4ms/10ms等。
进程往往需要多个循环获取多次时间片才能完成任务，因此需要操作系统记录上一次的数据，等进程下一次被分配时间片时再拿出来，这就是传说中的上下文Context。
进程上下文被存储和拿出的过程被称为上下文切换Context Switch，上下文切换是比较消耗资源的，因此时间片的划分就显得很重要：
RR算法也非银弹，但是响应时间和公平性得到了有效保障，是个非常有意义的算法模型。
多级反馈队列( Multi-Level Feedback Queue )尝试去同时解决响应时间和周转时间两个问题，具体做法：
设置了多个任务队列，每个队列对应的优先级不同，队列内部的优先级相同
优先分配CPU给高优先级的任务，同优先级队列中的任务采用RR轮询机制
通过对任务运行状态的追踪来调整优先级，也就是所谓的Feedback反馈机制
任务在运行期间有较多IO请求和等待，预测为交互进程，优先级保持或提升
任务在运行期间一直进行CPU计算，预测为非交互进程，优先级保持或下降
最初将所以任务都设置为高优先级队列，随着后续的运行状态再进行调整
运行期间有IO操作则保持优先级
运行期间无IO操作则把任务放到低一级的队列中
不同队列分配不同的时间片
高优先级队列往往是IO型任务，配置较小的时间片来保障响应时间
低优先级队列往往是CPU型任务，配置较长时间片来保障任务一直运行
饥饿问题
CPU密集型的任务随着时间推移优先级会越来越低，在IO型进程多的场景下很容易出现饥饿问题，一直无法得到调度
任务是CPU密集型还是IO密集型可能是动态变化的，低优先级队列中的IO型任务的响应时间被拉升，调度频率下降
作弊问题
基于MLFQ对IO型任务的偏爱，用户可能为CPU密集型任务编写无用的IO空操作，从而人为提升任务优先级，相当于作弊
针对上述问题MLFQ还需增加几个补丁：
MLFQ的算法思想在1962年被提出，其作者也获得了图灵奖，可谓是影响深远。
在朴素MLFQ算法基础上出现一些变种，通过工程实现和经验配置最终被使用到操作系统中，成为真正的工业级进程调度器。
Linux的进程调度器是不断演进的，先后出现过三种里程碑式的调度器：
CFS调度器可以说是一种O(logn)调度器，但是其算法思想相比前两种有些不同，并且设计实现上也更加轻量，一直被Linux内核沿用至今。
要理解这些复杂的调度器设计，我们必须要有一个核心主线，再去理解精髓。
调度器需要解决的关键问题：
采用何种数据结构来组织进程以及如何实现pick next
如何根据进程优先级来确定进程运行时间
如何判断进程类型
判断进程的交互性质，是否为IO密集
奖励IO密集型&惩罚CPU密集型
实时进程高优&普通进程低优
如何确定进程的动态优先级
影响因素：静态优先级、nice值、IO密集型和CPU密集型产生的奖惩
在Linux中进程使用task_struct结构体来表示，其中有个counter表示进程剩余的CPU时间片：
struct task_struct {
long counter;
long nice;
unsigned long policy;
int processor;
unsigned long cpus_runnable, cpus_allowed;
}counter值在调度周期开始时被赋值，随着调度的进行递减，直至counter=0表示无可用CPU时间，等待下一个调度周期。
O(n)调度器中调度权重是在goodness函数中完成计算的：
static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
{
int weight;
weight = -1;
/*进程可以设置调度策略为SCHED_YIELD即“礼让”策略，这时候它的权值为-1,权值相当低*/
if (p->policy & SCHED_YIELD)
goto out;
/*
* Non-RT process - normal case first.
*/
/*对于调度策略为SCHED_OTHER的进程，没有实时性要求，它的权值仅仅取决于
* 时间片的剩余和它的nice值，数值上nice越小，则优先级越高，总的权值 = 时间片剩余 + (20 - nice)
* */
if (p->policy == SCHED_OTHER) {
/*
* Give the process a first-approximation goodness value
* according to the number of clock-ticks it has left.
*
* Don't do any other calculations if the time slice is
* over..
*/
weight = p->counter;
if (!weight)
goto out;
#ifdef CONFIG_SMP
/* Give a largish advantage to the same processor... */
/* (this is equivalent to penalizing other processors) */
if (p->processor == this_cpu)
weight += PROC_CHANGE_PENALTY;
#endif
/* .. and a slight advantage to the current MM */
if (p->mm == this_mm || !p->mm)
weight += 1;
weight += 20 - p->nice;
goto out;
}
/*
*对于实时进程，也就是SCHED_FIFO或者SCHED_RR调度策略，
*具有一个实时优先级，总的权值仅仅取决于该实时优先级，
*总的权值 = 1000 + 实时优先级。
* */
weight = 1000 + p->rt_priority;
out:
return weight;
}从代码可以看到：
#if HZ < 200
#define TICK_SCALE(x) ((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x) ((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x) (x)
#elif HZ < 1600
#define TICK_SCALE(x) ((x) << 1)
#else
#define TICK_SCALE(x) ((x) << 2)
#endif
#define NICE_TO_TICKS(nice) (TICK_SCALE(20-(nice))+1)NICE_TO_TICKS是个宏函数，根据不同的调度频率HZ有对应的TICK_SCALE宏定义，这样就解决了不同优先级的进程的时间片分配问题。
O(n)调度器对实时进程和普通进程采用不同的调度策略：
在runqueue中搜索下一个合适的进程是基于动态优先级来实现的，动态优先级最高的就是下一个被执行的进程。
O(n)调度器设计和实现上存在一些问题，但是其中的很多思想为后续调度器设计指明了方向，意义深远。
O(n)调度器在linux内核中大约使用了4年，在Linux 2.6.0采纳了Red Hat公司Ingo Molnar设计的O(1)调度算法，该调度算法的核心思想基于Corbato等人提出的多级反馈队列算法。
O(1)调度器引入了多个队列，并且增加了负载均衡机制，对新出现的进行任务分配到合适的cpu-runqueue中：
struct runqueue {
spinlock_t lock;
unsigned long nr_running;
unsigned long long nr_switches;
unsigned long expired_timestamp, nr_uninterruptible;
unsigned long long timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
int best_expired_prio;
atomic_t nr_iowait;
......
};prio_array_t结构体的定义：
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef struct prio_array prio_array_t;
struct prio_array {
unsigned int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
rq->best_expired_prio = MAX_PRIO;
}
#define NICE_TO_PRIO(nice) (MAX_RT_PRIO + (nice) + 20)
#define NS_TO_JIFFIES(TIME) ((TIME) / (1000000000 / HZ))
#define CURRENT_BONUS(p) \
(NS_TO_JIFFIES((p)->sleep_avg) * MAX_BONUS / \
MAX_SLEEP_AVG)
static int effective_prio(task_t *p)
{
int bonus, prio;
if (rt_task(p))
return p->prio;
bonus = CURRENT_BONUS(p) - MAX_BONUS / 2;
prio = p->static_prio - bonus;
if (prio < MAX_RT_PRIO)
prio = MAX_RT_PRIO;
if (prio > MAX_PRIO-1)
prio = MAX_PRIO-1;
return prio;
}O(1)调度器为了实现复杂场景IO密集型任务的识别，做了大量的工作仍然无法到达100%的准确，但不可否认O(1)调度器是一款非常优秀的产品。
O(1)调度器本质上是MLFQ算法的思想，随着时间的推移也暴露除了很多问题，主要集中在O(1)调度器对进程交互性的判断上积重难返。
无论是O(n)还是O(1)都需要去根据进程的运行状况判断它属于IO密集型还是CPU密集型，再做优先级奖励和惩罚，这种推测本身就会有误差，而且场景越复杂判断难度越大。
是继续优化进程交互性算法，还是另辟蹊径呢？一直困扰着Linux社区的大神们。
在CFS出现之前，不得不提一位有态度&有实力的麻醉师Con Kolivas，同时也是linux内核开发者，他在进程调度领域有自己独到的见解。
Con Kolivas针对O(1)调度器存在的维护和优化问题，提出了楼梯调度算法（Staircase Deadline Scheduler）和 基于公平策略RSDL调度器(The Rotating Staircase Deadline Schedule)，遗憾的是Linux之父并没有采纳RDSL调度器。
对此Con Kolivas感到很愤怒，离开了Linux内核开发社区，但是事实上从后面CFS调度器几个版本的修订来看，Con Kolivas的大方向是正确的，离开之后的Con Kolivas又开发了BFS(Brain Fuck Scheduler)来对抗CFS调度器。
“没错，BFS调度器译为脑残调度器，可见Con Kolivas的愤怒和不满。
在2.6.23内核中引入scheduling class的概念，将调度器模块化，系统中可以有多种调度器，使用不同策略调度不同类型的进程：
这样一来，CFS调度器就不关心实时进程了，专注于普通进程就可以了。
CFS( Completely Fair Scheduler )完全公平调度器，从实现思想上和之前的O(1)/O(n)很不一样。
这个世界怎么会有绝对的公平呢？为啥这个调度器敢说自己是完全公平呢？
这一切CFS是如何实现的呢？我们继续看！
O(1)和O(n)都将CPU资源划分为时间片，采用了固定额度分配机制，在每个调度周期进程可使用的时间片是确定的，调度周期结束被重新分配。
CFS摒弃了固定时间片分配，采用动态时间片分配，本次调度中进程可占用的时间与进程总数、总CPU时间、进程权重等均有关系，每个调度周期的值都可能会不一样。
CFS调度器从进程优先级出发，它建立了优先级prio和权重weight之间的映射关系，把优先级转换为权重来参与后续的计算：
const int sched_prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};“普通进程的优先级范围是[100,139]，prio整体减小120就和代码左边的注释对上了，也就是nice值的范围[-20,19]，因此sched_prio=0相当于static_prio=120。
比如现有进程A sched_prio=0，进程B sched_prio=-5，通过sched_prio_to_weight的映射：
在CFS中引入sysctl_sched_latency(调度延迟)作为一个调度周期，真实的CPU时间表示为：
每个进程的物理运行时间时肯定不能一样的，CFS调度器只要保证的就是进程的虚拟运行时间相等即可。
那虚拟运行时间该如何计算呢？
“virtual_time = wall_time * nice_0_weight/sched_prio_to_weigh
比如现有进程A sched_prio=0，进程B sched_prio=-5：
经过这样映射，A和B的虚拟时间就相等了。
上述公式涉及了除法和浮点数运算，因此需要转换成为乘法来保证数据准确性，再给出虚拟时间计算的变形等价公式：
“virtual_time = (wall_time * nice_0_weight * 2^32/sched_prio_to_weigh)>>32
“令 inv_weight = 2^32/sched_prio_to_weigh
“则 virtual_time = (wall_time * 1024 * inv_weight)>>32
由于sched_prio_to_weigh的值存储在数组中，inv_weight同样可以：
const u32 sched_prio_to_wmult[40] = {
/* -20 */ 48388, 59856, 76040, 92818, 118348,
/* -15 */ 147320, 184698, 229616, 287308, 360437,
/* -10 */ 449829, 563644, 704093, 875809, 1099582,
/* -5 */ 1376151, 1717300, 2157191, 2708050, 3363326,
/* 0 */ 4194304, 5237765, 6557202, 8165337, 10153587,
/* 5 */ 12820798, 15790321, 19976592, 24970740, 31350126,
/* 10 */ 39045157, 49367440, 61356676, 76695844, 95443717,
/* 15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};经过一番计算，各个进程的虚拟运行时间一致了，似乎我们理解了"完全公平"的思想。
虚拟运行时间与优先级的衰减因子有关，也就是inv_weight随着nice值增大而增大，同时其作为分母也加速了低优先级进程的衰减。
“简言之：CFS将物理运行时间在不同优先级进程中发生了不同的通胀。
摒弃了固定时间片机制也是CFS的亮点，系统负载高时大家都少用一些CPU，系统负载低时大家都多用一些CPU，让调度器有了一定的自适应能力。
那么这些进程应该采用哪种数据结构来实现pick-next算法呢？
CFS调度器采用了红黑树来保存活跃进程任务，红黑树的增删查复杂度是O(logn)，但是CFS引入了一些额外的数据结构，可以免去遍历获得下一个最合适的进程。
红黑树的key是进程已经使用的虚拟运行时间，并且把虚拟时间数值最小的放到最左的叶子节点，这个节点就是下一个被pick的进程了。
前面已经论证了，每个进程的虚拟运行时间是一样的，数值越小表示被调度的越少，因此需要更偏爱一些，当虚拟运行时间耗尽则从红黑树中删除，下个调度周期开始后再添加到红黑树上。
本文由哈喽比特于2年以前收录，如有侵权请联系我们。
文章来源：https://mp.weixin.qq.com/s/OtA6S_KWvPbbLKJvgQYukA
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
