type
status
date
slug
summary
tags
category
icon
password

进程

进程是什么

通俗易懂的解释，进程就是一个正在运行的程序。
程序的运行往往需要依赖一定的系统资源，例如CPU、内存等，所以进程是资源分配的基本单位。
为了表示进程占用的资源和状态信息，操作系统用进程控制块(process control block，PCB)数据结构来描述进程。在 linux 下 PCB 为 task_struct。
PCB 是进程存在的唯一标识。这意味着一个进程的存在，必然会有一个 PCB，如果进程消失了，那么 PCB 也会随之消失。
PCB 包含的内容有：
  • 进程标识符：标识各个进程，每个进程都有一个并且唯一的标识符。
  • 用户标识符：进程归属的用户，用户标识符主要为共享和保护服务。
  • 进程当前状态：如 new、ready、running、waiting 或 blocked 等。
  • 进程优先级：进程抢占 CPU 时的优先级。
  • PC计数器：程序中即将被执行的下一条指令的地址
  • 上下文数据：进程执行时处理器的寄存器中的数据
  • 内存指针：包括程序代码和进程相关数据的指针，还有和其他进程共享的内存块的指针。
  • 文件I/O信息：所打开文件的列表和所使用的 I/O 设备信息。

进程的状态

虽然进程被描述为一个正在运行的程序，但事实上进程从产生到消亡并不是一直都处于运行状态。进程可能会因为某种原因而暂停运行处于等待状态，当使它暂停的原因消失后，它又进入准备运行状态。
一个完整的进程活动周期可能会存在五种状态：
notion image
  • 创建状态(new)：进程正在被创建时的状态。
  • 运行状态(Runing)：该时刻进程占用 CPU。
  • 就绪状态(Ready)：可运行，由于其他进程处于运行状态而暂时停止运行。
  • 阻塞状态(Blocked)：该进程正在等待某一事件发生(如等待输入/输出操作的完成)而暂时停止运行，这时，即使给它CPU控制权，它也无法运行。
  • 结束状态(Exit)：进程正在从系统中消失时的状态。
如果有大量处于阻塞状态的进程，进程可能会占用着物理内存空间。在虚拟内存管理的操作系统中，通常会把阻塞状态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从硬盘换入到物理内存。就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。
  • 阻塞挂起状态：进程在外存(硬盘)并等待某个事件的出现。
  • 就绪挂起状态：进程在外存(硬盘)，但只要进入内存，即刻立刻运行。
      • notion image
导致进程挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：
  • 通过 sleep 让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
  • 用户希望挂起一个程序的执行，比如在 Linux 中用 Ctrl+Z 挂起进程;
PCB 通过链表的方式进行组织，把具有相同状态的进程链在一起，组成各种队列。
  • 就绪队列：将所有处于就绪状态的进程链在一起。
  • 阻塞队列：把所有因等待某事件而处于等待状态的进程链在一起。
  • 运行队列：将所有处于进行状态的进程链在一起。在单核 CPU 系统中则只有一个运行指针了，因为单核 CPU 在某个时间，只能运行一个程序。
在 linux 下进程也被称为 task，进程 PCB 也被称为 task_struct。linux 下的进程分为七种状态：
  • 执行状态：
    • R (TASK_RUNNING)：可执行状态。只有在该状态的进程才可能在CPU上运行。linux下把正在CPU上执行的进程和可执行但是尚未被CPU调度的进程状态统一为TASK_RUNNING状态，所以同一时刻可能有多个进程处于TASK_RUNNING状态，但只有一个进程在占用CPU。
  • 睡眠状态：
    • S (TASK_INTERRUPTIBLE)：可中断的睡眠状态。处于这个状态的进程因为等待某某事件的发生（比如等待socket连接、等待信号量），进程列表中的绝大多数进程都处于TASK_INTERRUPTIBLE状态。
    • D (TASK_UNINTERRUPTIBLE)：不可中断的睡眠状态。不可中断指的是进程不响应异步信号，例如用 kill -9 无法杀死一个TASK_UNINTERRUPTIBLE状态的进程。一般用于内核某些某些处理流程是不能被打断的线程，例如读写设备文件。
  • 停止状态：
    • T (TASK_STOPPED)：暂停状态。向进程发送一个SIGSTOP信号，它就会因响应该信号而进入TASK_STOPPED状态；向进程发送一个SIGCONT信号，可以让其从TASK_STOPPED状态恢复到TASK_RUNNING状态。
    • T (TASK_TRACED)：跟踪状态。类似于TASK_STOPPED状态，但是不能被SIGCONT信号唤醒。
  • 退出状态：
    • X (EXIT_DEAD)：退出状态，进程即将被销毁。被标记为的EXIT_DEAD状态的进程会立即被彻底释放。
    • Z (EXIT_ZOMBIE)，退出状态，进程成为僵尸进程。进程占有的除了task_struct结构的其他资源将被回收，只剩下task_struct一个空壳。
linux 下进程状态的变迁却只有两个方向：从TASK_RUNNING状态变为非TASK_RUNNING状态、或者从非TASK_RUNNING状态变为TASK_RUNNING状态。
  • 进程从非TASK_RUNNING状态变为TASK_RUNNING状态，是由别的进程（也可能是中断处理程序）执行唤醒操作来实现的。
  • 进程从TASK_RUNNING状态变为非TASK_RUNNING状态，则有以下途径：
    • 响应信号而进入TASK_STOPED状态、或TASK_DEAD状态；
    • 执行系统调用主动进入TASK_INTERRUPTIBLE状态（如nanosleep系统调用）、或TASK_DEAD状态（如exit系统调用）
    • 由于执行系统调用需要的资源得不到满足，而进入TASK_INTERRUPTIBLE状态或TASK_UNINTERRUPTIBLE状态（如select系统调用）

进程间通信

既然进程是资源分配的基本单位，如果一个进程要访问另外一个进程的资源，就需要用到进程间通信的方式。常见的进程通信方式有：
  • 管道
  • 消息队列
  • 共享内存
  • 信号量
  • 信号
  • Socket

管道

管道创造一个管道文件，两个不同文件通过管道文件实现数据单向传输。管道又分为命名管道和匿名管道两种，匿名管道只能用于父子进程间通信；命名管道通过 mkfifo 命令创建，可以实现两个不相关的进程间的通信。
notion image
使用 fork 创建子进程，创建的子进程会复制父进程的文件描述符，这样就做到了两个进程各有 两个「 fd[0] 与 fd[1] 」，两个进程就可以通过各自的 fd 写入和读取同一个管道文件实现跨进程通信了。同时：
  • 父进程关闭读取的 fd[0]，只保留写入的 fd[1]
  • 子进程关闭写入的 fd[1]，只保留读取的 fd[0]
在 shell 里面执行 A | B 命令的时候，A 进程和 B 进程都是 shell 创建出来的子进程，A 和 B 之间不存在 父子关系，它俩的父进程都是 shell。
notion image
  • shell把读写管道端都关闭
  • 一个子进程关闭读端管道，一个子进程关闭写端管道
进程写入的管道数据都是缓存在内核中。管道这种通信方式效率低，不适合进程间频繁地交换数据。

消息队列

消息队列用于解决管道效率低下的问题。消息队列是保存在内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也就是消息体(数据块)，消息体是用户自定义的数据类型，消息的发送方和接收方要约定好消息体的数据类型， 所以每个消息体都是固定大小的存储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消息体，内核就会把这个消息体删除。
消息队列生命周期随内核，如果没有释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销毁。
消息队列的缺点：
  • 对消息件也有大小限制，不适合比较大数据的传输。
  • 存在用户态与内核态之间的数据拷⻉开销，因为进程写入数据到内核中的消息队列时，会发生从用户态拷⻉数据到内核态的过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷⻉数据到用户态的过程。

共享内存

共享内存用于解决消息队列需要在用户态和内核态来回拷贝数据的问题。共享内存就是两个不同的进程分别拿出一块虚拟地址空间（可以完全不同），映射到相同的物理内存中。
notion image

信号量

使用共享内存的通信方式，如果两个进程同时修改同一块共享内存，很有可能造成冲突。为了防止多进程竞争共享资源，而造成的数据错乱，就出现了信号量保护机制。信号量主要用于实现进程间的互斥与同步，而不是用于缓存进程间通信的数据。
信号量是一个计数器，表示资源的数量，控制信号量的方式有两种原子操作：
  • P 操作：这个操作会把信号量减去 1，相减后如果信号量 < 0，则表明资源已被占用，进程需 阻塞等待；相减后如果信号量 >= 0，则表明还有资源可使用，进程可正常继续执行。
  • V 操作：这个操作会把信号量加上 1，相加后如果信号量 <= 0，则表明当前有阻塞中的进 程，于是会将该进程唤醒运行；相加后如果信号量 > 0，则表明当前没有阻塞中的进程。
P 操作是用在进入共享资源之前，V 操作是用在离开共享资源之后，这两个操作是必须成对出现的。
两个进程互斥访问共享内存，我们可以初始化信号量为 1 。
notion image
具体的过程如下:
  • 进程 A 在访问共享内存前，先执行了 P 操作，由于信号量的初始值为 1，故在进程 A 执行 P 操作后 信号量变为 0，表示共享资源可用，于是进程 A 就可以访问共享内存。
  • 若此时，进程 B 也想访问共享内存，执行了 P 操作，结果信号量变为了 -1，这就意味着临界资源已 被占用，因此进程 B 被阻塞。
  • 直到进程 A 访问完共享内存，才会执行 V 操作，使得信号量恢复为 0，接着就会唤醒阻塞中的线程 B，使得进程 B 可以访问共享内存，最后完成共享内存的访问后，执行 V 操作，使信号量恢复到初始 值 1。

信号

信号用于通知接收进程某个事件已经发生。当信号发送到某个进程中时，操作系统会中断该进程的正常流程，并进入相应的信号处理函数执行操作，完成后再回到中断的地方继续执行。
信号只是用于通知进程发生了某个事件，除了信号本身的信息之外，并不具备传递用户数据的功能。
在 Linux 操作系统中， 为了响应各种各样的事件，提供了几十种信号，分别代表不同的意义。我们可以通过 kill -l 来查看所有的信号。注意信号编号是从 1 开始的。
常见的信号有：
信号
编号
解释
说明
SIGHUP
1
挂起
终端连接断开导致进程结束
SIGINT
2
程序终止(interrupt)
用户输入INTR字符(Ctrl+C)触发
SIGQUIT
3
程序退出
用户输入QUIT字符(Ctrl+/)触发，退出时会产生core文件
SIGILL
4
非法指令
通常是因为可执行文件本身出现错误，或者试图执行数据段，或者堆栈溢出
SIGKILL
9
杀死程序
立即结束程序的运行，该信号不能被处理和忽略
SIGALRM
14
定时器到期
由alarm发出的信号
SIGTERM
15
程序结束(terminate)
程序自己正常退出，该信号可以被处理和忽略
SIGSTOP
19
程序暂停(stopped)
暂停程序的运行，但程序还没结束，该信号不可以被处理和忽略
SIGTSTP
20
程序停止(tty stopped)
用户输入SUSP字符(Ctrl+Z)触发，类似于SIGSTOP，该信号可以被处理和忽略
注意：
  • 无法被捕捉和忽略的信号：SIGKILL，SEGSTOP
  • 不能恢复至默认动作的信号有：SIGILL，SIGTRAP
  • 默认会导致进程停止的信号有SIGSTOP，SIGTSTP，SIGTTIN，SIGTTOU。
信号是进程间通信机制中唯一的异步通信机制，因此可以在任何时候发送信号给某一进程。一旦有信号产生，我们就有下面这几种用户进程对信号的处理方式：
  1. 执行默认操作。Linux 对每种信号都规定了默认操作，例如，上面列表中的 SIGTERM 信号，就是终止进程的意思。
  1. 捕捉信号。我们可以为信号定义一个信号处理函数。当信号发生时，我们就执行相应的信号处理函数。
  1. 忽略信号。当我们不希望处理某些信号的时候，就可以忽略该信号，不做任何处理。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和 SEGSTOP ，它们用于在任何时候中断或结束某一进程。

socket

前面提到的管道、消息队列、共享内存、信号量和信号都是在同一台主机上进行进程间通信。Socket通信不仅可以实现同主机上进程间通信，还可以实现跨网络不同主机上的进程之间通信。
socket 的系统调用为：
  • domain 参数用来指定协议族，比如 AF_INET 用于 IPV4、AF_INET6 用于 IPV6、 AF_LOCAL/AF_UNIX 用于本机;
  • type 参数用来指定通信特性，比如 SOCK_STREAM 表示的是字节流，对应 TCP、SOCK_DGRAM 表示的是数据报，对应 UDP、SOCK_RAW 表示的是原始套接字;
  • protocal 参数原本是用来指定通信协议的，但现在基本废弃。因为协议已经通过前面两个参数指定完 成，protocol 目前一般写成 0 即可;
根据创建 socket 类型的不同，通信的方式也就不同:
  • 实现 TCP 字节流通信: socket 类型是 AF_INET 和 SOCK_STREAM;
  • 实现 UDP 数据报通信:socket 类型是 AF_INET 和 SOCK_DGRAM;
  • 实现本地进程间通信: 「本地字节流 socket 」类型是 AF_LOCAL 和 SOCK_STREAM，「本地数据 报 socket 」类型是 AF_LOCAL 和 SOCK_DGRAM。另外，AF_UNIX 和 AF_LOCAL 是等价的，所以 AF_UNIX 也属于本地 socket;
针对 tcp 协议的 socket 通信模型：
notion image
针对 udp 协议的 socket 通信模型：
notion image

线程

线程是什么

线程是进程当中的一条执行流程。同一个进程内多个线程之间可以共享代码段、数据段、打开的文件等资源，但每个线程各自都有一套独立的寄存器和栈，这样可以确保线程的控制流是相对独立的。进程是资源分配的基本单位，线程是cpu调度的基本单位。
notion image

进程和线程比较

  • 进程是资源分配的单位，线程是 CPU 调度的单位。
  • 进程有单独的内存空间，线程共享所属进程的内存空间，只有单独的程序计数器（pc）和堆栈。
  • 进程切换需要切换⻚表，开销大，速度慢；线程切换不需要切换页表，开销小，速度快。
  • 进程间的通信需要借助工具（管道、消息队列等）实现，同一进程下的线程通信因为共享内存空间可以直接通信。

线程的实现

线程的实现也有一个线程控制块(Thread Control Block, TCB)，主要有三种线程的实现方式：
  • 用户线程(User Thread)：在用户空间实现的线程，不是由内核管理的线程，是由用户态的线程库 来完成线程的管理。
  • 内核线程(Kernel Thread)：在内核中实现的线程，是由内核管理的线程。
  • 轻量级进程(LightWeight Process)：在内核中来支持用户线程。

用户线程

用户线程是基于用户态的线程管理库来实现的，那么TCB也是在 库里面来实现的，对于操作系统而言是看不到这个 TCB 的，它只能看到整个进程的 PCB。
所以，用户线程的整个线程管理和调度，操作系统是不直接参与的，而是由用户级线程库函数来完成线程 的管理，包括线程的创建、终止、同步和调度等。
用户线程的优点：
  • 每个进程都需要有它私有的线程控制块(TCB)列表，用来跟踪记录它各个线程状态信息(PC、栈指针、寄存器)，TCB 由用户级线程库函数来维护，可用于不支持线程技术的操作系统。
  • 用户线程的切换也是由线程库函数来完成的，无需用户态与内核态的切换，所以速度特别快。
用户线程的缺点：
  • 由于操作系统不参与线程的调度，如果一个线程发起了系统调用而阻塞，那进程所包含的用户线程都不能执行了。
  • 当一个线程开始运行后，除非它主动地交出 CPU 的使用权，否则它所在的进程当中的其他线程无法 运行，因为用户态的线程没法打断当前运行中的线程，它没有这个特权，只有操作系统才有，但是用 户线程不是由操作系统管理的。
  • 由于时间片分配给进程，故与其他进程比，在多线程执行时，每个线程得到的时间片较少，执行会比较慢。

内核线程

内核态线程由内核管理的，TCB 放在内核态，这样线程的创建、终止和管理都是由内核负责。
内核线程的优点：
  • 在一个进程当中，如果某个内核线程发起系统调用而被阻塞，并不会影响其他内核线程的运行;
  • 分配给线程，多线程的进程获得更多的 CPU 运行时间。
内核线程的缺点：
  • 在支持内核线程的操作系统中，由内核来维护进程和线程的上下文信息，如 PCB 和 TCB。
  • 线程的创建、终止和切换都是通过系统调用的方式来进行，因此对于系统来说，系统开销比较大。

轻量级进程

轻量级进程(Light-weight process，LWP)是内核支持的用户线程，一个进程可有一个或多个 LWP，每个 LWP 是跟内核线程一对一映射的，也就是 LWP 都是由一个内核线程支持。
另外，LWP 只能由内核管理并像普通进程一样被调度，Linux 内核是支持 LWP 的典型例子。
在大多数系统中，LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息。一般来说，一个进程代表程序的一个实例，而 LWP 代表程序的执行线程，因为一个执行线程不像进程那样需要那么多状态信息，所以 LWP 也不带有这样的信息。

linux下的线程实现

注意，并不是所有的操作系统都支持线程。windows原生支持了线程的实现，Linux没有原生语义的线程支持，所以在linux平台的线程都是使用轻量级进程来实现线程，一个线程就是一个轻量级进程。每一个执行实体都是一个task_struct结构, 通常称之为进程。
Linux2.0~2.4实现的是俗称LinuxThreads的多线程方式，到了2.6，基本上都是NPTL的方式了，目前最新实现算法是NGPT。
LinuxThreads专门为每一个进程构造了一个管理线程，负责处理线程相关的管理工作。当进程第一次调用pthread_create()创建一个线程的时候就会创建并启动管理线程。然后管理线程再来创建用户请求的线程。也就是说，用户在调用pthread_create后，先是创建了管理线程，再由管理线程创建了用户的线程。
NPTL中，内核有了线程组的概念, task_struct结构中增加了一个tgid(thread group id)字段.如果这个task是一个”主线程”, 则它的tgid等于pid, 否则tgid等于进程的pid(即主线程的pid)。
linux的和进程/线程相关的各种ID：
  • pid: 进程ID。
  • lwp: 线程ID。在用户态的命令(比如ps)中常用的显示方式。
  • tid: 线程ID，等于lwp。tid在系统提供的接口函数中更常用，比如syscall(SYS_gettid)和syscall(__NR_gettid)。
  • tgid: 线程组ID，也就是线程组leader的进程ID，等于pid。
  • ——分割线——
  • pgid: 进程组ID，也就是进程组leader的进程ID。
  • pthread id: pthread库提供的ID，生效范围不在系统级别，可以忽略。
  • sid: session ID for the session leader。
  • tpgid: tty process group ID for the process group leader。
从上面的列表看出，各种ID最后都归结到pid和lwp(tid)上。所以理解各种ID，最终归结为理解pid和lwp(tid)的联系和区别。
notion image
上图很好地描述了用户视角(user view)和内核视角(kernel view)看到线程的差别：
  • 从用户视角出发，在pid 42中产生的tid 44线程，属于tgid(线程组leader的进程ID) 42。甚至用ps和top的默认参数，你都无法看到tid 44线程。
  • 从内核视角出发，tid 42和tid 44是独立的调度单元，可以把他们视为”pid 42”和”pid 44”。
需要指出的是，有时候在Linux中进程和线程的区分也是不是十分严格的。即使线程和进程混用，pid和tid混用，根据上下文，还是可以清楚地区分对方想要表达的意思。上图中，从内核视角出发看到了pid 44，是从调度单元的角度出发，但是在top或ps命令中，你是绝对找不到一个pid为44的进程的，只能看到一个lwp(tid)为44的线程。

上下文切换

CPU上下文切换

CPU 上下文切换是指先把前一个任务的 CPU 上下文（也就是 CPU 寄存器和程序计数器）保存起来，然后加载新任务的上下文到这些寄存器和程序计数器，最后再跳转到程序计数器所指的新位置，运行新任务。而这些保存下来的上下文，会存储在系统内核中，并在任务重新调度执行时再次加载进来。这样就能保证任务原来的状态不受影响，让任务看起来还是连续运行。
CPU 上下文切换的种类有：
  • 系统调用（进程内部线程切换）
  • 进程上下文切换
  • 线程上下文切换
  • 中断上下文切换

系统调用

系统调用完成从用户态到内核态的互相转化。比如，当我们查看文件内容时，就需要多次系统调用来完成：首先调用 open() 打开文件，然后调用 read() 读取文件内容，并调用 write() 将内容写到标准输出，最后再调用 close() 关闭文件。系统调用的过程：
  1. 保存 CPU 寄存器里原来用户态的指令位，CPU 寄存器更新为内核态指令的新位置。
  1. 跳转到内核态运行内核任务。
  1. 当系统调用结束后，CPU 寄存器恢复原来保存的用户态，然后再切换到用户空间，继续运行进程。
一次系统调用的过程，其实是发生了两次 CPU 上下文切换。（用户态-内核态-用户态）。系统调用过程中，并不会涉及到虚拟内存等进程用户态的资源，也不会切换进程。这跟我们通常所说的进程上下文切换是不一样的：进程上下文切换，是指从一个进程切换到另一个进程运行；而系统调用过程中一直是同一个进程在运行。

进程上下文切换

因为 CPU 在同一时间只能执行一个进程的任务，在多个进程共享 CPU 资源的情况下，需要让 CPU 切换轮流执行多个进程。从一个进程切换到另一个进程运行，称为进程的上下文切换。进程是由内核管理和调度的，所以进程的切换只能发生在内核态。
因为进程切换是属于不同进程之间的切换，所以进程还需要保存用户态的资源。进程的上下文不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。
因此，进程的上下文切换就比系统调用时多了一步
  • 在保存内核态资源（当前进程的内核状态和 CPU 寄存器）之前，需要先把该进程的用户态资源（虚拟内存、栈等）保存下来
  • 加载了下一进程的内核态后，还需要刷新进程的虚拟内存和用户栈。
      • notion image
发生进程上下文切换的场景：
  • 为了保证所有进程可以得到公平调度，CPU 时间被划分为一段段的时间片，这些时间片再被轮流分配给各个进程。这样，当某个进程的时间片耗尽了，就会被系统挂起，切换到其它正在等待 CPU 的进程运行。
  • 进程在系统资源不足（比如内存不足）时，要等到资源满足后才可以运行，这个时候进程也会被挂起，并由系统调度其他进程运行。
  • 当进程通过睡眠函数 sleep 这样的方法将自己主动挂起时，自然也会重新调度。
  • 当有优先级更高的进程运行时，为了保证高优先级进程的运行，当前进程会被挂起，由高优先级进程来运行
  • 发生硬件中断时，CPU 上的进程会被中断挂起，转而执行内核中的中断服务程序。

线程上下文切换

线程与进程最大的区别在于：线程是调度的基本单位，而进程则是资源拥有的基本单位。说白了，所谓内核中的任务调度，实际上的调度对象是线程；而进程只是给线程提供了虚拟内存、全局变量等资源。
所以，对于线程和进程，我们可以这么理解： - 当进程只有一个线程时，可以认为进程就等于线程。 - 当进程拥有多个线程时，这些线程会共享相同的虚拟内存和全局变量等资源。这些资源在上下文切换时是不需要修改的。另外，线程也有自己的私有数据，比如栈和寄存器等，这些在上下文切换时也是需要保存的。
发生线程上下文切换的场景：
  • 前后两个线程属于不同进程。此时，因为资源不共享，所以切换过程就跟进程上下文切换是一样。
  • 前后两个线程属于同一个进程。此时，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

中断上下文切换

为了快速响应硬件的事件，中断处理会打断进程的正常调度和执行，转而调用中断处理程序，响应设备事件。而在打断其他进程时，就需要将进程当前的状态保存下来，这样在中断结束后，进程仍然可以从原来的状态恢复运行。
跟进程上下文不同，中断上下文切换并不涉及到进程的用户态。所以，即便中断过程打断了一个正处在用户态的进程，也不需要保存和恢复这个进程的虚拟内存、全局变量等用户态资源。中断上下文，其实只包括内核态中断服务程序执行所必需的状态，包括 CPU 寄存器、内核堆栈、硬件中断参数等。
对同一个 CPU 来说，中断处理比进程拥有更高的优先级，所以中断上下文切换并不会与进程上下文切换同时发生。同样道理，由于中断会打断正常进程的调度和执行，所以大部分中断处理程序都短小精悍，以便尽可能快的执行结束。
另外，跟进程上下文切换一样，中断上下文切换也需要消耗 CPU，切换次数过多也会耗费大量的 CPU，甚至严重降低系统的整体性能。所以，当你发现中断次数过多时，就需要注意去排查它是否会给你的系统带来严重的性能问题。

同步和互斥

同步就是并发进程/线程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通信息称为进程/线程同步。
互斥是指保证一个线程在占用共享资源区时，其他线程应该被阻止进入共享资源区。
同步与互斥是两种不同的概念：
  • 同步就好比：「操作 A 应在操作 B 之前执行」，「操作 C 必须在操作 A 和操作 B 都完成之后才能执行」
  • 互斥就好比：「操作 A 和操作 B 不能在同一时刻执行」
为了实现进程/线程间正确的协作，操作系统必须提供实现进程协作的措施和方法，主要的方法有两种:
  • 锁：加锁、解锁操作。
  • 信号量：P、V 操作。

锁

锁的原理：任何想进入临界区的线程，必须先执行加锁操作。若加锁操作顺利通过，则线程可进入临界区；在完成对临界资源的访问后再执行解锁操作，以释放该临界资源。
锁的种类有：
  • 互斥锁和自旋锁
  • 读写锁
  • 乐观锁和悲观锁

互斥锁和自旋锁

最底层的两种就是会「互斥锁和自旋锁」，有很多高级的锁都是基于它们实现的，你可以认为它们是各种锁的地基，所以我们必须清楚它俩之间的区别和应用。
当已经有一个线程加锁后，其他线程加锁则就会失败，互斥锁和自旋锁对于加锁失败后的处理方式是不一样的：
  • 互斥锁加锁失败后，线程会释放 CPU ，给其他线程。
  • 自旋锁加锁失败后，线程会忙等待，直到它拿到锁。
对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的：
  • 当加锁失败时，会从用户态陷入到内核态，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程。
  • 等到锁被释放后，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行，然后从内核态切回用户态。
因此有互斥锁加锁失败有两次线程上下文切换的成本。
自旋锁是通过 CPU 提供的 CAS 函数(Compare And Swap)，在「用户态」完成加锁和解锁操作，不会主动产生线程上下文切换，所以相比互斥锁来说，会快一些，开销也小一些。一般加锁的过程，包含两个步骤:
  1. 查看锁的状态，如果锁是空闲的，则执行第二步。
  1. 将锁设置为当前线程持有。
CAS 函数就把这两个步骤合并成一条硬件级指令，形成原子指令，这样就保证了这两个步骤是不可分割 的，要么一次性执行完两个步骤，要么两个步骤都不执行。
如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

读写锁

读写锁的工作原理是：
  • 当「写锁」没有被线程持有时，多个线程能够并发地持有读锁，这大大提高了共享资源的访问效率，因为「读锁」是用于读取共享资源的场景，所以多个线程同时持有读锁也不会破坏共享资源的数据。
  • 一旦「写锁」被线程持有后，读线程的获取读锁的操作会被阻塞，而且其他写线程的获取写锁的操作也会被阻塞。
所以说，写锁是独占锁，因为任何时刻只能有一个线程持有写锁，类似互斥锁和自旋锁，而读锁是共享锁，因为读锁可以被多个线程同时持有。
根据实现的不同，读写锁可以分为「读优先锁」和「写优先锁」：
  • 读优先锁：读锁能被更多的线程持有，以便提高读线程的并发性，它的工作方式是:当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候，会被阻塞，并且在阻塞过程中，后续来的读线程 C 仍然可以 成功获取读锁，最后直到读线程 A 和 C 释放读锁后，写线程 B 才可以成功获取写锁。
  • 写优先锁：当读线程 A 先持有了读锁，写线程 B 在获取写锁的时候， 会被阻塞，并且在阻塞过程中，后续来的读线程 C 获取读锁时会失败，于是读线程 C 将被阻塞在获取读锁 的操作，这样只要读线程 A 释放读锁后，写线程 B 就可以成功获取读锁。

乐观锁和悲观锁

前面提到的互斥锁、自旋锁、读写锁，都是属于悲观锁。
悲观锁做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。
乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：先修改完共享资源，再验证这段时间内 有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。乐观锁全程并没有加锁，所以它也叫无锁编程。
乐观锁虽然去除了加锁解锁的操作，但是一旦发生冲突，重试的成本非常高，所以只有在冲突概率非常低，且加锁成本非常高的场景时，才考虑使用乐观锁。

死锁

当两个线程为了保护两个不同的共享资源而使用了两个互斥锁，两个线程都在等待对方释放锁，在没有外力的作用下，这些线程会一直相互等待，就没办 法继续运行，这种情况就是发生了死锁。
死锁只有同时满足以下四个条件才会发生:
  • 互斥条件：多个线程不能同时使用同一个资源，例如如果线程 A 已经持有的资源，不能再同时被线程 B 持有。
  • 持有并等待条件：线程 A 在等待资源 2 的同时并不会释放自己已经持有的资源 1。
  • 不可剥夺条件：当线程已经持有了资源，在自己使用完之前不能被其他线程获取。
  • 环路等待条件：两个线程获取资源的顺序构成了环形链。
避免死锁问题就只需要破环其中一个条件就可以，最常⻅的并且可行的就是使用资源有序分配法，来破环环路等待条件。
  • 线程 A 和 线程 B 获取资源的顺序要一样，当线程 A 是先尝试获取资源 A，然后尝试获取资源 B 的时候， 线程 B 同样也是先尝试获取资源 A，然后尝试获取资源 B。也就是说，线程 A 和 线程 B 总是以相同的顺序申请自己想要的资源。

信号量

信号量表示资源的数量，对应的变量是一个整型( sem )变量。另外，还有两个原子操作的系统调用函数来控制信号量：
  • P 操作：将 sem 减 1 ，相减后，如果 sem < 0 ，说明资源不足，目前已经有线程在等待，则当前线程进入阻塞等待；如果 sem >= 0，说明资源充足，当前线程可以直接执行。
  • V 操作：将 sem 加 1 ，相加后，如果 sem <= 0 ，说明有线程在等待，唤醒一个等待中的进程/线程；如果 sem > 0，说明没有线程在等待，没有其他操作。
对于两个并发线程，互斥信号量的值仅取 1、0 和 -1 三个值，分别表示：
  • 如果互斥信号量为 1，表示没有线程进入临界区;
  • 如果互斥信号量为 0，表示有一个线程进入临界区;
  • 如果互斥信号量为 -1，表示一个线程进入临界区，另一个线程等待进入。
通过互斥信号量的方式，就能保证临界区任何时刻只有一个线程在执行，就达到了互斥的效果。

进程调度算法

进程调度算法的本质是为cpu选择下一个要运行的进程，使多个进程轮流使用cpu，造成多个进程同时运行的错觉。所以调度器的工作主要分为两个部分，调度策略和上下文切换：
  • 调度策略：决策什么时候切换进程和下一个获得CPU的进程。对于多核整体来讲，调度策略还要负责决策进程在那一个核心上运行。
  • 上下文切换：切换进程的时候要保存当前进程的上下文信息，以便于日后恢复执行。

进程的分类

按照优先级来分类：
  • 实时进程(RT进程)： 既然叫实时进程，则就对快速响应的要求就很高。比如航天系统，里面的计算就要求必须是实时的。否则就会出大事情，所以航天方面的操作系统一般不用linux，因为linux不是实时操作系统。
  • 普通进程： 普通进程就是实际进程的反面，对实时性要求不是很高，但是普通进程还是需要得到CPU的调度，不能饿死。
按照CPU的运行状态来分类：
  • CPU消耗型： CPU消耗型，此类进程就是一直占用CPU忙于计算，CPU利用率贼高，比如编译android系统则就是CPU消耗型，服务器上的后台程序，都是默默无闻的在一直干活
  • IO消耗型： IO消耗型就是会涉及到IO，需要和用户交互，比如键盘输入，鼠标滑动，占用CPU不是很高，大多数时间实在等待IO。
根据进程任务在占用CPU时使用权是否会被夺取分为：
  • 非抢占式调度：进程任务一旦占用CPU只有当任务完成或者因为某些原因主动释放CPU，除上述两种情况外不能被其他进程夺走。
  • 抢占式调度：进程任务占用CPU期间可以被其他进程夺走，具体由操作系统调度器决定下一个占用CPU的进程。
Linux采用抢占式调度，其可以提高CPU利用率、降低进程的响应时间等，同时也增加了切换进程时的开销，各有利弊。

调度器设计

我们一般会先设计调度器法，然后在调度器算法的基础实现调度器，在实际应用中再根据实际情况选择合适调度策略。

六种调度算法

调度算法
说明
缺点
先来先服务(First Come First Severd, FCFS)
先来后到，每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行。
长作业先运行，造成短作业饥渴
最短作业优先(Shortest Job First, SJF)
优先选择运行时间最短的进程来运行
短作业过多，造成长作业饥渴
高响应比优先(Highest Response Ratio Next, HRRN)
每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行
同时兼顾长短作业，但是首次运行的作业无法预知运行时间，只能通过历史执行时间来预测
时间片轮转(Round Robin, RR)
每个进程被分配一个时间段，称为时间片(Quantum)，即允许该进程在该时间段中运行。如果时间片用完，进程还在运行，那么将会把此进程从 CPU 释放出来，并把 CPU 分配另外一个进程；如果该进程在时间片结束前阻塞或结束，则 CPU 立即进行切换。
相对比较公平的调度算法
最高优先级(Highest Priority First，HPF)
从就绪队列中选择最高优先级的进程进行运行
低优先级的进程永远不会运行
多级反馈队列(Multilevel Feedback Queue，MLFQ)
「时间片轮转算法」和「最高优先级算法」的 综合和发展，见下详解
兼顾了⻓短作业，同时有较好的响应时间。
MLFQ算法是O(1)/CFS调度器的基础，是一个比较经典的调度算法。
notion image
  • 有多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短。
  • 新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成;
  • 当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行。
可以发现，对于短作业可能可以在第一级队列很快被处理完。对于⻓作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变⻓了，但是运行时间也会更⻓了，所以该算法很好的兼 顾了⻓短作业，同时有较好的响应时间。

五种调度类

调度类
说明
算法
对应进程
stop_sched_class
优先级最高的调度类，可以抢占其他所有进程，不能被其他进程抢占，用于处理内核紧急任务。
/
仅内核使用
dl_sched_class
使用红黑树，把进程按照绝对截止期限进行排序，选择最小进程进行调度运行
EDF
/
rt_sched_class
调度实时进程，存在两种policy：SCHED_FIFO和SCHED_RR
FIFO和RR
实时进程
fair_sched_class
调度普通的非实时进程，有两种policy：SCHED_NORMAL和SCHED_BATCH
CFS
普通进程
idel_sched_class
每个CPU都会有一个idle线程，当没有其他进程可以调度时，调度运行idle线程
CFS
IDEL进程

三种调度实体和队列

实体
说明
对应队列
sched_dl_entity
Deadline调度实体，对应dl_sched_class
dl_rq
sched_rt_entity
RT调度实体，对应rt_sched_class
rt_rq
sched_entity
普通进程调度实体，对应fair_sched_class
cfs_rq
调度器只考虑处于TASK_RUNNING状态的进程，其他状态进程调度器并不考虑。
调度器，会首先查看实时运行队列rt_rq，然后查看普通运行队列cfs_rq，最后查看idle运行队列。

六种调度策略

策略类别
描述
调度类
SCHED_RR
轮转调度算法，属于实时调度策略，采用Round-Robin语义，相同优先级的任务在当前时间片用完后放置到队列尾部，以保证公平性，高优先级的任务可以抢占低优先级的任务。
RT
SCHED_FIFO
先进先出调度算法，属于实时调度策略，相同优先级的任务先到先服务，高优先级的任务可以抢占低优先级的任务
RT
SCHED_DEADLINE
Earliest Deadline First(EDF)调度算法，针对突发型计算，且的对延迟和完成时间高度敏感的任务使用
DL
SCHED_NORMAL
用于普通进程，通过CFS调度器实现。SCHED_BATCH用于非交互的处理器消耗型进程，SCHED_IDLE是在系统负载很低时使用
CFS
SCHED_BATCH
是SCHED_NORMAL调度策略的一种，采用分时策略，根据动态优先级（nice接口），分配CPU运算资源，不支持抢占，允许任务运行更长时间，更好地使用高速缓存，适合批处理工作
CFS
SCHED_IDLE
优先级最低，在系统空闲的时候才运行这类进程.
CFS-IDL

相互关系

notion image

调度触发时机

Linux内核调度器有两种触发机制：
  • 主动放弃机制：进程打算睡眠或处于其他原因，放弃CPU
  • 周期性机制：以固定频率发生中断，检查是否需要进行调度切换
从调度机制出发，当前Linux内核具有两个调度器组成
  • 主调度器scheduler：当需要重新分配CPU资源时，需要使用调度函数schedule或__schedule进行实际调度。
  • 周期性调度器scheduler_tick：由内核时钟周期性触发，由所属类的task_tick操作完成周期性调度的通知和配置工作; 通过resched_curr或resched_task函数设置TIF_NEED_RESCHED，接下来在合适的时机由主调度函数完成真正的调度。
调度器触发时机：
  • 显式调用schedlue触发。
  • 调用cond_resched。
  • 系统调用或异常中断，从内核态返回用户空间时。
  • 中断上下文返回用户空间时。
内核抢占(默认开启)开启时，除了上述出发时机：
  • 在系统调用或异常中断上下文中，调用preempt_enable。
  • 在中断上下文中，上半部执行完毕，从中断处理函数返回到可抢占上下文时。

调度器实现

调度器的发展历史：
  • O(n) 调度器 linux0.11 - 2.4
  • O(1) 调度器 linux2.6
  • CFS调度器 linux2.6至今

O(n)调度器

O(n) 调度器是在内核2.4以及更早期版本采用的算法，O(n)代表的是寻找一个合适的任务的时间复杂度。调度器的特点是：
  • 定义了一个 runqueue 的运行队列，将进程的状态变为 Running 的不管是实时进程，还是普通进程都会添加到此运行队列中，队列里面的进程排序是无序的。
  • 当需要从运行队列中选择一个合适的任务时，就需要从头到尾遍历队列，比较每个进程的优先级，优先级高的先运行。遍历的时间复杂度是O(n)，运行队列中的任务数目越大，调度器的效率就越低。
  • 进程和线程统一采用task_struct结构，实时进程采用的是SCHED_RR或者SCHED_FIFO调度策略，普通进程采用的是SCHED_OTHER调度策略。
  • task_struct里面使用 nice值代表这个进程的静态优先级。nice值的取值范围是[-20.19], 取值越小优先级越高。进程的默认nice值是0，则进程默认的静态优先级就等于20。以上针对普通进程，实时进程则是直接是在实时进程的静态优先级上加上1000。
  • 多个cpu共享全局队列，并非每个cpu有单独的队列。
notion image
  • counter代表的是进程的时间片，就是进程在一个调度周期中可与运行的时间。
  • nice代表这个进程的静态优先级。通过宏NICE_TO_TICKS，可以将对应的nice值转化为对应的时间片，存储在counter中
  • policy就是进程的调度策略，实时进程采用的是SCHED_RR或者SCHED_FIFO。普通进程采用的是SCHED_OTHER
    • SCHED_RR：同等优先级采用轮转的方式，不同优先级还是高优先级先调度
    • SCHED_FIFO：同等优先级采用先来后到的次序，就是先调度的进程如果没运行完毕，后面的只能排队。不同优先级还是高优先级的优先。如果高优先级的实时进程没运行完，低优先级的也是不能运行的。
  • pocessor: 代表当前进程运行在那个处理器上，会在SMP系统中使用
  • cpu_allowed：代表当前进程允许在那些CPU上可以运行。
O(n)调度器的缺点：
  • 时间复杂度问题，时间复杂度是O(n),当系统中的进程很少的时候性能还可以，但是当系统中的进程逐渐增多，选择下一个进程的时间则是逐渐增大。而且当系统中无可运行的进程时，重新初始化进程的时间片也是相当耗时，在系统中进程很多的情况系下。
  • SMP扩展问题。当需要picknext下一个进程时，需要对整个runqueue队列进行加锁的操作，spin_lock_irq(&runqueue_lock);当系统中进程数目比较多的时候，则在临界区的时间就比较长，导致其余的CPU自旋比较浪费
  • 实时进程的运行效率问题，因为实时进程和普通进程在一个列表中，每次查实时进程时，都需要全部扫描整个列表，导致实时进程不是很“实时”
  • CPU资源浪费问题：因为系统中只有一个runqueue,则当运行队列中的进程少于CPU的个数时，其余的CPU则几乎是idle状态，浪费资源
  • cache缓存问题：当系统中的进程逐渐减少时，原先在CPU1上运行的进程，不得不在CPU2上运行，导致在CPU2上运行时，cacheline则几乎是空白的，影响效率。
总之O(n)调度器有很多问题，不过有问题肯定要解决的。所以在Linux2.6引入了O(1)的调度器。
参考 Linux O(n)调度器

O(1)调度器

O(1)算法用于解决O(n)的问题，他的特点是：
  • 实现了per-cpu-runqueue，每个CPU都有一个runqueue。
  • 每一个runqueue运行队列维护两个数组：活跃数组active和过期数组expired，分别存储分别存储就绪进程和时间片用完的进程。数组元素按照进程的优先级从低到高排列。O(n)采用全局优先级：实时进程[0,99]，普通进程[100,139]，数值越低优先级越高，更容易被调度。
  • 每个数组元素对应一个进程链表，链表元素是优先级相同的进程。
  • 每个数组都提供了一个bitmap结构，从高位到低位每bit对应优先级从高到低的每个数组元素。如果该bit的值为1，说明对应优先级的链表不为空；如果该bit的值为0，说明对应优先级的链表为空。
notion image
O(1)pciknext的过程：
  1. 去active数组的bitmap里面从高位到低位查找第一个为1的bit。
  1. 查找该bit对应的数组元素，即寻找优先级最高且非空的数组元素。因为数组元素是一个进程链表，直接取链表的第一个元素，这个就是要执行的下一个进程。所以每次查找进程的时间复杂度为O(1)。
  1. 该进程的时间片执行完后，把他放进expire数组。（优先级可能会改变，所以放进expire数组的位置可能会和active数组不同）。
  1. 当acitve数组中无进程可运行时，说明该轮调度周期所有进程的时间片都已经耗光，这时候调换active和expired的指针，开始下一轮调度周期。
notion image
总的来说 O(1) 调度器的出现是为了解决 O(n) 调度器不能解决的问题，但 O(1) 调度器有个问题，一个高优先级多线程的应用会比低优先级单线程的应用获得更多的资源，这就会导致一个调度周期内，低优先级的应用可能一直无法响应，直到高优先级应用结束。
参考Linux O(1)调度器

CFS调度器

CFS(Completely Fair Scheduler)调度器采用和O(1)/O(n)调度器完全不同的设计思路，基于楼梯调度算法（Staircase Deadline Schedule, SD）和 基于公平策略RSDL调度器(The Rotating Staircase Deadline Schedule)，目的是实现完全公平的调度。
在2.6.23内核中引入scheduling class的概念，将调度器模块化，系统中可以有多种调度器，使用不同策略调度不同类型的进程：
  • DL Scheduler 采用sched_deadline策略
  • RT Scheduler 采用sched_rr和sched_fifo策略
  • CFS Scheduler 采用sched_normal和sched_batch策略
  • IDEL Scheduler 采用sched_idle策略
所以CFS调度器就不关心实时进程了，专注于普通进程就可以了。CFS调度器的特点：
  • CFS摒弃了固定时间片分配，采用动态时间片分配。O(1)和O(n)都将CPU资源划分为时间片，采用了固定额度分配机制，在每个调度周期进程可使用的时间片是确定的，调度周期结束才重新分配。CFS的动态调度中进程可占用的时间与进程总数、总CPU时间、进程权重等均有关系，每个调度周期的值都可能会不一样。
  • 保留普通进程的优先级piro范围[100,139]和nice范围[-20, 19]，引入新的概念权重weight，建立了优先级(或者说nice)和权重之间的映射关系，把优先级转换为权重来计算进程所能获取的运行时间百分比。
  • 引入虚拟时间vruntime的概念。vruntime类似于在一次调度周期时间轴上里面每个进程的开始位置，vruntime越小，进程在时间轴上的位置越靠前，在本次调度周期里面所能获得的物理运行时间也就越长。CFS的绝对公平思想，是保证所有进程的vruntime相同，而不是保证所有进程的物理运行时间相同。
  • 采用了红黑树结构来保存活跃进程任务。红黑树的key是进程已经使用的vruntime，并且把vruntime值最小的放到最左的叶子节点，这个节点就是下一个被pick的进程了。当vruntime耗尽则从红黑树中删除，下个调度周期开始后再添加到红黑树上。
  • 当进程的数目小于8时，则调度周期为6ms。当系统的进程数目大于8时，则调度器周期等于进程的数目乘以0.75ms。可以理解为在一个调度周期中一个进程至少保证执行0.75ms。

vruntime计算

CFS 保留普通进程的优先级prio范围[100,139]和nice值范围[-20, 19]，(prio-120)或者nice和权重weight是一一对应的关系。数值越小代表优先级越大，同时也意味着权重值越大。nice值和权重之间的转换关系是：
代码中已经事先计算好了nice和weight的对应表
nice=0 虚拟运行时间 = 物理运行时间
nice>0 虚拟运行时间 > 物理运行时间
nice<0 虚拟运行时间 < 物理运行时间
通过以上对应表，根据进程优先级（或者nice）计算进程的实际运行时间。
比如现有进程A sched_prio=0，进程B sched_prio=-5，通过sched_prio_to_weight的映射：
进程A weight=1024，进程B weight = 3121
进程A的CPU占比 = 1024/(1024+3121)= 24.7%
进程B的CPU占比 = 3121/(1024+3121) = 75.3%
假如CPU总时间是10ms，那么根据A占用2.47ms，B占用7.53ms
每个进程的物理运行时间都是不同的，我们需要把物理运行时间来映射成vruntime。
  • wall_time：实际运行时间
  • nice_0_weight：nice值为0对应的weight值，也就是1024
  • sched_prio_to_weigh：进程优先级对应的weight
      • 接着上面计算
      A的wall_time=2.47ms，B的wall_time=7.53ms
      nice_0_weight表示sched_prio=0的权重为1024
      进程A的虚拟时间：2.471024/1024=2.47ms进程B的虚拟时间：7.531024/3121=2.47ms
经过这样映射，多个进程的vruntime就相等了，就是实现了“完全公平”的思想。

vruntime存储结构

为了能够快速找到虚拟运行时间最小的进程，Linux 内核使用红黑树来保存可运行的进程。红黑树的key是vruntime的值，红黑树的左节点比父节点小，而右节点比父节点大。所以查找最小节点时，只需要获取红黑树的最左节点即可。
notion image
实际运行时间映射成红黑树的过程：每个sched_latency周期内，根据各个任务的权重值，可以计算出运行时间runtime；运行时间runtime可以转换成虚拟运行时间vruntime；根据虚拟运行时间的大小，插入到CFS红黑树中，虚拟运行时间少的调度实体放置到左边。在下一次任务调度的时候，选择虚拟运行时间少的调度实体来运行，即从 CFS 红黑树最左边节点获取一个调度实体。
参考 CFS Scheduler（CFS调度器）
Relate Posts
Linux Systemd 入门教程：实战篇
Linux Systemd 入门教程：命令篇
Linux的磁盘挂载
Linux的救援模式和紧急模式
Linux系列：文件系统
Linux系列：内存管理
Linux系列：文件系统 Linux系列：内存管理
mcbilla
mcbilla
一个普通的干饭人🍚
Announcement
type
status
date
slug
summary
tags
category
icon
password
🎉欢迎来到飙戈的博客🎉
-- 感谢您的支持 ---
👏欢迎学习交流👏