Linux Kernel: Abstract

1. 操作系统基本概念

操作系统是一个基本程序的集合，在这个集合中，最重要的程序称为内核（Kernel）。当操作系统启动时，内核被装载到 RAM 中。内核为操作系统提供了主要功能，一般把“内核”作为“操作系统”的同义词。

操作系统有两个目标：

1. 与硬件交互：为硬件平台上的低层可编程部件提供服务
2. 为用户程序提供执行环境

当用户程序想要使用硬件资源时，需要向操作系统发送请求；内核对这个请求进行评估，如果允许使用该硬件资源，则由内核代表与相关硬件进行交互。为了实现这种机制，操作系统依靠特殊的硬件机制来禁止用户程序直接与硬件交互；CPU 至少引入了两种执行模式：用户程序的非特权模式 & 内核的特权模式；在 Unix 中分别称为用户态（User Model）& 内核态（Kernel Model）。

1.1 多用户系统

多用户系统（Multiuser System）是指能够并发且独立地执行分别属于多个用户的应用程序的系统。

并发是多个应用程序能同时处于活动状态并且竞争各种资源，如 CPU，内存，硬盘等。独立是指每个应用程序能够执行自己的任务而不需要考虑其他应用程序的行为。

多用户系统需要具备以下特点：

• 用户身份认证机制
• 应用程序运行的保护机制：防止不同用户程序之间的干扰
• 分配给每个用户的资源的记账机制

上述安全机制的实现与 CPU 特权模式相关；Unix 是多用户系统

1.2 用户与组

在多用户系统中，每个用户在机器上都有私用空间，比如磁盘空间。

操作系统需要保证用户空间的私有部分仅仅对其拥有者是可见的

每个用户在操作系统中都有一个唯一标识，叫做用户标识符（User ID）；同时，为了与其他用户有选择地共享资料，每个用户可以是一个或者多个用户组的成员，组由用户组标识符唯一标识（User Group ID）。

每个文件也与一个用户组对应：比如同组用户可以读，其他用户不可读

Unix 系统中存在一个 root 用户，操作系统不对其进行进行任何限制，root 能够访问系统中的任何一个文件，干涉任意一个用户程序。

1.3 进程

进程（Process）是操作系统对正在运行程序的一个抽象。一个进程可以看作“程序执行的一个实例”或者“一个运行程序的执行上下文”。

每个进程都有一个地址空间（Address Space）：允许进程引用的内存地址集合。

在多用户系统中，多个进程能够并发执行，并且能够竞争系统资源；这种允许进程并发活动的系统被称为多道程序系统或者多处理系统。

进程与程序之间的关系：几个进程能够并发地执行同一个程序，而一个进程能够顺序执行多个程序

在单处理器系统上，在某一个时刻只能有一个进程占用 CPU；操作系统中的调度程序（Scheduler）用于协调进程的执行。在不同的操作系统中，进程的执行方式分为两种：

• 非抢占式：只有当进程自愿放弃 CPU 时，调度程序才能被调用
• 抢占式：CPU 可以被其他进程抢占；比如，操作系统记录每个进程占有 CPU 的时间，并周期性地激活调度程序

Unix 是具有抢占式进程的多处理系统

Unix 采用进程/内核模式。每个进程都认为自己是系统中的唯一进程，独占操作系统所提供的服务。当进程发出系统调用时，硬件就会把特权模式由用户态切换到内核态，之后进程以有限的目的开始一个内核过程的执行。当请求调用结束，内核过程迫使硬件返回到用户态，然后进程从系统调用的下一条指令继续执行。

2. Unix 文件系统概述

2.1 文件

Unix 文件是以字节序列组成的信息载体，内核并不解释文件的内容。文件被组织成一个树形结构的命名空间中：

除了叶子节点外，其他节点都表示目录名；目录节点包含它下面的文件及目录所有的信息。

文件名长度一般限制在 255 个字符内；同一个目录下的文件名不能相同

Unix 进程有一个当前工作目录，属于进程执行上下文，用于标识进程所用的文件目录。同时，进程使用路径名（Path Name）标识特定的文件。

”.”表示当前工作目录；“..”表示父目录

2.2 软链接与硬链接

包含在目录中的文件名就是一个文件的硬链接（Hard Link），简称链接。

在同一个目录或者不同的目录中，同一个文件可以有多个链接，因此对应多个文件名。

一个文件可以对应多个文件名，而一个文件名就是一个链接

$ ln P1 P2  # 为由路径 P1 标识的文件创建一个路径名为 P2 的硬链接

硬链接有两个限制：

1. 不允许给目录创建硬链接：会使得目录树变成环形图，导致不能通过文件名定位文件
2. 只有在同一个文件系统中的文件之间才能创建链接：Unix 系统中可能包含了多种文件系统

为了突破上面的两个限制，引入了软链接（Soft Link），也称为符号链接。符号链接是短文件（软链接也是文件），包含另一个文件的任意一个路径名。路径名可以指向任意文件系统的任意文件或者目录，甚至可以指向一个不存在的文件。

$ ln -s P1 P2 # 创建一个路径名为 P2 的软链接，P2 指向路径名 P1；对 P2 的引用都自动转化为对 P1 的引用

总结：硬链接相当于对源文件的直接引用，软链接是对源文件的间接引用。

2.2 文件类型

Unix 文件类型分为：

• 普通文件
• 目录
• 符号链接
• 面向块的设备文件
• 面向字符的设备文件
• 管道 & 命名管道
• 套接字

前三种是基本的文件类型；设备文件与 IO 设备及相关驱动程序有关；管道与套接字是用于进程间通信的特殊文件。

2.3 文件描述符与索引节点

Unix 文件的内容与文件描述信息是分开存储的：

1. 文件内容是由字节序列组成，不包含任何控制信息，如文件长度等
2. 文件的描述信息存储在索引节点（Index Node）中，每个文件都有自己的索引节点；文件系统用索引节点来标识文件

索引节点中包含的信息有：

• 文件类型
• 与文件相关的硬链接个数
• 以字节为单位的文件长度
• 在文件系统中用于标识文件的索引节点号
• 文件拥有者的 UID
• 文件的用户组 ID
• 访问权限和文件模式

2.4 文件操作的系统调用

当用户访问文件内容时，实际上是访问存储在硬件块设备上的数据。由于处于用户态的进程不能直接与底层硬件交互，所以每次文件操作必须在内核态下进行。

2.4.1 打开文件

fd = open(path, flag, mode); // flag 指定打开文件的方式（读，写，追加）

该系统调用创建一个“打开文件”对象，并返回文件描述符。

其中，打开文件对象包括：

• 文件操作的一些数据结构：表示文件当前位置的 offset；指定文件打开方式的一组标识
• 进程可以调用的一些内核函数指针

文件描述符表示进程与打开文件之间的交互，而打开的文件对象包含了与这种交互相关的数据。

同一个打开文件对象可以由同一个进程的几个文件描述符标识

多个进程同时打开一个文件时，文件系统会给每个进程分配一个单独的打开文件对象与单独的文件描述符。

2.4.2 访问打开的文件

对于普通的 Unix 文件，可以顺序访问，也可以随机访问；默认是顺序访问。

内核把文件指针存放在打开文件对象中

read（）与 write() 是从文件指针的当前位置开始操作；如果需要更新文件指针的值，必须显示调用 lseek()。

2.4.3 关闭文件

res = close(fd);

该方法用于释放与文件描述符相对应的打开文件对象。

进程终止时，内核会关闭所有仍然打开的文件

2.4.4 重命名与删除文件

res = rename(oldPath, newPath); // 更新了文件链接的名字
res = unlink(pathName); // 减少文件链接数，删除了对应的目录项；当链接数为 0 时，文件才会被真正删除

删除与重命名文件时，并不需要打开文件。这两个操作并没有对文件的内容进行更新，而是对目录的内容进行了更新。

3. Unix 内核概述

3.1 进程/内核模式

正如之前描述的，CPU 既可以运行在用户态，也可以运行在内核态。当应用程序在用户态下执行时，不能直接访问内核的数据机构与程序；当应用程序运行在内核态下是，便没有这些限制。

CPU 模型为从用户态转换到内核态提供了特殊的指令，反之亦然

进程是动态的实体，通常只有有限的生命周期。

内核本身并不是进程，而是进程的管理者。对于进程/内核模式假设：请求内核服务的进程使用系统调用（System Call）的特殊编程机制。每个系统调用都设置了一组识别进程请求的参数，然后执行与硬件相关的 CPU 指令完成从用户态到内核态的转换。

除了用户进程外，Unix 系统还包括了几个内核线程的特权进程，特点如下：

• 以内核态运行在内核地址空间
• 不与用户直接交互
• 系统启动时创建，一直处于活跃状态直到系统关闭

有几种方式可以使进程进行用户态与内核态的转换：

1. 进程进行系统调用
2. 正在执行进程的 CPU 发出一个异常（Exception）信号（如无效的指令），由内核代表产生异常的进程处理异常
3. 外围设备向 CPU 发出一个中断信号（Interrupt）以通知时间的发生（如 IO 操作已完成）；中断信号交由内核中的中断处理程序来处理
4. 内核线程被执行：内核线程运行在内核态

3.2 进程实现

每个进程都由一个进程描述符（Process Descriptor）表示，该描述符包含了进程当前状态的信息。

当进程暂停时，就把相关寄存器中的内容保存在进程描述符中，寄存器包括：

• 程序计数器 & 栈指针寄存器
• 通用寄存器
• 浮点寄存器
• 包含 CPU 状态信息的处理器控制寄存器
• 用来跟踪进程对 RAM 访问的内存管理寄存器

当进程被重新恢复执行时，内核将进程描述符中对应的字段装载到 CPU 寄存器中。

当进程等待某一个事件时，会被置入进程描述符等待队列中等待事件的发生。

3.3 可重入内核

Unix 内核是可重入（Reentrant）的，是指多个进程可以同时在内核态下执行。

在单处理器系统上只有一个进程在运行，但是可以有多个进程在内核态下被阻塞，比如等待 CPU或者 IO 操作完成

如果发生硬件中断，可重入内核就可以挂起正在执行的进程去响应中断，即使该进程正处于内核态。这种实现方式能够提高发出中断的设备控制器的吞吐量，否则该设备需要一直等待 CPU 直到 CPU 重新从内核态切换为用户态。

内核控制路径（Kernel Control Path）是指内核处理系统调用，异常或者中断所执行的指令序列。而可重入性内核可以使得 CPU 交错执行内核控制路径。

上图显示了交错与非交错的内核控制路径；其中

• User：在用户态下运行一个进程
• Excp：运行一个异常处理程序或者系统调用程序
• Intr：运行一个中断处理程序

3.4 进程地址空间

进程运行在私有地址空间中。处于用户态的进程涉及到私有栈，数据区，代码区；处于内核态的进程访问内核的数据区，代码区，但是使用另外的私有栈。

每个内核控制路径都引用自己的私有内核栈

进程间也能共享部分地址空间，实现进程间通信。另外，Linux 支持存在在磁盘上的文件部分映射到进程的部分地址空间中。

3.5 同步与临界区

为了实现可重入内核，需要引入同步机制，以防止不同的内核控制路径对同一个数据结构的访问出现不一致的状态。

对全局变量的安全访问一般是通过原子操作（Atomic Operation）实现。临界区（Critical Region）是指存在这样一段代码，进入这段代码的进程必须完成，之后另一个进程才能进入。

常见的几种同步内核控制路径的方式：

3.5.1 非抢占式内核

当进程在内核态执行时，不能被任意挂起，也不能被其他进程抢占。这样，在单处理器系统中，中断或者异常处理程序便不能修改内核数据结构，保证了数据的一致性。

局限：

1. 对于多处理器系统，非抢占式方式仍然不能避免不同 CPU 上的内核控制路径并发访问同一个数据结构
2. 非抢占式内核会降低系统的执行效率

3.5.2 禁止中断

单处理器系统中还有一种同步机制：在进入临界区前禁止所有硬件中断，离开后再重新启用中断。

局限：

1. 如果临界区执行耗时比较大，那么在较长时间内会使得硬件处于冻结状态
2. 禁止中断只会对本地 CPU 起作用，在多处理器系统中，还需要结合其他同步方式

3.5.3 信号量

信号量（Semaphore）是一个广泛使用的同步机制；其仅仅是一个与数据结构（临界区）相关的计数器，所有内核线程在访问这个数据结构之前都需要检查信号量。信号量可以看作一个对象，组成如下：

• 一个整数变量
• 一个等待进程的链表
• 两个原子方法：down() & up()

down()：对信号量的值减 1，如果新值小于 0，那么就会把正在运行的进程加入到该信号量链表中，然后阻塞该进程（调用调度程序）

up()：对信号量的值加 1，如果新值大于或者等于 0，则激活该信号量链表中的一个或者多个进程

执行流程如下：

每个需要保护的数据结构（临界区）都有一个相关的信号量，初始值为 1。当内核控制路径试图访问该数据结构时，首先对信号量执行 down() 操作，如果信号量的新值不是负值，则允许访问；否则将内核控制路径的进程阻塞并添加到信号量链表中。当另一个进程访问数据结构结束时，执行 up() 操作，同时允许信号量链表中的一个或者多个进程继续执行。

3.5.4 自旋锁

信号量机制虽然有效，但是会比较耗时：内核需要将进程插入到信号量链表中，之后再挂起进程。在完成这两个操作时，其他的内核控制路径可能已经释放了信号量。因此对于执行临界区耗时较小的情况来说，可以推荐使用自旋锁（Spin Lock）。

自旋锁与信号量类似，但是没有进程链表；当一个进程发现锁被其他进程持有时，它就执行一个紧凑的循环执行进行自旋，直到锁能够被获取。

3.5.5 避免死锁

当使用内核信号量比较多的情况时，很可能会出现死锁（DeadLock）的状态：受影响的进程或者内核控制路径完全处于冻结的状态。

为了减少内核控制路径交错执行时出现死锁的概率，有些操作系统通过按规定的顺序请求信号量来避免死锁。

3.6 信号与进程间通信

Unix 信号（Signal）是一种把系统事件上报给进程的机制。系统事件分为两种

1. 异步通告：如终端输入 ctrl-c，内核会向前台进程发出中断信号
2. 同步错误或者异常：如进程访问内存非法地址时，内核会向进程发送异常信号

进程对收到的信号的处理方式有：

1. 忽略该信号
2. 异步地执行一个指定的过程（信号处理程序）

同时，如果进程不指定处理方式，内核就会根据信号类型的不同，有五种默认的执行操作：

• 终止进程
• 将进程上下文与地址空间 core dump，并终止进程
• 忽略信号
• 挂起进程
• 恢复进程

Unix 在用户态下的进程间通信机制有：信号量，消息队列，共享内存等。

该信号量与内核中的信号量类似，之不过是在用户态下；消息队列可以通过指定的队列允许进程之间交换消息；共享内存为进程之间交换和共享数据提供了最快的方式。

3.7 进程管理

系统调用 fork()：创建新的进程；_exit()：终止进程；exec()：装入一个新的程序。

fork() 创建子进程时，使用的是写时复制技术，把内存页的复制延迟到最后一刻。

3.8 内存管理

3.8.1 虚拟内存

虚拟内存（Virtual Memory）是一种抽象，作为一种逻辑层处于应用程序内存请求与硬件内存管理单元（Memory Management Unit）之间；虚拟内存的优势有：

• 多个进程可以并发执行
• 应用程序所需的内存大于实际可用物理内存时也可以运行
• 程序只有部分代码装入内存时进程也可以执行
• 允许进程访问可用物理内存的子集
• 程序可重定位（可以把程序放在物理内存的任何地方）
• 进程可以共享库函数或者内存映像

虚拟内存系统主要是虚拟地址空间（Virtual Address Space）的概念。当进程使用虚拟地址时，内核与 MMU 协同定位其在内存中的实际物理地址。

虚拟内存通过把可用 RAM 划分成大小为 4KB or 8KB 的页框，并且引入页表来指定虚拟地址与物理地址之间的对应关系。

一块连续的虚拟地址请求可以通过分配一组非连续的物理地址页框来实现

3.8.1 进程虚拟地址空间处理

进程的虚拟地址空间包括了进程可以引用的所有虚拟内存地址。内核分配个进程的虚拟地址空间由以下内存区组成：

• 程序可执行代码
• 程序的初始化数据 & 未初始化数据
• 初始程序栈（用户态栈）
• 共享库
• 堆（程序动态请求的内存）

通过请求调页（Demand Paging）的内存分配策略可以使得进程在其页还没有加载到内存时就可以执行；当进程访问一个不存在的页时，MMU 就会产生一个异常，之后异常处理程序会为其分配一个空闲页框并加载数据。

3.9 设备驱动程序

内核通过设备驱动程序与 IO 设备交互。

设备驱动程序包含在内核中

通过设备驱动程序，内核可以以统一的方式对待所有的设备，并且通过相同的接口访问这些设备。