Linux 进程管理与调度

引言

本文整理了 Linux 内核中进程管理与调度的相关知识,其他 Linux 相关文章均收录于 <Linux系列文章>

进程管理与调度

现代操作系统都能同时运行多个进程,至少从用户的角度来看是这个样子的。每一个处理器上某一指定时刻只能有一个程序可以运行,在多处理器系统中,并行运行的进程数目取决于 CPU 的数量。

内核和处理器相互配合,给用户以多任务并行的错觉,这是通过以很短的时间间隔在运行的应用程序之间不停地切换而做到的。因为切换的间隔足够短,所以用户根本感觉不到短时间内的停滞,从而觉得计算机能够同时做多件事。

由于操作系统通过上述方式管理程序的运行,就引出了如下几个问题:

  • 除非明确声明,否则程序之间不能彼此干扰。一个程序不能读取或修改其他程序的内存,否则就会访问到其他程序的私有数据。
  • CPU 时间应该在各个应用程序之间尽可能公平的分享,并允许某些应用程序的优先级比其他应用程序更高。

第一个问题,我们后面介绍内存管理的时候再详细说明,这里我们主要关心 CPU 时间分配的策略以及如何进行程序之间的切换。

进程优先级

前面我们提到过,进程之间可能优先级各不相同,对于优先级较高的进程,理想的情况是它能够分配更多的 CPU 时间,反之,如果优先度较低,则分配较少的 CPU 时间。下图给出了 CPU 时间分配的一个简图,进程的运行按时间片调度,分配给进程的时间片份额与其相对重要性相当。系统中时间的流动对应于圆盘的转动,而 CPU 则由圆周旁的“扫描器”表示。最终效果是,尽管所有的进程都有机会运行,但重要的进程会比次要的得到更多的 CPU 时间。
time-segment
这种方案我们称之为抢占式多任务处理,各个任务按照优先级分配到一定的时间段执行。当时间段到期后,内核收回控制权,让下一个进程运行,而前一个进程的所有运行状态,即 CPU 寄存器和页表,都会保存起来,因而其执行状态不会丢失。当该进程恢复执行时,其进程状态可以完全恢复。

上述的简化模型忽略了几个问题,某些进程可能在等待其他事件,如网络包的接收,磁盘 IO 的完成,在等待过程中它无事可做,这时候还把 CPU 时间分配给它显然不利于充分利用 CPU 资源。另一个如果有一些进程需要实时调度的话可能需要还没等当前进程的时间片耗尽就抢先执行。这里就牵扯到实时进程的概念,我们不妨看一看:

  • 硬实时进程:有严格的时间限制,某些任务必须在指定的时间内完成。试想一下如果飞机处于着陆过程中,而飞行员想要拉起机头。如果飞机几秒后才能拉起机头的话,可能就太晚了!Linux 不支持硬实时处理,不过一些修改版的 Linux 支持,这些修改版中 Linux 内核作为一个独立的进程运行着,它用来处理不是那么重要的任务,而实时任务的执行由内核的更下层管理。只有当没有硬实时的任务时,内核才能得以运行。
  • 软实时进程:是硬实时进程的弱化,尽管仍然需要尽快完成实时任务,但是稍微晚一点也不会影响太大。不过这种软实时进程拿到的 CPU 时间至少要好过普通进程。
  • 普通进程:大多数进程是没有特定时间约束的普通进程,但仍然需要根据其重要性分配优先级。

总结一下,在 Linux 中进程会分为两大类,软实时进程和普通进程,当软实时进程存在时,会立即抢占普通进程的执行,此外软实时进程之间也有优先度的划分,优先级高的软实时进程会抢占优先级低的软实时进程。当没有软实时进程时,普通进程开始运作,它们根据优先级的不同划分不同大小的 CPU 时间执行,这很类似前面提到的基于时间片的简要模型,不过要注意的是在 2.6.23 之后 Linux 中已经不存在时间片的概念了,Linux 采用了一个完全公平调度器 CFS 来规划每个进程的运行时间,这些我们后面就会介绍到。

进程的生命周期

进程并不是一直都可以立即运行,有时候它必须等待来自外部的信号,当信号到来之后才能回到可运行状态,例如等待键盘输入。进行进程调度的时候,显然我们需要将 CPU 时间分配给可立即运行的进程才对,否则就是在浪费 CPU 资源。进程可以有如下状态:

  • 运行:该进程此刻正在执行。
  • 等待:该进程能够运行,但是可能现在没轮到它执行,CPU 当前被分配给另一个进程。
  • 睡眠:进程正在睡眠无法运行,它在等待一个外部事件,调度器无法在下次任务切换的时候选择该进程,只有当外部事件到来之后,内核将该进程的状态改为等待状态,之后调度器才有机会选择它作为下一个运行的进程。
  • 终止:当进程退出时,会处于终止状态。

process-lifecycle

  • 上图描述了一个进程的各种可能的状态转换。首先,该进程可能已经就绪,但没有运行,因为 CPU 分配给了其他进程(因此该进程的状态是“等待”)。在调度器授予 CPU 时间之前,进程会一直保持该状态。
  • 在分配 CPU 时间之后,其状态改变为“运行”(路径4)。
  • 在调度器决定从该进程收回 CPU 资源时(可能的原因稍后讲述),进程状态从“运行”改变为“等待”(路径2),循环重新开始。
  • 如果进程必须等待事件,则其状态从“运行”改变为“睡眠”(路径1),但进程状态无法从“睡眠”直接改变为“运行”。在所等待的事件发生后,进程先变回到“等待”状态(路径3),然后重新回到正常循环。
  • 在程序执行终止(例如,用户关闭应用程序)后,过程状态由“运行”变为“终止”(路径5)。

上文没有列出的一个特殊的进程状态是所谓的“僵尸”状态。顾名思义,这样的进程已经死亡,但仍然以某种方式活着。实际上,说这些进程死了,是因为其资源(内存、与外设的连接,等等)已经释放,因此它们无法也决不会再次运行。说它们仍然活着,是因为进程表中仍然有对应的表项。

那么僵尸是如何产生的?其原因在于 UNIX 操作系统下进程创建和销毁的方式。程序由另一个进程或一个用户杀死(通常是通过发送 SIGTERM 或 SIGKILL 信号来完成,这等价于正常地终止进程),进程的父进程在子进程终止时必须调用或已经调用 wait4 系统调用。这相当于向内核证实父进程已经确认子进程的终结。该系统调用使得内核可以释放为子进程保留的资源。

只有在程序终止而父进程没有调用 wait4 的情况下,才会出现“僵尸”状态。在进程终止之后,其数据尚未从进程表删除之前,进程总是暂时处于“僵尸”状态。有时候(例如,如果父进程编程极其糟糕,没有发出wait调用),僵尸进程可能稳定地寄身于进程表中,直至下一次系统重启。从进程工具(如ps或top)的输出,可以看到僵尸进程。因为残余的数据在内核中占据的空间极少,所以这几乎不是问题。

另外一类进程的状态是通过内核态和用户态划分的。这反映了现在 CPU 的两种不同状态,其中一个具有无限的权力,而另一个则受到各种限制。例如,可能禁止访问某些内存区域。这是进程之间实现隔离的前提,防止用户进程之间互相打扰。

进程通常处于用户状态,只能访问自己的数据,无法干扰其他进程,甚至感知不到其他进程的存在。

如果进程想要访问系统资源或者功能,则必须切换到核心态,前面提到过进程可以通过系统调用的方式切换到内核态,除此之外,还有一种机制是中断,虽然系统调用也是通过软中断的方式实现,但是这里我们特指硬中断,系统调用是应用程序有意触发的,而中断的发生或多或少是不可预测的。通常这种中断的发生和正在运行的应用程序之间没有任何关系。例如当网络包到来时,可能和当前正在运行的进程不相干。当这种情况发生时,当前运行中的进程是无法感知到的,因为内核通过抢占调度的方式来处理中断。

这就牵扯到抢占调度的问题,那么什么时候进程可以被抢占调度呢?

  • 普通进程随时可以被抢占,甚至由其他进程抢占。当一个重要进程变得可运行时,调度器可能决定立即执行该程序,即使当前进程仍然在正常运行。对于实现良好交互体验和低系统延迟来说,抢占至关重要。
  • 当系统处于核心态,并且正在处理系统调用时,那么系统中的其他进程是无法抢占其 CPU 时间的,调度器必须等其系统调用结束后,才能选择另一个进程执行,但是中断可以终止系统调用
  • 中断可以暂停处于用户态或者核心态的进程,甚至可以抢占正在运行的中断处理程序,中断具有最高优先级,因为中断发生时必须尽快处理。

在内核 2.5 开发期间,一个称之为内核抢占(kernel preemption)的选项添加到内核。该选项支持在紧急情况下切换到另一个进程,甚至当前是处于核心态执行系统调用(中断处理期间是不行的)。尽管内核会试图尽快执行系统调用,但对于依赖恒定数据流的应用程序来说,系统调用所需的时间仍然太长了。内核抢占可以减少这样的等待时间,从而保证“更平滑的”程序执行。

进程表示

内核的进程是通过名为 task_struct 的数据结构建立的,其中包含了很多和进程相关的信息,这里我们将其划分为多个部分简单介绍一下:

  • 状态和执行信息,如待决信号,使用的二进制格式,进程 ID,到父进程和其他相关进程的指针,优先级和 cpu 时间等。
  • 有关于已分配的虚拟内存的信息。
  • 进程身份凭证,如用户 ID,组 ID 以及权限等。
  • 使用的文件,包含代码二进制文件,以及进程所处理的所有文件的文件系统信息。
  • 线程信息记录了该进程特定于 CPU 的运行时间数据。
  • 进程间通讯的信息
  • 进程所用的信号处理程序,用来响应信号

进程的状态 state 可以为如下值:

  • TASK_RUNNING:进程处于可运行状态,不过当前 CPU 可能并不是由该进程持有。
  • TASK_INTERRUPTIBLE:表示等待某事件或其他资源的睡眠进程,在内核发送信号给该进程表明事件发生时,进程变为 TASK_RUNNING 状态。
  • TASK_UNINTERRUPTIBLE:因内核指示而停用的睡眠进程。它不能由外部信号唤醒,只能由内核唤醒。
  • TASK_STOPPED:进程特意停止,如由调试器暂停。
  • TASK_TRACED:本不是进程状态,用于从停止的进程中,将当前被调试的那些与常规的进程区分开。
  • EXIT_ZOMBIE:前面介绍的僵尸状态。
  • EXIT_DEAD:指 wait 系统调用已经发出,而进程完全从系统移除之前的状态。

Linux 还提供了限制机制,对进程使用的资源施加限制,可限制的资源如下图所示:
rlimit
这些限制存在 task_struct 的 rlim 数组中,数组项类型为 struct rlimit,其中包括软限制和硬限制,软限制 <= 硬限制。我们可以通过查看/proc/pid/limits 来查看进程的当前限制:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
cat /proc/self/limits
Limit Soft Limit Hard Limit Units
Max cpu time unlimited unlimited seconds
Max file size unlimited unlimited bytes
Max data size unlimited unlimited bytes
Max stack size 8388608 unlimited bytes
Max core file size 0 unlimited bytes
Max resident set unlimited unlimited bytes
Max processes 4096 7282 processes
Max open files 65535 65535 files
Max locked memory 65536 65536 bytes
Max address space unlimited unlimited bytes
Max file locks unlimited unlimited locks
Max pending signals 7282 7282 signals
Max msgqueue size 819200 819200 bytes
Max nice priority 0 0
Max realtime priority 0 0
Max realtime timeout unlimited unlimited us

进程与线程

我们知道在 Linux 中一个进程默认只有一个线程,新进程的创建是通过 fork 和 exec 系统调用来产生。

fork 生成当前进程的一个相同副本,该副本称之为子进程。原进程的所有资源都以适当的方式复制到子进程,因此该系统调用之后,原来的进程就有了两个独立的实例。这两个实例的联系包括: 同一组打开文件、同样的工作目录、内存中同样的数据(两个进程各有一份副本),等等。此外二者并无关联。

exec 从一个可执行的二进制文件加载另一个应用程序,来代替当前运行的进程。换句话说,加载了一个新程序。因为 exec 并不创建新进程,所以必须首先使用 fork 复制一个旧的程序,然后调用 exec 在系统上创建另一个应用程序。

在 Linux 中一个 task struct 可以代表一个进程,该进程只包含一个默认线程,这听上去有点蠢,这不是废话吗(task struct 当然代表了一个进程),但是你要知道 Linux 不像其他系统那样将一个进程的多个线程都打包进同一个进程描述结构体中,相反的,Linux 中一个 task_struct 结构体还可以表示一个线程。

Linux 提供了 clone 系统调用,clone 的工作原理和 fork 基本相同,但是新进程不是独立于父进程的,而是可以与其共享某些资源。比如内存数据,打开的文件和安装的信号处理程序。clone 是用来实现线程的,但是仅仅靠它是不够的,还需要用户空间库来提供完整的线程实现。

命名空间

命名空间提供了虚拟化的一种轻量级实现,是我们可以看到系统全局属性的不同视图。原来,Linux 以及其他 Unix 系统中,许多资源都是全局的,例如 PID,这样所有人所能查看到的 PID 列表就是相同的。同时,每个进程都有一个对应的用户 UID,相同 UID 的进程之间可以互相影响,比如在一个进程中关闭另一个相同 UID 的进程,不过如果两个进程的 UID 不同的话,这类操作是受限的,除非当前使用的是 root 用户,root 用户基本上可以做任何事。这样看上去没有什么问题,每个进程通过 UID 限制了其权限,使其无法操作非法的资源,但是某些情况下,可能云提供商可能需要给予某一用户所有 Linux 资源的访问权限,这就需要给他 root 权限,但是为了有效利用资源,又需要同一个物理主机上运行多个这样的用户。这时候就需要使用 KVM 这样的虚拟化技术,来为不同的用户提供一个虚拟空间,但是这种解决方案在资源的利用上做得不是很好,每个用户都要运行一个独立的内核。

而命名空间则另辟蹊径,所需资源少,一台物理机就只运行一个内核,所有全局资源都可以通过命名空间的方式分组,各个命名空间内的用户只能看到同组内的资源。本质上,命名空间建立了系统的不同视图,命名空间以分层的结构来组织,某一命名空间内全局资源映射到父命名空间的一个资源。换句话说,子命名空间的资源在父命名空间中能够被看到。下图描述了 PID 的命名空间管理方式,同一命名空间下 PID 不会重复,但是多个命名空间的不同进程 PID 可能会相同,换句话说<PID + 命名空间>的二元组是全局唯一的。
namespace
除了上述这种带层级结构的命名空间之外,还有一些比较简单的量,它们是平坦的非层级的,在这种情况下,父子命名空间是没有关系的,比如 hostname。

在进行 fork 或 clone 时可以指定是否共享父进程的命名空间,还是建立新的命名空间,同时也可以通过 unshare 系统调用来将进程的某些部分从父进程中分离,其中也包括命名空间。通过这两种手段从父命名空间分离后,对于一些简单的量来说,子进程的改动就不会传播到父进程的命名空间,而父进程的修改也不会波及子进程。

在每个进程的描述信息中,包含一个 nsproxy 结构体,这里面保存了该进程的各类命名空间信息。
nsproxy

1
2
3
4
5
6
7
8
9
struct nsproxy {
atomic_t count;
struct uts_namespace *uts_ns; // 包含内核名称,版本,主机名等
struct ipc_namespace *ipc_ns; // 与进程间通讯 IPC 相关的信息
struct mnt_namespace *mnt_ns; // 装载的文件系统视图
struct pid_namespace *pid_ns; // 有关进程 ID 的信息
struct user_namespace *user_ns; // 用户相关命名空间参数
struct net *net_ns; // 网络相关命名空间参数
}

进程 ID 号

我们已经知道,每个 UNIX 进程都会被分配一个号码(PID),用于在命名空间中标识它。通过 fork 或者 clone 会自动由内核分配一个新的 PID。但是除了 PID 之外,一个进程还有其他的一些 ID:

  • TGID: 处于某个线程组的进程都有统一的线程组 ID,如果一个进程没有使用线程,则 TGID 等于 PID。在一个线程组中,主进程成为组长,TGID 等于组长的 PID。
  • PGID: 独立进程可以合并为进程组(pgrp),进程组成员的 pgrp 都是相同的,即组长的 PID。通过进程组,我们能够一次性向组内所有成员发送信号,管道连接的进程就从属于同一个进程组,当我们使用 CTRL + C 发送终止信号时,所有通过管道连接的进程都会关闭。
  • SID: 几个进程可以合成一个会话,会话中的所有进程都具有相同的会话 ID,它可以用于终端程序。

很显然,前面提到的命名空间增加了进程 ID 的管理复杂度。比如以层级结构组织的 PID,新建立一个命名空间时,父命名空间可以看到该子空间的 PID,而子空间内无法看到父空间的 PID。这就意味着,一个进程会有多个 PID,对于每个可以看到该进程的空间内都会有一个与之对应的 PID。

首先,内核本身和初始化命名空间中每个进程有一个唯一的 ID 称为全局 ID,对于上述的每种 ID 类型都有一个给定的全局 ID,保证整个系统中是唯一的。而对于某一特定的命名空间,都存在一个局部域内的 ID,我们称之为局部 ID,对于每个局部 ID,只在所属的命名空间内有效。

全局 PID 和 TGID 直接保存在 task_struct 中,而全局会话 ID 和全局进程组 ID 则保存在 task_struct->signal 中。除了这些全局 ID 之外,内核还要维护所有命名空间内的局部 ID,我们可以通过下图来了解内核是如何管理这些局部 ID 的。
pid-manage

所有进程 ID(包括 PID PGID SID) 的信息都通过一种叫做 pid 的结构体保存,所以一个 pid struct 可以代表多个类型的进程 ID(PID,PGID,SID),之所以没有 TGID 是因为 TGID 等于线程组的 PID,当需要获得 TGID 时,直接访问 task_struct->group_leader 的 PID 即可,所以我们这里着重讨论除了 TGID 之外其他 3 种 ID 类型的管理。

在上图中有 3 个 task_struct,我们假设它们是同一个进程组的 3 个进程,A 进程是组长,为了在一个 task_struct 结构中保存 3 种局部 ID(PID,PGID,SID),所以在 task_struct 中有一个 pids 数组(数据结构为 pid_link),数组的 0,1,2 号位置分别代表了局部 PID,局部 PGID,和局部 SID。从图中我们可以看到 A 进程的 pids[0](代表 PID)和 B C 进程的 pids[1] 都指向了同一个 pid 结构体,因为进程 A 是进程 BC 的进程组组长。
pid-manage
在 pid 结构体中,首先有一个 tasks 数组,它保存了所有使用了该 pid 结构体的 task_struct 链表(链表头),这个 tasks 数组存在 3 个元素,0,1,2 号元素分别代表 PID,PGID,SID 使用该 pid 结构体的 task_struct 链表(链表头),这有点像 task_struct 中的 pids 数组,数组中的 3 个元素分别代表了 PID,PGID 和 SID。我们回到 tasks 数组的讨论中来,这个地方有点绕,什么是使用该 pid 结构体的 task_struct 链表。我们以上图的例子来看,tasks[0](代表 PID) 指向了 A 进程,是因为 A 进程的 pids[0](代表 PID) 指向了该 pid 结构体,而 tasks[1](代表 TGID)指向了 B 进程,而 B 进程的又指向了 C 进程,这是因为进程 B C 的进程组 ID 使用了该 pid 结构体(还记得吗,前面我们假设 ABC 三个进程在同一个进程组,并且 A 为组长)。

不知道大家有没有理解 tasks 数组和 pids 数组的关系,我们换个角度来看,如果某个 task_struct 的 pids[N] 指向了一个 pid 结构体,那么通过该 pid 结构体的 tasks[N] 就能找到该 task_struct,因为 tasks[N] 指向了一个链表,该链表中包含了这个 task_struct。
pid-manage
除了 tasks 之外,pid 结构体还保存了 level 字段,它标识了该 pid 在命名空间中最大的深度,level = 2,就是说它最深级别为 2,在 level 0,level1,和 level2 中都有对应的 ID,后半段的 number 数组(数据结构为 upid)就对应了该 pid 在不同深度的命名空间中的属性,从图中我们可以看出在 level 0 的命名空间中 ID 为 289,level 1 中 ID 为 134,level2 中对应的 ID 是 45,ns 属性指向了命名空间结构体。

为了能够通过<PID + 命名空间>这个二元组快速找到对应的资源,内核还维护了一个散列表,散列表的 key 是<PID + 命名空间>,散列表的 value 是 pid 中的 upid 结构体。通过这个 upid 结构体就能顺藤摸瓜般地找到所有和该<pid + 命名空间>相关的所有资源信息。

除了管理这些进程 ID 之外,内核还要负责提供某种机制来生成唯一的 ID,这里我们只需要能生成唯一的 PID 即可,其他 ID 均可由 PID 派生出来。

  • PGID: 进程组组长的 PID
  • TGID:线程组组长的 PID
  • SID:会话领导进程的 PID

Linux 为了跟踪已经分配的和仍然使用的 PID,使用了一个大的位图,其中每个 PID 有一个比特位标识,PID 的值可以根据比特位在位图中的位置来确定。因此,分配一个空闲的 PID,本质上就是从位图中找到一个值为 0 的比特,接下来将该比特的值置为 1。反之,释放一个 PID 就将对应的比特位置为 0。

从建立进程的命名空间,一直到初始的全局命名空间,内核会为每个命名空间分别维护一个上述的位图,通过它来为每个命名空间分别创建一个局部 PID。

进程关系

前面我们已经或多或少的提到过,在 Linux 中进程之间是存在一个家族关系的,如果 A 进程创建了进程 B,则 A 进程称为父进程而 B 进程称为子进程。如果 A 进程又创建了一个进程 C,那么进程 BC 之间互为兄弟关系。
process-family

调度器实现

我们已经介绍了进程如何在内核中表示,以及多个进程之间怎么构建起关联关系。接下来该介绍一下调度器了,它负责控制进程之间怎么共享 CPU 时间。它既要让各个进程之间尽可能公平地分享 CPU 时间,同时又要考虑优先级。

在介绍实际的调度算法之前,我们不妨先来看一看一些一般性的知识,在 Linux 中有两种方法会激活调度,一种比较直接,比如进程打算睡眠或出于其他原因放弃 CPU;另一种是通过周期性的时钟中断触发的,这是以一个固定的频率进行,不时地检测是否有必要进行进程切换。在下面的介绍中,主动调度我们称为通用调度器,周期性调度我们称为核心调度器。
shceduler
这里 Linux 对调度行为进行了分层,在调度器这一层,主要进行和调度策略无关的逻辑,其主要调用下一层的调度器类来完成进程选择的任务,内核支持不同的调度策略:完全公平调度,实时调度,在无事可做时运行空闲进程。在选中下一个要运行的进程后,调度器要进行底层的任务切换,这往往与 CPU 架构有比较大的联系,这就通常需要配合汇编语言。有一点要注意的是,一个进程只会归某一个调度器类管辖。

进程优先级计算

1
2
3
4
5
6
7
8
9
10
11
12
struct task_struct {
...
int prio,static_prio,normal_prio;
unsigned int rt_priority;
const struct sched_class *sched_class;
unsigned int policy;
cpumask_t cpus_allowed;
struct list_head run_list;
unsigned int time_slice;
struct sched_entity se;
...
}
  • 在 task_struct 中,有 4 个成员来表示一个进程的优先级:prio 和 normal_prio 表示动态优先级,static_prio 表示进程的静态优先级,rt_priority 则和这三个不同,它只作用于实时进程。
    • 静态优先级(static_prio)是进程启动时分配的优先级,也可以通过 nice 等系统调用修改,它的取值范围是 -20 ~ 19。值越低优先级越高。
    • 普通优先级(normal_prio)表示基于静态优先级和调度策略计算出来的优先级。因此,即便普通进程和实时进程具有相同的静态优先级,其普通优先级也不同,在创建子进程时,子进程会继承普通优先级。
    • prio 则是调度器需要考虑的优先级,有些时候系统可能需要临时提高某一进程的优先级,因此需要这个变量来表示。由于该优先级的提高是临时的,因此静态和普通优先级不受影响。
    • rt_priority 表示实时进程的优先级,取值范围是 0 ~ 99,值越大优先级越高。
  • 每个进程除了优先级的标识外,还有一个 sched_class 字段表示该进程所属的调度器类。而进程的 policy 属性则表示了该进程的调度策略,Linux 支持 5 种可能的值:
    • SCHED_NORMAL: 用于普通进程,我们主要介绍该类进程,它通过完全公平调度器类来处理。
    • SCHED_BATCH:用于非交互,CPU 密集型批处理进程,它不会抢占另一个进程,因此不会打扰交互式进程。他也通过完全公平调度器类管理。
    • SCHED_IDLE:重要度比较低,调度权重最小,通过完全公平调度器类来处理。
    • SCHED_RR: 实现了一种循环调度,由实时调度器类负责。
    • SCHED_FIFO:先入先出调度,由实时调度器类负责。
  • cpus_allowed 是一个位域,用来限制进程可以在哪些 CPU 上运行。
  • run_list 和 time_slice 是循环实时调度器类使用的资源,run_list 表示循环调度任务的列表头(维护包含各个进程的一个运行表),而 time_slice 表示该进程可使用的剩余 CPU 时间。
  • se 字段表明 task_struct 是一个可调度实体,在 linux 中,不仅可以以进程作为调度目标,也可以把一个进程组作为调度目标,或者按用户作为调度目标,它们都可以通过调度器类进行调度,来保证一个各个调度实体之间的公平性,这里我们着重介绍以进程作为调度实体的情况。

在内核中,Linux 对优先级进行了转换,用户设定的静态优先级(static_prio),和实时优先级(rt_priority)被映射到了从 0 ~ 139 的范围内(normal_prio),根据进程的调度策略,会以不同的方式进行计算,0 ~ 99 对应了实时进程(rt_priority),100 ~ 139 对应了普通进程(static_prio)。
priority
至此我们知道了,normal_prio 是如何通过 static_prio 和 rt_priority 计算出来的,prio 属性是内核视情况临时提高进程优先级时设置的,这里我们先不展开介绍。有了这些信息,我们得明确一下内核在进行调度时,使用了哪个优先级作为参考。

1
2
3
4
5
6
7
8
9
static int effective_prio(struct task_struct *p)
{
// 先计算 normal_prio,如果是实时进程则根据 rt_priority 换算到 0 ~ 99,否则通过 static_prio 换算到 100 ~ 139
p->normal_prio = normal_prio(p);
// 如果内核改变了 prio 属性 并且其值达到了实时进程的阈值 100,则返回 prio 否则返回 normal_prio
if (!rt_prio(p->prio))
return p->normal_prio;
return p->prio;
}

在这里,我们先介绍了进程的优先级计算方案,这至关重要,因为无论是周期性调度还是主动调度,都要根据现有的进程优先级来分配 CPU 时间。明白了优先级的计算方法之后,我们开始看一看调度器这一层的活儿。

调度器

调度器分两类,周期性调度和主动调度。如果系统正在活动中,内核会按照频率 HZ 自动触发周期性调度。这个周期性的触发任务有两个作用:

  1. 管理内核中与整个系统和各个进程的度量相关的统计信息。
  2. 激活负责当前进程的调度类的周期性调度方法。

除了周期性调度外,在内核中的很多地方,如果要将 CPU 分配给另一个进程,都会直接调用主动调度器,比如在系统调用结束后,内核会检查当前进程是否设置了重新调度标志 TIF_NEED_RESCHED,前面介绍的周期性调度器可能就会设置该标志,举个例子:可能一个进程调用了一个花销较大的系统调用,在未开启内核抢占的情况下,其他进程无法抢占该系统调用,只会将该进程的 TIF_NEED_RESCHED 设置为 1,等其系统调用结束后,主动进行进程调度。

好了,现在回到实际的调度过程中来:

  1. 当要进行进程调度时,调度器首先获取该 CPU 上的就绪进程队列 rq,然后通知调度器类(put_prev_task)当前进程要被另一个取代了,注意这并不是将进程从就绪队列剔除,只是更新一些统计信息。
  2. 从调度器类中选取下一个要运行的进程(put_prev_task),如果没有其他进行可以调度的话,当前进程还会继续运行。但如果找到了下一个要运行的进程,就要开始进行硬件级的进程切换。
  3. 调度器通过 context_switch 进行进程的上下文切换,其下层的代码就和各个体系结构相关了。

在进行上下文切换时主要进行如下两个工作:

  1. 它会通过 task_struct->mm 更换内存管理上下文,主要包括加载页表,(部分或全部)刷出地址转换后备缓冲器(TLB),向内存管理单元(MMU)提供新的信息。这些都深入到 CPU 的细节中,我们就不深入介绍了。
  2. 切换处理器寄存器内容和内核栈(虚拟地址空间的用户部分在第一步中已经完成,其中就包括了用户态的栈,因此用户栈不需要显式地变更),此项工作在不同体系结构下差别很大,代码通常使用汇编语言。

有一点例外是,内核线程没有自身的用户空间内存上下文,所以它可能在某个随机进程的地址空间上执行,内核线程 task_struct->mm 为 NULL,从当前进程”借来”的地址空间记录在 active_mm 中。

到这为止,调度器这一层就介绍完了,我们回顾一下 Linux 是如何进行调度的,首先会有一个周期性的触发器来触发调度任务,这是通过硬件中断来进行了,它一般会以硬件的方式向 CPU 发送中断信号,CPU 会在执行下一条指令前,跳转到该中断信号对应的中断处理程序上(这个中断处理程序会调用调度器),也就是说这会强制打断当前运行的进程,你不必担心一个进程写一个死循环会一直占据 CPU。

然后,在调度器这里会判断当前是否需要进行进程切换,如果当前进程才刚开始运行没多久,显然没必要换入下一个进程,因为太频繁的进程调度会浪费 CPU 时间,如果存在下一个要运行的进程,它会先进行判断,当前进程是否能够被抢占:

  • 比如系统调用时可能就不能被抢占(除非开启内核抢占),这时候就需要将进程的 TIF_NEED_RESCHED 置为 true,等该进程的系统调用结束后,主动进行调度。
  • 如果当前进程在用户态执行用户代码,显然可以被抢占,这时候如果调度器类觉得该运行下一个进程了,那么就会开始进行上下文切换,前面刚详细介绍了切换过程,这里就不赘述了。
  • 如果现在正在执行某一中断处理程序,也不能被抢占,因为进程没法抢占中断处理程序,它具有最高执行优先级,这时会等待中断处理程序结束后,再择机进行调度(可能是主动的也可能是周期性调度的)

说完了周期性调度的职责,我们再看看主动调度的过程,主动调度可能发生在很多地方,比如系统调用结束时,就如前面说的会检查 TIF_NEED_RESCHED 标识来决定是否进行主动调度,此外还有进程被挂起(等待其他资源)等等。如果下层调度器类觉得需要进行进程调度时,它就会进行相关上下文切换。
shceduler
说完了不同调度器的职责,我们还要知道每个 CPU 上都会有一个就绪队列(执行进程队列),每个 CPU 上都对应了独立的一个调度器层(包括主动调度,和周期调度),调度器下层还存在多个调度器类,实时调度器类,完全公平调度器类,这些我们后面会介绍,这里先有一个概念就行。当前 CPU 的就绪队列中的每个进程都由某个确定的调度器类管辖。当要进行调度时,调度器层会帮我们进行调度器的选择。每个进程只能出现在一个 CPU 就绪队列中,因为不可能在多个 CPU 上同时运行一个进程。

希望各位同学读到这,能够对这个 Linux 进程有一个全局上认识,比如:Linux 如果管理进程的数据,什么时候进行调度,以及调度的完整过程,这里我们还没有介绍具体的调度算法,但是你要知道 Linux 中对调度算法分层就是为了将通用的部分抽象出来,这样以后切换调度算法时,能不影响这些通用的过程。在清楚地理解了这些通用过程后,我们接下来,就开始介绍 Linux 的两大调度算法,即两大调度器类的内容了。

调度器类

在调度器类这一层,Linux 将其抽象为一个接口,各个调度器类都实现了该接口,调度器类之间的层次结构是平坦的,它们之间的优先级关系是:实时>完全公平>空闲;当需要进行调度时,实时进程在完全公平进程之前处理,而完全公平进程优于空闲进程。

1
2
3
4
5
6
7
8
9
10
11
12
struct sched_class {
const struct sched_class *next;
void (*enqueue_task) (struct rq *rq,struct task_struct *p,int wakeup);
void (*dequeue_task) (struct rq *rq,struct task_struct *p,int sleep);
void (*yield_task) (struct rq *rq);
void (*check_preempt_curr) (struct rq *rq,struct task_struct *p);
struct task_struct * (*pick_next_task) (struct rq *rq);
void (*put_prev_task) (struct rq *rq,struct task_struct *p);
void (*set_curr_task) (struct rq *rq);
void (*task_tick) (struct rq *rq,struct task_struct *p);
void (*task_new) (struct rq *rq,struct task_struct *p);
}
  • enqueue_task:向就绪队列添加一个新进程,在进程从睡眠状态变成可运行时,会发生。
  • dequeue_task:提供逆向操作,将一个进程从就绪队列去除。事实上,在进程从可运行状态切换到不可运行状态时,就会发生该操作。内核有可能因为其他理由将进程从就绪队列去除,比如,进程的优先级可能需要改变。
  • yield_task:在进程想要自愿放弃对处理器的控制权时,可使用 sched_yield 系统调用。这导致内核调用 yield_task。
  • check_preempt_curr:用一个新唤醒的进程来抢占当前进程。例如,当等待某一事件的进程被唤醒时,会调用该函数,确认是否可以抢占当前运行的进程。
  • pick_next_task:用于选择下一个将要运行的进程
  • put_prev_task:在用另一个进程代替当前运行的进程之前调用。要注意,这些操作并不等价于将进程加入或撤出就绪队列的操作,如 enqueue_task 和 dequeue_task。相反,它们负责向进程提供或撤销 CPU。但在不同进程之间切换,那仍然需要执行一个底层的上下文切换。
  • set_curr_task:在进程的调度策略发生变化时,需要调用 set_curr_task。
  • task_tick:在每次激活周期性调度器时,由周期性调度器调用。
  • new_task:用于建立 fork 系统调用和调度器之间的关联。每次新进程建立后,则用 new_task 通知调度器。
完全公平调度器类

首先我们把注意力放在完全公平调度器类 CFS 上。在 CFS 中有一个虚拟时钟,它是用来度量进程在 CFS 中能得到的 CPU 时间。这个虚拟时钟是通过进程的实际运行时间和其负荷权重计算出来的,优先度越大的进程,它的 CPU 使用权重就大,在 Linux 中每个 static_prio 即 nice 值(-20 ~ 19)都有一个对应的 CPU 执行权重。

1
2
3
4
5
6
7
8
9
10
static const int prio_to_weight[40] = {
/* -20 */ 8876171755564834627336291
/* -15 */ 2915423254187051494911916
/* -10 */ 95487620610049043906
/* -5 */ 31212501199115861277
/* 0 */ 1024820655526423
/* 5 */ 335272215172137
/* 10 */ 11087705645
/* 15 */ 3629231815
}

上述数组中,就记录了从 nice 值到 CPU 执行权重之间的映射关系,相邻比例因子之间相差 1.25 倍,这样进程每降低一个 nice 值,则多获得 10% 的执行时间,每升高一个 nice 值,则放弃 10% 的执行时间。举个例子,假设 AB 进程的 nice 值都是 0,也就是说它们的执行权重都是 1024,每个进程的 CPU 份额就是1024 /(1024 + 1024)= 0.5,如果 B 进程 nice 值加一,就变成 820 / (1024 + 820) ≈ 0.45 这相较于 0.5 来说下降了 10 %。

前面我们说过虚拟时间是和其 CPU 权重相关的,具体是什么关系呢?它们的关系是 virtual_time = real_time * NICE_0_CPU_WEIGHT / CURRENT_CPU_WEIGHT,它以 NICE 值为 0 作为基准点,通过对应的 CPU 负载权重和 NICE 0 的比值,等比换算虚拟时间。
v-time-r-time
从图中我们可以看出,NICE 值越大意味着它的优先级越低,它的虚拟时钟走的越快,而 NICE 值越小它的虚拟时钟走得越慢。CFS 尽可能保证各个进程的虚拟时间的分配是公平的,这就间接地保证了优先级越高的进程,它能获得的实际 CPU 时间就越长。现在思绪有点乱的同学可以先停下来,捋一下这个关系。

接下来,我们看一看 CFS 是如何组织这些进程的虚拟运行时间,并如何利用它的,首先 CFS 会维护一个红黑树,它根据进程的虚拟运行时间来计算 key(虚拟时间越小越靠左),以进程作为 value。这也就是说,CFS 进程加入进程移除进程的时间复杂度为 O(logN)。该红黑树的最左节点,就是虚拟运行时间最小的进程,它会被最先进行调度。越重要的进程虚拟时间涨的越慢,它在红黑树的左侧停留的时间更长,所以它相对于其他进程会更容易被调度。但当进程运行时,其虚拟时间就会稳定的增加,这样它就会在红黑树中缓慢向右移动,这样其他进程就会被调度。
cfs-red-black
现在,我们通过红黑树对就绪队列进行了排序,越急迫需要 CPU 时间的进程(虚拟时间越小)越排在队列的前面,而 CFS 选择队列最左边的进程运行,实际上就是在消除对它的亏欠,毕竟它虚拟时间最短,相当于它执行的时间最少,我们理应让它先执行。这样就是 CFS 名称的由来,为了保证大家都一样的”公平”分配 CPU,当然这种”公平”是考虑到进程的优先级的。

这时候还会有一个问题,就是每个进程给挑选出来的进程分配多长时间的 CPU 呢?如果分配的太长,后面进程可能很久都不会得到运行,这样它可能就会”饿死”,这显然不是我们期望的,在 CFS 调度算法中没有时间片的概念,Linux 之前的调度算法是基于时间片的,每个进程可以被执行指定长度的时间片,时间片耗尽后调度下一个进程,现在的 Linux CFS 中有一个系统参数 sysctl_sched_latency,它代表了一个进程每个多久就至少需要被调度一次,我们称之为一个调度周期,它的默认值是 20 ms。除此之外,还有一个参数,描述了前面的 sysctl_sched_latency 对多大规模的进程数目生效,试想一下,如果一个机器上有一万个,我们显然很难保证,每个进程 20 ms 调度一次,那会意味着进程间的切换会过于频繁。所以这里我们还要引入一个 sched_nr_latency,它代表了一个调度周期中能处理的最大活动进程数,如果当前活动进程数超过该上限 sched_nr_latency,就需要根据它们的比值等比的扩大 sysctl_sched_latency,sysctl_sched_latency * running_task / sched_nr_latency

在一个调度周期内,CFS 中的所有活动进程会按照其相对权重分配 CPU 执行时长。想象一下,CPU 权重越大的进程,当 CFS 选它作为下一个要执行的进程时,会给它分配一个较长的 CPU 执行时间,但是因为其虚拟运行时间的计算也是要根据权重计算的,这样算下来,在一个调度周期内所有的进程最终虚拟时间增长会是相同的。没搞明白的同学,我再次建议你停下来捋一下思路。

明确了,CFS 如何组织运行队列后,我们来看一看完整的调度过程,假设这时候周期性调度器触发:

  1. 它先会更新一下当前进程的运行时间
  2. 然后看看运行队列中是否有其他可运行的进程,如果没有的话,自然需要让当前进程继续执行
  3. 如果有其他进程需要被调度,确认当前运行的进程其运行时间是否大于其分配的 CPU 时间
    • 如果当前进程执行时间已经大于其分配的 CPU 时间,则将 task_struct 中的 TIF_NEED_RESCHED 设为 true,核心调度器会在合适的时机发起调度(如果不能抢占调度,则等主动调度过程来进行相关操作,如果能抢占调度,则直接抢占调度,这点我们前面介绍过)
    • 否则,让当前进程继续运行

接下来,我们介绍一下当进程被唤醒时的操作过程。首先,内核要通过调度器类来确认新进程能否抢占当前运行的进程,注意这个过程不涉及核心调度器,如果被唤醒的进程是实时进程(由实时调度器类管理),而当前运行的进程是普通进程(由 CFS 管理),则会直接抢占,因为实时进程优先级大于普通进程。而如果两个进程都是普通进程,则会进行一个比较过程,如果当前进程才刚开始运行没多久,我们就不允许抢占,内核确保被抢占着至少获取一定的时间份额,试想一下如果没有这个限制,那么所有进程都不停地唤醒->睡眠->唤醒的话,会把大部分时间都花费在上下文切换上。那么每个进程至少要分配多大的时间份额呢?这个值通过 sysctl_sched_wakeup_granularity 控制,默认是 4 ms,注意这里指的是实际时间。

最后,我们看一看新进程的调度处理过程。在一个新进程启动时,默认会比父进程更先得到调度,试想一下新进程很可能是父进程通过 fork->exec 创建的,在调用 exec 之前这个过程中子进程还共享着父进程的资源(写时复制),如果父进程先于子进程得到调度,不就会涉及写时拷贝了吗,而如果子进程先调度并顺利执行了 exec,就避免了写时拷贝的性能损失。可以说 Linux 上的进程如此轻量级,主要是就是因为写时拷贝技术 + 子进程优先调度。子进程加入到运行队列后,会先计算进程的虚拟时间,virtual_time = run_queue->min_virtual_time + child_process_weight / run_queue->weight_sum * sysctl_sched_latency,注意 sysctl_sched_latency 会根据当前运行的进程数进行缩放,这里为了简化公式所以用 sysctl_sched_latency 代替。计算完,虚拟时间之后,会和父进程的虚拟时间进行比较,如果父进程的虚拟时间小于子进程,则会交换双方的虚拟时间,这样才能保证子进程先于父进程被调度,处理完所有的这些之后,将子进程放入红黑树中的合适位置,然后立即请求重新调度,这样父进程就会被换出并且子进程会先于父进程调度。

实时调度器类

讲完了完全公平调度器类后,我们再来看看实时进程的调度器类。按照 POSIX 的强制要求,除了普通进程外,Linux 还支持两种实时调度类。因为 Linux 的调度器分层,所以这两种调度器类可以很容易集成进内核中,而不需修改调度器层。

实时进程和普通进程有一个根本不同,就是如果系统有一个实时进程在运行,那么调度器总会先选择运行它,除非有一个优先级更高的实时进程要运行。

现有的两种实时调度器类:

  • 循环进程(RR):有时间片,其值在进程运行时会减少,就像普通进程,当时间片耗尽时,重置它们的时间片,并将其置于队尾,队列中的下一个实时进程开始执行。这确保了在同一优先级的多个进程之间总是依次执行。
  • 先进先出进程(FIFO):没有片,在被调度器选择后,可以运行任意长的时间。

很明显,如果实时进程编写的不好,系统就会变得无法使用。只要写一个死循环,循环体不进入睡眠即可。所以在编写实时应用时要多加小心。这里大家可能会问,前面不是说 CPU 周期性触发调度么,为什么这里写一个死循环就没法抢占了呢?这是因为,对于实时应用的处理策略是,低优先级不抢占高优先级,所以并不是内核没能力抢占,而是原则上不愿意抢占。

在实时调度器类这块的实现非常类似与原来的 O(1) 调度器,该调度器以时间复杂度为常数而著称,尽管前面提到的 CFS 时间复杂度是 O(logN),但是除非有大量进程同时处于可运行状态,否则调度器的性能影响可以忽略不计。

我们已经说过,实时调度器类按照优先级管理实时进程,高优先级具有绝对权威,所以 Linux 按照优先级的不同划分出了多个队列,每个优先级有一个对应的队列,为了能够按照优先级从高到低的顺序快速找到第一个有活动进程的队列,内核用一个 bitmap 来表述每个优先级是否存在活动进程,一个 bit 位代表了一个优先级。
rs
上图就是循环调度器类 RR 的数据管理格式,进程的入队出队都比较简单,就找到和优先级匹配的队列,然后入队或者出队即可,当队列不为空或者为空时,设置或者清除 bitmap 对应的位。注意,新进程总是排列在队列的尾部。

周期调度的过程同样很简单, FIFO 进程最容易,因为它可以运行任意时长,必须通过 yield 系统调用主动让出 CPU 给另一个进程。而如果是循环进程,则减少剩余时间片,如果时间片尚未耗尽,就什么也不做,如果时间片耗尽就重置为 DEF_TIMESLICE(100 * HZ / 1000,即 100ms),如果不是唯一的实时进程,则排列到队列尾部。通过设置 TIF_NEED_RESCHED 来让调度器层择机进行调度。

调度器增强

除了上述的调度内容外,Linux 还要考虑一些增强的功能,例如在多核处理器 SMP 上,内核必须考虑如下问题:

  • CPU 负荷要尽可能公平的分散在所有的处理器上。
  • 进程和系统的某些 CPU 获取需要一些亲和性,例如绑定在某一块 CPU 上执行。
    • Linux 提供了 sched_setaffinity 系统调用来修改进程与 CPU 的绑定关系。
  • 内核必须要能将一个进程从一个 CPU 移到另一个。

在 SMP 上内核必能能够支持负载均衡,实际上周期性调度函数会在执行完前面所说的工作后触发一个 SCHEDULE_SOFTIRQ 软中断,该终端会在适当的时机对当前 CPU 执行负载均衡任务。
soft-irq-schedule
就绪队列是特定于 CPU 的,内核为了给每个就绪队列提供一个负载均衡的机制,为每个就绪队列增加了一个迁移队列,可以接受迁移请求,这些请求就保存在迁移队列中。当某一 CPU 的就绪队列调度任务过于繁忙,或者被限制不能在本 CPU 上运行该进程,则会向其它 CPU 的就绪队列发送迁移请求。

那么此外,还有一点需要知道的是,所有的就绪队列被组织为调度域。这可以将物理上临近或共享高速缓存的 CPU 集结起来,应优先选择在这些 CPU 之间迁移进程。在内核中有很多参数可以调配相关内容,比如可以设置多长时间间隔才能发起负载均衡,导致队列需要重新负载均衡的最小不平衡条件等等。

负载均衡分两个方向进行,一个是前面所提到的周期性的负载均衡,它有一些限制,如果周期性的负载均衡效果不佳会触发主动负载均衡,它们之间有什么区别呢?我们不妨看看它们的工作内容。

周期性负载均衡先遍了所有调度队列,确认达到最低的不平衡条件,然后找到最繁忙的队列,将其中的某些任务移到自己的队列中,至于要移动哪些进程,就要参考前面的调度域条件和 CPU 亲和度条件等。除此之外,还要保证被迁移的进程没有处于运行状态,或者刚结束运行,因为这些情况下 CPU 高速缓存充满了该进程的数据,迁移之后这些高速缓存相当于被浪费了。注意这里它只会移动一些优先级比较低的进程,如果目标队列的所有进程优先级都过高,则将唤醒该 CPU (最忙 CPU)的主动迁移线程(一个内核线程,与 CPU 绑定,负责对应 CPU 上的进程迁移任务)进行主动负载均衡任务,并将自己的 CPU (空闲 CPU)号记录在目标就绪进程队列(最忙 CPU)中来表明希望主动负载均衡将进程已交给自己来运行(空闲 CPU)。

接下来迁移线程(最忙 CPU)会开始主动迁移任务,它会检查是否有其他 CPU (空闲 CPU)请求进行进程迁移,如果有它会尽可能地将自身的某个进程迁移到请求迁移的 CPU (空闲 CPU)上。完成主动迁移后,它会确认自己的迁移队列中是否有别的迁移请求,如果有,就完成该迁移任务,否则重新回到正常的进程调度中去。

总结一下,周期性负载均衡是把最忙 CPU 上运行的进程提取出来一些自己执行,而主动负载均衡是把自己的进程分给别的 CPU 执行。

除此之外,当用 exec 系统调用启动一个新进程时,是进行进程迁移的良好时机,因为这种进程不会出现高速缓存浪费的情况。它会挑选一个负载最小的 CPU 运行,这就可能会想起发送一个迁移请求。

前面我们提到过进程并不是内核调度的唯一目标,我们还可以对进程组和用户进行调度,调度器确认每个用户获得的 CPU 时间,然后该 CPU 时间又会在该用户的所有进程中以公平的方式分配。这就意味着如果一个用户的进程越多,那么每个进程分配的 CPU 就越少,单用户的总 CPU 时间和进程的多少无关。

除了通过用户组进行分配外,内核还提供了控制组 cgroups,该特性使得可以通过特殊文件系统 cgroups 来创建任意的进程集合,甚至可以分为多个层次。可用的 CPU 时间首先在控制组之间分配,然后在组内进行进程间分配。docker 就是通过该方式控制资源的使用的。
group-schedule
最后,我们来谈谈内核抢占,前面提到过这个概念,它能够让系统更平滑的切换进程。如上所述,在系统调用后返回用户状态之前,或者是内核中某些指定的点上,都会调用调度器。这确保除了一些明确指定的情况之外,内核是无法中断的,这不同于用户进程。如果内核处于相对耗时较长的操作中,比如文件系统或内存管理相关的任务,这种行为可能会带来问题。内核代表特定的进程执行相当长的时间,而其他进程则无法运行。这可能导致系统延迟增加,用户体验到“缓慢的”响应。如果多媒体应用长时间无法得到 CPU,则可能发生视频和音频漏失现象。

在编译内核时启用对内核抢占的支持,则可以解决这些问题。如果高优先级进程有事情需要完成,那么在启用内核抢占的情况下,不仅用户空间应用程序可以被中断,内核也可以被中断。切记,内核抢占和用户层进程被其他进程抢占是两个不同的概念!

内核抢占是在内核版本2.5开发期间增加的。尽管使内核可抢占所需的改动非常少,但该机制不像抢占用户空间进程那样容易实现。如果内核无法一次性完成某些操作(例如,对数据结构的操作),那么可能出现竞争条件而使得系统不一致。

因此内核不能在任意点上被中断。内核的某些易于出现问题的部分每次只能由一个处理器访问,这些部分使用所谓的自旋锁保护: 到达危险区域(亦称之为临界区)的第一个处理器会获得锁,在离开该区域时释放该锁。另一个想要访问该区域的处理器在此期间必须等待,直到第一个处理器释放锁为止。只有此时它才能获得锁并进入临界区。

如果内核可以被抢占,即使单处理器系统也会像是 SMP 系统。考虑正在临界区内部工作的内核被抢占的情形。下一个进程也在核心态操作,凑巧也想要访问同一个临界区。这实际上等价于两个处理器在临界区中工作,我们必须防止这种情形。每次内核进入临界区时,我们必须停用内核抢占。

那么内核如何跟踪它能否被抢占呢?在每个进程中都会有一个抢占计数器:preempt_count。该变量标识了是否可以被中断,如果该值为零则可以被中断,否则不行。每次内核进入重要区域,就会停止抢占,那时候就会将该值+1。当退出该区域时,会将该值-1。这里之所以使用 int 而不是 bool 是因为它允许嵌套进入临界区,只有退出所有临界区时才会允许内核抢占。

即便开启了内核抢占,如果抢占计数器大于 0,那么抢占仍然是停用的,因此内核不能被中断,该函数立即结束。如果在某些重要的点上内核停用了硬件中断(比如进入自旋锁时,为了防止中断引发死锁,会停用中断),以保证一次性完成相关的处理,那么抢占也是不可能的。irqs_disabled 会检测是否停用了中断,如果已经停用,则内核不能被抢占。

除了内核抢占之外,内核也在切换进程方面做了不少努力,例如在内核态处理长循环任务时,会在不重要的地方插入很多调度检查,如果发现当前进程需要被调度,即 TIF_NEED_RESCHED 标志为 true,则会进行主动调度过程。这样即便没有开启内核抢占,也能从系统调用中进行进程调度任务。

参考内容

[1]《Linux内核设计与实现》
[2]《Linux系统编程》
[3]《深入理解Linux内核》
[4]《深入Linux内核架构》
[5] Linux 内核进程管理之进程ID
[6] 服务器三大体系SMP、NUMA、MPP介绍
[7] Linux中的物理内存管理 [一]
[8] Linux内核中的page migration和compaction机制简介
[9] 物理地址、虚拟地址(线性地址)、逻辑地址以及MMU的知识
[10] 逻辑地址
[11] linux内核学习笔记-struct vm_area_struct
[12] Linux中匿名页的反向映射
[13] 系统调用过程详解
[14] 再谈Linux内核中的RCU机制
[15] Unix domain socket 和 TCP/IP socket 的区别
[16] Linux通用块设备层
[17] ext2文件系统结构分析
[18] linux ACL权限规划:getfacl,setfacl使用
[18] 查找——图文翔解RadixTree(基数树)
[19] 页缓存page cache和地址空间address_space
[20] rocketmq使用的系统参数(dirty_background_ration dirty_ratio)
[21] Linux内存调节之zone watermark
[22] Linux的内存回收和交换
[23] Linux中的内存回收[一]
[24] linux内存源码分析 - 内存回收(整体流程)
[25] Linux 软中断机制分析
[26] 对 jiffies 溢出、回绕及 time_after 宏的理解
[27] learn-linux-network-namespace
[28] 显式拥塞通知
[29] 聊聊 TCP 长连接和心跳那些事
[30] 关于 TCP/IP,必知必会的十个问题
[31] TCP协议三次握手连接四次握手断开和DOS攻击
[32] TCP 的那些事儿(上)
[33] TCP 的那些事儿(下)

贝克街的流浪猫 wechat
您的打赏将鼓励我继续分享!
  • 本文作者: 贝克街的流浪猫
  • 本文链接: https://www.beikejiedeliulangmao.top/linux/process-and-schedule/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
  • 创作声明: 本文基于上述所有参考内容进行创作,其中可能涉及复制、修改或者转换,图片均来自网络,如有侵权请联系我,我会第一时间进行删除。