时钟或者钟表（clock）是一种计时工具，每个人都至少有一块，可能在你的手机里，也可能佩戴在你的手腕上。如果Linux也是一个普通人的话，那么她的手腕上应该有十几块手表，包括：CLOCK_REALTIME、CLOCK_MONOTONIC、CLOCK_PROCESS_CPUTIME_ID、CLOCK_THREAD_CPUTIME_ID、CLOCK_MONOTONIC_RAW、CLOCK_REALTIME_COARSE、CLOCK_MONOTONIC_COARSE、CLOCK_BOOTTIME、CLOCK_REALTIME_ALARM、CLOCK_BOOTTIME_ALARM、CLOCK_TAI。本文主要就是介绍Linux内核中的形形色色的“钟表”。

二、理解Linux中各种clock分类的基础

既然本文讲Linux中的计时工具，那么我们首先面对的就是“什么是时间？”，这个问题实在是太难回答了，因此我们这里就不正面回答了，我们只是从几个侧面来窥探时间的特性，而时间的本质就留给物理学家和哲学家思考吧。

1、如何度量时间

时间往往是和变化相关，因此人们往往喜欢使用有固定周期变化规律的运动行为来定义时间，于是人们把地球围自转一周的时间分成24份，每一份定义为一个小时，而一个小时被平均分成3600份，每一份就是1秒。然而，地球的运动周期不是那么稳定，怎么办？多测量几个，平均一下嘛。

虽然通过天体的运动定义了秒这样的基本的时间度量单位，但是，要想精确的表示时间，我们依赖一种有稳定的周期变化的现象。上一节我们说过了：地球围绕太阳运转不是一个稳定的周期现象，因此每次观察到的周期不是固定的（当然都大约是24小时的样子），用它来定义秒多少显得不是那么精准。科学家们发现铯133原子在能量跃迁时候辐射的电磁波的振荡频率非常的稳定（不要问我这是什么原理，我也不知道），因此被用来定义时间的基本单位：秒（或者称之为原子秒）。

2、Epoch

定义了时间单位，等于时间轴上有了刻度，虽然这条代表时间的直线我们不知道从何开始，最终去向何方，我们终归是可以把一个时间点映射到这条直线上了。甚至如果定义了原点，那么我们可以用一个数字（到原点的距离）来表示时间。

如果说定义时间的度量单位是技术活，那么定义时间轴的原点则完全是一个习惯问题。拿出你的手表，上面可以读出2017年5月10，23时17分28秒07毫秒……作为一个地球人，你选择了耶稣诞辰日做原点，讲真，这弱爆了。作为linuxer，你应该拥有这样的一块手表，从这个手表上只能看到一个从当前时间点到linux epoch的秒数和毫秒数。Linux epoch定义为1970-01-01 00:00:00 +0000 (UTC)，后面的这个UTC非常非常重要，我们后面会描述。

除了wall time，linux系统中也需要了解系统自启动以来过去了多少的时间，这时候，我们可以把钟表的epoch调整成系统的启动时间点，这时候获取系统启动时间就很容易了，直接看这块钟表的读数即可。

3、时间调整

记得小的时候，每隔一段时间，老爸的手表总会慢上一分钟左右的时间，也是他总是在7点钟，新闻联播之前等待那校时的最后一响。一听到“刚才最后一响是北京时间7点整”中那最后“滴”的一声，老爸也把自己的手表调整成为7点整。对于linux系统，这个操作类似clock_set接口函数。

类似老爸机械表的时间调整，linux的时间也需要调整，机械表的发条和齿轮结构没有那么精准，计算机的晶振亦然。前面讲了，UTC的计时是基于原子钟的，但是来到Linux内核这个场景，我们难道要为我们的计算机安装一个原子钟来计时吗？当然可以，如果你足够有钱的话。我们一般人的计算机还是基于系统中的本地振荡器来计时的，虽然精度不理想，但是短时间内你也不会有太多的感觉。当然，人们往往是向往更精确的计时（有些场合也需要），因此就有了时间同步的概念（例如NTP（Network Time Protocol））。

所谓时间同步其实就是用一个精准的时间来调整本地的时间，具体的调整方式有两种，一种就是直接设定当前时间值，另外一种是采用了润物细无声的形式，对本地振荡器的输出进行矫正。第一种方法会导致时间轴上的时间会向前或者向后的跳跃，无法保证时间的连续性和单调性。第二种方法是对时间轴缓慢的调整（而不是直接设定），从而保证了连续性和单调性。

4、闰秒（leap second）

通过原子秒延展出来的时间轴就是TAI（International Atomic Time）clock。这块“表”不管日出、日落，机械的按照ce原子定义的那个秒在推进时间。冷冰冰的TAI clock虽然精准，但是对人类而言是不友好的，毕竟人还是生活在这颗蓝色星球上。而那些基于地球自转，公转周期的时间（例如GMT）虽然符合人类习惯，但是又不够精确。在这样的背景下，UTC（Coordinated Universal Time）被提出来了，它是TAI clock的基因（使用原子秒），但是又会适当的调整（leap second），满足人类生产和生活的需要。

OK，至此，我们了解了TAI和UTC两块表的情况，这两块表的发条是一样的，按照同样的时间滴答（tick，精准的根据原子频率定义的那个秒）来推动钟表的秒针的转动，唯一不同的是，UTC clock有一个调节器，在适当的时间，可以把秒针向前或者向后调整一秒。

TAI clock和UTC clock在1972年进行了对准（相差10秒），此后就各自独立运行了。在大部分的时间里，UTC clock跟随TAI clock，除了在适当的时间点，realtime clock会进行leap second的补偿。从1972年到2017年，已经有了27次leap second，因此TAI clock的读数已经比realtime clock（UTC时间）快了37秒。换句话说，TAI和UTC两块表其实可以抽象成一个时间轴，只不过它们之间有一个固定的偏移。在1972年，它们之间的offset是10秒，经过多年的运转，到了2017年，offset累计到37秒，让我静静等待下一个leap second到了的时刻吧。

5、计时范围

有一类特殊的clock称作秒表，启动后开始计时，中间可以暂停，可以恢复。我们可以通过这样的秒表来记录一个人睡眠的时间，当进入睡眠状态的时候，按下start按键开始计时，一旦醒来则按下stop，暂停计时。linux中也有这样的计时工具，用来计算一个进程或者线程的执行时间。

6、时间精度

时间是连续的吗？你眼中的世界是连续的吗？看到窗外清风吹拂的树叶的时候，你感觉每一个树叶的形态都被你捕捉到了。然而，未必，你看急速前进的汽车的轮胎的时候，感觉车轮是倒转的。为什么？其实这仅仅是因为我们的眼睛大约是每秒15～20帧的速度在采样这个世界，你看到的世界是离散的。算了，扯远了，我们姑且认为时间的连续的，但是Linux中的时间记录却不是连续的，我们可以用下面的图片表示：

系统在每个tick到来的时候都会更新系统时间（到linux epoch的秒以及纳秒值记录），当然，也有其他场景进行系统时间的更新，这里就不赘述了。因此，对于linux的时间而言，它是一些离散值，是一些时间采样点的值而已。当用户请求时间服务的时候，例如获取当前时间（上图中的红线），那么最近的那个Tick对应的时间采样点值再加上一个当前时间点到上一个tick的delta值就精准的定位了当前时间。不过，有些场合下，时间精度没有那么重要，直接获取上一个tick的时间值也基本是OK的，不需要校准那个delta也能满足需求。而且粗粒度的clock会带来performance的优势。

7、睡觉的时候时间会停止运作吗？

在现实世界提出这个问题会稍显可笑，鲁迅同学有一句名言：时间永是流逝，街市依旧太平。但是对于Linux系统中的clock，这个就有现实的意义了。比如说clock的一个重要的派生功能是创建timer（也就是说timer总是基于一个特定的clock运作）。在一个5秒的timer超期之前，系统先进入了suspend或者关机状态，这时候，5秒时间到达的时候，一般的timer都不会触发，因为底层的clock可能是基于一个free running counter的，在suspend或者关机状态的时候，这个HW counter都不再运作了，你如何期盼它能唤醒系统，来执行timer expired handler？但是用户还是有这方面的实际需求的，最简单的就是关机闹铃。怎么办？这就需要一个特别的clock，能够在suspend或者关机的时候，仍然可以运作，推动timer到期触发。

三、Linux下的各种clock总结

在linux系统中定义了如下的clock id：

>#define CLOCK_REALTIME            0
>#define CLOCK_MONOTONIC            1
>#define CLOCK_PROCESS_CPUTIME_ID    2
>#define CLOCK_THREAD_CPUTIME_ID        3
>#define CLOCK_MONOTONIC_RAW        4
>#define CLOCK_REALTIME_COARSE        5
>#define CLOCK_MONOTONIC_COARSE        6
>#define CLOCK_BOOTTIME            7
>#define CLOCK_REALTIME_ALARM        8
>#define CLOCK_BOOTTIME_ALARM        9
>#define CLOCK_SGI_CYCLE            10    /* Hardware specific */
>#define CLOCK_TAI            11

CLOCK_PROCESS_CPUTIME_ID和CLOCK_THREAD_CPUTIME_ID这两个clock是专门用来计算进程或者线程的执行时间的（用于性能剖析），一旦进程（线程）被切换出去，那么该进程（线程）的clock就会停下来。因此，这两种的clock都是per-process或者per-thread的，而其他的clock都是系统级别的。

根据上面一章的各种分类因素，我们可以将其他clock总结整理如下：

建立在cpu 础之上的内核-聊聊cpu

超线程是针对cpu提出的一种概念与实现，那么超线程的定义是什么？从某文档中摘抄的定义如下：

超线程(hyper-theading)其实就是同时多线程(simultaneous multi-theading),是一项允许一个CPU执行多个控制流的技术。它的原理很简单，就是把一颗CPU当成两颗来用，将一颗具有超线程功能的物理CPU变成两颗逻辑CPU，而逻辑CPU对操作系统来说，跟物理CPU并没有什么区别。因此，操作系统会把工作线程分派给这两颗（逻辑）CPU上去执行，让（多个或单个）应用程序的多个线程，能够同时在同一颗CPU上被执行。注意：两颗逻辑CPU共享单颗物理CPU的所有执行资源。因此，我们可以认为，超线程技术就是对CPU的虚拟化。

比如上述描述，说超线程是让多个线程能同时在同一颗cpu上被执行，其实我觉得这种描述都不够准确，精确的定义应该是：

超线程是同一个时钟周期内一个物理核心上可以执行两个线程或者进的技术。

超线程的定义主要在三个点上，第一个就是同一个时钟周期内，第二个是同一个物理核心，第三个就是两个线程同时执行。

正常情况下，没有超线程技术，以上三个条件是绝对无法满足的。

现在开始去分析超线程的实现过程。

首先，为了让单核cpu发挥更大的作，超线程只是其中一种技术，相关的技术还有很多，比如超标量技术等。

指令的基本执行过程包括：
>取指Fetch）:：从存储器取指令，并更新PC
>译码（Decode）：指令译码，从寄存器堆读出寄存器的值
>执行（Execute）：运算指令：进行算术逻辑运算，访存指令：计算存储器的地址
>访存（Memory）：Load指令：从存储器读指令，Store指令：将数据写入寄存器
>回写（Write Back）：将数据写入寄存器堆

更具体而言，在具体执行过程中，这几个步骤还会区分前端和后端，而且还会有一些相关的技术。
再具体而言，

前端

>前端按顺序取指令和译码，将X86指令翻译成uop。通过分支预测来提前执行最可能的程序路径。
>带有超标量功能的执行引擎每时钟周期最多执行6条uop。带有乱序功能的执行引擎能够重排列uop执行顺序，只要源数据准备好了，即可执行uop。
>顺序提交功能确保最后执行结果，包括碰到的异常，跟源程序顺序一致。

后端

The Out-of-Order Engine

当一个执行流程再等待资源时，比如l2 cache数据，乱序引擎可以把另一个执行流程的uop发射给执行核心。

> Renamer：每时钟周期最多发射4条uop(包括unfused, micro-fused, or macro-fused)。它的工作为：1 重命名uop里的寄存器，解决false dependencies问题。2 分配资源给给uop，例如load or store buffers。3 绑定uop到合适的dispatch port。
>某些uop可以在rename阶段完成，从而不占用之后的执行带宽。
>Micro-fused load 和store操作此时会分解为2条uop，这样就会占用2个发射槽（总共4个）。（没明白为啥之前2条uop融合为一条了现在又分解回2条）
>Scheduler:当uop需要的资源就绪时，即可调度给下一步执行。根据执行单元可用的ports，writeback buses，就绪uop的优先级, 调度器来选择被发射的uop。
>The Execution Core：具有6个ports，每时钟周期最多发射6条uop。指令发射给port执行完成后，需要把数据通过writeback bus写回。每个port有多个不同运算器，这意味着可以有多个不同uop在同一个port里执行，不同uop的写回延时并不相同，但是writeback bus只能独享，这就会造成uop的等待。Sandy Bridge架构尽可能消除改延时，通过把不同类型数据写回到不同的execution stack中来避免。

而超线程的实现就是基于以上前端和后端过程的改造与实现。

首先从物理cpu层面上：

从因特尔的cpu开发手册上，我们可以找到超线程的相关实现部分，架构图如下：

从该架构图上，我们可以看到一个物理核心上有两个逻辑核心，他们有共享的部分也有独立的部分，比如APIC，这个叫做可编程中断控制器，也就是说逻辑核心也是可以自己独立接收中断信号的。

通过该手册，我们可以清楚的了解到超线程中的逻辑核与物理核之间的区别。

The following features are part of he architectural state of logical processors within Intel 64 or IA-32 processors supporting Intel Hyper-Threading Technology. The features can be subdivided into three groups:【以下相关寄存器的作用在文章建立在cpu 基础之上的内核-聊聊cpu中有介绍，但是通过该手册可以了解到，逻辑核心中的大部分寄存器都是独立的，换句话说，在cpu核心中存在双份】

>Duplicated for each logical processor
>Shared by logical processors in a physical processor
>Shared or duplicated, depending on the implementation
>The following features are duplicated for each logical processor:
>General purpose registers (EAX, EBX, ECX, EDX, ESI, EDI, ESP, and EBP)
>Segment registers (CS, DS, SS, ES, FS, and GS)
>EFLAGS and EIP registers. Note that the CS and EIP/RIP registers for each logical processor point to the instruction stream for the thread being executed by the logical processor.
>x87 FPU registers (ST0 through ST7, status word, control word, tag word, data operand pointer, and instruction pointer)
>MMX registers (MM0 through MM7)
>XMM registers (XMM0 through XMM7) and the MXCSR register
>Control registers and system table pointer registers (GDTR, LDTR, IDTR, task register)
>Debug registers (DR0, DR1, DR2, DR3, DR6, DR7) and the debug control MSRs
>Machine check global status (IA32_MCG_STATUS) and machine check capability (IA32_MCG_CAP) MSRs
>Thermal clock modulation and ACPI Power management control MSRs
>Time stamp counter MSRs
>Most of the other MSR registers, including the page attribute table (PAT). See the exceptions below.
>Local APIC registers.
>Additional general purpose registers (R8-R15), XMM registers (XMM8-XMM15), control register,IA32_EFER on Intel 64 processors.
The following features are shared by logical processors:
>Memory type range registers (MTRRs)
Whether the following features are shared or duplicated is implementation-specific:
>IA32_MISC_ENABLE MSR (MSR address 1A0H)
>Machine check architecture (MCA) MSRs (except for the IA32_MCG_STATUS and IA32_MCG_CAP MSRs)
>Performance monitoring control and counter MSRs

其次从指令处理流程上：

整体流程如下

从指令处理过程中，两个逻辑核心都是单独的处理流

前端处理部分

红和黄分属不同的逻辑核心，在有些步骤不作区分，比如解码

后端部分，在某些流程共享，某些流程独立。

更加具体的可以阅读相关论文

https://www.moreno.marzolla.name/teachi … _art01.pdf

简而言之，超线程的实现是基于物理层面cpu的支持，在一个物理核心中通过改造寄存器的数量以及共享其他资源，从而实现近似于两个物理核心的能力，在操作系统层面可以把线程和进程向上调度，从而更充分的利用资源，提升cpu性能。

但是共享内存队列难免会有 入队+出队 2次 memcpy 。

而且要变长共享内存队列，如果支持多生产者进程+多消费者进程 ，就要处理线程安全方面的问题， 比较麻烦。

process_vm_readv() ,  process_vm_writev() 是 Linux 3.2 新增的 syscall，用于在多个进程的地址空间之间，高效传输大块数据。

https://www.man7.org/linux/man-pages/ma … adv.2.html

https://github.com/open-mpi/ompi/blob/m … _get.c#L96

在此， 我提个设想，可以用  process_vm_readv 实现一个多进程内存队列，相比之下，优势是：
>在处理 多线程/多进程 并发时，更简单
>省掉一次 memcpy。

函数声明

#include <sys/uio.h>
ssize_t process_vm_readv(pid_t pid,
                         const struct iovec *local_iov,
                         unsigned long liovcnt,
                         const struct iovec *remote_iov,
                         unsigned long riovcnt,
                         unsigned long flags);
ssize_t process_vm_writev(pid_t pid,
                          const struct iovec *local_iov,
                          unsigned long liovcnt,
                          const struct iovec *remote_iov,
                          unsigned long riovcnt,
                          unsigned long flags);

参数说明
>pid                    进程pid号
>struct iovec *local_iov        结构体local进程指向一个数组基地址
>liovcnt                    local进程数组大小
>struct iovec *remote_iov    结构体remote进程指向一个数组基地址
>riovcnt                remote进程数组大小
>flags                    默认0

介绍

这些系统调用在不同进程地址空间之间传输数据。调用进程：“local进程”以及“remote进程”。数据直接在两个进程的地址空间传输，无需通过内核空间。前提是必须知道传输数据的大小。

process_vm_readv()从remote进程传送数据到local进程。要传输的数据由remote_iov和riovcnt标识：remote_iov指向一个数组，用于描述remote进程的地址范围，而riovcnt指定remote_iov中的元素数。数据传输到由local_iov和liovcnt指定的位置：local_iov是指向描述地址范围的数组的指针。并且liovcnt指定local_iov中的元素数。

process_vm_writev()系统调用是process_vm_readv()的逆过程。它从local进程传送数据到remote进程。除了转移的方向，参数liovcnt，local_iov，riovcnt和remote_iov具有相同的参数含义，与process_vm_readv()相同。

local_iov和remote_iov参数指向iovec结构的数组，在<sys / uio.h>中定义为：

<sys/uio.h>
   struct iovec {
               void  *iov_base;    /* 地址基址 */
               size_t iov_len;     /* 数据传输字节数 */
           };

缓冲区以数组顺序处理。 这意味着process_vm_readv()在进行到local_iov [1]之前会完全填充local_iov [0]，依此类推。 同样，在进行remote_iov [1]之前，将完全读取remote_iov[0]，依此类推。

同样，process_vm_writev()在local_iov [1]之前写出local_iov [0]的全部内容，并在remote_iov [1]之前完全填充remote_iov [0]。

remote_iov[i].iov_len

和

local_iov[i].iov_len

的长度不必相同。 因此，可以将单个本地缓冲区拆分为多个远程缓冲区，反之亦然。

flags参数当前未使用，必须设置为0。
返回值

成功后，process_vm_readv()返回读取的字节数，process_vm_writev()返回写入的字节数。 如果发生部分读/写，则此返回值可能小于请求的字节总数。 调用方应检查返回值以确定是否发生了部分读/写。

错误时，返回-1并正确设置errno。

示例

以下代码示例演示了process_vm_readv()的用法，它从具有PID的进程中读取地址上的19个字节，并将前10个字节写入buf1，并将后10个字节写入buf2。

#include <sys/uio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <string.h>
#include <fcntl.h>
#include <errno.h>
#include <iostream>

using namespace std;

int main(void) {
    struct iovec local[2];
    struct iovec remote[1];
    char buf1[10];
    char buf2[10];
    char remote_addr[]={"abc1234567890defABC"};
    long data_len = strlen(remote_addr);

    ssize_t nread;
    pid_t pid = getpid();             //PID of remote process

//读remotedata_len个字节，buf1 ：10 ； buf2 :10
    local[0].iov_base = buf1;
    local[0].iov_len = 10;
    local[1].iov_base = buf2;
    local[1].iov_len = 10;
    remote[0].iov_base = remote_addr;
    remote[0].iov_len = data_len;


    nread = process_vm_readv(pid, local, 2, remote, 1, 0);
    cout<<"cout nread:"<<nread<<endl;
    fprintf(stderr,"read in CreateProcess %s, Process ID %d \n",strerror(errno),pid);

    printf("buf1: %s\n",buf1);
    printf("buf2: %s\n",buf2);

}

相关的系统调用还有readv,writev,preadv,pwritev,preadv2,pwrite2

#include <sys/uio.h>

       ssize_t readv(int fd, const struct iovec *iov, int iovcnt);

       ssize_t writev(int fd, const struct iovec *iov, int iovcnt);

       ssize_t preadv(int fd, const struct iovec *iov, int iovcnt,
                      off_t offset);

       ssize_t pwritev(int fd, const struct iovec *iov, int iovcnt,
                       off_t offset);

       ssize_t preadv2(int fd, const struct iovec *iov, int iovcnt,
                       off_t offset, int flags);

       ssize_t pwritev2(int fd, const struct iovec *iov, int iovcnt,
                        off_t offset, int flags);

示例如下：

int main(){
    char *str0 = "hello ";
    char *str1 = "world\n";
    struct iovec iov[2];
    ssize_t nwritten;

    iov[0].iov_base = str0;
    iov[0].iov_len = strlen(str0);
    iov[1].iov_base = str1;
    iov[1].iov_len = strlen(str1);

    nwritten = writev(STDOUT_FILENO, iov, 2);

    printf("nwritten: %d\n",nwritten);
}

一般来说，在操作系统中会运行多个进程（几个到几千个不等），但一台计算机的 CPU 资源是有限的，如 8 核的 CPU 只能同时运行 8 个进程。那么当进程数大于 CPU 核心数时，操作系统是如何同时运行这些进程的呢？

这里就涉及 进程调度 问题。

操作系统运行进程的时候，是按 时间片 来运行的。时间片 是指一段很短的时间段（如20毫秒），操作系统会为每个进程分配一些时间片。当进程的时间片用完后，操作系统将会把当前运行的进程切换出去，然后从进程队列中选择一个合适的进程运行，这就是所谓的 进程调度。如下图所示：

什么是组调度

一般来说，操作系统调度的实体是 进程，也就是说按进程作为单位来调度。但如果按进程作为调度实体，就会出现以下情况：

   Linux 是一个支持多用户的操作系统，如果 A 用户运行了 10 个进程，而 B 用户只运行了 2 个进程，那么就会出现 A 用户使用的 CPU 时间是 B 用户的 5 倍。如果 A 用户和 B 用户都是花同样的钱来买的虚拟主机，那么对 B 用户来说是非常不公平的。

为了解决这个问题，Linux 实现了 组调度 这个功能。那么什么是 组调度 呢？

组调度 的实质是：调度时候不再以进程作为调度实体，而是以 进程组 作为调度实体。比如上面的例子，可以把 A 用户运行的进程划分为 进程组A，而 B 用户运行的进程划分为 进程组B。

调度的时候，进程组A 和 进程组B 分配到相同的可运行 时间片，如 进程组A 和 进程组B 各分配到 100 毫秒的可运行时间片。由于 进程组A 有 10 个进程，所以每个进程分配到的可运行时间片为 10 毫秒。而 进程组B 只有 2 个进程，所以每个进程分配到的可运行时间片为 50 毫秒。

下图是 组调度 的原理：

如上图所示，当内核进行调度时，首先以 进程组 作为调度实体。当选择出最优的 进程组 后，再从 进程组 中选择出最优的进程进行运行，而被切换出来的进程将会放置回原来的 进程组。

由于 组调度 是建立在 cgroup 机制之上的，而 cgroup 又是基于 虚拟文件系统，所以 进程组 是以树结构存在的。也就是说，进程组 除了可以包含进程，还可以包含进程组。如下图所示：

  cgroup 相关的知识点可以参考文章：《cgroup介绍》 和 《cgroup实现原理》

在 Linux 系统启动时，会创建一个根进程组 init_task_group。然后，我们可以通过使用 cgroup 的 CPU 子系统创建新的进程组，如下命令：

$ mkdir /sys/cgroup/cpu/A                     # 在根进程组中创建进程组A
$ mkdir /sys/cgroup/cpu/B                     # 在根进程组中创建进程组B
$ mkdir /sys/cgroup/cpu/A/C                   # 在进程组A中创建进程组C
$ echo 1923 > /sys/cgroup/cpu/A/cgroup.procs  # 向进程组A中添加进程ID为1923的进程

Linux 在调度的时候，首先会根据 完全公平调度算法 从根进程组中筛选出一个最优的进程或者进程组进行调度。

   如果筛选出来的是进程，那么可以直接把当前运行的进程切换到筛选出来的进程运行即可。
   如果筛选出来的是进程组，那么就继续根据 完全公平调度算法 从进程组中筛选出一个最优的进程或者进程组进行调度（重复进行第一步操作），如此类推。

组调度实现

接下来，我们将介绍 组调度 是如何实现的。在分析之前，为了对 完全公平调度算法 有个大体了解，建议先看看这篇文章：《Linux完全公平调度算法 》。
1. 进程组

在 Linux 内核中，使用 task_group 结构表示一个进程组。其定义如下：

struct task_group {
    struct cgroup_subsys_state css; // cgroup相关结构

    struct sched_entity **se;       // 调度实体(每个CPU分配一个)
    struct cfs_rq **cfs_rq;         // 完全公平调度运行队列(每个CPU分配一个)
    unsigned long shares;           // 当前进程组权重(用于获取时间片)
    ...

    // 由于进程组支持嵌套, 也就是说进程组可以包含进程组
    // 所以, 进程组可以通过下面3个成员组成一个树结构
    struct task_group *parent;  // 父进程组
    struct list_head siblings;  // 兄弟进程组
    struct list_head children;  // 子进程组
};

下面介绍一下 task_group 结构各个字段的作用：

    se：完全公平调度算法 是以 sched_entity 结构作为调度实体（也就是说运行队列中的元素都是 sched_entity 结构），而 sched_entity 结构既能代表一个进程，也能代表一个进程组。这个字段主要作用是，将进程组放置到运行队列中进行调度。由于进程组中的进程可能会在不同的 CPU 上运行，所以这里为每个 CPU 分配一个 sched_entity 结构。
    cfs_rq：完全公平调度算法 的运行队列。完全公平调度算法 在调度时是通过 cfs_rq 结构完成的，cfs_rq 结构使用一棵红黑树将需要调度的进程或者进程组组织起来，然后选择最左端的节点作为要运行的进程或进程组，详情可以参考文章：《Linux完全公平调度算法》。由于进程组可能在不同的 CPU 上调度，所以进程组也为每个 CPU 分配一个运行队列。
   shares：进程组的权重，用于计算当前进程组的可运行时间片。
   parent、siblings、children：用于将系统中所有的进程组组成一棵亲属关系树。

task_group、sched_entity 和 cfs_rq 这三个结构的关系如下图所示：

从上图可以看出，每个进程组都为每个 CPU 分配一个可运行队列，可运行队列中保存着可运行的进程和进程组。Linux 调度的时候，就是从上而下（从根进程组开始）地筛选出最优的进程进行运行。
2. 调度过程

当 Linux 需要进行进程调度时，会调用 schedule() 函数来完成，其实现如下（经精简后）：

void __sched schedule(void)
{
    struct task_struct *prev, *next;
    struct rq *rq;
    int cpu;
    ...

    rq = cpu_rq(cpu); // 获取当前CPU的可运行队列
    ...

    prev->sched_class->put_prev_task(rq, prev); // 把当前运行的进程放回到运行队列
    next = pick_next_task(rq, prev);            // 从可运行队列筛选一个最优的可运行的进程

    if (likely(prev != next)) {
        ...
        // 将旧进程切换到新进程
        context_switch(rq, prev, next); /* unlocks the rq */
        ...
    }

    ...
}

schedule() 函数会调用 pick_next_task() 函数来筛选最优的可运行进程，我们来看看 pick_next_task() 函数的实现过程：

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
    const struct sched_class *class;
    struct task_struct *p;

    // 如果所有进程都是使用完全公平调度
    if (likely(rq->nr_running == rq->cfs.nr_running)) {
        p = fair_sched_class.pick_next_task(rq);
        if (likely(p))
            return p;
    }
    ...
}

从 pick_next_task() 函数的实现来看，其最终会调用 完全公平调度算法 的 pick_next_task() 方法来完成筛选工作，我们来看看这个方法的实现：

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct task_struct *p;
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    ...

    do {
        se = pick_next_entity(cfs_rq); // 从可运行队列中获取最优的可运行实体

        // 如果最优可运行实体是一个进程组,
        // 那么将继续从进程组中获取到当前CPU对应的可运行队列
        cfs_rq = group_cfs_rq(se);
    } while (cfs_rq);

    p = task_of(se); // 最后一定会获取一个进程
    ...

    return p; // 返回最优可运行进程
}

我们来分析下 pick_next_task_fair() 函数到流程：

    从根进程组中筛选出最优的可运行实体（进程或进程组）。
    如果筛选出来的实体是进程，那么直接返回这个进程。
    如果筛选出来的实体是进程组，那么将会继续对这个进程组中的可运行队列进行筛选，直至筛选出一个可运行的进程。

  怎么区分 sched_entity 实体是进程或者进程组？sched_entity 结构中有个 my_q 的字段，当这个字段设置为 NULL 时，说明这个实体是一个进程。如果这个字段指向一个可运行队列时，说明这个实体是一个进程组。

CRIU是一个为Linux实现检查点/恢复功能的项目。全称Checkpoint/Restore In Userspace，或者CRIU，是一个Linux软件。它可以冻结正在运行的容器（或单个应用程序）并将其状态检查点保存到磁盘上。保存的数据可以用于恢复应用程序并将其完全运行到冻结时的状态。使用此功能，现在可以实现应用程序或容器的实时迁移、快照、远程调试等许多其他功能。CRIU最初是Virtuozzo的一个项目，并得到社区的巨大帮助。它目前被（集成到）OpenVZ、LXC /LXD、Docker、Podman和其他软件中，并为许多Linux发行版打包。
使用场景

    容器实时迁移：容器被检查点，然后将镜像复制到另一台计算机上，然后进行恢复。从远程观察者的角度来看，容器只是暂时冻结了。
    快速启动服务：CRIU可以帮助加速需要启动时间较长的服务或应用程序的启动过程，通过在服务的初始化状态创建检查点，以便在需要时可以快速启动。
    无缝内核升级：CRIU可用于在不中断正在运行的进程的情况下进行内核升级，确保系统保持在线并运行。
    网络负载均衡：CRIU可以与负载均衡器一起使用，以实现流量在不同节点之间的无缝切换，从而提高系统的可伸缩性和可用性。
    高性能计算问题：在高性能计算环境中，CRIU可用于保存和恢复运行中的计算任务，以便在硬件或软件故障发生时保护计算工作。
    桌面环境挂起/恢复：CRIU可以用于实现桌面环境中应用程序的挂起和恢复，以便在需要时恢复到以前的状态。
    进程复制：CRIU允许将进程从一个系统复制到另一个系统，这对于应用程序迁移和负载均衡非常有用。
    应用程序的“保存”功能：CRIU可以为不具备“保存”功能的应用程序（如游戏）添加保存和恢复功能，以便用户可以在中断后继续进行。
    应用程序快照：CRIU可以创建应用程序的快照，以便在需要时可以恢复到特定状态。
    将“遗忘”的应用程序移动到“屏幕”：CRIU可以帮助将在后台运行的应用程序转移到前台或“屏幕”，以便用户更容易访问它们。
    在另一台机器上分析应用程序行为：CRIU可用于在不同的系统上分析应用程序的运行和行为，以进行性能和安全性分析。
    调试挂起的应用程序：CRIU可以用于调试挂起状态的应用程序，以便了解其状态和执行。
    容错系统：CRIU可用于创建容错系统，以在故障时自动保存和恢复系统状态。
    更新模拟测试：CRIU可以用于模拟系统更新和升级，以检查它们对系统的影响，而无需实际执行更新。
    零停机崩溃恢复：CRIU可以用于实现零停机的崩溃恢复，确保系统在发生故障时可以迅速恢复到正常运行状态。

CRIU实现原理

CRIU的功能的实现基本分为两个过程,checkpoint和restore。在checkpoint过程，criu主要通过ptrace机制把一段特殊代码动态注入到dumpee进程（待备份的程序进程）并运行，这段特殊代码就实现了收集dumpee进程的所有上下文信息，然后criu把这些上下文信息按功能分类存储为一个个镜像文件。在restore过程。criu解析checkpoint过程产生的镜像文件，以此来恢复程序备份前的状态没，让程序从备份前的状态继续运行。
  下面详细介绍checkpoint和restore这两个过程。
Checkpoint

checkpoint的过程基本依赖ptrace（linux 提供的系统调用，进程跟踪）功能实现。程序严重依赖/proc文件系统，/proc是一个基于内存的文件系统，包括CPU、内存、分区划分、[I/O地址]、直接内存访问通道和正在运行的进程等等，Linux通过/proc访问内核内部数据结构及更改内核设置等，它从/proc收集的信息包括：

    文件描述信息（通过/proc/p i d / f d 和/proc/pid/fdinfo）
    管道参数信息
    内存表（通过/proc/p i d / m a p s 和/proc/pid/map_files/）

checkpoint过程中，criu做的工作由如下步骤组成：
说明：在描述checkpoint中，我们把criu进程称为dumper进程，简称dumper。把要备份的进程称为dumpee进程，简称dumpee。

步骤1：收集并且冻结dumpee的进程树
  dumper通过dumpee的pid遍历/proc/%pid/task/路径收集线程tid，并且递归遍历/proc/p i d / t a s k / pid/task/pid/task/tid/children，然后通过 ptrace函数的PTRACE_ATTACH和PTRACE_SEIZE命令冻结dumpee程序。

步骤2：收集dumpee的资源并保存
  在这个阶段，dumper获取dumpee的所有可获取的资源信息并写到文件里。这些资源的获取通过如下步骤：

    通过 /proc/p i d / s m a p s ∗ ∗ 解 析 所 有 V M A s 区 域 ， 并且通过∗∗/proc/pid/map_files 连接读取所有maps文件。
    通过 /proc/$pid/fd获取文件描述号。
    通过ptrace接口和解析/proc/$pid/stat块完成一个进程的核心参数（寄存器和friends）的获取。
    通过ptrace接口向dumpee注入parasite code。这个过程由两步完成：首先注入mmap系统调用到任务被冻结那一刻的CS:IP位置，然后ptrace允许我们运行这个被注入的系统调用，这样我们就在被监控进程里申请到了足够的内存用于parasite code块。接下来把parasite code拷贝到这个新申请到的内存地址，并把CS:IP指向到parasite code的位置。

步骤3：清理dumpee
  dumper获取到dumpee所有信息（比如内存页，它只能从被监控程序内部地址空间写出）后，我们使用ptrace的系列参数去掉步骤2中对dumpee进程的修改。主要是对被注入代码的清理并并恢复dumpee的地址空间。基本通过PTRACE_DETACH 和 PTACE_CONT。然后criu可以选择杀死dumpee或者让dumpee继续运行。上面的test实例中选择的就是在备份dumpee后杀死进程，实际工作中，如果要对程序做差分备份（或者叫增量备份）时可以选择继续运行dumpee。
Restore

恢复程序的过程完全依赖checkpoint过程后产生的镜像文件，主要过程分如下4步：

步骤1：处理共享资源
  在这个步骤里，criu读取*.img镜像文件并找出哪些（子）进程共享了哪些资源，比如共享内存。如果有共享资源存在，稍后共享资源由这个程序的某个（子）进程还原，其他进程要么在第2阶段继承一个（如会话），要么以其他方式获取。例如，后者是通过unix套接字与SCM-CREDS消息一起发送的共享文件，或者是通过memfd文件描述符还原的共享内存区域。

步骤2：生成进程树
  在这一步，CRIU会调用fork()函数一次或多次来重新创建所需进程。

步骤3：恢复基本的资源信息
  在此阶段CRIU打开文件、准备namespaces、重新映射所有私有内存区域、创建sockets、调用chdir() 和 chroot()等等。

步骤4：切换到dumpee的上下文
  通过将restorer.built-in.bin的代码注入到dumpee进程，来完成余下的内存区域、timers、credentials、threads的恢复。
支持的系统平台

x86：主流x86架构（Intel、AMD），兼容i386
arm：细分armv6/armv7/armv8指令集，向下兼容
aarch64：arm架构额64位系统（基于armv8指令集的64位架构）
ppc64：IBM power系列架构
s390：IBM System z系列大型机硬件平台
mips：龙芯mips架构，根据浪潮云对龙芯平台的需求开发
参考文献

https://github.com/checkpoint-restore/criu

https://criu.org/Main_Page

对于容器技术而言，它实现资源层面上的限制和隔离，依赖于 Linux 内核所提供的 cgroup 和 namespace 技术。

我们先对这两项技术的作用做个概括：

cgroup 的主要作用：管理资源的分配、限制；
namespace 的主要作用：封装抽象，限制，隔离，使命名空间内的进程看起来拥有他们自己的全局资源；

本篇，我们重点来聊 namespace 。

Namespace 是什么？

我们引用 wiki 上对 namespace 的定义：

“Namespaces are a feature of the Linux kernel that partitions kernel resources such that one set of processes sees one set of resources while another set of processes sees a different set of resources. The feature works by having the same namespace for a set of  resources and processes, but those namespaces refer to distinct resources.”

namespace 是 Linux 内核的一项特性，它可以对内核资源进行分区，使得一组进程可以看到一组资源；而另一组进程可以看到另一组不同的资源。该功能的原理是为一组资源和进程使用相同的 namespace，但是这些 namespace 实际上引用的是不同的资源。

这样的说法未免太绕了些，简单来说 namespace 是由 Linux 内核提供的，用于进程间资源隔离的一种技术。将全局的系统资源包装在一个抽象里，让进程（看起来）拥有独立的全局资源实例。同时 Linux 也默认提供了多种 namespace，用于对多种不同资源进行隔离。

在之前，我们单独使用 namespace 的场景比较有限，但 namespace 却是容器化技术的基石。

我们先来看看它的发展历程。

Namespace 的发展历程

图 1 ，namespace 的历史过程
最早期 - Plan 9

namespace 的早期提出及使用要追溯到 Plan 9 from Bell Labs ，贝尔实验室的 Plan 9。这是一个分布式操作系统，由贝尔实验室的计算科学研究中心在八几年至02年开发的（02年发布了稳定的第四版，距离92年发布的第一个公开版本已10年打磨），现在仍然被操作系统的研究者和爱好者开发使用。在 Plan 9 的设计与实现中，我们着重提以下3点内容：

文件系统：所有系统资源都列在文件系统中，以 Node 标识。所有的接口也作为文件系统的一部分呈现。
Namespace：能更好的应用及展示文件系统的层次结构，它实现了所谓的 “分离”和“独立”。
标准通信协议：9P协议（Styx/9P2000）。

开始加入 Linux Kernel

Namespace 开始进入 Linux Kernel 的版本是在 2.4.X，最初始于 2.4.19 版本。但是，自 2.4.2 版本才开始实现每个进程的 namespace。

图 3 ，Linux Kernel Note

图 4 ，Linux Kernel 对应的各操作系统版本
Linux 3.8 基本实现

Linux 3.8 中终于完全实现了 User Namespace 的相关功能集成到内核。这样 Docker 及其他容器技术所用到的 namespace 相关的能力就基本都实现了。

图 5 ，Linux Kernel 从 2001 到2013 逐步演变，完成了 namespace 的实现

Namespace 类型

系统主机名和 NIS(Network Information Service) 主机名（有时称为域名）

Cgroup namespaces

Cgroup namespace 是进程的 cgroups 的虚拟化视图，通过 /proc/[pid]/cgroup 和 /proc/[pid]/mountinfo 展示。

使用 cgroup namespace 需要内核开启 CONFIG_CGROUPS 选项。可通过以下方式验证：

(MoeLove) ➜ grep CONFIG_CGROUPS /boot/config-$(uname -r)
CONFIG_CGROUPS=y

cgroup namespace 提供的了一系列的隔离支持：

防止信息泄漏（容器不应该看到容器外的任何信息）。
简化了容器迁移。
限制容器进程资源，因为它会把 cgroup 文件系统进行挂载，使得容器进程无法获取上层的访问权限。

每个 cgroup namespace 都有自己的一组 cgroup 根目录。这些 cgroup 的根目录是在 /proc/[pid]/cgroup 文件中对应记录的相对位置的基点。当一个进程用 CLONE_NEWCGROUP（clone(2) 或者 unshare(2)） 创建一个新的 cgroup namespace时，它当前的 cgroups 的目录就变成了新 namespace 的 cgroup 根目录。

(MoeLove) ➜ cat /proc/self/cgroup 
0::/user.slice/user-1000.slice/session-2.scope

当一个目标进程从 /proc/[pid]/cgroup 中读取 cgroup 关系时，每个记录的路径名会在第三字段中展示，会关联到正在读取的进程的相关 cgroup 分层结构的根目录。如果目标进程的 cgroup 目录位于正在读取的进程的 cgroup namespace 根目录之外时，那么，路径名称将会对每个 cgroup 层次中的上层节点显示 ../ 。

我们来看看下面的示例（这里以 cgroup v1 为例，如果你想看 v2 版本的示例，请在留言中告诉我）：

在初始的 cgroup namespace 中，我们使用 root （或者有 root 权限的用户），在 freezer 层下创建一个子 cgroup 名为 moelove-sub，同时，将进程放入该 cgroup 进行限制。

**(MoeLove) ➜ mkdir -p /sys/fs/cgroup/freezer/moelove-sub
(MoeLove) ➜ sleep 6666666 & 
[1] 1489125                  
(MoeLove) ➜ echo 1489125 > /sys/fs/cgroup/freezer/moelove-sub/cgroup.procs
**

我们在 freezer 层下创建另外一个子 cgroup，名为 moelove-sub2， 并且再放入执行进程号。可以看到当前的进程已经纳入到  moelove-sub2的 cgroup 下管理了。

(MoeLove) ➜ mkdir -p /sys/fs/cgroup/freezer/moelove-sub2
(MoeLove) ➜ echo $$
1488899
(MoeLove) ➜ echo 1488899 > /sys/fs/cgroup/freezer/moelove-sub2/cgroup.procs 
(MoeLove) ➜ cat /proc/self/cgroup |grep freezer
7:freezer:/moelove-sub2

我们使用 unshare(1) 创建一个进程，这里使用了 -C参数表示是新的 cgroup namespace， 使用了 -m参数表示是新的 mount namespace。

(MoeLove) ➜ unshare -Cm bash
root@moelove:~#

从用 unshare(1) 启动的新 shell 中，我们可以在 /proc/[pid]/cgroup 文件中看到，新 shell 和以上示例中的进程：

root@moelove:~# cat /proc/self/cgroup | grep freezer
7:freezer:/
root@moelove:~# cat /proc/1/cgroup | grep freezer
7:freezer:/..

# 第一个示例进程

root@moelove:~# cat /proc/1489125/cgroup | grep freezer
7:freezer:/../moelove-sub

从上面的示例中，我们可以看到新 shell 的 freezer cgroup 关系中，当新的 cgroup namespace 创建时，freezer cgroup 的根目录与它的关系也就建立了。

root@moelove:~# cat /proc/self/mountinfo | grep freezer
1238 1230 0:37 /.. /sys/fs/cgroup/freezer rw,nosuid,nodev,noexec,relatime - cgroup cgroup rw,freezer

第四个字段 ( /..) 显示了在 cgroup 文件系统中的挂载目录。从 cgroup namespaces 的定义中，我们可以知道，进程当前的 freezer cgroup 目录变成了它的根目录，所以这个字段显示 /.. 。我们可以重新挂载来处理它。

root@moelove:~# mount --make-rslave /
root@moelove:~# umount /sys/fs/cgroup/freezer
root@moelove:~# mount -t cgroup -o freezer freezer /sys/fs/cgroup/freezer
root@moelove:~# cat /proc/self/mountinfo | grep freezer
1238 1230 0:37 / /sys/fs/cgroup/freezer rw,relatime - cgroup freezer rw,freezer
root@moelove:~# mount |grep freezer
freezer on /sys/fs/cgroup/freezer type cgroup (rw,relatime,freezer)

IPC namespaces

IPC namespaces 隔离了 IPC 资源，如 System V IPC objects、  POSIX message queues。每个 IPC namespace 都有着自己的一组 System V IPC 标识符，以及 POSIX 消息队列系统。在一个 IPC namespace 中创建的对象，对所有该 namespace 下的成员均可见（对其他 namespace 下的成员均不可见）。

使用 IPC namespace 需要内核支持 CONFIG_IPC_NS 选项。如下：

(MoeLove) ➜ grep CONFIG_IPC_NS /boot/config-$(uname -r)
CONFIG_IPC_NS=y

可以在 IPC namespace 中设置以下 /proc 接口：

    /proc/sys/fs/mqueue - POSIX 消息队列接口
    /proc/sys/kernel - System V IPC 接口 （msgmax, msgmnb, msgmni, sem, shmall, shmmax, shmmni, shm_rmid_forced）
    /proc/sysvipc - System V IPC 接口

当 IPC namespace 被销毁时（空间里的最后一个进程都被停止删除时），在 IPC namespace 中创建的 object 也会被销毁。
Network namepaces

Network namespaces 隔离了与网络相关的系统资源（这里罗列一些）：

    network devices - 网络设备
    IPv4 and IPv6 protocol stacks - IPv4、IPv6 的协议栈
    IP routing tables - IP 路由表
    firewall rules - 防火墙规则
    /proc/net （即 /proc/PID/net）
    /sys/class/net
    /proc/sys/net 目录下的文件
    端口、socket
    UNIX domain abstract socket namespace

使用 Network namespaces 需要内核支持 CONFIG_NET_NS 选项。如下：

(MoeLove) ➜ grep CONFIG_NET_NS /boot/config-$(uname -r)
CONFIG_NET_NS=y

一个物理网络设备只能存在于一个 Network namespace 中。当一个 Network namespace 被释放时（空间里的最后一个进程都被停止删除时），物理网络设备将被移动到初始的 Network namespace 而不是上层的 Network namespace。

一个虚拟的网络设备(veth(4)) ，在 Network namespace 间通过一个类似管道的方式进行连接。这使得它能存在于多个 Network namespace，但是，当 Network namespace 被摧毁时，该空间下包含的 veth(4) 设备可能被破坏。
Mount namespaces

Mount namespaces 最早出现在 Linux 2.4.19 版本。Mount namespaces 隔离了各空间中挂载的进程实例。每个 mount namespace 的实例下的进程会看到不同的目录层次结构。

每个进程在 mount namespace 中的描述可以在下面的文件视图中看到：

  /proc/[pid]/mounts
  /proc/[pid]/mountinfo
  /proc/[pid]/mountstats

一个新的 Mount namespace 的创建标识是 CLONE_NEWNS ，使用了 clone(2) 或者 unshare(2) 。

如果 Mount namespace 用 clone(2) 创建，子 namespace 的挂载列表是从父进程的 mount namespace 拷贝的。
如果 Mount namespace 用 unshare(2) 创建，新 namespace 的挂载列表是从调用者之前的 moun namespace 拷贝的。

如果 mount namespace 发生了修改，会引起什么样的连锁反应？下面，我们就在 共享子树中谈谈。

每个 mount 都被可以有如下标记 ：

MS_SHARED - 与组内每个成员分享 events 。也就是说相同的 mount 或者 unmount 将自动发生在组内其他的 mounts  中。反之，mount 或者 unmount 事件 也会影响这次的 event 动作。
MS_PRIVATE - 这个 mount 是私有的。mount 或者 unmount events 都不会影响这次的 event 动作。
MS_SLAVE - mount 或者 unmount events 会从 master 节点传入影响该节点。但是这个节点下的 mount 或者 unmount events 不会影响组内的其他节点。
MS_UNBINDABLE - 这也是个私有的 mount 。任何尝试绑定的 mount 在这个设置下都将失败。

在文件 /proc/[pid]/mountinfo 中可以看到 propagation 类型的字段。每个对等组都会由内核生成唯一的 ID ，同一对等组的 mount 都是这个 ID（即，下文中的 X ）。

(MoeLove) ➜ cat /proc/self/mountinfo  |grep root  
65 1 0:33 /root / rw,relatime shared:1 - btrfs /dev/nvme0n1p6 rw,seclabel,compress=zstd:1,ssd,space_cache,subvolid=256,subvol=/root
1210 65 0:33 /root/var/lib/docker/btrfs /var/lib/docker/btrfs rw,relatime shared:1 - btrfs /dev/nvme0n1p6 rw,seclabel,compress=zstd:1,ssd,space_cache,subvolid=256,subvol=/root

  shared:X - 在组 X 中共享。
  master:X - 对于组 X 而言是 slave，即，从属于 ID 为 X 的主。
  propagate_from:X - 接收从组 X 发出的共享 mount。这个标签总是个 master:X 一同出现。
  unbindable -  表示不能被绑定，即，不与其他关联从属。

新 mount namespace 的传播类型取决于它的父节点。如果父节点的传播类型是 MS_SHARED ，那么新 mount namespace 的传播类型是 MS_SHARED ，不然会默认为 MS_PRIVATE。

关于 mount namespaces 我们还需要注意以下几点：

（1）每个  mount namespace 都有一个 owner user namespace。如果新的 mount namespace 和拷贝的 mount namespace 分属于不同的 user namespace ，那么，新的 mount namespace 优先级低。

（2）当创建的 mount namespace 优先级低时，那么，slave 的 mount events 会优先于 shared 的 mount events。

（3）高优先级和低优先级的 mount namespace 有关联被锁定在一起时，他们都不能被单独卸载。

（4）mount(2) 标识和 atime 标识会被锁定，即，不能被传播影响而修改。
小结

以上就是关于 Linux 内核中 namespace 的一些介绍了，篇幅原因，剩余部分以及 namespace 在容器中的应用我们放在下一篇中介绍，敬请期待

cgroups 是Linux内核提供的一种可以限制单个进程或者多个进程所使用资源的机制，可以对 cpu，内存等资源实现精细化的控制，目前越来越火的轻量级容器 Docker 就使用了 cgroups 提供的资源限制能力来完成cpu，内存等部分的资源控制。

另外，开发者也可以使用 cgroups 提供的精细化控制能力，限制某一个或者某一组进程的资源使用。比如在一个既部署了前端 web 服务，也部署了后端计算模块的八核服务器上，可以使用 cgroups 限制 web server 仅可以使用其中的六个核，把剩下的两个核留给后端计算模块。

本文从以下四个方面描述一下 cgroups 的原理及用法：

    cgroups 的概念及原理
    cgroups 文件系统概念及原理
    cgroups 使用方法介绍
    cgroups 实践中的例子

概念及原理
cgroups子系统

cgroups 的全称是control groups，cgroups为每种可以控制的资源定义了一个子系统。典型的子系统介绍如下：

    cpu 子系统，主要限制进程的 cpu 使用率。
    cpuacct 子系统，可以统计 cgroups 中的进程的 cpu 使用报告。
    cpuset 子系统，可以为 cgroups 中的进程分配单独的 cpu 节点或者内存节点。
    memory 子系统，可以限制进程的 memory 使用量。
    blkio 子系统，可以限制进程的块设备 io。
    devices 子系统，可以控制进程能够访问某些设备。
    net_cls 子系统，可以标记 cgroups 中进程的网络数据包，然后可以使用 tc 模块（traffic control）对数据包进行控制。
    freezer 子系统，可以挂起或者恢复 cgroups 中的进程。
    ns 子系统，可以使不同 cgroups 下面的进程使用不同的 namespace。

这里面每一个子系统都需要与内核的其他模块配合来完成资源的控制，比如对 cpu 资源的限制是通过进程调度模块根据 cpu 子系统的配置来完成的；对内存资源的限制则是内存模块根据 memory 子系统的配置来完成的，而对网络数据包的控制则需要 Traffic Control 子系统来配合完成。本文不会讨论内核是如何使用每一个子系统来实现资源的限制，而是重点放在内核是如何把 cgroups 对资源进行限制的配置有效的组织起来的，和内核如何把cgroups 配置和进程进行关联的，以及内核是如何通过 cgroups 文件系统把cgroups的功能暴露给用户态的。
cgroups 层级结构（Hierarchy）

内核使用 cgroup 结构体来表示一个 control group 对某一个或者某几个 cgroups 子系统的资源限制。cgroup 结构体可以组织成一颗树的形式，每一棵cgroup 结构体组成的树称之为一个 cgroups 层级结构。cgroups层级结构可以 attach 一个或者几个 cgroups 子系统，当前层级结构可以对其 attach 的 cgroups 子系统进行资源的限制。每一个 cgroups 子系统只能被 attach 到一个 cpu 层级结构中。

比如上图表示两个cgroups层级结构，每一个层级结构中是一颗树形结构，树的每一个节点是一个 cgroup 结构体（比如cpu_cgrp, memory_cgrp)。第一个 cgroups 层级结构 attach 了 cpu 子系统和 cpuacct 子系统， 当前 cgroups 层级结构中的 cgroup 结构体就可以对 cpu 的资源进行限制，并且对进程的 cpu 使用情况进行统计。 第二个 cgroups 层级结构 attach 了 memory 子系统，当前 cgroups 层级结构中的 cgroup 结构体就可以对 memory 的资源进行限制。

在每一个 cgroups 层级结构中，每一个节点（cgroup 结构体）可以设置对资源不同的限制权重。比如上图中 cgrp1 组中的进程可以使用60%的 cpu 时间片，而 cgrp2 组中的进程可以使用20%的 cpu 时间片。

####cgroups与进程

上面的小节提到了内核使用 cgroups 子系统对系统的资源进行限制，也提到了 cgroups 子系统需要 attach 到 cgroups 层级结构中来对进程进行资源控制。本小节重点关注一下内核是如何把进程与 cgroups 层级结构联系起来的。

在创建了 cgroups 层级结构中的节点（cgroup 结构体）之后，可以把进程加入到某一个节点的控制任务列表中，一个节点的控制列表中的所有进程都会受到当前节点的资源限制。同时某一个进程也可以被加入到不同的 cgroups 层级结构的节点中，因为不同的 cgroups 层级结构可以负责不同的系统资源。所以说进程和 cgroup 结构体是一个多对多的关系。

上面这个图从整体结构上描述了进程与 cgroups 之间的关系。最下面的P代表一个进程。每一个进程的描述符中有一个指针指向了一个辅助数据结构css_set（cgroups subsystem set）。 指向某一个css_set的进程会被加入到当前css_set的进程链表中。一个进程只能隶属于一个css_set，一个css_set可以包含多个进程，隶属于同一css_set的进程受到同一个css_set所关联的资源限制。

上图中的”M×N Linkage”说明的是css_set通过辅助数据结构可以与 cgroups 节点进行多对多的关联。但是 cgroups 的实现不允许css_set同时关联同一个cgroups层级结构下多个节点。 这是因为 cgroups 对同一种资源不允许有多个限制配置。

一个css_set关联多个 cgroups 层级结构的节点时，表明需要对当前css_set下的进程进行多种资源的控制。而一个 cgroups 节点关联多个css_set时，表明多个css_set下的进程列表受到同一份资源的相同限制。
cgroups文件系统

Linux 使用了多种数据结构在内核中实现了 cgroups 的配置，关联了进程和 cgroups 节点，那么 Linux 又是如何让用户态的进程使用到 cgroups 的功能呢？ Linux内核有一个很强大的模块叫 VFS (Virtual File System)。 VFS 能够把具体文件系统的细节隐藏起来，给用户态进程提供一个统一的文件系统 API 接口。 cgroups 也是通过 VFS 把功能暴露给用户态的，cgroups 与 VFS 之间的衔接部分称之为 cgroups 文件系统。下面先介绍一下 VFS 的基础知识，然后再介绍下 cgroups 文件系统的实现。
VFS

VFS 是一个内核抽象层，能够隐藏具体文件系统的实现细节，从而给用户态进程提供一套统一的 API 接口。VFS 使用了一种通用文件系统的设计，具体的文件系统只要实现了 VFS 的设计接口，就能够注册到 VFS 中，从而使内核可以读写这种文件系统。 这很像面向对象设计中的抽象类与子类之间的关系，抽象类负责对外接口的设计，子类负责具体的实现。其实，VFS本身就是用 c 语言实现的一套面向对象的接口。
通用文件模型

VFS 通用文件模型中包含以下四种元数据结构：

    超级块对象(superblock object)，用于存放已经注册的文件系统的信息。比如ext2，ext3等这些基础的磁盘文件系统，还有用于读写socket的socket文件系统，以及当前的用于读写cgroups配置信息的 cgroups 文件系统等。

    索引节点对象(inode object)，用于存放具体文件的信息。对于一般的磁盘文件系统而言，inode 节点中一般会存放文件在硬盘中的存储块等信息；对于socket文件系统，inode会存放socket的相关属性，而对于cgroups这样的特殊文件系统，inode会存放与 cgroup 节点相关的属性信息。这里面比较重要的一个部分是一个叫做 inode_operations 的结构体，这个结构体定义了在具体文件系统中创建文件，删除文件等的具体实现。

    文件对象(file object)，一个文件对象表示进程内打开的一个文件，文件对象是存放在进程的文件描述符表里面的。同样这个文件中比较重要的部分是一个叫 file_operations 的结构体，这个结构体描述了具体的文件系统的读写实现。当进程在某一个文件描述符上调用读写操作时，实际调用的是 file_operations 中定义的方法。 对于普通的磁盘文件系统，file_operations 中定义的就是普通的块设备读写操作；对于socket文件系统，file_operations 中定义的就是 socket 对应的 send/recv 等操作；而对于cgroups这样的特殊文件系统，file_operations 中定义的就是操作 cgroup 结构体等具体的实现。

    目录项对象(dentry object)，在每个文件系统中，内核在查找某一个路径中的文件时，会为内核路径上的每一个分量都生成一个目录项对象，通过目录项对象能够找到对应的 inode 对象，目录项对象一般会被缓存，从而提高内核查找速度。

#####cgroups文件系统的实现

基于 VFS 实现的文件系统,都必须实现 VFS 通用文件模型定义的这些对象，并实现这些对象中定义的部分函数。cgroup 文件系统也不例外,下面来看一下 cgroups 中这些对象的定义。

首先看一下 cgroups 文件系统类型的结构体：

static struct file_system_type cgroup_fs_type = {
        .name = "cgroup",
        .mount = cgroup_mount,
        .kill_sb = cgroup_kill_sb,
};

这里面两个函数分别代表安装和卸载某一个 cgroup 文件系统所需要执行的函数。每次把某一个 cgroups 子系统安装到某一个装载点的时候，cgroup_mount 方法就会被调用，这个方法会生成一个 cgroups_root（cgroups层级结构的根）并封装成超级快对象。

然后看一下 cgroups 超级块对象定义的操作：

static const struct super_operations cgroup_ops = {
        .statfs = simple_statfs,
        .drop_inode = generic_delete_inode,
        .show_options = cgroup_show_options,
        .remount_fs = cgroup_remount,
};

本文并不去研究这些函数的代码实现是什么样的，但是从这些代码可以推断出，cgroups 通过实现 VFS 的通用文件系统模型，把维护 cgroups 层级结构的细节，隐藏在 cgroups 文件系统的这些实现函数中。

从另一个方面说，用户在用户态对 cgroups 文件系统的操作，通过 VFS 转化为对 cgroups 层级结构的维护。通过这样的方式，内核把 cgroups 的功能暴露给了用户态的进程。
cgroups使用方法
cgroups文件系统挂载

Linux中，用户可以使用mount命令挂载 cgroups 文件系统，格式为: mount -t cgroup -o subsystems name /cgroup/name，其中 subsystems 表示需要挂载的 cgroups 子系统， /cgroup/name 表示挂载点，如上文所提，这条命令同时在内核中创建了一个cgroups 层级结构。

比如挂载 cpuset, cpu, cpuacct, memory 4个subsystem到/cgroup/cpu_and_mem 目录下，就可以使用 mount -t cgroup -o remount,cpu,cpuset,memory cpu_and_mem /cgroup/cpu_and_mem

在centos下面，在使用yum install libcgroup安装了cgroups模块之后，在 /etc/cgconfig.conf 文件中会自动生成 cgroups 子系统的挂载点:

mount {
    cpuset  = /cgroup/cpuset;
    cpu = /cgroup/cpu;
    cpuacct = /cgroup/cpuacct;
    memory  = /cgroup/memory;
    devices = /cgroup/devices;
    freezer = /cgroup/freezer;
    net_cls = /cgroup/net_cls;
    blkio   = /cgroup/blkio;
}

上面的每一条配置都等价于展开的 mount 命令，例如mount -t cgroup -o cpuset cpuset /cgroup/cpuset。这样系统启动之后会自动把这些子系统挂载到相应的挂载点上。

####子节点和进程

挂载某一个 cgroups 子系统到挂载点之后，就可以通过在挂载点下面建立文件夹或者使用cgcreate命令的方法创建 cgroups 层级结构中的节点。比如通过命令cgcreate -t sankuai:sankuai -g cpu:test就可以在 cpu 子系统下建立一个名为 test 的节点。结果如下所示：

[root@idx cpu]# ls
cgroup.event_control  cgroup.procs  cpu.cfs_period_us  cpu.cfs_quota_us  cpu.rt_period_us   cpu.rt_runtime_us  cpu.shares  cpu.stat  lxc  notify_on_release  release_agent  tasks  test

然后可以通过写入需要的值到 test 下面的不同文件，来配置需要限制的资源。每个子系统下面都可以进行多种不同的配置，需要配置的参数各不相同，详细的参数设置需要参考 cgroups 手册。使用 cgset 命令也可以设置 cgroups 子系统的参数，格式为 cgset -r parameter=value path_to_cgroup。

当需要删除某一个 cgroups 节点的时候，可以使用 cgdelete 命令，比如要删除上述的 test 节点，可以使用 cgdelete -r cpu:test命令进行删除

把进程加入到 cgroups 子节点也有多种方法，可以直接把 pid 写入到子节点下面的 task 文件中。也可以通过 cgclassify 添加进程，格式为 cgclassify -g subsystems:path_to_cgroup pidlist，也可以直接使用 cgexec 在某一个 cgroups 下启动进程，格式为gexec -g subsystems:path_to_cgroup command arguments.
实践中的例子

相信大多数人都没有读过 Docker 的源代码，但是通过这篇文章，可以估计 Docker 在实现不同的 Container 之间资源隔离和控制的时候，是可以创建比较复杂的 cgroups 节点和配置文件来完成的。然后对于同一个 Container 中的进程，可以把这些进程 PID 添加到同一组 cgroups 子节点中已达到对这些进程进行同样的资源限制。

通过各大互联网公司在网上的技术文章，也可以看到很多公司的云平台都是基于 cgroups 技术搭建的，其实也都是把进程分组，然后把整个进程组添加到同一组 cgroups 节点中，受到同样的资源限制。

笔者所在的广告组，有一部分任务是给合作的广告投放网站生成“商品信息”，广告投放网站使用这些信息，把广告投放在他们各自的网站上。但是有时候会有恶意的爬虫过来爬取商品信息，所以我们生成了另外“一小份”数据供优先级较低的用户下载，这时候基本能够区分开大部分恶意爬虫。对于这样的“一小份”数据，对及时更新的要求不高，生成商品信息又是一个比较费资源的任务，所以我们把这个任务的cpu资源使用率限制在了50%。

首先在 cpu 子系统下面创建了一个 halfapi 的子节点：cgcreate abc:abc -g cpu:halfapi。

然后在配置文件中写入配置数据：echo 50000 > /cgroup/cpu/halfapi/cpu.cfs_quota_us。cpu.cfs_quota_us中的默认值是100000，写入50000表示只能使用50%的 cpu 运行时间。

最后在这个cgroups中启动这个任务：cgexec -g "cpu:/halfapi" php halfapi.php half >/dev/null 2>&1

在 cgroups 引入内核之前，想要完成上述的对某一个进程的 cpu 使用率进行限制，只能通过 nice 命令调整进程的优先级，或者 cpulimit 命令限制进程使用进程的 cpu 使用率。但是这些命令的缺点是无法限制一个进程组的资源使用限制，也就无法完成 Docker 或者其他云平台所需要的这一类轻型容器的资源限制要求。

同样，在 cgroups 之前，想要完成对某一个或者某一组进程的物理内存使用率的限制，几乎是不可能完成的。使用 cgroups 提供的功能，可以轻易的限制系统内某一组服务的物理内存占用率。 对于网络包，设备访问或者io资源的控制，cgroups 同样提供了之前所无法完成的精细化控制。
结语

本文首先介绍了 cgroups 在内核中的实现方式，然后介绍了 cgroups 如何通过 VFS 把相关的功能暴露给用户，然后简单介绍了 cgroups 的使用方法，最后通过分析了几个 cgroups 在实践中的例子，进一步展示了 cgroups 的强大的精细化控制能力。

笔者希望通过整篇文章的介绍，读者能够了解到 cgroups 能够完成什么样的功能，并且希望读者在使用 cgroups 的功能的时候，能够大体知道内核通过一种什么样的方式来实现这种功能。
参考

1 cgroups 详解：http://files.cnblogs.com/files/lisperl/cgroups%E4%BB%8B%E7%BB%8D.pdf 2 how to use cgroup: http://tiewei.github.io/devops/howto-use-cgroup/ 3 Control groups, part 6: A look under the hood: http://lwn.net/Articles/606925/

并行程序设计演进

如何正确有效的保护共享数据是编写并行程序必须面临的一个难题，通常的手段就是同步。同步可分为阻塞型同步（Blocking Synchronization）和非阻塞型同步（ Non-blocking Synchronization）。

阻塞型同步是指当一个线程到达临界区时，因另外一个线程已经持有访问该共享数据的锁，从而不能获取锁资源而阻塞（睡眠），直到另外一个线程释放锁。常见的同步原语有 mutex、semaphore 等。如果同步方案采用不当，就会造成死锁（deadlock），活锁（livelock）和优先级反转（priority inversion），以及效率低下等现象。

为了降低风险程度和提高程序运行效率，业界提出了不采用锁的同步方案，依照这种设计思路设计的算法称为非阻塞型同步，其本质就是停止一个线程的执行不会阻碍系统中其他执行实体的运行。
先有阻塞型同步

互斥锁（英語：Mutual exclusion，缩写Mutex）是一种用于多线程编程中，防止两条线程同时对同一公共资源进行读写的机制。该目的通过将代码切片成一个一个的临界区域（critical section）达成。临界区域指的是一块对公共资源进行存取的代码。

信号量(Semaphore)，是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用，可以认为mutex是0-1信号量；

读写锁是计算机程序的并发控制的一种同步机制，它把对共享资源的访问者划分成读者和写者，读者只对共享资源进行读访问，写者则需要对共享资源进行写操作，读操作可并发重入，写操作是互斥的。
再有非阻塞型同步

当今比较流行的非阻塞型同步实现方案有三种：

    Wait-free（无等待）
    Wait-free 是指任意线程的任何操作都可以在有限步之内结束，而不用关心其它线程的执行速度。Wait-free 是基于 per-thread 的，可以认为是 starvation-free 的。非常遗憾的是实际情况并非如此，采用 Wait-free 的程序并不能保证 starvation-free，同时内存消耗也随线程数量而线性增长。目前只有极少数的非阻塞算法实现了这一点。
    简单理解：任意时刻所有的线程都在干活；
    Lock-free（无锁）
    Lock-Free是指能够确保执行它的所有线程中至少有一个能够继续往下执行。由于每个线程不是 starvation-free 的，即有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行，因此系统作为一个整体是在持续执行的，可以认为是 system-wide 的。所有 Wait-free 的算法都是 Lock-Free 的。
    简单理解：任意时刻至少一个线程在干活；
    Obstruction-free（无障碍）
    Obstruction-free 是指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行。一旦共享数据被修改，Obstruction-free 要求中止已经完成的部分操作，并进行回滚。所有 Lock-Free 的算法都是 Obstruction-free 的。
    简单理解：只要数据有修改，就会重新获取，并且把已经完成操作回滚重来；

综上所述，不难得出 Obstruction-free 是 Non-blocking synchronization 中性能最差的，而 Wait-free 性能是最好的，但实现难度也是最大的，因此 Lock-free 算法开始被重视，并广泛运用于各种程序设计中，这里主要介绍Lock_free算法。

lock-free（无锁）往往可以提供更好的性能和伸缩性保证，但实际上其优点不止于此。早期这些概念首先是在操作系统上应用的，因为一个不依赖于锁的算法，可以应用于各种场景下，而无需考虑各种错误，故障，失败等情形。比如死锁，中断，甚至CPU失效。
主流无锁技术

Atomic operation（原子操作），在单一、不间断的步骤中读取和更改数据的操作。需要处理器指令支持原子操作：

● test-and-set (TSR)

● compare-and-swap (CAS)

● load-link/store-conditional (ll/sc)

Spin Lock（自旋锁）是一种轻量级的同步方法，一种非阻塞锁。当 lock 操作被阻塞时，并不是把自己挂到一个等待队列，而是死循环 CPU 空转等待其他线程释放锁。

Seqlock (顺序锁) 是Linux 2.6 内核中引入一种新型锁，它与 spin lock 读写锁非常相似，只是它为写者赋予了较高的优先级。也就是说，即使读者正在读的时候也允许写者继续运行，读者会检查数据是否有更新，如果数据有更新就会重试，因为 seqlock 对写者更有利，只要没有其他写者，写锁总能获取成功。

RCU(Read-Copy Update)，顾名思义就是读-拷贝修改，它是基于其原理命名的。对于被RCU保护的共享数据结构，读者不需要获得任何锁就可以访问它，但写者在访问它时首先拷贝一个副本，然后对副本进行修改，最后使用一个回调（callback）机制在适当的时机把指向原来数据的指针替换为新的被修改的数据。这个时机就是所有引用该数据的CPU都退出对共享数据的访问。

本文主要讲解RCU的核心原理。
历史背景

高性能并行程序中，数据一致性访问是一个非常重要的部分，一般都是采用锁机制（semaphore、spinlock、rwlock等）进行保护共享数据，根本的思想就是在访问临界资源时，首先访问一个全局的变量（锁），通过全局变量的状态来控制线程对临界资源的访问。但是，这种思想是需要硬件支持的，硬件需要配合实现全局变量（锁）的读-修改-写，现代CPU都会提供这样的原子化指令。

采用锁机制实现数据访问的一致性存在如下两个问题：

    效率问题。锁机制的实现需要对内存的原子化访问，这种访问操作会破坏流水线操作，降低了流水线效率，这是影响性能的一个因素。另外，在采用读写锁机制的情况下，写锁是排他锁，无法实现写锁与读锁的并发操作，在某些应用下会降低性能。
    扩展性问题。例如，当系统中CPU数量增多的时候，采用锁机制实现数据的同步访问效率偏低。并且随着CPU数量的增多，效率降低，由此可见锁机制实现的数据一致性访问扩展性差。

原始的RCU思想

在多线程场景下，经常我们需要并发访问一个数据结构，为了保证线程安全我们会考虑使用互斥设施来进行同步，更进一步我们会根据对这个数据结构的读写比例而选用读写锁进行优化。但是读写锁不是唯一的方式，我们可以借助于COW技术来做到写操作不需要加锁，也就是在读的时候正常读，写的时候，先加锁拷贝一份，然后进行写，写完就原子的更新回去，使用COW实现避免了频繁加读写锁本身的性能开销。
优缺点

由于 RCU 旨在最小化读取端开销，因此仅在以更高速率使用同步逻辑进行读取操作时才使用它。如果更新操作超过10%，性能反而会变差，所以应该选择另一种同步方式而不是RCU。

    好处
        几乎没有读取端开销。零等待，零开销
        没有死锁问题
        没有优先级倒置问题（优先级倒置和优先级继承）
        无限制延迟没有问题
        无内存泄漏风险问题
    缺点
        使用起来有点复杂
        对于写操作，它比其他同步技术稍慢
    适用场景

核心原理
理论基础-QSBR算法

(Quiescent State-Based Reclamation)

这个算法的核心思想就是识别出线程的不活动(quiescent)状态，那么什么时候才算是不活动的状态呢？这个状态和临界区状态是相对的，线程离开临界区就是不活动的状态了。识别出不活动状态了，还需要把状态通知出去，让其他线程知道，这整个过程可以用下面的图来描述:

上面有四个线程，线程1执行完更新操作后添加了释放内存的callback，此时线程2,3,4都读取的是之前的内容，等他们执行完成后分别回去调用onQuiescentState来表明自己已经不不活动了，等到最后一个线程调用onQuiescentState的时候就可以去调用注册的callback了。要实现上面这个过程其要点就是选择适合的位置执行onQuiescentState，还有就是如何知道谁是最后一个执行onQuiescentState的线程。

批量回收，如果更新的次数比较多的话，但是每次只回调一个callback，释放一次内存就会导致内存释放跟不上回收的速度，为此需要进行批量回收，每次更新都会注册新的callback，当第一次所有的线程都进入不活动状态的时候就把当前的所有callback保存起来，等待下一次所有线程进入不活动的状态的时候就回调前一次所有的callback。
基本架构

Linux 内核RCU 参考QSBR算法设计一套无锁同步机制。

    多个读者可以并发访问共享数据，而不需要加锁；
    写者更新共享数据时候，需要先copy副本，在副本上修改，最终，读者只访问原始数据，因此他们可以安全地访问数据，多个写者之间是需要用锁互斥访问的（比如用自旋锁）；
    修改资源后，需要更新共享资源，让后面读者可以访问最新的数据；
    等旧资源上所有的读者都访问完毕后，就可以回收旧资源了；

RCU 模型

    Removal：在写端临界区部分，读取（Read()），进行复制（Copy），并执行更改（Update）操作；
    Grace Period：这是一个等待期，以确保所有与执行删除的数据相关的reader访问完毕；
    Reclamation：回收旧数据；

三个重要概念

静止状态QS(Quiescent State): CPU发生了上下文切换称为经历一个quiescent state；

宽限期GP(Grace Period): grace period就是所有CPU都经历一次quiescent state所需要的等待的时间，也即系统中所有的读者完成对共享临界区的访问；

GP原理

读侧临界部分RCS(Read-Side Critical Section): 保护禁止其他CPU修改的代码区域，但允许多个CPU同时读；

三个主要的角色

读者reader：

    安全访问临界区资源；
    负责标识进出临界区；

写者updater：

    复制一份数据，然后更新数据；
    用新数据覆盖旧数据，然后进入grace period；

回收者reclaimer：

    等待在grace period之前的读者退出临界区；
    在宽限期结束后，负责回收旧资源；

三个重要机制
发布/订阅机制

    主要用于更新数据，即使在数据被同时修改时线程也能安全浏览数据。RCU通过发布-订阅机制（Publish-Subscribe Mechanism）实现这种并发的插入操作能力；

延迟回收机制：

    实现检查旧数据上所有RCU读者完成，用于安全删除旧数据；

多版本机制：

    维护最近更新对象的多个版本，用于允许读者容忍并发的插入和删除新对象的多个版本；

最后总结

最后，总结一下RCU锁的核心思想：

    读者无锁访问数据，标记进出临界区；
    写者读取，复制，更新；
    旧数据延迟回收；

RCU核心思想就三句话，产品经理都说简单，但Linux内核实现却不是这么简单。除了要实现基本功能，需要考虑很多复杂情况：

内核的RCU系统可以说是内核最复杂系统之一，为了高性能和多核扩展性，设计了非常精巧的数据结构：

同时巧妙实现了很多核心流程：

    检查当前CPU是否度过QS；
    QS report(汇报宽限期度过)；
    宽限期的发起与完成；
    rcu callbacks处理；

其中很多实现都可以说是非常精巧，结合了预处理，批量处理，延后（异步）处理，多核并发，原子操作，异常处理，多场景精细优化等多种技术，性能好，可扩展性强，稳定性强，有一定的学习和参考价值，即使你的工作不是内核编程，里面体现很多编程思想和代码设计思想，也是值得大家学习的。

1. CPU 隔离 – 简介

2. CPU 隔离 – Full Dynticks 深探

3. CPU 隔离 – Nohz_full

4. CPU 隔离 – 管理和权衡

5. CPU 隔离 – 实践

本文是第三篇。
NOHZ_FULL

“nohz_full=” 内核引导参数是当前用于配置 full dynticks 和 CPU 隔离的主接口。

CPU 列表参数传给 nohz_full 的作用是定义一组要隔离的 CPU。例如，假设您有 8 个 CPU，希望隔离 CPU 4、5、6、7：

nohz_full=4-7

关于 cpu-list 参数格式请参考：https://www.kernel.org/doc/html/latest/admin-guide/kernel-parameters.html#cpu-lists。

nohz_full 的作用

当一个 CPU 包含在 nohz_full 引导参数的 CPU 列表中,内核会试图从那个 CPU 中排除尽可能多的内核干扰。本系列的第二篇文章已经从理论上解释了关闭计时器 Tick 的准备工作，这就是最终需要执行的操作：

定时器中断

满足以下条件时，定时器可以停止：

    在一个 CPU 上运行的任务无法被抢占。这意味着在使用以下策略时，您不能有一个以上的任务同时运行：SCHED_OTHER、SCHED_BATC 和 SCHED_IDLE(https://man7.org/linux/man-pages/man2/sched_setscheduler.2.html)。
    如果两个或多个任务都拥有最高优先级，则这一规则同样适用于 SCHED_RR (https://man7.org/linux/man-pages/man2/s … ler.2.html)。在隔离 CPU 上运行单个任务才更不容易出错。
    任务不使用 posix-cpu-timers（https://man7.org/linux/man-pages/man2/timer_create.2.html）。
    任务不使用 perf 事件（https://man7.org/linux/man-pages/man2/perf_event_open.2.html）。
    如果您在 x86 上运行，您的机器必须有一个可靠的时间戳计数器(TSC: https://www.suse.com/c/cpu-isolation-no … 我们稍后介绍这一点。

残余的 1 Hz Tick（每秒钟中断）仍然存在，目的是为了维护调度程序内部统计。它以前在隔离的 CPU 上执行，但现在，这个事件使用一个未绑定的工作队列被卸载到 nohz_full 范围之外的 CPU。这意味着一个干净的设置可以在 CPU 上 100%无 Tick 运行。

定时器回调

未绑定定时器回调执行被移动到 nohz_full 范围之外的任何 CPU，因此，它们不会在错误的地方触发定时器 Tick。与此同时，被固定的定时器 Tick 不能转移到其他地方。我们稍后会探讨如何处理。

工作队列和其他内核线程

与定时器回调类似,未绑定的内核工作队列和 kthread 被移动到 nohz_full 范围之外的任何 CPU。但是,被固定的工作队列和 kthread 不能移动到其他地方。我们稍后会探讨如何处理。

RCU

大部分 RCU 处理任务都被卸载到隔离范围外的 CPU 上。CPU 设置为 nohz_full 在 NOCB 模式下运行(https://lwn.net/Articles/522262/)，这意味着在这些 CPU 上排队的 RCU 回调是在非隔离的 CPU 上运行的未绑定 kthreads 中执行。不需要传递“rcu_nocbs=” 内核参数，因为这在传递“nohz_full=” 参数时自动处理。

CPU 也不需要通过 Tick 来积极报告静止状态，因为它在返回到用户空间时进入RCU扩展静止状态。

Cputime 记账

将 CPU 切换到 full dynticks cputime 记账，这样它就不再依赖周期性事件。
其他隔离设置

尽管 nohz_full 是整个隔离设置的重要组成部分，但也需要考虑其他细节，其中重要的两项包括：

用户任务仿射

如果您想运行一个不被干扰的任务，一定不希望其他线程或进程与其共享 CPU。full dynticks 最终只在单个任务中运行，因此，需要：

    将每个隔离任务仿射到 nohz_full 范围内的一个 CPU。每个 CPU 必须只有一个隔离任务。
    将其他所有任务仿射到 nohz_full 范围之外。

有多种方式可以将您的任务仿射到一组 CPU 上，从底层系统调用 sched_setaffinity() (https://man7.org/linux/man-pages/man2/s … ity.2.html) ，到 taskset 等命令行工具(https://man7.org/linux/man-pages/man1/taskset.1.html)。另外也建议使用强大的 cgroup 接口，例如 cpusets (https://www.kernel.org/doc/html/latest/ … usets.html)。

IRQ 仿射

硬件 IRQ（除计时器和其他特定的中断之外）可能会在任何 CPU 上运行，并打乱您的隔离集。产生的干扰可能不仅仅是占用 CPU 时间和破坏 CPU 缓存的中断，IRQ 可能会在 CPU 上启动进一步的异步工作：softirq、计时器、工作队列等。因此，将 IRQ 仿射到 nohz_full 范围之外的 CPU 通常是一个好想法。这种仿射可以通过文件而取消：

/proc/irq/$IRQ/smp_affinity

$IRQ 是向量号，更多细节可见内核文档：https://www.kernel.org/doc/Documentation/IRQ-affinity.txt

        WALT时间是什么呢，是进程占用CPU时间吗？想象一下，有两个进程，在一个时间窗口内，A进程在2.6G频率上运行了5ms，B进程在小核500M频率上运行了5ms。如果仅考虑CPU占用时间，那么它们的负载是相同的，这显然与实际情况不符。所以WALT时间，不仅要考虑CPU占用时间，还要考虑所在CPU的运算能力、运行频率。函数scale_exec_time()用于计算WALT时间，参数delta是CPU运行时间，rq是进程所在运行队列（与CPU对应），SCHED_CAPACITY_SHIFT是10。

static u64 scale_exec_time(u64 delta, struct rq *rq)
{
	unsigned long capcurr = capacity_curr_of(cpu_of(rq));
 
	return (delta * capcurr) >> SCHED_CAPACITY_SHIFT;
}
 
unsigned long capacity_curr_of(int cpu)
{
	return cpu_rq(cpu)->cpu_capacity_orig *
	       arch_scale_freq_capacity(NULL, cpu)
	       >> SCHED_CAPACITY_SHIFT;
} 

capacity_curr_of()中cpu_capacity_orig的值最终来源于per_cpu变量cpu_scale。

#define arch_scale_cpu_capacity scale_cpu_capacity
static void update_cpu_capacity(struct sched_domain *sd, int cpu)
{
	unsigned long capacity = arch_scale_cpu_capacity(sd, cpu);
	struct sched_group *sdg = sd->groups;
	struct max_cpu_capacity *mcc;
	unsigned long max_capacity;
	int max_cap_cpu;
	unsigned long flags;
 
	cpu_rq(cpu)->cpu_capacity_orig = capacity;
    ...............................................................
}
unsigned long scale_cpu_capacity(struct sched_domain *sd, int cpu)
{
	return per_cpu(cpu_scale, cpu);
}

capacity_curr_of()中arch_scale_freq_capacity()最终是获取的per_cpu变量freq_scale。

#define arch_scale_freq_capacity cpufreq_scale_freq_capacity
unsigned long cpufreq_scale_freq_capacity(struct sched_domain *sd, int cpu)
{
	return per_cpu(freq_scale, cpu);
}

        上面计算WALT时间的代码，可以简化为如下的运算公式：

         cpu_scale是当前CPU运算能力尺度化。市面上有各种各样的CPU，它们的运算能力各不相同，同一系列的CPU也会迭代升级运算能力，如果以CPU实际运算能力为参数，很难做到算法的统一。内核用CPU运算能力尺度化来解决该问题，定义系统中最高运算能力核的cpu_scale为1024，其它核的cpu_scale为该(CPU运算能力/最大核运算能力)*1024。CPU各个核的cpu_scale都由SOC厂商给出，MTK平台可以cat各cpu目录下cpu_capacity节点查看cpu_scale。

        freq_scale是某CPU当前频率运算能力的瓷都化，系统定义当前核最高频率运行时的freq_scale为1024，其它频率的freq_scale为当前频率运算能力/最高频率运算能力*1024。为什么用频率的运算能力比，而不是频率比呢？是因为有些厂商的CPU是CONFIG_NONLINER_FREQ_CTL类型的，它的运算能力与频率不是正比关系。例如MTK的某些SOC就是这样的芯片，它的运算能力与频率不成正比，只能查表来看某频点运算能力。

综上，我们可以把WALT时间的运算公式做如下表示：

        从上面的公式可以看出，进程只有在最大核的最高频点上运行时，其CPU占用时间才会等于WALT时间，其它情况WALT时间都是CPU占用时间按一定比例缩短的结果。

1.进程负载计算

        进程的task_struct中有一个ravg类型的变量用于保存WALT相关的信息。其中mark_start是上一次统计的时间，sum指进程在当前窗口已经运行的WALT时间，数组sum_history[RAVG_HIST_SIZE_MAX]保存进程在前5个历史窗口期内的WALT时间，demand是由sum_history[]历史数据推算出的值。

struct ravg {
	u64 mark_start;
	u32 sum, demand;
	u32 sum_history[RAVG_HIST_SIZE_MAX];
	u32 curr_window, prev_window;
	u16 active_windows;
};

         在进程切换等情况下，会统计WALT时间，有三种情况。情况一，如果当前时间(wallclock)与上次统计时间(mark_start)在一个时间窗口内，只需要将wallclock - mark_start转换为WALT时间后累加到ravg.sum即可。情况二，如果当前时间(wallclock)与上次统计时间(mark_start)跨了一个窗口，首先计算mark_start到当前窗口起始位置这部分WALT时间，并累加到ravg.sum后调用update_history()，将ravg.sum存入历史窗口。然后计算当前窗口起始时间到现在(wallclock)的这部分WALT时间，并赋值到ravg.sum。情况三，如果当前时间(wallclock)与上次统计时间(mark_start)跨了多个窗口，首先计算mark_start到它下一个窗口起始位置这部分WALT时间，并累加到ravg.sum后调用update_history()，将ravg.sum存入历史窗口。然后计算中间跨过窗口的WALT时间并更新到历史窗口中，最后计算当前窗口起始时间到现在(wallclock)的这部分WALT时间，并赋值到ravg.sum。

//进程切换时更新负载
static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct pin_cookie cookie;
	struct rq *rq;
	int cpu;
	u64 wallclock;
    ................................................................
	next = pick_next_task(rq, prev, cookie);
	wallclock = walt_ktime_clock();
	walt_update_task_ravg(prev, rq, PUT_PREV_TASK, wallclock, 0);
	walt_update_task_ravg(next, rq, PICK_NEXT_TASK, wallclock, 0);
	clear_tsk_need_resched(prev);
	clear_preempt_need_resched();
    ................................................................
}
 
void walt_update_task_ravg(struct task_struct *p, struct rq *rq,
	     int event, u64 wallclock, u64 irqtime)
{
	if (walt_disabled || !rq->window_start)
		return;
 
	lockdep_assert_held(&rq->lock);
    //更新窗口起始位置
	update_window_start(rq, wallclock);
 
	if (!p->ravg.mark_start)
		goto done;
    //更新进程负载
	update_task_demand(p, rq, event, wallclock);
	update_cpu_busy_time(p, rq, event, wallclock, irqtime);
 
done:
	trace_walt_update_task_ravg(p, rq, event, wallclock, irqtime);
 
	p->ravg.mark_start = wallclock;
}
 
//更新窗口起始位置
static void update_window_start(struct rq *rq, u64 wallclock)
{
	s64 delta;
	int nr_windows;
 
	delta = wallclock - rq->window_start;
    ..............................................................
	if (delta < walt_ravg_window)
		return;
 
	nr_windows = div64_u64(delta, walt_ravg_window);
	rq->window_start += (u64)nr_windows * (u64)walt_ravg_window;
 
	rq->cum_window_demand = rq->cumulative_runnable_avg;
}
 
static void update_task_demand(struct task_struct *p, struct rq *rq,
	     int event, u64 wallclock)
{
	u64 mark_start = p->ravg.mark_start;
	u64 delta, window_start = rq->window_start;
	int new_window, nr_full_windows;
	u32 window_size = walt_ravg_window;
 
	new_window = mark_start < window_start;
    ................................................................
	//情况一
	if (!new_window) {
		/* The simple case - busy time contained within the existing
		 * window. */
		add_to_task_demand(rq, p, wallclock - mark_start);
		return;
	}
    //情况二、三代码相同，只是情况二nr_full_windows为0
	delta = window_start - mark_start;
	nr_full_windows = div64_u64(delta, window_size);
	window_start -= (u64)nr_full_windows * (u64)window_size;
    //计算mark_start到它下一个窗口起始位置之间的WALT时间
	add_to_task_demand(rq, p, window_start - mark_start);
 
	/* Push new sample(s) into task's demand history */
	update_history(rq, p, p->ravg.sum, 1, event);
	//计算中间跨越窗口的WALT时间
	if (nr_full_windows)
		update_history(rq, p, scale_exec_time(window_size, rq),
			       nr_full_windows, event);
 
	/* Roll window_start back to current to process any remainder
	 * in current window. */
	window_start += (u64)nr_full_windows * (u64)window_size;
 
	/* 计算当前窗口起始时间到现在之间的WALT时间 */
	mark_start = window_start;
	add_to_task_demand(rq, p, wallclock - mark_start);
}

         demand值是在update_history()中更新的，有四种策略可选：WINDOW_STATS_RECENT，用本次更新进来的值；WINDOW_STATS_MAX，用所有历史记录中的最大值；WINDOW_STATS_AVG，用历史记录中的平均值；WINDOW_STATS_MAX_RECENT_AVG，本次更新进来的值与历史平均值中较大的那个。

#define WINDOW_STATS_RECENT		0
#define WINDOW_STATS_MAX		1
#define WINDOW_STATS_MAX_RECENT_AVG	2
#define WINDOW_STATS_AVG		3
#define WINDOW_STATS_INVALID_POLICY	4
 
static void update_history(struct rq *rq, struct task_struct *p,
			 u32 runtime, int samples, int event)
{
	u32 *hist = &p->ravg.sum_history[0];
	int ridx, widx;
	u32 max = 0, avg, demand;
	u64 sum = 0;
 
	/* Ignore windows where task had no activity */
	if (!runtime || is_idle_task(p) || exiting_task(p) || !samples)
			goto done;
 
	/* Push new 'runtime' value onto stack */
	widx = walt_ravg_hist_size - 1;
	ridx = widx - samples;
	for (; ridx >= 0; --widx, --ridx) {
		hist[widx] = hist[ridx];
		sum += hist[widx];
		if (hist[widx] > max)
			max = hist[widx];
	}
 
	for (widx = 0; widx < samples && widx < walt_ravg_hist_size; widx++) {
		hist[widx] = runtime;
		sum += hist[widx];
		if (hist[widx] > max)
			max = hist[widx];
	}
 
	p->ravg.sum = 0;
 
	if (walt_window_stats_policy == WINDOW_STATS_RECENT) {
		demand = runtime;
	} else if (walt_window_stats_policy == WINDOW_STATS_MAX) {
		demand = max;
	} else {
		avg = div64_u64(sum, walt_ravg_hist_size);
		if (walt_window_stats_policy == WINDOW_STATS_AVG)
			demand = avg;
		else
			demand = max(avg, runtime);
	}
    ....................................................................
	if (!task_has_dl_policy(p) || !p->dl.dl_throttled) {
		if (task_on_rq_queued(p))
			fixup_cumulative_runnable_avg(rq, p, demand);
		else if (rq->curr == p)
			fixup_cum_window_demand(rq, demand);
	}
 
	p->ravg.demand = demand;
    ....................................................................
}

        进程负载的计算公式如下，可以看出1024就是满负载时的值，进程满负载必须满足：在整个时间窗口内都处于运行状态，并且所在核是大核，运行频率是大核最高频率。

static inline unsigned long task_util(struct task_struct *p)
{
#ifdef CONFIG_SCHED_WALT
	if (!walt_disabled && (sysctl_sched_use_walt_task_util ||
				p->prio < sched_use_walt_nice)) {
		unsigned long demand = p->ravg.demand;
		return (demand << SCHED_CAPACITY_SHIFT) / walt_ravg_window;
	}
#endif
	return p->se.avg.util_avg;
}

2.CPU负载计算

        CPU负载计算是在update_cpu_busy_time()中完成的，计算方法与进程负载类似。不同的是，CPU负载计算只用了一个历史窗口，就是运行队列中的prev_runnable_sum。

static inline unsigned long cpu_util_freq(int cpu)
{
	unsigned long util = cpu_rq(cpu)->cfs.avg.util_avg;
	unsigned long capacity = capacity_orig_of(cpu);
 
#ifdef CONFIG_SCHED_WALT
	if (!walt_disabled && sysctl_sched_use_walt_cpu_util)
		util = div64_u64(cpu_rq(cpu)->prev_runnable_sum,
				walt_ravg_window >> SCHED_CAPACITY_SHIFT);
#endif
	return (util >= capacity) ? capacity : util;
}

    WALT(Windows-Assist Load Tracing)，从字面意思来看，是以window作为辅助项来跟踪cpu load，用来表现cpu当前的loading情况，用于后续任务调度、迁移、负载均衡等功能。在 load 的基础上，添加对于demand的记录用于之后的预测。只统计runable和running time。
    WALT由Qcom研发，主要用于移动设备对性能功耗要求比较高的场景，在与用户交互时需要尽快响应，要能及时反应负载的增加和减少以驱动频点及时的变化。当前的PELT负载跟踪算法更主要的是体现负载的连续性，对于突变性质的负载的反应不是很友好，负载上升慢，下降也慢。
    打开 CONFIG_SCHED_WALT 使能此feature。
    辅助计算项 window 的划分方法是将系统自启动开始以一定时间作为一个周期，分别统计不同周期内 Task 的 Loading 情况，并将其更新到Runqueue中；目前 Kernel 中是设置的一个 window 的大小是20ms，统计 5 个window内的Loading情况，当然，这也可以根据具体的项目需求进行配置。

二、相关数据结构

(1) 嵌入在 task_struct 中的 walt_task_struct

/*
 * 'mark_start' 标记窗口内事件的开始（任务唤醒、任务开始执行、任务被抢占）
 * 'sum' 表示任务在当前窗口内的可运行程度。它包含运行时间和等待时间，并按频率进行缩放。//就是在当前窗口的运行时间吧
 * 'sum_history' 跟踪在之前的 RAVG_HIST_SIZE 窗口中看到的 'sum' 的历史记录。任务完全休眠的窗口将被忽略。
 * 'demand' 表示在以前的 sysctl_sched_ravg_hist_size 窗口中看到的最大总和(根据window_policy选的)。 'demand'可以为任务驱动频率的改变。#######
 * 'curr_window_cpu' 代表任务对当前窗口各CPU上cpu繁忙时间的贡献
 * 'prev_window_cpu' 表示任务对前一个窗口中各个 CPU 上的 cpu 繁忙时间的贡献
 * 'curr_window' 表示 curr_window_cpu 中所有条目的总和
 * 'prev_window' 代表 prev_window_cpu 中所有条目的总和
 * 'pred_demand' 代表任务当前预测的cpu繁忙时间
 * 'busy_buckets' 将历史繁忙时间分组到用于预测的不同桶中
 * 'demand_scaled' 表示任务的需求缩放到 1024 //就是上面demand成员缩放到1024
 */
struct walt_task_struct {
    u64        mark_start;
    u32        sum, demand; //sum在 add_to_task_demand 中更新
    u32        coloc_demand; //存的是5个历史窗口的平均值
    u32        sum_history[RAVG_HIST_SIZE_MAX]; 
    u32        *curr_window_cpu, *prev_window_cpu; //这个是per-cpu的
    u32        curr_window, prev_window;
    u32        pred_demand;
    u8        busy_buckets[NUM_BUSY_BUCKETS]; //10个
    u16        demand_scaled;
    u16        pred_demand_scaled;
    u64        active_time; //is_new_task中判断此值是小于100ms就认为是新任务，rollover_task_window是唯一更新位置
    u32        unfilter; //update_history中对其进行赋值，colocate中选核时，是否需要跳过小核判断了它
    u64        cpu_cycles;
    ...
} 

(2) 嵌入在 rq 中的 walt_rq

struct walt_rq {
    ...
    struct walt_sched_stats walt_stats;
    u64            window_start;
    u32            prev_window_size;
    u64            task_exec_scale; //walt_sched_init_rq中初始化为1024
    u64            curr_runnable_sum;
    u64            prev_runnable_sum;
    u64            nt_curr_runnable_sum;
    u64            nt_prev_runnable_sum; //nt 应该是walt认为的new task的意思
    u64            cum_window_demand_scaled;
    struct group_cpu_time    grp_time;
    /*
     * #define DECLARE_BITMAP_ARRAY(name, nr, bits) unsigned long name[nr][BITS_TO_LONGS(bits)]
     * unsigned long top_tasks_bitmap[2][BITS_TO_LONGS(1000)]; //只跟踪curr和prev两个窗口的情况。
     */
    DECLARE_BITMAP_ARRAY(top_tasks_bitmap, NUM_TRACKED_WINDOWS, NUM_LOAD_INDICES);
    u8            *top_tasks[NUM_TRACKED_WINDOWS]; //2 指针数组
    u8            curr_table; //只使用两个window进行跟踪，标识哪个是curr的，curr和prev构成一个环形数组，不停翻转
    int            prev_top; //应该是rq->wrq.top_tasks[]中前一个窗最大值的下标
    int            curr_top; //是rq->wrq.top_tasks[]中当前窗最大值的下标
    u64            cycles;
    ...
};

struct walt_sched_stats {
    int nr_big_tasks;
    u64 cumulative_runnable_avg_scaled; //只统计runnable任务的，在update_window_start中赋值给rq->wrq.cum_window_demand_scaled
    u64 pred_demands_sum_scaled;
    unsigned int nr_rtg_high_prio_tasks;
}; 

三、负载计算函数

1. walt算法负载计算入口函数

 /* event 取 TASK_UPDATE 等，由于每个tick中断中都会调度，一般两次执行统计的 wc-ms 一般不会超过4ms */
void walt_update_task_ravg(struct task_struct *p, struct rq *rq, int event, u64 wallclock, u64 irqtime) //walt.c
{
    u64 old_window_start;

    /* 还没初始化或时间没更新，直接返回 */
    if (!rq->wrq.window_start || p->wts.mark_start == wallclock)
        return;

    lockdep_assert_held(&rq->lock);

    /* 更新ws，返回最新的ws */
    old_window_start = update_window_start(rq, wallclock, event);

    /* 对应还没初始化的情况, ws是per-rq的，ms是per-task的，wc是全局的 */
    if (!p->wts.mark_start) {
        update_task_cpu_cycles(p, cpu_of(rq), wallclock);
        goto done;
    }
    /*更新 rq->wrq.task_exec_scale 和 p->wts.cpu_cycles = cur_cycles; */
    update_task_rq_cpu_cycles(p, rq, event, wallclock, irqtime);

    /*更新任务的负载和历史记录，返回 wc-ms 的差值，也就是距离上次统计任务运行的时间值 */
    update_task_demand(p, rq, event, wallclock);

    /*更新任务和rq的window相关统计信息，记录per-rq的prev和curr两个窗口内任务负载分布情况 */
    update_cpu_busy_time(p, rq, event, wallclock, irqtime);

    /*更新预测需求*/
    update_task_pred_demand(rq, p, event);

    if (event == PUT_PREV_TASK && p->state) {
        p->wts.iowaited = p->in_iowait;
    }

    trace_sched_update_task_ravg(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

    trace_sched_update_task_ravg_mini(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

done:
    /* 更新per-task的 ms，ms是在动态变化的 */
    p->wts.mark_start = wallclock;

    /*构成一个内核线程，每个窗口执行一次*/
    run_walt_irq_work(old_window_start, rq);
}

此函数中的两个trace解析：
(1) trace_sched_update_task_ravg(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

参数原型：
(struct task_struct *p, struct rq *rq, enum task_event evt, u64 wallclock, u64 irqtime, struct group_cpu_time *cpu_time)

打印内容：

<idle>-0     [004] d..2 50167.767150: sched_update_task_ravg: wc 50167994699141 ws 50167988000001 delta 6699140
event PICK_NEXT_TASK cpu 4 cur_freq 434 cur_pid 0 task 17043 (kworker/u16:5) ms 50167994687631 delta 11510 
demand 3340045 coloc_demand: 1315008 sum 1235016 irqtime 0 pred_demand 3340045 rq_cs 1112353 rq_ps 4085339 
cur_window 930130 (0 136431 573963 0 219736 0 0 0 ) prev_window 2138941 (222138 156646 973556 0 219811 566790 0 0 ) 
nt_cs 2513 nt_ps 20395 active_time 100000000 grp_cs 0 grp_ps 1691783, grp_nt_cs 0, grp_nt_ps: 0 curr_top 58 prev_top 13 

字段解析：
wc：为参数4 wallclock;
ws: 为 window_start，取自 rq->wrq.window_start;
delta：取自 wallclock - rq->wrq.window_start 的差值。
event：task_event_names[参数3], 字符串表示的事件类型
cpu：取自 rq->cpu
cur_freq：取自 rq->wrq.task_exec_scale，update_task_rq_cpu_cycles()中，若不使用 use_cycle_counter，赋值为 cpu_capaticy * (freq / maxfreq)
cur_pid: 取自 rq->curr->pid
task：取自参数1 p 的 p->pid
kworker/u16:5：取自参数1 p 的 p->comm
ms：是 mark_start 取自 p->wts.mark_start
delta：打印中有两个同名的delta，这是第二个，取自 wallclock - p->wts.mark_start
demand：取自 p->wts.demand，单位是ns，就是根据 p->wts.sum 取平均或和最近窗口两者之间的最大值
coloc_demand：取自 p->wts.coloc_demand
sum：取自 p->wts.sum，表示最近一个窗口运行时间之和，单位ns，在将其更新到history数组后，清0.
irqtime：取自参数4
pred_demand：取自 p->wts.pred_demand
rq_cs：取自 rq->wrq.curr_runnable_sum 表示
rq_ps：取自 rq->wrq.prev_runnable_sum 表示
cur_window：取自 p->wts.curr_window，表示任务在当前窗口中所有cpu上的运行时间之和，是后面数组的累加。
(0 136431 573963 0 219736 0 0 0 )：取自 p->wts.curr_window_cpu per-cpu的，表示任务在当前窗口中在每个cpu上运行的时间
prev_window：取自 p->wts.prev_window
(222138 156646 973556 0 219811 566790 0 0 )：取自 p->wts.prev_window_cpu 也是per-cpu的，表示任务在前一个窗口中在每个cpu上运行的时间
nt_cs：取自 rq->wrq.nt_curr_runnable_sum nt应该表示的是new task的缩写
nt_ps：取自 rq->wrq.nt_prev_runnable_sum
active_time：取自 p->wts.active_time is_new_task()中判断它，唯一更新位置rollover_task_window()中调用is_new_task()判断是新任务时 p->wts.active_time += task_rq(p)->wrq.prev_window_size;
grp_cs：取自 cpu_time ? cpu_time->curr_runnable_sum : 0 根据最后一个参数来判断是更新rq的还是更新rtg group的
grp_ps：取自 cpu_time ? cpu_time->prev_runnable_sum : 0
grp_nt_cs：取自 cpu_time ? cpu_time->nt_curr_runnable_sum : 0
grp_nt_ps：取自 cpu_time ? cpu_time->nt_prev_runnable_sum : 0
curr_top：取自 rq->wrq.curr_top 记录的是当前窗口中 rq->wrq.top_tasks[]中最大值的下标
prev_top：取自 rq->wrq.prev_top 记录的是前一个窗口中 rq->wrq.top_tasks[]中最大值的下标

(2) trace_sched_update_task_ravg_mini(p, rq, event, wallclock, irqtime, &rq->wrq.grp_time);

参数原型：
(struct task_struct *p, struct rq *rq, enum task_event evt, u64 wallclock, u64 irqtime, struct group_cpu_time *cpu_time)

打印内容：

<idle>-0     [005] d..2 280546.887141: sched_update_task_ravg_mini: wc 112233604355205 ws 112233596000001 delta 8355204
event PUT_PREV_TASK cpu 5 task 0 (swapper/5) ms 112233604337548 delta 17657 demand 2400000 rq_cs 1374618 rq_ps 1237818
cur_window 0 prev_window 0 grp_cs 0 grp_ps 0

字段解析：
wc：取自参数 wallclock
ws：取自 rq->wrq.window_start
delta：取自 wallclock - rq->wrq.window_start
event：取自 task_event_names[evt]
cpu：取自 rq->cpu
task：取自 p->pid
swapper/5：取自 p->comm
ms：取自 p->wts.mark_start
delta：两个同名，这是第二个，取自 wallclock - p->wts.mark_start
demand：取自 p->wts.demand
rq_cs：取自 rq->wrq.curr_runnable_sum
rq_ps：取自 rq->wrq.prev_runnable_sum
cur_window：取自 p->wts.curr_window
prev_window：取自 p->wts.prev_window
grp_cs：取自 cpu_time ? cpu_time->curr_runnable_sum : 0
grp_ps：取自 cpu_time ? cpu_time->prev_runnable_sum : 0

2. walt_update_task_ravg 的调用路径

tick_setup_sched_timer //tick_sched.c timer到期回调函数中指定 tick_sched_timer
        update_process_times //time.c tick中断中调用
            scheduler_tick //core.c 周期定时器中断，传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)
        //任务显式阻塞或设置 TIF_NEED_RESCHED 并且在中断或返回用户空间调度点或preempt_enable()
            __schedule //core.c 在这个主调度器函数中调用了三次，若选出的prev != next，调用两次，分别传参(prev, rq, PUT_PREV_TASK, wallclock, 0)和(next, rq, PICK_NEXT_TASK, wallclock, 0)，若选出的prev == next，传参(prev, rq, TASK_UPDATE, wallclock, 0)
__irq_enter //hardirq.h __handle_domain_irq()中调用，中断入口：handle_arch_irq=gic_handle_irq-->handle_domain_irq
__do_softirq //softirq.c
    account_irq_enter_time //vtime.h
    account_irq_exit_time //vtime.h
        irqtime_account_irq //cputime.c 若curr是idle task，并且是在硬中断或软中断上下文则调用，否则调用walt_sched_account_irqstart
            walt_sched_account_irqend //walt.c，传参(curr, rq, IRQ_UPDATE, wallclock, delta);
    move_queued_task
    __migrate_swap_task
    try_to_wake_up //core.c 当新选出的cpu和任务之前运行的不是同一个cpu调用
    dl_task_offline_migration
    push_dl_task
    pull_dl_task
    detach_task
    push_rt_task
    pull_rt_task
        set_task_cpu //core.c 若新选出的cpu和任务之前的cpu不是同一个cpu，对任务进行迁移，然后调用，此时task->on_rq = TASK_ON_RQ_MIGRATING
            fixup_busy_time //walt.c 连续调用三次，分别传参 (task_rq(p)->curr, task_rq(p), TASK_UPDATE, wallclock, 0)和(dest_rq->curr, dest_rq, TASK_UPDATE, wallclock, 0)和(p, task_rq(p), TASK_MIGRATE, wallclock, 0)
cpufreq_freq_transition_end //cpufreq.c set_cpu_freq()中在设置频点前调用cpufreq_freq_transition_begin，设置后调用这个函数
    cpufreq_notify_post_transition //cpufreq.c 相同参数调用两次      
        notifier_trans_block.notifier_call //回调，对应val=CPUFREQ_POSTCHANGE时通知
            cpufreq_notifier_trans //walt.c 两层循环，对freq_domain_cpumask中的每一个cpu，对cluster中的每一个cpu，都调用，传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)
sync_cgroup_colocation //walt.c cpu_cgrp_subsys.attach=cpu_cgroup_attach-->walt_schedgp_attach中对每一个cpuset都调用
sched_group_id_write //qc_vas.c 对应/proc/<pid>/sched_group_id
    __sched_set_group_id //传参group_id=0才调用
        remove_task_from_group //walt.c 传参(rq, p->wts.grp, p, REM_TASK)
    __sched_set_group_id //传参group_id非0才调用
        add_task_to_group //walt.c 传参(rq, grp, p, ADD_TASK)
            transfer_busy_time //walt.c 连续调用两次，分别传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)和(p, rq, TASK_UPDATE, wallclock, 0)
    fixup_busy_time    //当task的cpu和参数cpu不是同一个时调用
    walt_proc_user_hint_handler //walt.c /proc/sys/kernel/sched_user_hint作用load = load * (sched_user_hint / 100) 维持1s后清0
        walt_migration_irq_work.func //walt.c irq_work 结构的回调
walt_update_task_ravg //又回来了，work的响应函数中queue work，构成一个"内核线程不"停执行
    run_walt_irq_work //walt.c 若新的window_start和旧的不是同一个就调用
        walt_cpufreq_irq_work.func //walt.c irq_work 结构的回调
            walt_irq_work //walt.c 对每个cluster的每个cpu都调用，传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)
    wake_up_q
    wake_up_process
    wake_up_state
    default_wake_function
        try_to_wake_up
            walt_try_to_wake_up //walt.h 连续调用两次，分别传参(rq->curr, rq, TASK_UPDATE, wallclock, 0)和(p, rq, TASK_WAKE, wallclock, 0)
                walt_update_task_ravg

walt_update_task_ravg 通过参数 event 可以控制哪些事件不更新负载。

3. update_window_start 函数

/* 唯一调用路径：walt_update_task_ravg --> this */
static u64 update_window_start(struct rq *rq, u64 wallclock, int event) //walt.c
{
    s64 delta;
    int nr_windows;
    u64 old_window_start = rq->wrq.window_start;

    delta = wallclock - rq->wrq.window_start;
    if (delta < 0) {
        printk_deferred("WALT-BUG CPU%d; wallclock=%llu is lesser than window_start=%llu", rq->cpu, wallclock, rq->wrq.window_start);
        SCHED_BUG_ON(1);
    }

    /* sched_ravg_window 默认是20ms, 不足一个窗口就不更新，直接退出*/
    if (delta < sched_ravg_window)
        return old_window_start;

    /* 下面是delta大于一个window的，计算历经的整窗的个数 */
    nr_windows = div64_u64(delta, sched_ravg_window);
    rq->wrq.window_start += (u64)nr_windows * (u64)sched_ravg_window; /* 更新ws */

    rq->wrq.cum_window_demand_scaled = rq->wrq.walt_stats.cumulative_runnable_avg_scaled;
    rq->wrq.prev_window_size = sched_ravg_window;

    return old_window_start;
}

可以看到，rq->wrq.window_start、rq->wrq.cum_window_demand_scaled 是最先更新的。然后返回旧的 window_start，

4. update_task_cpu_cycles 函数

static void update_task_cpu_cycles(struct task_struct *p, int cpu, u64 wallclock) //walt.c
{
    if (use_cycle_counter)
        p->wts.cpu_cycles = read_cycle_counter(cpu, wallclock);
}

在 p->wts.mark_start 为0的时候，调用这个函数，应该是做初始化的。

5. update_task_rq_cpu_cycles 函数
'

/* 唯一调用路径 walt_update_task_ravg --> this */
static void update_task_rq_cpu_cycles(struct task_struct *p, struct rq *rq, int event, u64 wallclock, u64 irqtime) //walt.c
{
    u64 cur_cycles;
    u64 cycles_delta;
    u64 time_delta;
    int cpu = cpu_of(rq);

    lockdep_assert_held(&rq->lock);

    if (!use_cycle_counter) {
        /* freq / maxfreq * cpu_capacity, arch_scale_cpu_capacity 为函数 topology_get_cpu_scale */
        rq->wrq.task_exec_scale = DIV64_U64_ROUNDUP(cpu_cur_freq(cpu) * arch_scale_cpu_capacity(cpu), rq->wrq.cluster->max_possible_freq);
        return;
    }

    cur_cycles = read_cycle_counter(cpu, wallclock); /*return rq->wrq.cycles;*/

    /*
     * 如果当前任务是空闲任务并且 irqtime == 0，CPU 确实空闲并且它的循环计数器可能没有增加。
     * 我们仍然需要估计的 CPU 频率来计算 IO 等待时间。 在这种情况下使用先前计算的频率。
     */
    if (!is_idle_task(rq->curr) || irqtime) {
        if (unlikely(cur_cycles < p->wts.cpu_cycles)) //这应该是溢出了
            cycles_delta = cur_cycles + (U64_MAX - p->wts.cpu_cycles);
        else
            cycles_delta = cur_cycles - p->wts.cpu_cycles;

        cycles_delta = cycles_delta * NSEC_PER_MSEC;

        if (event == IRQ_UPDATE && is_idle_task(p))
            /*
             * 在空闲任务的 mark_start 和 IRQ 处理程序进入时间之间的时间是 CPU 周期计数器停止时间段。
             * 在 IRQ 处理程序进入 walt_sched_account_irqstart() 时，补充空闲任务的 cpu 周期计数器，因
             * 此cycles_delta 现在表示 IRQ 处理程序期间增加的周期，而不是从进入空闲到 IRQ 退出之间的时间段。
             * 因此使用 irqtime 作为时间增量。
             */
            time_delta = irqtime;
        else
            time_delta = wallclock - p->wts.mark_start;
        SCHED_BUG_ON((s64)time_delta < 0);

        /* (cycles_delta * cpu_capacity) / (time_delta * max_freq) = cycles_delta/time_delta * cpu_capacity/max_freq*/
        rq->wrq.task_exec_scale = DIV64_U64_ROUNDUP(cycles_delta * arch_scale_cpu_capacity(cpu), time_delta * rq->wrq.cluster->max_possible_freq);

        trace_sched_get_task_cpu_cycles(cpu, event, cycles_delta, time_delta, p);
    }

    p->wts.cpu_cycles = cur_cycles;
}

其中Trace:

trace_sched_get_task_cpu_cycles(cpu, event, cycles_delta, time_delta, p);

参数原型：

(int cpu, int event, u64 cycles, u64 exec_time, struct task_struct *p)

打印内容：

shell svc 7920-7921  [006] d..4 53723.502493: sched_get_task_cpu_cycles: cpu=6 event=2 cycles=105682000000 exec_time=78229 freq=1350931 legacy_freq=2035200
max_freq=2035200 task=19304 (kworker/u16:5)

字段解析：

前4个字段直接来自参数，
freq：取自 cycles/exec_time, 其中 cycles 是乘以了 NSEC_PER_MSEC 的，exec_time 的单位是ns。
legacy_freq：取自 cpu_rq(cpu)->wrq.cluster->max_possible_freq，单位KHz
max_freq：取自 cpu_rq(cpu)->wrq.cluster->max_possible_freq * cpu_rq(cpu)->cpu_capacity_orig / SCHED_CAPACITY_SCALE
task：取自 p->pid
kworker/u16:5：取自 p->comm

6. update_history 解析

update_task_demand 中若判断不需要更新 task 的 p->wts.sum, 但是又有新窗口产生时，调用这个函数更新历史负载。

/*
 * 当一个任务的新窗口开始时调用，记录最近结束的窗口的 CPU 使用率。 通常'samples'应该是1。
 * 比如说，当一个实时任务同时运行而不抢占几个窗口时，它可以 > 1，也就是说连续运行3个窗口才
 * 更新的话，samples就传3。
 *
 * update_task_demand()调用传参：(rq, p, p->wts.sum, 1, event)  sum 是几5个窗口的
 */
static void update_history(struct rq *rq, struct task_struct *p, u32 runtime, int samples, int event) //walt.c
{
    u32 *hist = &p->wts.sum_history[0];
    int ridx, widx;
    u32 max = 0, avg, demand, pred_demand;
    u64 sum = 0;
    u16 demand_scaled, pred_demand_scaled;

    /* Ignore windows where task had no activity */
    if (!runtime || is_idle_task(p) || !samples)
        goto done;

    /* Push new 'runtime' value onto stack */
    /* hist[5]中的元素向后移动samples个位置，runtime值插入到hist[0]中，hist[0]是最新的时间 */
    widx = sched_ravg_hist_size - 1; /* 5-1=4 */
    ridx = widx - samples; //widx=4, samples=1, ridx=3; samples=2, ridx=2
    for (; ridx >= 0; --widx, --ridx) {
        hist[widx] = hist[ridx];
        sum += hist[widx];  //此循环 sum = hist[4] + hist[3] + hist[2] + hist[1]
        if (hist[widx] > max)
            max = hist[widx]; //max保存最近4个窗中的最大值
    }

    /*
     * 若samples=1, hist[0] = runtime
     * 若samples=2, hist[0] = runtime, hist[1] = runtime
     * ...
     */
    for (widx = 0; widx < samples && widx < sched_ravg_hist_size; widx++) {
        hist[widx] = runtime; //hist[0]中存放的是最近的一个窗中运行的时间
        sum += hist[widx]; //sum再加上hist[0]
        if (hist[widx] > max)
            max = hist[widx]; //max保存的是最近5个窗中最大的值了
    }

    /* 将p->wts.sum放入history数组后就清0了, 也说明这个sum是一个窗的sum值 */
    p->wts.sum = 0;

    /*可以通过 sched_window_stats_policy 文件进行配置下面4种window policy */
    if (sysctl_sched_window_stats_policy == WINDOW_STATS_RECENT) { //为0，返回最近一个窗口的运行时间值
        demand = runtime;
    } else if (sysctl_sched_window_stats_policy == WINDOW_STATS_MAX) { //为1，返回最近5个窗口运行时间的最大值
        demand = max;
    } else {
        avg = div64_u64(sum, sched_ravg_hist_size); //求最近5个窗口运行时间的平均值
        if (sysctl_sched_window_stats_policy == WINDOW_STATS_AVG) //为3，返回最近5个窗口平均运行时间值
            demand = avg;
        else
            demand = max(avg, runtime); //为2，默认配置，返回最近5个窗口平均运行时间值 与 最近1个窗口运行时间值中的较大的那个
    }

    pred_demand = predict_and_update_buckets(p, runtime);

    /* demand_scaled = demand/(window_size/1024) == (demand / window_size) * 1024
     * 传参demand可以认为是p的负载了
     */
    demand_scaled = scale_demand(demand);
    /* pred_demand_scaled = pred_demand/(window_size/1024) == (pred_demand / window_size) * 1024 */
    pred_demand_scaled = scale_demand(pred_demand);

    /*
     * 限流的deadline调度类任务出队列时不改变p->on_rq。 由于出队递减 walt stats 避免再次递减它。
     * 当窗口滚动时，累积窗口需求被重置为累积可运行平均值（来自运行队列上的任务的贡献）。如果当前任务已经出队，
     * 则它的需求不包括在累积可运行平均值中。所以将任务需求单独添加到累积窗口需求中。
     */
    /*这里增加的是rq上的统计值，不是per-entity的了*/
    if (!task_has_dl_policy(p) || !p->dl.dl_throttled) {
        if (task_on_rq_queued(p)) {
            fixup_walt_sched_stats_common(rq, p, demand_scaled, pred_demand_scaled); /*这里加的是demand_scaled的差值*/
        } else if (rq->curr == p) {
            walt_fixup_cum_window_demand(rq, demand_scaled);
        }
    }

    /*赋值给per-entiry上的统计值，demand_scaled 对 p->wts.demand_scaled 的赋值一定要保证，这是walt负载跟踪算法重要的部分*/
    p->wts.demand = demand; /* 对应一个窗中运行的时间(根据window policy不同而有差异) */
    p->wts.demand_scaled = demand_scaled; /* 对应一个窗中运行的时间(根据window policy不同而有差异)缩放到1024 */ #############
    p->wts.coloc_demand = div64_u64(sum, sched_ravg_hist_size); /*5个窗口运行时间之和除以5，即5个窗口的平均运行时间*/
    p->wts.pred_demand = pred_demand;
    p->wts.pred_demand_scaled = pred_demand_scaled;

    /* demand_scaled 大于指定的阈值时，会做一些事情 */
    if (demand_scaled > sysctl_sched_min_task_util_for_colocation) {
        p->wts.unfilter = sysctl_sched_task_unfilter_period; /*单位是ns，默认值是100ms*/
    } else {
        if (p->wts.unfilter)
            p->wts.unfilter = max_t(int, 0, p->wts.unfilter - rq->wrq.prev_window_size); //相当于衰减一个窗口的大小
    }

done:
    trace_sched_update_history(rq, p, runtime, samples, event);
}

其中Trace:

trace_sched_update_history(rq, p, runtime, samples, event);

参数原型：

(struct rq *rq, struct task_struct *p, u32 runtime, int samples, enum task_event evt)

打印内容：

sched_update_history: 24647 (kworker/u16:15): runtime 279389 samples 1 event TASK_WAKE demand 717323
coloc_demand 717323 pred_demand 279389 (hist: 279389 88058 520130 1182596 1516443) cpu 1 nr_big 0

字段解析：

24647：取自 p->pid
kworker/u16:15：取自 p->comm
runtime：来自参数3，表示最近一个窗口中的运行时间，也是 p->wts.sum 的值
samples：来自参数4，表示更新几个窗的历史
event：取自 task_event_names[event]
demand：取自 p->wts.demand，是scale之前的根据不同window policy计算出来的负载值
coloc_demand：取自 p->wts.coloc_demand，即5个窗口的平均值
pred_demand：取自 p->wts.pred_demand，表示预测的负载需求
(hist: 279389 88058 520130 1182596 1516443)：取自 p->wts.sum_history[5]，是任务在最近5个窗口中分别运行的时间
cpu：取自 rq->cpu
nr_big：取自 rq->wrq.walt_stats.nr_big_tasks

用于预测任务的 demand 的 bucket 相关更新：

static inline u32 predict_and_update_buckets(struct task_struct *p, u32 runtime) //walt.c
{

    int bidx;
    u32 pred_demand;

    if (!sched_predl) //为1
        return 0;

    /* 根据传入的时间值获得一个桶的下标，桶一共有10个成员 */
    bidx = busy_to_bucket(runtime);
    /* 使用 p->wts.busy_buckets 用于计算 */
    pred_demand = get_pred_busy(p, bidx, runtime);
    /* 更新 p->wts.busy_buckets */
    bucket_increase(p->wts.busy_buckets, bidx);

    return pred_demand;
}

static inline int busy_to_bucket(u32 normalized_rt)
{
    int bidx;

    bidx = mult_frac(normalized_rt, NUM_BUSY_BUCKETS, max_task_load()); /*args1*10/16; arg1*arg2/arg3*/
    bidx = min(bidx, NUM_BUSY_BUCKETS - 1); //min(p->wts.sum * 10 / 16, 9) 运行一个满窗是桶10，运行1ms-2ms返回1

    /* 合并最低的两个桶。 最低频率落入第二桶，因此继续预测最低桶是没有用的。*/
    if (!bidx)
        bidx++;

    return bidx;
}

/*
 * get_pred_busy - 计算运行队列上的任务的预测需求
 *
 * @p：正在更新预测的任务
 * @start: 起始桶。 返回的预测不应低于此桶。
 * @runtime：任务的运行时间。 返回的预测不应低于此运行时。
 * 注意：@start 可以从@runtime 派生。 传入它只是为了在某些情况下避免重复计算。
 *
 * 根据传入的@runtime 为任务@p 返回一个新的预测繁忙时间。该函数搜索表示繁忙时间等于或大于@runtime
 * 的桶，并尝试找到用于预测的桶。 一旦找到，它会搜索历史繁忙时间并返回落入桶中的最新时间。 如果不
 * 存在这样的繁忙时间，则返回该桶的中间值。
 */
/*假设传参是p->wts.sum=8ms,那么传参就是(p, 5, 8)，*/
static u32 get_pred_busy(struct task_struct *p, int start, u32 runtime)
{
    int i;
    u8 *buckets = p->wts.busy_buckets; //10个元素
    u32 *hist = p->wts.sum_history; //5个元素
    u32 dmin, dmax;
    u64 cur_freq_runtime = 0;
    int first = NUM_BUSY_BUCKETS, final; //从最大值10开始找
    u32 ret = runtime;

    /* skip prediction for new tasks due to lack of history */
    /* 由于累积运行时间小于100ms的新任务缺少历史运行时间，不对其进行预测 */
    if (unlikely(is_new_task(p)))
        goto out;

    /* find minimal bucket index to pick */
    /* 找到最小的桶下标进行pick, 只要桶中有数据就选择 */
    for (i = start; i < NUM_BUSY_BUCKETS; i++) {
        if (buckets[i]) {
            first = i;
            break;
        }
    }

    /* 若没找到桶下标，就直接返回 runtime，注意 runtime 可能大于10 */
    if (first >= NUM_BUSY_BUCKETS)
        goto out;

    /* 计算用于预测的桶 */
    final = first;

    /* 确定预测桶的需求范围 */
    if (final < 2) {
        /* 最低的两个桶合并 */
        dmin = 0;
        final = 1;
    } else {
        dmin = mult_frac(final, max_task_load(), NUM_BUSY_BUCKETS); //final * 20 / 10, max_task_load返回一个满窗
    }
    dmax = mult_frac(final + 1, max_task_load(), NUM_BUSY_BUCKETS); //(final + 1) * 20 / 10

    /*
     * search through runtime history and return first runtime that falls
     * into the range of predicted bucket.
     * 搜索运行历史并返回落在预测桶范围内的第一个运行。在最近的5个窗口中查找
     */
    for (i = 0; i < sched_ravg_hist_size; i++) {
        if (hist[i] >= dmin && hist[i] < dmax) {
            ret = hist[i];
            break;
        }
    }
    /* no historical runtime within bucket found, use average of the bin 
     * 若找不到存储桶内的历史运行时间，就使用垃圾桶的平均值 */
    if (ret < dmin)
        ret = (dmin + dmax) / 2;
    /*
     * 在窗口中间更新时，运行时间可能高于所有记录的历史记录。 始终至少预测运行时间。
     */
    ret = max(runtime, ret);
out:
    /* 由于 cur_freq_runtime 是0，所以 pct 恒为0 */
    trace_sched_update_pred_demand(p, runtime, mult_frac((unsigned int)cur_freq_runtime, 100,  sched_ravg_window), ret);

    return ret;
}

/*
 * bucket_increase - 更新所有桶的计数
 *
 * @buckets：跟踪任务繁忙时间的桶数组
 * @idx: 要被递增的桶的索引
 *
 * 每次完成一个完整的窗口时，运行时间落入 (@idx) 的桶计数增加。 所有其他桶的计数都会衰减。 
 * 根据桶中的当前计数，增加和衰减的速率可能不同。
 */
/*传参： (p->wts.busy_buckets, bidx)*/
static inline void bucket_increase(u8 *buckets, int idx)
{
    int i, step;

    for (i = 0; i < NUM_BUSY_BUCKETS; i++) { //10
        if (idx != i) { //不相等就衰减
            if (buckets[i] > DEC_STEP) //2
                buckets[i] -= DEC_STEP; //2
            else
                buckets[i] = 0;
        } else { //相等
            step = buckets[i] >= CONSISTENT_THRES ? INC_STEP_BIG : INC_STEP; //16 16 8
            if (buckets[i] > U8_MAX - step) //255-step
                buckets[i] = U8_MAX; //255
            else
                buckets[i] += step; //就是加step，上面判断是为了不要溢出
        }
    }
}

其中Trace:

trace_sched_update_pred_demand(p, runtime, mult_frac((unsigned int)cur_freq_runtime, 100,  sched_ravg_window), ret);

参数原型：

(struct task_struct *p, u32 runtime, int pct, unsigned int pred_demand)

打印内容：

sched_update_pred_demand: 1174 (Binder:1061_2): runtime 556361 pct 0 cpu 1 pred_demand 556361 (buckets: 0 255 0 0 0 0 0 0 0 0)

字段解析：

1174：取自 p->pid
Binder:1061_2：取自 p->comm
runtime：取自参数2
pct：取自参数3
cpu：取自task_cpu(p)
pred_demand：取自参数4
(buckets: 0 255 0 0 0 0 0 0 0 0)：取自 p->wts.busy_buckets[10]

/* 
 * update_history --> this，如果task在rq上才会调用传参: (rq, p, demand_scaled, pred_demand_scaled)，参数是缩放到0--1024后的
 * 也就是说这个函数里面计算的包含 runnable 的
 */
static void fixup_walt_sched_stats_common(struct rq *rq, struct task_struct *p, u16 updated_demand_scaled, u16 updated_pred_demand_scaled)
{
    /* p->wts.demand_scaled 约是由 p->wts.sum scale后得来的(window plicy策略影响), 后者是一个窗口中任务运行的时长。新的减旧的，结果处于[-1024,1024] */
    s64 task_load_delta = (s64)updated_demand_scaled - p->wts.demand_scaled;
    /* p->wts.pred_demand_scaled 是由桶算法预测得来的 */
    s64 pred_demand_delta = (s64)updated_pred_demand_scaled - p->wts.pred_demand_scaled;

    /* 直接加上传入的增量，注意增量可能是负数，一个进程的负载变低了，差值就是负数了*/
    fixup_cumulative_runnable_avg(&rq->wrq.walt_stats, task_load_delta, pred_demand_delta);
    /*累加demand_scaled的增量*/
    walt_fixup_cum_window_demand(rq, task_load_delta); /*上下两个函数都是对rq->wrq.中的成员赋值*/
}

/*
 * 如果task在rq上调用路径：update_history --> fixup_cumulative_runnable_avg 传参：(&rq->wrq.walt_stats, task_load_delta, pred_demand_delta)
 * 传参为时间差值。
 */
static inline void fixup_cumulative_runnable_avg(struct walt_sched_stats *stats, s64 demand_scaled_delta, s64 pred_demand_scaled_delta)
{
    /*
     * 增量差值可正可负，rq 的 cumulative_runnable_avg_scaled 初始化后就只有在这里有赋值了。
     * 这里根据根据当前窗口负载值快速变化。
     */
    stats->cumulative_runnable_avg_scaled += demand_scaled_delta;
    BUG_ON((s64)stats->cumulative_runnable_avg_scaled < 0);

    stats->pred_demands_sum_scaled += pred_demand_scaled_delta;
    BUG_ON((s64)stats->pred_demands_sum_scaled < 0);
}

说明 rq->wrq.walt_stats.cumulative_runnable_avg_scaled 和 rq->wrq.walt_stats.pred_demands_sum_scaled 统计的只是 runnable 状态的负载值。这里加上有符号的delta值，可以快速的反应runnable状态的负载的变化。

/* 
 * 如果task在rq上调用路径：update_history --> fixup_walt_sched_stats_common --> this 传参：(rq, task_load_delta)
 * 如果rq->curr == p 时调用路径：update_history --> this 传参：(rq, demand_scaled)
 * 说明这里面更新的成员统计的级包括 runnable 的分量，也保留 running 的分量
 */
static inline void walt_fixup_cum_window_demand(struct rq *rq, s64 scaled_delta)
{
    rq->wrq.cum_window_demand_scaled += scaled_delta;

    if (unlikely((s64)rq->wrq.cum_window_demand_scaled < 0))
        rq->wrq.cum_window_demand_scaled = 0;
}

rq->wrq.cum_window_demand_scaled 统计的既包括 runnable 的又包括 running 的。runnable 的累加的是差值，而 running 的累加的直接是 demand_scaled 的值，若是一部分 runnable 的任务变成 running 了，前者减少，后者增加，体现在结果上可能是不变的。

7. update_task_demand 函数

/*
 * 计算任务的cpu需求和/或更新任务的cpu需求历史
 *
 * ms = p->wts.mark_start
 * wc = wallclock
 * ws = rq->wrq.window_start
 *
 * 三种可能：
 *  a) 任务事件包含在一个窗口中。 16ms per-window, window_start < mark_start < wallclock
 *       ws    ms    wc
 *       |    |    |
 *       V    V    V
 *       |---------------|
 *
 * 在这种情况下，如果事件是合适的 p->wts.sum 被更新（例如：event == PUT_PREV_TASK）
 *
 * b) 任务事件跨越两个窗口。mark_start < window_start < wallclock
 *
 *       ms    ws     wc
 *       |    |     |
 *       V    V     V
 *      ------|-------------------
 *
 * 在这种情况下，如果事件是合适的 p->wts.sum 更新为 (ws - ms) ，然后记录一个新的窗口的采样，如果事件是合
 * 适的然后将 p->wts.sum 设置为 (wc - ws) 。
 *
 * c) 任务事件跨越两个以上的窗口。
 *
 *        ms ws_tmp                   ws  wc
 *        |  |                       |   |
 *        V  V                       V   V
 *        ---|-------|-------|-------|-------|------
 *           |                   |
 *           |<------ nr_full_windows ------>|
 *
 * 在这种情况下，如果事件是合适的，首先 p->wts.sum 更新为 (ws_tmp - ms) ，p->wts.sum 被记录，然后，如果
 * event 是合适的 window_size 的 'nr_full_window' 样本也被记录，最后如果 event 是合适的，p->wts.sum 更新
 * 到 (wc - ws)。
 *
 * 重要提示：保持 p->wts.mark_start 不变，因为 update_cpu_busy_time() 依赖它！
 *
 */
/* walt_update_task_ravg-->this 唯一调用位置 */
static u64 update_task_demand(struct task_struct *p, struct rq *rq, int event, u64 wallclock) //walt.c
{
    u64 mark_start = p->wts.mark_start; //进来时还没更新
    u64 delta, window_start = rq->wrq.window_start; //进来时已经更新了
    int new_window, nr_full_windows;
    u32 window_size = sched_ravg_window; //20ms
    u64 runtime;

    new_window = mark_start < window_start; //若为真说明经历了新窗口
    /* 若判断不需要更新负载，直接更新历史 p->wts.sum_history[]，而没有更新 p->wts.sum */
    if (!account_busy_for_task_demand(rq, p, event)) {
        if (new_window) {
            /*
             * 如果计入的时间没有计入繁忙时间，并且新的窗口开始，
             * 则只需要关闭前一个窗口与预先存在的需求。 多个窗口
             * 可能已经过去，但由于空窗口被丢弃，因此没有必要考虑这些。
             *
             * 如果被累积的时间没有被计入繁忙时间，并且有新的窗口开始，
             * 则只需要与预先存在需求的前一个窗口被关闭。 虽然可能有多
             * 个窗口已经流逝了，但由于WALT算法是空窗口会被丢弃掉，因
             * 此没有必要考虑这些。
             */
            update_history(rq, p, p->wts.sum, 1, event);
        }
        return 0;
    }
    /* 下面是需要更新的情况了 */

    /* (1) 还是同一个窗口，对应上面的情况a */
    if (!new_window) {
        /* 简单的情况 - 包含在现有窗口中的繁忙时间。*/
        return add_to_task_demand(rq, p, wallclock - mark_start);
    }

    /* (2) 下面就是跨越了窗口，先求情况b */
    /* 繁忙时间至少跨越两个窗口。 暂时将 window_start 倒回到 mark_start 之后的第一个窗口边界。*/
    delta = window_start - mark_start;
    nr_full_windows = div64_u64(delta, window_size);
    window_start -= (u64)nr_full_windows * (u64)window_size;

    /* Process (window_start - mark_start) first */
    /* 这里累加的是  情况b/情况c 中ws_tmp-ms这段的delta值 */
    runtime = add_to_task_demand(rq, p, window_start - mark_start);

    /* Push new sample(s) into task's demand history */
    /* 将最开始的不足一个window窗口大小的delta计算出来的p->wts.sum放入历史数组中 */
    update_history(rq, p, p->wts.sum, 1, event);

    /* (3) 下面就对应情况c了，由于c和b都有最开始不足一个窗口的一段，在上面计算b时一并计算了 */
    if (nr_full_windows) {
        u64 scaled_window = scale_exec_time(window_size, rq); //等于直接return window_size

        /* 一下子更新 nr_full_windows 个窗口的负载到历史窗口负载中，每个窗口都是满窗 */
        update_history(rq, p, scaled_window, nr_full_windows, event);
        /* runtime 累积运行时间进行累加 ==>只要搞清什么时候标记ms和什么时候调用这个函数计算负载，就可以知道计算的是哪段的 ######## */
        runtime += nr_full_windows * scaled_window;
    }

    /* 将 window_start 滚回当前以处理当前窗口，以便于计算当前窗口中的剩余部分。*/
    window_start += (u64)nr_full_windows * (u64)window_size;

    /* 这里是计算情况b和情况c的wc-ws段 */
    mark_start = window_start;

    runtime += add_to_task_demand(rq, p, wallclock - mark_start); //runtime 继续累加

    /* 返回值表示此次 update_task_demand 更新的时间值，是 wc-ms 的差值 */
    return runtime;
}

此函数中始终没有更新回去 p->wts.mark_start，其是在 walt_update_task_ravg 函数最后更新的。rq->wrq.window_start 在上面第一个函数中就更新了。

/* update_task_demand --> this */
static int account_busy_for_task_demand(struct rq *rq, struct task_struct *p, int event) //walt.c
{
    /* (1) 不需要统计 idle task 的 demand，直接返回*/
    if (is_idle_task(p))
        return 0;

    /*
     * 当一个任务被唤醒时，它正在完成一段非繁忙时间。 同样，如果等待时间
     * 不被视为繁忙时间，那么当任务开始运行或迁移时，它并未运行并且正在完成
     * 一段非繁忙时间。
     */
    /*就是这些情况跳过统计，!SCHED_ACCOUNT_WAIT_TIME 恒为假，所以是只判断了 TASK_WAKE */
    /* (2) 是唤醒事件 或 不需要计算walit事件并且事件是pick和migrate, 不需要更新 */
    if (event == TASK_WAKE || (!SCHED_ACCOUNT_WAIT_TIME && (event == PICK_NEXT_TASK || event == TASK_MIGRATE)))
        return 0;

    /* (3) idle进程退出的时候也不需要统计 */
    if (event == PICK_NEXT_TASK && rq->curr == rq->idle)
        return 0;

    /*
     * TASK_UPDATE can be called on sleeping task, when its moved between related groups
     */
    /*context_switch()的时候更改的rq->curr*/
    /* (4) 若是update事件，且p是curr任务，需要更新。否则若p在队列上需要更新，不在队列上不需要更新 */
    if (event == TASK_UPDATE) {
        if (rq->curr == p)
            return 1;

        return p->on_rq ? SCHED_ACCOUNT_WAIT_TIME : 0; //这里可调整是否记录任务在rq上的等待的时间
    }

    /* (5) 都不满足，默认是需要更新 */
    return 1;
}

p是idle task，或 事件是 TASK_WAKE，或idle任务退出时的 PICK_NEXT_TASK 事件，或事件是 TASK_UPDATE 但是 p 不是curr任务也没有在rq上，就不需要计算busy time。只有事件是 TASK_UPDATE，且任务p是 rq->curr 任务或者 p是在rq 上等待，则需要更新。若不需要更新的话，又产生了新的窗口，那就调用 update_history()更新负载历史就退出了。

/* update_task_demand --> this 唯一调用路径也是在 walt_update_task_ravg 中 */
static u64 add_to_task_demand(struct rq *rq, struct task_struct *p, u64 delta) //walt.c
{
    /* delta = (delta * rq->wrq.task_exec_scale) >> 10, 由于 rq->wrq.task_exec_scale 初始化为1024，所以还是delta*/
    delta = scale_exec_time(delta, rq);
    /* 这里更新了 p->wts.sum，并将最大值钳位在一个窗口大小*/
    p->wts.sum += delta;
    if (unlikely(p->wts.sum > sched_ravg_window))
        p->wts.sum = sched_ravg_window;

    return delta;
}

更新 p->wts.sum 值，并且返回 delta 值。这也是 sum 的唯一更新位置，唯一调用路径也是从 walt_update_task_ravg 函数调用下来的。

8. update_cpu_busy_time 函数

/* walt_update_task_ravg --> this 这是唯一调用路径，传参(p, rq, event, wallclock, irqtime)*/
static void update_cpu_busy_time(struct task_struct *p, struct rq *rq, int event, u64 wallclock, u64 irqtime)
{
    int new_window, full_window = 0;
    int p_is_curr_task = (p == rq->curr);
    u64 mark_start = p->wts.mark_start;
    u64 window_start = rq->wrq.window_start; //walt_update_task_ravg-->update_window_start 最先更新的rq->wrq.window_start
    u32 window_size = rq->wrq.prev_window_size;
    u64 delta;
    u64 *curr_runnable_sum = &rq->wrq.curr_runnable_sum;
    u64 *prev_runnable_sum = &rq->wrq.prev_runnable_sum;
    u64 *nt_curr_runnable_sum = &rq->wrq.nt_curr_runnable_sum;
    u64 *nt_prev_runnable_sum = &rq->wrq.nt_prev_runnable_sum;
    bool new_task;
    struct walt_related_thread_group *grp;
    int cpu = rq->cpu;
    u32 old_curr_window = p->wts.curr_window;

    new_window = mark_start < window_start;
    if (new_window)
        full_window = (window_start - mark_start) >= window_size;

    /* 处理每个任务的窗口翻转。 我们不关心空闲任务。*/
    if (!is_idle_task(p)) {
        if (new_window)
            /* 将 p->wts 的 curr_window 赋值给 prev_window，然后将 curr_window 清0 */
            rollover_task_window(p, full_window);
    }

    new_task = is_new_task(p); //运行时间小于5个窗口的任务

    /* p是curr任务并且有了个新窗口才执行 */
    if (p_is_curr_task && new_window) {
        /* rq的一些成员，prev_*_sum=curr_*_sum, 然后将 curr_*_sum 赋值为0 */
        rollover_cpu_window(rq, full_window);
        rollover_top_tasks(rq, full_window); //这里面已经更新了rq->wrq.curr_table ############
    }

    /* 判断是否需要记录 */
    if (!account_busy_for_cpu_time(rq, p, irqtime, event))
        goto done;
    /*----下面就是需要计算的了----*/

    grp = p->wts.grp;
    if (grp) {
        struct group_cpu_time *cpu_time = &rq->wrq.grp_time;
        /* 注意：指向更改了! */
        curr_runnable_sum = &cpu_time->curr_runnable_sum;
        prev_runnable_sum = &cpu_time->prev_runnable_sum;

        nt_curr_runnable_sum = &cpu_time->nt_curr_runnable_sum;
        nt_prev_runnable_sum = &cpu_time->nt_prev_runnable_sum;
    }

    if (!new_window) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。 
         * 没有翻转，因为我们没有启动一个新窗口。 这方面的一个例子是当
         * 任务开始执行然后在同一窗口内休眠时。
         */
        if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq))
            delta = wallclock - mark_start;
        else
            delta = irqtime;
        delta = scale_exec_time(delta, rq); //等于直接return delta
        *curr_runnable_sum += delta;
        if (new_task)
            *nt_curr_runnable_sum += delta;

        if (!is_idle_task(p)) {
            p->wts.curr_window += delta;
            p->wts.curr_window_cpu[cpu] += delta;
        }

        goto done;
    }
    /*----下面就是有一个新窗口的情况了----*/

    if (!p_is_curr_task) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。
         * 一个新窗口也已启动，但 p 不是当前任务，因此窗口不会翻转 
         * - 只需拆分并根据需要将计数分为 curr 和 prev。 仅在为当前任
         * 务处理新窗口时才会翻转窗口。
         *
         * irqtime 不能由不是当前正在运行的任务的任务计算。
         */

        if (!full_window) {
            /* 一个完整的窗口还没有过去，计算对上一个完成的窗口的部分贡献。*/
            delta = scale_exec_time(window_start - mark_start, rq);
            p->wts.prev_window += delta;
            p->wts.prev_window_cpu[cpu] += delta;
        } else {
            /* 由于至少一个完整的窗口已经过去，对前一个窗口的贡献是一个完整的窗口(window_size) */
            delta = scale_exec_time(window_size, rq);
            p->wts.prev_window = delta;
            p->wts.prev_window_cpu[cpu] = delta;
        }

        *prev_runnable_sum += delta;
        if (new_task)
            *nt_prev_runnable_sum += delta;

        /* 只占当前窗口的一部分繁忙时间 */
        delta = scale_exec_time(wallclock - window_start, rq);
        *curr_runnable_sum += delta;
        if (new_task)
            *nt_curr_runnable_sum += delta;

        p->wts.curr_window = delta; /*对当前窗的贡献直接复制给当前窗*/
        p->wts.curr_window_cpu[cpu] = delta;

        goto done;
    }
    /*----下面p是当前任务的情况了----*/

    if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq)) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。 一个新窗口已经启动， 
         * p 是当前任务，因此需要翻转。 如果以上三个条件中的任何一个为真，那么这个繁忙的时
         * 间就不能算作 irqtime。
         *
         * 空闲任务的繁忙时间不需要计算。
         *
         * 一个例子是一个任务开始执行，然后在新窗口开始后休眠。
         */

        if (!full_window) {
            /* 一个完整的窗口还没有过去，计算对上一个完整的窗口的部分贡献。*/
            delta = scale_exec_time(window_start - mark_start, rq); //等效直接返回window_start - mark_start
            if (!is_idle_task(p)) {
                p->wts.prev_window += delta;
                p->wts.prev_window_cpu[cpu] += delta;
            }
        } else {
            /* 由于至少一个完整的窗口已经过去，对前一个窗口的贡献是完整的窗口（window_size）*/
            delta = scale_exec_time(window_size, rq);
            if (!is_idle_task(p)) {
                p->wts.prev_window = delta;
                p->wts.prev_window_cpu[cpu] = delta;
            }
        }

        /* 在这里通过覆盖 prev_runnable_sum 和 curr_runnable_sum 中的值来完成翻转。*/
        *prev_runnable_sum += delta;
        if (new_task)
            *nt_prev_runnable_sum += delta;

        /* 计算在当前窗口忙时的一片时间 */
        delta = scale_exec_time(wallclock - window_start, rq);
        *curr_runnable_sum += delta;
        if (new_task)
            *nt_curr_runnable_sum += delta;

        if (!is_idle_task(p)) {
            p->wts.curr_window = delta;
            p->wts.curr_window_cpu[cpu] = delta;
        }

        goto done;
    }
    /*---- 下面就对应 irqtime && is_idle_task(p) && ！cpu_is_waiting_on_io(rq) 的情况了，并且累积上面的条件 ----*/

    if (irqtime) {
        /*
         * account_busy_for_cpu_time() = 1 所以忙时间需要计入当前窗口。
         * 一个新窗口已经启动，p 是当前任务，因此需要翻转。 当前任务必
         * 须是空闲任务，因为不为其他任何任务计算irqtime。
         *
         * 空闲一段时间后，每次我们处理 IRQ 活动时都会计算 Irqtime，因
         * 此我们知道 IRQ 繁忙时间为 wallclock - irqtime。
         */

        SCHED_BUG_ON(!is_idle_task(p));
        mark_start = wallclock - irqtime;

        /*
         * 滚动窗口。 如果 IRQ 繁忙时间只是在当前窗口中，那么这就是所有需要计算的。
         */
        if (mark_start > window_start) {
            *curr_runnable_sum = scale_exec_time(irqtime, rq); //等效于直接返回irqtime，因为是idle线程，之前应该是0的
            return;
        }
        /*---下面是ms<=ws---*/

        /*
         * IRQ 繁忙时间跨越多个窗口。 先处理当前窗口开始前的忙时间。
         */
        delta = window_start - mark_start;
        if (delta > window_size)
            delta = window_size;
        delta = scale_exec_time(delta, rq);
        *prev_runnable_sum += delta; //这直接加不会超过一个窗的大小吗？

        /* Process the remaining IRQ busy time in the current window.  处理当前窗口中剩余的 IRQ 忙时间。*/
        delta = wallclock - window_start;
        rq->wrq.curr_runnable_sum = scale_exec_time(delta, rq);

        return;
    }

done:
    if (!is_idle_task(p))
        update_top_tasks(p, rq, old_curr_window, new_window, full_window);
}

值更新当前窗口和前一个窗口的busy时间，主要用于更新任务的： p->wts.curr_window、p->wts.curr_window_cpu[cpu]，更新rq 的 rq->wrq.curr_runnable_sum、rq->wrq.prev_runnable_sum，若是一个walt认为的新任务，还更新 rq->wrq.nt_curr_runnable_sum、rq->wrq.nt_prev_runnable_sum。然后是更新 top-task 的一些成员

下面分别是对 task、cpu、top_tasks 维护的 window 进行更新。有一个新的窗口到来时更新，若更新时已经经历了一个或多个完整的window，那么对prev和curr window 相关的描述结构进行清理备用。

static u32 empty_windows[NR_CPUS];
/* 将 p->wts 的 curr_window 赋值给 prev_window，然后将 curr_window 清0 */
static void rollover_task_window(struct task_struct *p, bool full_window)
{
    u32 *curr_cpu_windows = empty_windows; //数组，每个cpu一个
    u32 curr_window;
    int i;

    /* Rollover the sum */
    curr_window = 0;

    /* 若经历了一个full_window, prev和curr window都清理待用 */
    if (!full_window) {
        curr_window = p->wts.curr_window;
        curr_cpu_windows = p->wts.curr_window_cpu;
    }

    p->wts.prev_window = curr_window;
    p->wts.curr_window = 0;

    /* Roll over individual CPU contributions 滚动每个 CPU 的贡献 */
    for (i = 0; i < nr_cpu_ids; i++) {
        p->wts.prev_window_cpu[i] = curr_cpu_windows[i];
        p->wts.curr_window_cpu[i] = 0;
    }

    if (is_new_task(p))
        p->wts.active_time += task_rq(p)->wrq.prev_window_size; //active_time 的唯一更新位置, walt认为的新任务
}

清理的是任务的 p->wts.prev_window_cpu、p->wts.curr_window、p->wts.prev_window_cpu[]、p->wts.curr_window_cpu[]

/*
 * rq的一些成员，prev_*_sum=curr_*_sum, 然后将 curr_*_sum 赋值为0，将curr赋值给prev,
 * 若是有经历了多个窗口curr和prev窗口都需要清理待用。
 */
static void rollover_cpu_window(struct rq *rq, bool full_window)
{
    u64 curr_sum = rq->wrq.curr_runnable_sum;
    u64 nt_curr_sum = rq->wrq.nt_curr_runnable_sum;
    u64 grp_curr_sum = rq->wrq.grp_time.curr_runnable_sum;
    u64 grp_nt_curr_sum = rq->wrq.grp_time.nt_curr_runnable_sum;

    if (unlikely(full_window)) {
        curr_sum = 0;
        nt_curr_sum = 0;
        grp_curr_sum = 0;
        grp_nt_curr_sum = 0;
    }

    rq->wrq.prev_runnable_sum = curr_sum;
    rq->wrq.nt_prev_runnable_sum = nt_curr_sum;
    rq->wrq.grp_time.prev_runnable_sum = grp_curr_sum;
    rq->wrq.grp_time.nt_prev_runnable_sum = grp_nt_curr_sum;

    rq->wrq.curr_runnable_sum = 0;
    rq->wrq.nt_curr_runnable_sum = 0;
    rq->wrq.grp_time.curr_runnable_sum = 0;
    rq->wrq.grp_time.nt_curr_runnable_sum = 0;
}

清理的是 rq->wrq 的 和 rq->wrq.grp_time 的 prev_runnable_sum、curr_runnable_sum、nt_prev_runnable_sum、nt_curr_runnable_sum

static void rollover_top_tasks(struct rq *rq, bool full_window)
{
    /* 跟踪的是2个，构成一个环形数组 */
    u8 curr_table = rq->wrq.curr_table;
    u8 prev_table = 1 - curr_table;
    int curr_top = rq->wrq.curr_top;

    /*将prev window的数据结构清理后待用*/
    clear_top_tasks_table(rq->wrq.top_tasks[prev_table]); //memset(arg, 0, NUM_LOAD_INDICES * sizeof(u8));
    clear_top_tasks_bitmap(rq->wrq.top_tasks_bitmap[prev_table]);//将bit数组的内容清0,然后将 NUM_LOAD_INDICES bit设置为1

    /*若是已经经历了多个window,那么之前标记的curr window也是旧窗口了，需要清理待用*/
    if (full_window) {
        curr_top = 0;
        clear_top_tasks_table(rq->wrq.top_tasks[curr_table]);
        clear_top_tasks_bitmap(rq->wrq.top_tasks_bitmap[curr_table]);
    }

    /*两个window的下标进行翻转，curr-->prev,prev-->curr*/
    rq->wrq.curr_table = prev_table;
    rq->wrq.prev_top = curr_top;
    rq->wrq.curr_top = 0;
}

清理的是 rq->wrq 的 top_task 相关的成员。

然后调用 account_busy_for_cpu_time 判断清理后任务的和cpu的是否还需要更新上去

/* update_cpu_busy_time-->this, 传参(rq, p, irqtime, event) */
static int account_busy_for_cpu_time(struct rq *rq, struct task_struct *p, u64 irqtime, int event)
{
    if (is_idle_task(p)) {
        /* TASK_WAKE && TASK_MIGRATE is not possible on idle task!  idle task不可能出现唤醒和迁移 */
        if (event == PICK_NEXT_TASK)
            return 0;

        /* PUT_PREV_TASK, TASK_UPDATE && IRQ_UPDATE are left */
        return irqtime || cpu_is_waiting_on_io(rq);
    }

    if (event == TASK_WAKE)
        return 0;

    if (event == PUT_PREV_TASK || event == IRQ_UPDATE)
        return 1;

    /*
     * TASK_UPDATE can be called on sleeping task, when its moved between related groups
     * TASK_UPDATE 当它在相关组之间移动时可能在睡眠的任务上调用，
     */
    if (event == TASK_UPDATE) {
        if (rq->curr == p)
            return 1;

        return p->on_rq ? SCHED_FREQ_ACCOUNT_WAIT_TIME : 0; //在rq上和或正在迁移是1，但是冒号前后都是0
    }

    /* TASK_MIGRATE, PICK_NEXT_TASK left */
    return SCHED_FREQ_ACCOUNT_WAIT_TIME; //0
}

top_task 维护的窗口更新：

/* 
 * update_cpu_busy_time-->this 若p不是idle任务，就调用，传参(p, rq, old_curr_window, new_window, full_window) 
 * @ old_curr_window：取自 p->wts.curr_window，表示p在窗口翻转前在当前窗口的运行时间
 * @ new_window：bool值，若ms<ws为真
 * @ full_window：bool值，若ws-ms>window_size为真
 */
static void update_top_tasks(struct task_struct *p, struct rq *rq, u32 old_curr_window, int new_window, bool full_window)
{
    /* 只使用两个窗口进行跟踪，当前是0，perv就是1，当前是1，prev就是0，两个数据结构构成一个环形缓存区 */
    u8 curr = rq->wrq.curr_table;
    u8 prev = 1 - curr;
    u8 *curr_table = rq->wrq.top_tasks[curr];
    u8 *prev_table = rq->wrq.top_tasks[prev];
    int old_index, new_index, update_index;
    u32 curr_window = p->wts.curr_window;
    u32 prev_window = p->wts.prev_window;
    bool zero_index_update;

    /* 两个窗的运行时间相等或新窗口还没有到来 */
    if (old_curr_window == curr_window && !new_window)
        return;

    /* 在一个窗中运行的时间越长，index就越大, 参数是一个窗口中的运行时长*/
    old_index = load_to_index(old_curr_window);
    new_index = load_to_index(curr_window);

    if (!new_window) {
        zero_index_update = !old_curr_window && curr_window;
        if (old_index != new_index || zero_index_update) {
            if (old_curr_window)
                curr_table[old_index] -= 1; //上一个窗口的累计值衰减
            if (curr_window)
                curr_table[new_index] += 1; //新窗口的累计值增加
            if (new_index > rq->wrq.curr_top)
                rq->wrq.curr_top = new_index; //更新rq->wrq.curr_top成员
        }

        if (!curr_table[old_index])
            __clear_bit(NUM_LOAD_INDICES - old_index - 1, rq->wrq.top_tasks_bitmap[curr]); //这个bit数组表示此运行时间下有没有计数值

        if (curr_table[new_index] == 1)
            __set_bit(NUM_LOAD_INDICES - new_index - 1, rq->wrq.top_tasks_bitmap[curr]);

        return;
    }
    /*---下面是new_window!=0的情况了---*/

    /*
     * 对于此任务来说窗口已经翻转。 当我们到达这里时，curr/prev 交换已经发生。 
     * 所以我们需要对新索引使用 prev_window 。
     */
    update_index = load_to_index(prev_window);

    if (full_window) { //至少有一个满窗
        /*
         * 这里有两个案例。 要么'p' 运行了整个窗口，要么根本不运行。 在任何一种情况下，
         * prev 表中都没有条目。 如果 'p' 运行整个窗口，我们只需要在 prev 表中创建一个
         * 新条目。 在这种情况下，update_index 将对应于 sched_ravg_window，因此我们可
         * 以无条件地更新顶部索引。
         */
        if (prev_window) {
            prev_table[update_index] += 1;
            rq->wrq.prev_top = update_index;
        }

        if (prev_table[update_index] == 1)
            __set_bit(NUM_LOAD_INDICES - update_index - 1, rq->wrq.top_tasks_bitmap[prev]);
    } else { //产生了新窗口，但是还没达到一个满窗
        zero_index_update = !old_curr_window && prev_window;
        if (old_index != update_index || zero_index_update) {
            if (old_curr_window)
                prev_table[old_index] -= 1;

            prev_table[update_index] += 1;

            if (update_index > rq->wrq.prev_top)
                rq->wrq.prev_top = update_index;

            /* 减为0是清理对应bit，首次设置为1时设置相应bit。top_tasks_bitmap[]在任务迁移时有使用 */
            if (!prev_table[old_index])
                __clear_bit(NUM_LOAD_INDICES - old_index - 1, rq->wrq.top_tasks_bitmap[prev]);
            if (prev_table[update_index] == 1)
                __set_bit(NUM_LOAD_INDICES - update_index - 1, rq->wrq.top_tasks_bitmap[prev]);
        }
    }

    if (curr_window) {
        curr_table[new_index] += 1;

        if (new_index > rq->wrq.curr_top)
            rq->wrq.curr_top = new_index;

        if (curr_table[new_index] == 1)
            __set_bit(NUM_LOAD_INDICES - new_index - 1, rq->wrq.top_tasks_bitmap[curr]);
    }
}

top_tasks 的维护中也使用到了桶，新窗运行时间对应的 curr_table[]成员加1，之前窗口运行时间对应的 prev_table[] 成员减1。

9. update_task_pred_demand 函数

/*
 * 在窗口翻转时计算任务的预测需求。如果任务当前窗口繁忙时间超过预测需求，则在此处更新以反映任务需求。
 */
void update_task_pred_demand(struct rq *rq, struct task_struct *p, int event)
{
    u32 new, old;
    u16 new_scaled;

    if (!sched_predl) //1
        return;

    if (is_idle_task(p))
        return;

    if (event != PUT_PREV_TASK && event != TASK_UPDATE &&
            (!SCHED_FREQ_ACCOUNT_WAIT_TIME || (event != TASK_MIGRATE && event != PICK_NEXT_TASK)))
        return;

    /*
     * 当它在相关组之间移动时，TASK_UPDATE 可以在睡眠任务上调用。
     */
    if (event == TASK_UPDATE) {
        if (!p->on_rq && !SCHED_FREQ_ACCOUNT_WAIT_TIME)
            return;
    }

    new = calc_pred_demand(p);
    old = p->wts.pred_demand;

    if (old >= new)
        return;
    /*---下面就是 new > old 的情况---*/

    new_scaled = scale_demand(new); //new/window_size*1024
    /* p是on rq的状态并且不是已经被throttle的deadline任务 */
    if (task_on_rq_queued(p) && (!task_has_dl_policy(p) || !p->dl.dl_throttled))
        fixup_walt_sched_stats_common(rq, p, p->wts.demand_scaled, new_scaled);

    p->wts.pred_demand = new;
    p->wts.pred_demand_scaled = new_scaled;
}

注意，这里再次调用了 fixup_walt_sched_stats_common，在 walt_update_task_ravg 函数中，在 update_history 中已经调用过一次，进入条件也相同，也是p在队列上。

static inline u32 calc_pred_demand(struct task_struct *p)
{
    /* 预测的需求比当前窗口的大，就返回预测的需求 */
    if (p->wts.pred_demand >= p->wts.curr_window)
        return p->wts.pred_demand;

    return get_pred_busy(p, busy_to_bucket(p->wts.curr_window), p->wts.curr_window);
}

get_pred_busy 和 busy_to_bucket 两个函数上面都有列出。

10. run_walt_irq_work 函数

static inline void run_walt_irq_work(u64 old_window_start, struct rq *rq) //walt.c
{
    u64 result;

    /*若是还是同一个窗，直接退出*/
    if (old_window_start == rq->wrq.window_start)
        return;

    /* 
     * atomic64_cmpxchg(*ptr, old, new) 函数功能是：将old和ptr指向的内容比较，如果相等，
     * 则将new写入到ptr指向的内存中，并返回old，如果不相等，则返回ptr指向的内容。
     */
    result = atomic64_cmpxchg(&walt_irq_work_lastq_ws, old_window_start, rq->wrq.window_start);
    if (result == old_window_start) {
        walt_irq_work_queue(&walt_cpufreq_irq_work); //触发回调 walt_irq_work()，构成一个"内核线程"，循环往复执行

        trace_walt_window_rollover(rq->wrq.window_start);
    }
}

walt_irq_work_queue 会触发 walt_irq_work() 被调用，这个函数中又会调用 walt_update_task_ravg，walt_update_task_ravg 函数会在每个tick中调用，这里这样实现可能是针对没有tick的场景使用。

其中Trace:

trace_walt_window_rollover(rq->wrq.window_start);

参数原型：

(u64 window_start)

打印内容：

//20ms间隔执行一次
<idle>-0     [002] d..2 48262.320451: walt_window_rollover: window_start=48262548000001
<idle>-0     [001] d.h2 48262.340457: walt_window_rollover: window_start=48262568000001

字段解析：

window_start 就是打印 rq->wrq.window_start 的记录的时间值，单位是ns.

四、总结

    WALT负载计算算法是基于窗口的，对window有一个rollover的操作，只跟踪curr和prev两个窗口，curr窗口的下标由 wrq.curr_table 指向，两个窗口构成一个唤醒缓冲区，prev和curr进行不断切换。
    walt_update_task_ravg 函数通过其 event 成员决定对哪些事件计算负载，再根据其调用路径和其调用函数对是否是在rq上，是否是p=rq->curr可以判断统计的是哪部分的负载。
    预测负载这块，对于任务和CPU都使用了桶，任务是10个桶，对于cpu的curr和prev两个窗口分别是1000个成员，命中累加，不命中衰减。
    walt_update_task_ravg 在tick的调用路径中有调用，应该是为了无tick情况下walt仍然能正常工作，使用irq_work构成一个内核线程以一个窗口的周期来更新窗口。

五、补充

    task util的获取：task_util() WALT: p->wts.demand_scaled；PELT: p->se.avg.util_avg
    cpu util的获取：cpu_util_cum() WALT: rq->wrq.cum_window_demand_scaled；PELT: rq->cfs.avg.util_avg
    task_util() 函数

static inline unsigned long task_util(struct task_struct *p)
{
#ifdef CONFIG_SCHED_WALT
    if (likely(!walt_disabled && sysctl_sched_use_walt_task_util))
        return p->wts.demand_scaled;
#endif
    return READ_ONCE(p->se.avg.util_avg);
}

NUMA（Non-Uniform Memory Access，非一致性存储器访问）的设计理念是将 CPU 和 Main Memory 进行分区自治（Local NUMA node），又可以跨区合作（Remote NUMA node），以这样的方式来缓解单一内存总线存在的瓶颈。

不同的 NUMA node 都拥有几乎相等的资源，在 Local NUMA node 内部会通过自己的存储总线访问 Local Memory，而 Remote NUMA node 则可以通过主板上的共享总线来访问其他 Node 上的 Remote Memory。

显然的，CPU 访问 Local Memory 和 Remote Memory 所需要的耗时是不一样的，所以 NUMA 才得名为 “非一致性存储器访问"。同时，因为 NUMA 并非真正意义上的存储隔离，所以 NUMA 同样只会保存一份操作系统和数据库系统的副本。也就是说，默认情况下，耗时的远程访问是很可能存在的。

这种做法使得 NUMA 具有一定的伸缩性，更加适合应用在服务器端。但也由于 NUMA 没有实现彻底的主存隔离，所以 NUMA 的扩展性也是有限的，最多可支持几百个 CPU/Core。这是为了追求更高的并发性能所作出的妥协。

基本对象概念

    Node（节点）：一个 Node 可以包含若干个 Socket，通常是一个。
    Socket（插槽）：一颗物理处理器 SoC 的封装。
    Core（核心）：一个 Socket 封装的若干个物理处理器核心（Physical processor）。
    Hyper-Thread（超线程）：每个 Core 可以被虚拟为若干个（通常为 2 个）逻辑处理器（Virtual processors）。逻辑处理器会共享大多数物理处理器资源（e.g. 内存缓存、功能单元）。
    Processor（逻辑处理器）：操作系统层面的 CPU 逻辑处理器对象。
    Siblings：操作系统层面的 Physical processor 和下属 Virtual processors 之间的从属关系。

下图所示为一个 NUMA Topology，表示该服务器具有 2 个 Node，每个 Node 含有一个 Socket，每个 Socket 含有 6 个 Core，每个 Core 又被超线程为 2 个 Thread，所以服务器总共的 Processor = 2 x 1 x 6 x 2 = 24 颗，其中 Siblings[0] = [cpu0, cpu1]。

查看 Host 的 NUMA Topology

#!/usr/bin/env python
# SPDX-License-Identifier: BSD-3-Clause
# Copyright(c) 2010-2014 Intel Corporation
# Copyright(c) 2017 Cavium, Inc. All rights reserved.

from __future__ import print_function
import sys
try:
    xrange # Python 2
except NameError:
    xrange = range # Python 3

sockets = []
cores = []
core_map = {}
base_path = "/sys/devices/system/cpu"
fd = open("{}/kernel_max".format(base_path))
max_cpus = int(fd.read())
fd.close()
for cpu in xrange(max_cpus + 1):
    try:
        fd = open("{}/cpu{}/topology/core_id".format(base_path, cpu))
    except IOError:
        continue
    except:
        break
    core = int(fd.read())
    fd.close()
    fd = open("{}/cpu{}/topology/physical_package_id".format(base_path, cpu))
    socket = int(fd.read())
    fd.close()
    if core not in cores:
        cores.append(core)
    if socket not in sockets:
        sockets.append(socket)
    key = (socket, core)
    if key not in core_map:
        core_map[key] = []
    core_map[key].append(cpu)

print(format("=" * (47 + len(base_path))))
print("Core and Socket Information (as reported by '{}')".format(base_path))
print("{}\n".format("=" * (47 + len(base_path))))
print("cores = ", cores)
print("sockets = ", sockets)
print("")

max_processor_len = len(str(len(cores) * len(sockets) * 2 - 1))
max_thread_count = len(list(core_map.values())[0])
max_core_map_len = (max_processor_len * max_thread_count)  \
                      + len(", ") * (max_thread_count - 1) \
                      + len('[]') + len('Socket ')
max_core_id_len = len(str(max(cores)))

output = " ".ljust(max_core_id_len + len('Core '))
for s in sockets:
    output += " Socket %s" % str(s).ljust(max_core_map_len - len('Socket '))
print(output)

output = " ".ljust(max_core_id_len + len('Core '))
for s in sockets:
    output += " --------".ljust(max_core_map_len)
    output += " "
print(output)

for c in cores:
    output = "Core %s" % str(c).ljust(max_core_id_len)
    for s in sockets:
        if (s,c) in core_map:
            output += " " + str(core_map[(s, c)]).ljust(max_core_map_len)
        else:
            output += " " * (max_core_map_len + 1)
    print(output)

OUTPUT：

$ python cpu_topo.py
======================================================================
Core and Socket Information (as reported by '/sys/devices/system/cpu')
======================================================================

cores =  [0, 1, 2, 3, 4, 5]
sockets =  [0, 1]

       Socket 0    Socket 1
       --------    --------
Core 0 [0]         [6]
Core 1 [1]         [7]
Core 2 [2]         [8]
Core 3 [3]         [9]
Core 4 [4]         [10]
Core 5 [5]         [11]

上述输出的意义：

    有两个 Socket（物理 CPU）
    每个 Socket 有 6 个 Core（物理核)，总计 12 个

Output：

$ python cpu_topo.py
======================================================================
Core and Socket Information (as reported by '/sys/devices/system/cpu')
======================================================================

cores =  [0, 1, 2, 3, 4, 5]
sockets =  [0, 1]

       Socket 0        Socket 1
       --------        --------
Core 0 [0, 12]         [6, 18]
Core 1 [1, 13]         [7, 19]
Core 2 [2, 14]         [8, 20]
Core 3 [3, 15]         [9, 21]
Core 4 [4, 16]         [10, 22]
Core 5 [5, 17]         [11, 23]

    有两个 Socket（物理 CPU）。
    每个 Socket 有 6 个 Core（物理核)，总计 12 个。
    每个 Core 有两个 Virtual Processor，总计 24 个。

NUMA 架构中的多线程性能开销
1、跨 Node 的 Memory 访问开销

NUMA（非一致性存储器访问）的意思是 Kernel Thread 访问 Local Memory 和 Remote Memory 所需要的耗时是不一样的。

NUMA 的 CPU 分配策略有下 2 种：

    cpu-node-bind：约束 Kernel Thread 运行在指定的若干个 NUMA Node 上。
    phys-cpu-bind：约束 Kernel Thread 运行在指定的若干个 CPU Core 上。

NUMA 的 Memory 分配策略有下列 4 种：

    local-alloc：约束 Kernel Thread 只能访问 Local Node Memory。
    preferred：宽松地为 Kernel Thread 指定一个优先 Node，如果优先 Node 上没有足够的 Memory 资源，则允许运行在访问 Remote Node Memory。
    mem-bind：规定 Kernel Thread 只能请求指定的若干个 Node 上的 Memory，但并不严格规定只能访问 Local NUMA Memory。
    inter-leave：规定 Kernel Thread 可以使用 RR 算法轮转地从指定的若干个 Node 上请求访问 Memory。

2、跨 Core 的多线程 Cache 同步开销

NUMA Domain Scheduler 是 Kernel 针对 NUMA 体系架构实现的 Kernel Thread 调度器，目的是为了让 NUMA 中的每个 Core 都尽量均衡的忙碌。

根据 NUMA Topology 的特性呈一颗树状结构。NUMA Domain Scheduling，从叶节点向上根节点遍历，直到所有的 NUMA Domain 中的负载都是均衡的。当然，用户可以对不同的 Domain 设置相应的调度策略。

但这种针对所有 Cores 的均衡优化是有代价的，比如：将同一个 User Process 对应若干个 Kernel Thread 均衡到不同的 Cores 上执行，会使得 Core Cache 失效，造成性能下降。

    Cache 可见性（并发安全）问题：分别在 Core1 和 Core2 上运行的 Kernel Thread 都会在各自的 L1/L2 Cache 中缓存数据，但这些数据对彼此是不可见的，即：如果在 Core1 不将 Cache 中的数据写回到 Main Memory 的前提下，Core2 永远看不见 Core1 对某个变量数值的修改。继而会导致多线程共享数据不一致的情况。
    Cache 一致性（并发性能）问题：如果多个 Kernel Thread 运行在多个 Cores 上，同时这些 Threads 之间存在共享数据，而这些数据有存储在 Cache 中，那么就存在 Cache 一致性数据同步的必要。例如：分别在 Core1 和 Core2 上运行的 Kernel Thread 希望保证共享数据是一致的，那么就需要强制性的将 Core1 Cache 中对变量数值的修改写回到 Main Memory，然后 Core1 通知 Core2 数值更新了，再让 Core2 从 Main Memory 获取到最新的数值，并加载到 Core2 Cache 中。为了维护 Cache 数据的一致性所产生的流量会为主存数据总线带来压力，继而影响到 CPU 的性能。
    Cache 失效性（并发性能）问题：如果出于均衡的考虑，调度器会主动出发线程切换，例如：将在 Core1 上运行的 Kernel Thread 动态的调度到另一个空闲的 Core2 上运行，那么在 Core1 Cache 上的数据就需要先写回到 Memory，然后再进行调度。如果此时 Core1 和 Core2 分属于不同的 NUMA Node，那么就会出现更加耗时的 Remote Memory 访问。

如下图所示，在不同的 Domain 中存在着不同的 Cache 成本。虽然 NUMA Domain Scheduling 自身也具有软亲和特性，但其到底是侧重于 NUMA Cores 的均衡调度，而不是保证应用程序的执行性能。

可见，NUMA Domain Scheduler 的均衡调度机制和高并发性能是相悖的。

3、多线程上下文切换开销

在 Core 执行任务期间，需要将线程的执行现场信息存储在 Core 的 Register 和 Cache 中，这些数据集称为 Context（上下文），有下列 3 种类型：

    User Level Context：PC 程序计数器、寄存器、线程栈等。
    Register Context：通用寄存器、PC 程序寄存器、处理器状态寄存器、栈指针等。
    Kernel Level Context：进程描述符（task_struct）、PC 程序计数器、寄存器、虚拟地址空间等。

多线程的 Context Switch（上下文切换）也可以分为 2 个层面：

    User Level Thread 层面：由高级编程语言线程库实现的 Multiple User Threads，在单一个 Core 上进行时间分片轮训被动切换，或协作式自动切换。由于 User Thread 的 User Level Context 非常轻量，且共享同一个 User Process 的虚拟地址空间，所以 User Level 层面的 Context Switch 开销小，速度快。
    Kernel Level Thread 层面：Multiple Kernel Threads 由 Kernel 中的 NUMA Domain Scheduler 在多个 Cores 上进行调度和切换。由于 Kernel Thread 的 Context 更大（Kernel Thread 执行现场，包括：task_struct 结构体、寄存器、程序计数器、线程栈等），且涉及跨 Cores 之间的数据同步和主存访问，所以 Kernel Level 层面的 Context Switch 开销大，速度慢。

进行线程切换的过程中，首先会将一个线程的 Context 存储在相应的用户或内核堆栈中，然后把下一个要运行的线程的 Context 加载到 Core 的 Register 和 Cache 中。

可见，多线程的 Context Switch 势必会导致处理器性能的下降。并且 User Level 和 Kernel Level 切换很可能是同时出现的，这些都是应用多线程模式所需要付出的代价。

使用 vmstat 指令查看当前系统的上下文切换情况：

$ vmstat
procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
 r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
 4  1      0 4505784 313592 7224876    0    0     0    23    1    2  2  1 94  3  0

    r：CPU 运行队列的长度和正在运行的线程数。
    b：正在阻塞的进程数。
    swpd：虚拟内存已使用的大小，如果大于 0，表示机器的物理内存不足了。如果不是程序内存泄露的原因，那么就应该升级内存或者把耗内存的任务迁移到其他机器上了。
    si：每秒从磁盘读入虚拟内存的大小，如果大于 0，表示物理内存不足或存在内存泄露，应该杀掉或迁移耗内存大的进程。
    so：每秒虚拟内存写入磁盘的大小，如果大于 0，同上。
    bi：块设备每秒接收的块数量，这里的块设备是指系统上所有的磁盘和其他块设备，默认块大小是 1024Byte。
    bo：块设备每秒发送的块数量，例如读取文件时，bo 就会大于 0。bi 和 bo 一般都要接近 0，不然就是 I/O 过于频繁，需要调整。
    in：每秒 CPU 中断的次数，包括时间中断。
    cs：每秒上下文切换的次数，这个值要越小越好，太大了，要考虑减少线程或者进程的数目。上下文切换次数过多表示 CPU 的大部分时间都浪费在上下文切换了而不是在执行任务。
    st：CPU 在虚拟化环境上在其他租户上的开销。

4、CPU 运行模式切换开销

CPU 运行模式切换同样会对执行性能造成影响，不过相对于上下文切换会更低一些，因为模式切换最主要的任务只是切换线程寄存器的上下文。

Linux 系统中的以下操作会触发 CPU 运行模式切换：

    系统调用 / 软中断：当应用程序需要访问 Kernel 资源时，需要通过 SCI 进入内核模式执行相应的内核代码，完成所需操作后再返回到用户模式。
    中断处理：当外设发生中断事件时，会向 CPU 发出中断信号，此时 Kernel 需要立即响应中断，进入内核模式执行相应的中断处理程序，处理完后再返回用户模式。
    异常处理：当 Kernel 出现运行时错误或其他异常情况，如：页错误、除零错误、非法操作等，操作系统需要进入内核模式执行相应的异常处理程序，进行错误恢复或提示，然后再返回用户模式。
    Kernel Thread 切换：当 User Process 下属的 Kernel Thread 进行切换时，首先需要切换相应的 Kernel Level Context 并执行，最后再返回用户模式下执行 User Process 的代码。

5、中断处理的开销

硬件中断（HW Interrupt）是一种外设（e.g. 网卡、磁盘控制器、鼠键、串行适配卡等）和 CPU 交互通信的机制，让 CPU 能够及时掌握外设发生的事件，并视乎于中断的类型来决定是否放下当前任务，尽快处理紧急的外设事件（e.g. 以太网数据帧到达，键盘输入)。

硬件中断的本质是一个 IRQ（中断请求信号）电信号。Kernel 为每个外设分配了一个 IRQ Number，以此来区分发出中断的设备类型。IRQ Number 又会映射到 Kernel ISR（中断服务路由列表）中的一个中断处理程序（通常又外设驱动提供）。

硬件中断是 Kernel 调度优先级最高的任务类型之一，进行抢占式调度，所以硬件中断通常都伴随着任务切换，将当前任务切换到中断处理程序的上下文。

一次中断处理，首先需要将 CPU 的状态寄存器数据保存到虚拟内存空间中的堆栈，然后运行中断服务程序，最后再将状态寄存器数据从堆栈中夹在到 CPU。整个过程需要至少 300 个 CPU 时钟周期。并且在多核处理器计算平台中，每个 Core 都有可能执行硬件中断处理程序，所以还存在着跨 Core 处理要面对的 Cache 一致性流量的问题。

可见，大量的中断处理，尤其是硬件中断处理会非常消耗 CPU 资源。
6、TLB 缓存失效的开销

因为 TLB（地址映射表高速缓存）的空间非常有限，在使用 4K 小页的操作系统中，出现 Kernel Thread 频繁切换时，会导致 TLB 缓存的虚拟地址空间映射条目频繁变更，产生大量的缓存缺失。
7、内存拷贝的开销

在网络报文处理场景中，NIC Driver 运行在内核态，当 Driver 收到的报文后，首先会拷贝到 TCP/IP Stack 处理，然后再拷贝到用户空间的应用程序缓冲区。这些拷贝处理的时间会占报文处理总时长的 57.1%。
NUMA 架构中的性能优化：使用多核编程代替多线程

为了解决上述问题，在 NUMA 架构中进一步提升多核处理器平台的性能，应该广泛采用 “多核编程代替多线程编程” 的思想，通过将 Kernel Threrad 与 NUMA Node 或 Core 建立亲和性，以此来避免多线程调度带来的开销。
NUMA 亲和性：避免 CPU 跨 NUMA 访问内存

在 Linux Shell 上，可以使用 numastat 指令来查看 NUMA Node 的内存分配统计数据；可以使用 numactl 指令可以将 User Process 绑定到指定的 NUMA Node，还可以绑定到指定的 NUMA Core 上。
CPU 亲和性：避免跨 CPU Cores 的 Kernel Thread 切换

CPU 亲和性（CPU Affinity）是 Kernel 的一种 Kernel Thread 调度属性（Scheduling Property），指定 Kernel Thread 要在特定的 CPU 上尽量长时间地运行而不被调度到其他的 CPU 上。在 NUMA 架构中，设置 Kernel Thread 的 CPU 亲和性，能够有效提高 Thread 的 CPU Cache 命中率，减少 Remote NUMA Memory 访问的损耗，以获得更高的性能。

    软 CPU 亲和性：是 Linux Scheduler 的默认调度策略，调度器会积极的让 Kernel Thread 在同一个 CPU 上运行。
    硬 CPU 亲和性：是 Linux Kernel 提供的可编程 CPU 亲和性，用户程序可以显式地指定 User Process 对应的 Kernel Thread 在哪个或哪些 CPU 上运行。

硬 CPU 亲和性通过扩展 task_struct（进程描述符）结构体来实现，引入 cpus_allowed 字段来表示 CPU 亲和位掩码（BitMask）。cpus_allowed 由 n 位组成，对应系统中的 n 个 Processor。最低位表示第一个 Processor，最高位表示最后一个 Processor，通过对掩码位置 1 来指定 Processors 亲和，当有多个掩码位被置 1 时表示运行进程在多个 Processor 间迁移，缺省为全部位置 1。进程的 CPU 亲和特性会传递给子线程。

在 Linux Shell 上，可以使用 taskset 指令来设定 User Process 的 CPU 亲和性，但不能保证 NUMA 亲和性的内存分配。
IRQ（中断请求）亲和性

Linux Kernel 提供了 irqbalance 程序来进行中断负载优化，在大部分场景中，irqbalance 提供的中断分配优化都是可以起到积极作用的，irqbalance 会自动收集系统数据来分析出使用模式，并依据系统负载状况将工作状态调整为以下 2 种模式：

    Performance mode：irqbalance 会将中断尽可能均匀地分发给各个 CPU 的 Core，以充分提升性能。
    Power-save mode：irqbalance 会将中断处理集中到第一个 CPU，保证其它空闲 CPU 的睡眠时间，降低能耗。

当然，硬件中断处理也具有亲和性属性，用于指定运行 IRP 对应的 ISR 的 CPU。在 Linux Shell 上，可以修改指定 IRQ Number 的 smp_affinity。注意，手动指定 IRQ 亲和性首先需要关闭 irqbalance 守护进程。

进程调度，即 Linux Kernel Scheduler 如何将多个 User Process 调度给 CPU 执行，从而实现多任务执行环境的公平竞争以及合理分配 CPU 资源。

在古早的单核环境中，Linux Scheduler 的主要目的是通过 "时间片轮转算法" 和 “优先级调度算法“ 来实现调度。而在现代多核环境中，Linux Scheduler 则需要考虑更多的复杂因素，如：CPU 负载均衡、Cache 亲和性、多核互斥等。所以本文主要讨论的是多核环境中的进程调度。

为了应对不同应用场景中的进程调度需求，Linux Kernel 实现了多种 Scheduler 类型，常见的有：

    CFS（Completely Fair Scheduler，完全公平调度器）
    RT（Real-time Scheduler，实时调度器）
    DS（Deadline Scheduler，最后期限调度器）

这些 Scheduler 会被作用于每个 CPU Cores 的 “就绪队列“ 中，且具有各自不同的调度算法和优先级策略。

在操作系统层面用户可以操作的只有用户进程实体，所以我们能够看见并使用的大多数调度配置都是针对 User Process 而言。

如下图，Kernel 将进程分为 2 大类型，对应各自的优先级区域以及不同的调度算法。

    实时进程：具有实时性要求，共有 0～99 这 100 个优先级。
    普通进程：没有实时性要求，共有 100～139 这 40 个级别。

但实际上，实时进程的优先级是初设后不可更改的。也就是说，从系统管理员的角度（Shell）只能配置普通进程的优先级。

针对普通进程的优先级配置，Linux 引入了 Nice level 的设计，Nice 值的范围是 -20～19 刚好对应到普通进程的 40 个优先级。其中，普通用户可以配置的范围是 0～19，而 Root 管理员则可以配置 -20～19。

CFS 完全公平调度器

Linux CFS（Completely Fair Scheduler，完全公平调度器）是 Kernel 默认使用的进程调度器，常用于通用计算场景。

CFS 的 “完全公平“ 并不是简单粗暴的按照 CPU 时间片大小来进行调度，而是会根据进程的运行时间来计算出优先级，运行时间较短的进程会拥有更高的优先级，从而保证了每个进程都能够获得公平的 CPU 时间。

具体而言，CFS 是一种基于红黑树的调度算法，它的目标是让所有进程都可以获得相同的 CPU 时间片。实现原理如下：

    CFS 在每个 CPU 上都有一棵红黑树，每个节点对应一个普通进程的 PCB（task_struct）和一个 Key。这个 Key 是进程的一个 VRT（虚拟运行时间），反应了进程在 CPU 上的运行时间。运行时间越长，VRT 就越大，优先级就越小。
    当一个新的普通进程被创建时，它会被加入到红黑树中，并且初始的 VRT 值为 0，表示拥有最高调度优先级。
    当 CPU 空闲时，就查询红黑树，并将 VRT 最小的就绪进程调度执行，完毕后增加其 VRT，降低其下次调度的优先级。

可见，CFS 的优点让每个进程都获得了公平的 CPU 时间。然而，CFS 的缺点是由于红黑树的操作复杂度较高，对于高并发的场景可能会影响系统的性能。

SCHED_NORMAL（普通进程调度算法）

SCHED_NORMAL 是 CFS 的基本实现，采用了上文中提到的 “时间片轮转“ 和 “动态优先级“ 调度机制。

    动态优先级：普通进程具有一个 nice 值来表示其优先级，nice 值越小，进程优先级越高。
    时间片轮转：如果有多个普通进程的优先级相同，则采用轮流执行的方式。

SCHED_BATCH（批量调度算法）

SCHED_BATCH 是一种针对 CPU 密集型批处理作业的调度算法。它的主要目的是在系统空闲时间运行一些需要大量 CPU 时间的后台任务。

区别于 SCHED_NORMAL，它并不使用时间片轮转和动态优先级调度机制，而是采用了一种基于进程组的批量处理策略。该算法会将所有的后台任务进程加入到一个进程组中，该进程组会共享一个可调度时间片。

在 SCHED_BATCH 中，进程组会被赋予更高的优先级，以确保后台任务能够在系统空闲时间得到足够的 CPU 时间。
RTS 实时调度器

Linux RTS（Real-Time Scheduler，实时调度器）采用固定优先级调度算法，优先级高的进程会获得更多的 CPU 时间。RTS 是 RT-Kernel 的默认调度算法，常用于对实时性要求高的计算场景。

RTS 的主要目的是保证实时任务的响应性和可预测性。固定优先级调度算法，总是可以让高优先级任务先运行，同时还实现了基于抢占的调度策略，以保证实时任务能够在预定的时间内运行完成。实现原理如下：

    RTS 优先级数值范围从 1（最高）～99（最低），其中 0 保留给 Kernel 使用。
    RTS 还实现了基于抢占的调度策略。当一个高优先级的任务到来时，它可以抢占当前正在运行的任务，并且直到运行完毕。
    RTS 使用了多队列的方法来管理实时进程。RTS 在每个 CPU 上维护 2 级就绪队列，一个是实时队列，一个是普通队列。并采用了不同的调度算法和优先级策略来进行调度。例如：实时进程采用 SCHED_FIFO 调度算法，普通进程采用 SCHED_RR。
    调度器每次选择下一个要运行的进程时，会先从实时队列中选择进程，如果实时队列为空，则从普通队列中选择进程。这样可以保证实时进程的优先级高于普通进程，同时也避免了实时进程长时间等待的情况。

RTS 的优点是能够保证实时任务的响应性和可预测性，但缺点是对于普通任务来说可能会出现长时间等待的情况。

SCHED_FIFO（先到先服务调度算法）

SCHED_FIFO 调度算法会按照进程的提交顺序来分配 CPU 时间，当一个进程获得 CPU 时间后，它会一直运行直到完成或者被更高优先级的进程抢占。因此，该算法可能导致低优先级进程的饥饿情况，因为高优先级进程可能会一直占用 CPU 时间。
SCHED_RR（时间片轮转调度算法）

与 SCHED_FIFO 类似，SCHED_RR 调度算法也会按照进程的提交顺序来分配 CPU 时间。不同之处在于，每个进程都被赋予一个固定的时间片，当时间片用完后，该进程就会被放回就绪队列的尾部，等待下一次调度。该算法可以避免低优先级进程饥饿的问题，因为每个进程都能够获得一定数量的 CPU 时间，而且高优先级进程也不能一直占用 CPU 时间。
DS 最后期限调度器

Linux DS（Deadline Scheduling，最后期限调度器）是一种基于最后期限（Deadline）的调度器。实现原理如下：

    DS 与 CFS 类似的采用了红黑树，但主要区别在于 DS 的树节点 Key 是 Deadline 值，而不是 VRT。
    DS 为每个进程赋予一个 Deadline，DS 会按照进程的最后期限的顺序，安排进程的执行顺序。进程的最后期限越近，其优先级就越高。
    当 CPU 空闲时，就查询红黑树，并将 Deadline 离与当前时间最近的就绪进程调度执行。

SCHED_DEADLINE（最后期限调度算法）

SCHED_DEADLINE 调度算法是 DS 调度器的默认调度算法，主要用于实时任务的调度。
进程调度策略的配置
ps 指令

我们在配置一个进程的调度策略之前，常常需要使用 ps 指令查看进程的状态信息。
查看进程资源使用信息

 $ ps aux

USER        PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root          1  0.1  0.0  78088  9188 ?        Ss   04:26   0:03 /sbin/init maybe-ubiquity
...
stack      2152  0.1  0.8 304004 138160 ?       S    04:27   0:04 nova-apiuWSGI worker 1
stack      2153  0.1  0.8 304004 138212 ?       S    04:27   0:04 nova-apiuWSGI worker 2
...

查看指定进程的 CPU 资源详细使用信息

$ pidstat -p 12285

02:53:02 PM   UID       PID    %usr %system  %guest    %CPU   CPU  Command
02:53:02 PM     0     12285    0.00    0.00    0.00    0.00     5  python 

    PID：进程 ID。
    %usr：进程在用户态运行所占 CPU 的时间比率。
    %system：进程在内核态运行所占 CPU 的时间比率。
    %CPU：进程运行所占 CPU 的时间比率。
    CPU：进程在哪个核上运行。
    Command：创建进程对应的命令。

查看进程优先级信息

$ ps -le

F S   UID    PID   PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 S     0      1      0  0  80   0 - 19522 ep_pol ?        00:00:03 systemd
1 S     0      2      0  0  80   0 -     0 kthrea ?        00:00:00 kthreadd
1 I     0      4      2  0  60 -20 -     0 worker ?        00:00:00 kworker/0:0H
1 I     0      6      2  0  60 -20 -     0 rescue ?        00:00:00 mm_percpu_wq
... 

    UID：进程执行者 ID。
    PID：进程 ID。
    PPID：父进程 ID。
    PRI：进程优先级，值越小优先级越高。
    NI：进程的 nice 值。

查看系统中所有的实时进程

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm |awk '$4 !~ /-/{print $0}'

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN          COMMAND
    7     7 FF      99   - 139   0  0.0 FF  S    smpboot_thread migration/0
   10    10 FF      99   - 139   0  0.0 FF  S    smpboot_thread watchdog/0
   11    11 FF      99   - 139   1  0.0 FF  S    smpboot_thread watchdog/1
   12    12 FF      99   - 139   1  0.0 FF  S    smpboot_thread migration/1

查看 nice 不为 0 的普通进程

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm|awk '$4 ~ /-/ &&$5 !~/0/ {print $0}'

   63    63 TS       -   5  14   2  0.0 TS  SN   ksm_scan_threa ksmd
   64    64 TS       -  19   0   2  0.0 TS  SN   khugepaged     khugepaged
12995 12995 TS       -  -4  23   1  0.0 TS  S<sl ep_poll        auditd

查看进程运行状态及其内核函数名称

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:34,nwchan,pcpu,comm

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN                               WCHAN %CPU COMMAND
    1     1 TS       -   0  19   4  0.0 TS  Ssl  ep_poll                            ffffff  0.0 systemd
    2     2 TS       -   0  19   0  0.0 TS  S    kthreadd                            b1066  0.0 kthreadd
    3     3 TS       -   0  19   0  0.0 TS  S    smpboot_thread_fn                   b905d  0.0 ksoftirqd/0
...
   44    44 TS       -   0  19   7  0.0 TS  R    -                                       -  0.0 kworker/7:0

    wchan：显示进程处于休眠状态的内核函数名称，如果进程正在运行则为 -，如果进程具有多线程且 ps 指令未显示，则为 *。
    nwchan：显示进程处于休眠状态的内核函数地址，正在运行的任务将在此列中显示短划线 -。

nice 指令

nice 指令用于修改普通进程的 nice 值。
设定即将启动的普通进程的 nice 值

nice -n -5 service httpd start

修改已经存在的普通进程的 nice 值

$ ps -le | grep nova-compute
4 S  1000  9301     1  2  80   0 - 530107 ep_pol ?       00:02:50 nova-compute

$ renice -10 9301
9301 (process ID) old priority 0, new priority -10

$ ps -le | grep nova-compute
4 S  1000  9301     1  2  70 -10 - 530107 ep_pol ?       00:02:54 nova-compute

chrt 指令

chrt 指令可用于修改进程的调度算法和优先级。

$ chrt --help
Show or change the real-time scheduling attributes of a process.

Set policy:
 chrt [options] <priority> <command> [<arg>...]
 chrt [options] --pid <priority> <pid>

Get policy:
 chrt [options] -p <pid>

Policy options:
 -b, --batch          set policy to SCHED_BATCH
 -d, --deadline       set policy to SCHED_DEADLINE
 -f, --fifo           set policy to SCHED_FIFO
 -i, --idle           set policy to SCHED_IDLE
 -o, --other          set policy to SCHED_OTHER
 -r, --rr             set policy to SCHED_RR (default)

修改进程的调度算法

$ chrt -r 10 bash

$ chrt -p $$
pid 13360's current scheduling policy: SCHED_RR
pid 13360's current scheduling priority: 10

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm |awk '$4 !~ /-/{print $0}'

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN          COMMAND
13360 13360 RR      10   -  50   7  0.0 RR  S    do_wait        bash

修改实时进程的优先级

$ ps -eo pid,tid,class,rtprio,ni,pri,psr,pcpu,policy,stat,wchan:14,comm |awk '$4 !~ /-/{print $0}'

  PID   TID CLS RTPRIO  NI PRI PSR %CPU POL STAT WCHAN          COMMAND
   27    27 FF      99   - 139   4  0.0 FF  S    smpboot_thread migration/4

$ chrt -p 31
pid 31's current scheduling policy: SCHED_FIFO
pid 31's current scheduling priority: 99

$ chrt -f -p 50 31

$ chrt -p 31
pid 31's current scheduling policy: SCHED_FIFO
pid 31's current scheduling priority: 50

core scheduling是v5.14中新增的功能，下图是内核数据结构为该功能所添加的字段。

为什么有core scheduling呢？因为当开启超线程(HyperThreading)时，一个物理核就变成了两个逻辑核，但，这两个逻辑核还是要共享物理核的某些缓存，这种共享会带来安全问题（例如：MDS、L1TF等）。core scheduling就是要解决 开启超线程(HyperThreading)时所带来的安全问题。

假设，在两个逻辑核上同时在运行进程P1和P2，由于两个逻辑核来源于同一个物理核，两个逻辑核会共享某些资源，这样，P1就可能泄露数据给P2（反之亦然）。怎么解决呢？很简单，core scheduling添加了这种功能：cpu调度器确保， 在同一时刻，绝不让 “不互相信任的进程” 运行在同一个物理核上。对于上面的例子：

1. 如果用户指定了P1和P2互相信任，则，cpu调度器允许，在同一时刻，P1和P2可以运行在同一个物理核上。

2. 如果用户不指定P1和P2互相信任，则，cpu调度器绝不会让P1和P2，在同一个时刻，运行在同一个物理核上。
解释几个名称

本文翻译自 Core Scheduling — The Linux Kernel documentation，文档中出现了“core”, “siblings”等，这里的”core”是指物理核， “siblings”是指开启HT时，所产生的逻辑核。

当开启HT时，一个“core”就变成了两个“siblings”，即，一个物理核会变成两个逻辑核，所以才有我们说的“4核8线程”、“8核16线程”。

此外，当说到“thread”时，其实也是指逻辑核。

可以 cat /proc/cpuinfo 来查看cpu信息

1. processor：每一个核（包括物理核以及由于HT而传送的逻辑核）。在kernel看来，无论物理核还是逻辑核，都是同等的核。

2. physical id：物理socket。同一个physical id上可以有多个物理核。

3. siblings：在该物理socket内，核的总个数（包括物理核以及由于HT而产生的逻辑核）。

4. core id：在该物理socket内，某个物理核的编号。跨物理socket时，core id会重复。

5. cpu cores：在当前物理socket内，物理核的个数。

怎么判断是否开启了HT呢，很简单：如果siblings == 2*(cpu cores)，则开启了HT。

还可以 lscpu 来查看

lscpu可以查看：

1. 物理socket 的个数。

2. 每个物理socket上 物理核的个数。

3. 每个物理核内逻辑核的个数。

Thread(s) per core:  1；每个物理核内，线程的个数。线程就是逻辑核。若开启HT，此处为2。我这里显示1，即并未开启HT。

Core(s) per socket:  2；每个物理socket内，物理核的个数。

Socket(s):           4；物理socket的个数。

再总结下

1. 同一个物理核会因为开启HT而变为两个核（即：两个逻辑核）。

2. 同一个物理核产生的两个逻辑核是可以并行执行某些指令的，但，两个逻辑核还会共享物理核的某些资源。

3. 在同一个时刻，当两个逻辑核执行的指令需要共享的资源时，那么，只能一个逻辑核运行，另一个等待。

以下翻译 Core Scheduling — The Linux Kernel documentation

正文开始

core scheduling允许userspace定义一组task，这一组task共享同一个core。用户或因为安全用例而分组（组内task 不信任 组外task），或因为性能用例而分组（有些workloads可能会从“运行在同一个core上”而受益，因为它们不需要被共享core上的同种硬件资源，或者，有些workloads更倾向于“运行在不同core上”，因为它们需要共享所需的硬件资源）。本文档仅描述安全用例。
Security usecase

cross-HT attack包含了attacker和victim，它们运行在同一个core的不同超线程上。MDS(Microarchitectural Data Sampling) 和 L1TF(L1 Terminal Fault)就是此类攻击。cross-HT attack唯一的彻底解决方案就是禁用超线程（Hyper Threading）。

core scheduling是scheduler的一个特性，它可以减缓（并不是根除）cross-HT attack。通过确保“只有位于用户指定信任组内的task才能够共享同一个core”，core scheudling就可以安全的开启HT。这种 core共享 还可以提高性能，尽管很多现实世界的实际workloads都显示core scheduling确实提高了性能，但，并不能100%确保它总是可以提高性能的。理论上，core scheduling的性能表现至少应该和HT被禁用时一样好。在实践中，绝大部情况也确实如此，但，也并非100%，这是因为在同一个core中，跨2个或更多个cpu 同步(synchronizing)调度决策引入了额外的overhead，尤其是当系统负载较轻时（lightly loaded），overhead就更为明显。相比于SMT-disabled（即关闭HT），total_threads <= N_CPUS/2时core scheduling引入的额外overhead会使得core scheduling表现更差，这里N_CPUS是cpu的总个数。所以，决定开启core scheduling前，你应该先测试workloads的表现。

Usage

core scheduling通过内核选项CONFIG_SCHED_CORE来开启或禁用。利用该特性，userspace定义一组task，希望这些task总是在同一core上被调度（同一个物理核，多个逻辑核）。利用这些信息，scheduler在满足系统调度需求的同时，确保，在同一个时刻，组内task 和 组外task 永远不会在同一个core上同时运行。

可以通过PR_SCHED_CORE prctl接口来开启core scheduling。该接口用于创建core scheduling组，以及从组中增删task。

 #include <sys/prctl.h>
 
int prctl(int option, unsigned long arg2, unsigned long arg3,
        unsigned long arg4, unsigned long arg5);
 
option:
 
    PR_SCHED_CORE
arg2:
 
    Command for operation, must be one off:
 
        PR_SCHED_CORE_GET – get core_sched cookie of pid.
 
        PR_SCHED_CORE_CREATE – create a new unique cookie for pid.
 
        PR_SCHED_CORE_SHARE_TO – push core_sched cookie to pid.
 
        PR_SCHED_CORE_SHARE_FROM – pull core_sched cookie from pid.
 
arg3:
 
    pid of the task for which the operation applies.
arg4:
 
    pid_type for which the operation applies. 
    It is one of PR_SCHED_CORE_SCOPE_-prefixed macro constants. 
    For example, if arg4 is PR_SCHED_CORE_SCOPE_THREAD_GROUP, 
    then the operation of this command will be performed
    for all tasks in the task group of pid.
arg5:
 
    userspace pointer to an unsigned long for
    storing the cookie returned by PR_SCHED_CORE_GET command.
    Should be 0 for all other commands.

进程必须得开启”PTRACE_MODE_READ_REALCREDS”的ptrace访问模式，这样，进程 才能够pull a cookie from a process或 push a cookie to a process。

Building hierarchies of tasks

The simplest way to build hierarchies of threads/processes which share a cookie and thus a core is to rely on the fact that the core-sched cookie is inherited across forks/clones and execs, thus setting a cookie for the ‘initial’ script/executable/daemon will place every spawned child in the same core-sched group.【写的什么鬼，看不懂】。

对于初始的’script/executable/daemon’设置cookie值，则由它们fork/clone/exec的子进程也就位于同一个core-sched组里面啦。

Cookie Transferral

可以在当前task和其他task之间传递cookie。使用PR_SCHED_CORE_SHARE_FROM 或 PR_SCHED_CORE_SHARE_TO 从一个特定的task继承cookie，或者向某个task共享cookie。结合起来，这允许一个简单的程序从位于core-sched的一个task中拖取cookie，然后将该cookie共享给已在运行的task。

Design/Implementation

每个被标记的task都在内核内部分配了一个 cookie。 如Usage中所述，具有相同 cookie 值的task相互信任，并共享同一个core。

基本思想是，每个调度事件都尝试为 core的所有siblings 选择task，以便，在任何时间点，所有选定的运行在同一个core上的task都是可信任的（即：具有相同的 cookie）。 kernel thread被认为总是可信任的。idle task也被认为是特殊的，因为它信任一切，一切也都信任它。

在任何一个core的siblings的调度事件期间，该siblings上的最高优先级的task被挑选出来并分配给调用 schedule()的siblings，如果该siblings有task入队。【写是什么鬼，看不懂。During a schedule() event on any sibling of a core, the highest priority task on the sibling’s core is picked and assigned to the sibling calling schedule(), if the sibling has the task enqueued. 】。对于core的其余siblings，如果siblings在它们自己的rq中有一个可运行的task，则选择具有相同 cookie 的最高优先级的task。如果具有相同 cookie 的task不可用，则选择idle task。 idle task是全局都被信任的。

一旦为core的所有siblings选择了一个task，就会给 选择了新task 的siblings 发送 IPI 。 收到 IPI 的siblings将立即切换到新task。 如果为siblings选择了idle task，则认为该siblings处于force idle状态。force idle的意思是，它的rq上可能有task要运行，但它仍然必须得执行idle task。下一节将详细介绍这一点。

Forced-idling of hyperthreads

scheduler尽其所能的找到彼此信任的task，从而，被选中调度所有task都是core内优先级最高的task。但，某些rq所持有tasks 与 core上最高优先级tasks并不兼容。相比于fairness，优选security，如果siblings的最高优先级的task 和 core范围内（一个core会有多个siblings）最高优先级task无法彼此信任，则，1或多个siblings可能会被强制选择一个低优先级的task。如果某个siblings不存在任何一个可信任的task，则，该siblings就被强制idle。

当选中的最高优先级的task运行时，reschedule-IPI事件会被发送到siblings，强制siblings进入idle。根据VM或普通usermode进程是否运行在HT，这会产生4种情况。

       HT1 (attack)            HT2 (victim)
A      idle -> user space      user space -> idle
B      idle -> user space      guest -> idle
C      idle -> guest           user space -> idle
D      idle -> guest           guest -> idle 

注意，为了更好的性能，我们并不会等待destination cpu(victim)进入idle模式。这是因为发送IPI会使得destination cpu立即从userspace进入kernel模式，或者，如果是guests虚拟机则立即进入VMEXIT。最多，这只会泄露一些无关紧要的调度元信息。还有可能，在某些架构上，IPI收到的可能会非常晚，不过，在x86上，这种情况尚未被观测到。

Trust model

通过给组内的task分配一个标记，即值相同的cookie值，core scheduling在组内的task间维护了信任关系。当启用core scheduling的系统启动时，所有task都被认为是信任彼此的。这是因为core scheduling并没有关于信任关系的任何信息，直到userspace使用上述的接口，kernel才用于组的信任关系。换句话说，所有task都有默认cookie值0，因此所有任务都是彼此信任的。需要避免forced-idling的siblings运行cookie值为0的task。

一旦userspace使用上述接口将task放入某个组，位于同一个组的task就信任彼此，这些task不再信任组外task，组外task也不会再信任它们。

Limitations of core-scheduling

core scheduling尝试确保只有被信任的task才可以同时运行在同一个core上。但，会有一个小的时间窗口，在此期间，不被信任的task也会同时运行在同一个core上，或，kernel和另外一个不被kernel所信任的task同时运行在同一个core上。

IPI processing delays

core scheduling只选择信任的task，让它们在同一个core上同时运行。IPI用于通知siblings要切换到新task上。但，在某些架构上，收取IPI可能存在硬件延迟，在x86上，这尚未被观察到。假设，cpu 1发送IPI，cpu 2是cpu 1的siblings，cpu 1发送了IPI，然后cpu 1上的attacker task开始运行了，但，cpu 2收到IPI太晚了，这就造成了，cpu 1和cpu 2上同时运行的并不是彼此信任的task。尽管，在进入user mode时，cache会被flush，在attacker开始运行之后，siblings上的victim task可能会在cache 和 micro architectural buffers中放置数据（于是attacker就可以访问到），这可能导致数据泄露。

Open cross-HT issues that core scheduling does not solve

1. For MDS

针对 “siblings同时运行user mode代码 和 kernel mode代码” 的攻击，core scheduling无法防护。即使所有的siblings运行的都是彼此信任的task，当kernel代表某个task执行代码时，kernel无法信任运行在siblings上的代码。对于任何siblings cpu组合模式（host模式 或guest模式），这种攻击是可能的。

2. For L1TF

针对 “L1TF guest attackter利用guest或host victim” 的攻击，core scheduling无法防护。这是因为guest attacker 可以构建无效的PTE，由于guest kernel的脆弱性 这种无效的PTE不能被反转。唯一的解决方式就是禁用EPT(Extended Page Tables)。

对于MDS和L1TF，如果guest vCPU被配置为不信任彼此（通过分开打tag的方式），那么，guest到guest的攻击就不存在啦。或者，设置系统管理策略 将guest to guest攻击当做是guest自己的问题。

另外一种解决方式是，让系统中的每一个 不被信任的task 不信任 任何其他 不被信任的task。当然，这会降低 不被信任task 的并行度，不过，这确实 在允许被信任task的进程共享同一个core的同时，解决上述问题。

3. Protecting the kernel (IRQ, syscall, VMEXIT)

不幸的是，core scheduling并不能保护 运行在siblings超线程上的kernel context免受 运行在其他siblings上的kernel context的打扰。解决方式的原型代码已被发布到LKML，以期解决该问题，但，这种窗口能否被实际利用，其所引入的性能overhead是否值的（更不用说，这增加了代码复杂度），依然值得商榷。

Other Use cases

core scheduling的主要用例是在SMT开启的前提下，减轻cross-HT的脆弱性。但，core scheduling还可以用在下面地方

1. 隔离 需要整个core的 task。这方面的例子包括realtime task，使用SIMD指令的task等。

2. 团伙scheduling（gang scheduling），一组task需要一起调度，这种需求也可以使用core scheduling。VM的vCPU就是该方面的一个例子。

进程：进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位，实现操作系统的并发。

线程：线程是进程的子任务，是CPU调度和分配的基本单位。

    一个程序至少拥有一个进程，一个进程至少拥有一个线程，线程依赖于进程而存在。进程执行时拥有独立的内存单元，而多个线程共享进程的内存。

2.进程间的通信方式

管道及命名管道：管道可用于具有父子亲缘关系的进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系的进程间的通信。

信号：信号是一种比较复杂的通信方式，用于接收进程某个事件已发生。

消息队列：消息队列是消息的链接表，它克服了，以上两种通信方式中信号量有限的缺点，具有写权限的进程可以按照一定的规则向消息队列中添加新信息，具有读权限的进程可以从消息队列中读取信息。

共享内存：可以说是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程对共享内存中数据的更新。这种方式依赖于某种同步操作，如互斥锁和信号量等。

信号量：主要作为进程之间及同一进程的不同线程之间的同步和互斥手段。

套接字：这是一种更为一般的进程间通信机制，他可以用于网络中不同机器之间的进程间的通信，应用非常广泛。
3.线程的同步方式

互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以可以保证公共资源不会同时被多个线程访问。

信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。

事件（信号）：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。
4.死锁，死锁产生条件

死锁：在两个或多个并发进程中，如果每个进程持有某种资源而等待其他进程释放它或者它们保持的资源，再改变这种状态之前，都不能向前推进，称这一组进程产生了死锁。（由于不合理的推进顺序或者资源分配导致产生了环路等待）

死锁产生的四个必要条件：

    互斥：至少一个资源处于非共享模式，即一次只能被一个进程使用；若其他进程申请使用该资源，则必须等到该资源被释放为止。

    占有并等待：一个进程必须占有至少一个资源，并等待另一个资源，而该资源为其他进程所占有

    非抢占：进程不能被强占，即资源只能被进程在完成任务后自愿释放。

    循环等待：若干进程之间形成一种头尾相接的环形等待资源关系。

5.死锁处理的基本策略和常用方法：

    预防死锁，避免死锁，检测死锁，解除死锁，鸵鸟算法（把头埋进沙子里，当做啥也没发生）

6.死锁预防的基本思想：

    只要确保死锁发生的四个必要条件中至少一个不成立，就能预防死锁的发生。

具体方法：

    打破互斥条件：允许进程同时访问某些资源。但是，有些进程不能被同时访问是由资源的属性决定的，因此这种方法并无实用价值。
    打破占有并等待条件：可以实行资源的预先分配策略（进程在运行前一次性向系统申请它所需要的所有资源，若所需全部资源得不到满足，则不分配任何资源，此进程暂不运行；只有当系统满足当前进程所有资源时，才一次性的将全部资源分配给该进程）或者只允许在没有占有资源时才可以申请资源（一个进程可以申请资源并使用他们，但是当前进程申请更多资源前，必须释放所占有资源）。这种策略存在一些缺点，在很多情况下，无法预知一个进程执行前所需的全部资源，因为进程是动态执行的，不可预知的；同时，会降低资源利用率，导致降低进程的并发性。
    打破非抢占条件：允许进程强行从占有者那里夺取某些资源。当一个进程占有了一部分资源，在其中请求新的资源且得不到满足，它必须释放所有的资源以使其他线程使用，这种预防死锁的方式实现起来困难会降低系统性能。
    打破循环等待条件：实行资源有序分配策略。对所有资源排序编号，所有进程对资源的请求必须严格按照资源序号递增的顺序提出，即只占用了小号资源才能申请大号资源，这样就不会产生环路，预防死锁发生。

7.死锁避免的基本思想

死锁避免的基本思想是动态的检测资源分配状态，以确保循环等待条件不成立，从而确保系统处于安全状态。所谓的安全状态指：如果系统能按照某个顺序为每个进程分配资源，那么系统状态是安全的，换句话说就是，如果存在一个安全序列，那么系统处于安全状态。资源分配图算法和银行家算法是两种经典的死锁避免算法，其可以确保，系统始终处于安全状态。其中资源分配图算法应用场景为每种资源类型只有一个实例（申请边，分配边，需求边，不形成环再允许分配）而银行家算法应用于每种资源类型可以有多个实例的场景。
8.死锁解除的常用方法

进程终止和资源抢占：

    所谓进程终止是指简单地终止一个或多个进程以打破循环等待，包括两种方式：终止死锁进程和一次只终止一个进程直到取消死锁循环为止。

    所谓资源抢占是指从一个或多个死锁进程那里抢占一个或多个资源，此时需要考虑三个问题：

        选择一个牺牲品
        回滚，回滚到安全状态
        饥饿，在代价因素中加上回滚次数，回滚的越多则越不可能继续被作为牺牲品。避免一个进程被一直回滚。

9.进程有几种状态

    就绪状态：进程已获得除处理机外的所需资源，等待分配处理及资源
    运行状态：占用处理机资源运行，处于此状态的进程数小于等于CPU数
    阻塞状态：进程等待某种条件，条件满足前无法执行

10.线程有哪几种状态

    就绪：线程准备运行，不一定立马就能开始执行
    运行中：进程正在执行线程代码
    等待中：线程处于阻塞状态，等待外部的处理结束
    睡眠中：线程被强制睡眠
    I/O阻塞：等待I/O操作完成
    同步阻塞：等待获取锁
    死亡：线程完成了执行

11.分页和分段有什么区别（内存管理）

    段式分配管理是一种符合用户视角的内存分配管理方案，在段式存储管理中，将程序的地址空间划分为若干段，堆栈段；这样每个进程有一个二维地址空间，相互独立，互不干扰。段式管理的优点是：没有内碎片（因为段大小可变，改变段大小来消除内碎片）。但段换入换出时，会产生外部碎片（比如4K的段换5K的段，会产生1K的外碎片）

    页式存储管理方案是一种用户视角内存与物理内存相分离的内存分配管理方案。在页式存储管理中，将程序的逻辑地址分为固定大小的页，而物理内存划分为同样大小的帧，程序加载时，可以将任意一页放入内存中任意一个帧，这些帧不必连续，从而实现离散分离。页式存储管理的优点是：没有外部碎片（因为页大小固定），单会产生内碎片（一个页可能填充不满）

两者不同点：

    目的不同：分页是由于系统管理的需要而不是用户的需要，他是信息的物理单位；分段的目的是为了更好地满足用户的需要，它是信息的逻辑单位，它含有一组其意义相对完整的信息
    大小不同：页的大小固定且有系统决定，而段的长度大小却不固定，由其所完成的功能决定
    地址空间不同：段向用户提供二维地址空间，页向用户提供的是一维地址空间
    信息共享：段是信息的逻辑单位，便于存储保护和信息的共享，页的保护、共享受到限制
    内存碎片：页式存储管理的优点是没有外碎片，单会产生内碎片，段式管理的优点是没有内碎片，但段的换入换出时会产生外部碎片

12.操作系统进程调度策略

    FCFS（先来先服务，队列实现，非抢占）：先请求CPU的进程先分配到CPU
    SJF（最短作业优先调度算法）：平均等待时间最短，但难以知道下一个CPU区间长度
    优先级调度算法（可以是抢占的也可以是非抢占的）：优先级越高的越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞式饥饿，解决方案：老化（随着时间推移，那些越老的进程优先级越高）
    时间片轮转调度算法（可抢占）：队列中没有进程被分配超过一个时间片的CPU时间，除非他是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么进程就被抢占并放回就绪队列
    多级队列调度算法：将就绪队列分成多个独立的队列，每个队列都有自己独立的调度算法，队列之间采用固定优先级抢占调度，其中，一个进程根据自身属性被永久地分配到一个队列中。
    多级反馈队列调度算法：与多级队列调度算法相比，其允许进程在多列之间移动，若进程使用过多CPU时间，那么他会被转移到更低的优先级队列，在较低的优先级队列等待时间过长的进程会被转移到更高优先级的队列，以防饥饿发生。

13.进程同步的机制有哪些

    原子操作，信号量机制，自旋锁管理，会合、分布式管理（?）

14.虚拟内存是什么

    内存的发展历程：没有内存抽象->有内存抽象->连续内存分配->不连续内存分配

    虚拟内存允许执行进程不完全在内存中。虚拟内存的基本思想是：每个进程拥有独立的地址空间，这个空间被分为相等大小的多个块，称为页，每个页都是一段连续的地址。这些页被映射到物理内存，但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时，由硬件立即进行必要的映射；当程序引用到一部分不在物理内存中的地址空间时，有操作系统负责将缺失的部分装入物理内存并重新执行失败的命令。这样，对于进程而言，逻辑上似乎拥有很大的内存空间，实际其中一部分对应物理内存上的一块（称为帧，通常也和帧大小相等），还有一些没加载在内存中的对应在硬盘上，注意：请求分页系统，请求分段系统和请求段页式系统都是针对虚拟内存的，通常请求实现内存和外村的信息置换，虚拟内存实际上可以比物理内存大。当访问虚拟内存时，会访问内存管理单元去匹配对应的物理地址，如果虚拟内存的页并不存在于物理内存中会产生缺页中断，从磁盘取得缺的页放入内存，如果内存已满，会根据某种算法将磁盘中的页换出。

15.页面置换算法有哪些

    FIFO先进先出算法：比如作业调度（实现简单）
    LRU最近最少用算法根据使用时间到现在的长短来判断
    OPT最优置换算法：理论最优，保证置换出去的页是不再被使用的页（或最长时间里不被使用的页）
    LFU最少使用次数算法：根据使用次数判断

16. 虚拟内存的应用与优点有哪些

    虚拟内存很适合在多道程序设计系统中使用，许多程序的片段同时保存在内存中。当一个程序等待它的一部分读入内存时，可以吧CPU交给另一个进程使用。

    在内存中可以保留多个进程，系统并发性提高
    接触了用户与内存间的紧密约束，进程可以比内存的全部空间还大

17.颠簸是什么（抖动）

颠簸本质上是指频繁的页调度行为，具体来讲，进程发生缺页中断，这时必须置换某一个页。然而，其他所有页都在使用，它置换一个页，但又立刻再次需要这个页。因此会不断地产生缺页中断，导致整个系统效率急剧下降，这种现象称为颠簸。
18.如何解决内存颠簸

    如果是因为页面置换策略失误，可以修改算法来解决这个问题
    如果是因为运行的程序太多，造成程序无法同时将所有频繁访问的页面调入内存，则要降低多道程序的数量
    否则，终止该进程或增加物理内存的容量

19.局部性原理是什么

    时间上的局限性：最近被访问的页在不久的将来还会被访问
    空间上的局限性：内存中被访问的页周围的页很可能被访问