linux kernel

Linux内核分析（一）内核简介

Posted by lan_cyl on June 25, 2016

Linux是类Unix操作系统大家庭的一员。Linux出现的时候已经有很多商业Unix系统了：System V Release 4(SVR4), BSD4.4, Digital Unix, AIX, HP-UX, Solaris, Mac OS X. 除了Linux外，还有些其他的开源类Unix内核，例如FreeBSD, NetBSD, OpenBSD.

Linux最初是Linus Torvalds 1991年 为自己的IBM个人机（基于Intel 80386微处理器）开发的操作系统。Linus现在仍致力于Linux系统的改进，更新多种硬件的驱动开发，协调全世界上千个Linux开发者的行动。过去几年，开发者实现了Linux在多种架构上的使用，包括Alpha, Itanium, AMD64, PowerPC, zSeries等等.

Linux内核不包含所有的Unix应用，例如：文件系统工具集、窗口系统、图形桌面、系统管理员命令行、文本编辑器、编译器等等，但是这些都有开源应用，可以自行安装在任一基于Linux的系统下。

因为Linux仅仅是一个内核，所以很多用户都使用商业的发行版，来得到一个完整的Unix操作系统。Linux源代码一般位于 /usr/src/linux 文件夹，也可以从官网下载。

Linux Versus Other Unix-Like Kernels

所有的商业类Unix系统都源自于SVR4或者4.4BSD，都基于一些共同的标准，例如IEEE’s Portable Operating Systems base on Unix(POSIX), X/Open’s Common Applications Environment(CAE)。这些标准仅指定应用程序接口(API)，不对内核的内部设计做任何限制。

为了定义公共的用户接口，类Unix系统通常会共享基本的设计思想和特征，Linux也一样。因此学习Linux也能很好的帮你理解其他类Unix系统。

2.6版的Linux内核，旨在兼容IEEE POSIX标准。这也意味着很多现存的Unix应用程序可以稍作修改甚至不做修改，直接在Linux系统上编译运行。更甚于，Linux包含了现代Unix操作系统的所有特征，例如：虚拟内存、虚拟文件系统、轻量级进程、Unix信号量、SVR4 进程间通信、支持对称多处理器(SMP)系统等等。

Linux源于Unix，但是不局限于任一Unix变体，他从多种不同的Unix变体中选择最好的特性和设计。

下面列出了一些对比：

单内核 Monolithic Kernel

  • Linux是单内核的，大部分Unix也是。单内核的所有代码(VFS, IPC, Scheduler, Memory Allocation, Device Drivers, etc)全部在内核空间执行，微内核只有部分内核代码(file system, device drivers, etc)以内核态执行。当然Linux支持模块操作，但是会把模块代码载入内核空间执行。优势就是大家都在内核空间执行，能减少进程间通信的压力。参见Why is Linux called a monolithic kernel? – stackoverflow、為什麼 Linux 不用微內核？ – 知乎

Modules

  • 传统的Unix内核都是静态编译链接的，主要的商业Unix系统里也只有SVR4.2和Solaris内核有类似的模块化机制。Linux内核会根据需要动态加载、卸载模块代码。

Kernel threading

  • 一些Unix内核，比如Solaris和SVR4.2/MP，被组织成内核线程集合。一个内核线程是一个可独立调度的可执行上下文；可能跟一个用户程序关联，也可能仅仅执行一些内核函数。内核线程上下文切换的开销更小，因为内核线程总是在公共地址空间上操作。Linux以受限的方式使用内核线程执行一些定期的内核函数；

Multithreaded application support

  • 一个多线程的用户程序可以包含很多轻量级进程(lightweight process, LWP)，这些进程可以共享内存地址空间、物理内存页、打开的文件等。Linux将LWP视为基本的可执行上下文，通过非标准的系统调用 clone() 来创建可共享资源的LWP作为一个线程，没有线程的单独数据结构。而所有的商业类Unix系统的LWP都基于内核线程实现。Linux多线程

Preemptive kernel

  • 当编译的时候开启“Preemptible Kernel”选项的时候，Linux 2.6能任意地交织处于特权模式的执行流。除了Linux 2.6，很少有商业类Unix系统完全支持可剥夺内核的。抢占式内核设计。

Multiprocessor support

  • 有些Unix kernel变体利用了多处理器系统的优势。Linux 2.6支持不同内存模型的对称多处理器(symmetric multiprocessing, SMP)，包括NUMA：这种系统能使用多种处理器，每个处理器能处理任何任务。虽然内核代码的一些部分仍然使用“大内核锁”来串行执行，但是公平来讲，Linux 2.6达到了对SMP的最优利用。

Filesystem

  • Linux的文件系统别具一格。没有什么特殊需要可以使用Ext2文件系统，Ext3能避免系统崩溃后冗长的文件系统检查。如果要处理很多小文件，可以选择ReiserFS文件系统。除了Ext3和ReiserFS，其他一些日志文件系统也可以被用于Linux，包括IBM AIX的日志文件系统(Journaling File System (JFS)), Silicon Graphcis IRIX的 XFS文件系统。借助于强大的面向对象的虚拟文件系统技术(启发于Solaris和SVR4)，向Linux移植新的文件系统比向其他内核容易的多。

STREAMS

  • Linux没有类似于SVR4的STREAM I/O 子系统，尽管这个子系统出现在大部分Unix内核里，并且成为写设备驱动、终端驱动和网络协议的最好的接口。我们有虚拟文件系统就够了。

商业Unix总是增加一些新特性来扩大市场，但是这些特性并不总是特别有用、稳定、具有创造性。事实上，现在的Unix内核相当臃肿。相反的，Linux(还有其他的开放源代码的操作系统)不受市场的限制，可以自由的根据设计者的意愿发展(主要是Linus Torvalds的意愿)。下面列出Linux比商业的Unix的更优秀的地方：

Linux是免费的 这就不用说了，不但免费还开源，源代码随便瞅

Linux的所有组件完全可定制 编译内核之前，可以通过配置项选择需要编译的特性。

Linux可以运行在非常低端、便宜的硬件平台上 可以使用4MB RAM的Intel 80386构建一个网络服务器

Linux功能强大 速度快，能充分利用硬件的特性。Linux的首要目标就是高效，因此Linus抛弃了商业Unix的很多设计，因为这些设计中有隐含的性能代价。

Linux开发者是优秀的程序员 Linux系统非常稳定，具有非常低的失败率合系统维护时间。

Linux内核小而紧凑 可以将包含少许系统程序的内核镜像放到一个1.44MB的软盘里，据我们所知，没有任何一个商业类Unix能从一个软盘里启动。

Linux跟很多操作系统高度兼容 能直接挂载大部分的文件系统；能使用多种网络层；引入合适的库，甚至能直接运行其他系统的应用程序。

Linux的支持很好 不管你信不信，Linux打补丁和升级比其他任何系统都容易。当你向一个新闻组或者邮件列表提交一个问题之后，数小时内就会得到回复。更甚者，新的硬件投向市场几个星期后设备驱动就出来了。相反硬件厂商仅会给很少的几个商业操作系统提供设备驱动，因此所有的商业类Unix变体都运行硬件组件的受限子集上。

Hardware Dependency

Linux试图将硬件依赖和硬件独立的代码分开，arch和include文件夹里面的子文件夹分别代表对不同硬件平台的支持。总之我们支持了超多的硬盘平台哦。

Linux Versions

Linux版本号的说明，总觉得用个图更好说明。

Basic Operatin System Concepts

计算机系统都包含操作系统，操作系统里最重要的就是内核了。系统启动的时候内核被加载到RAM中，包含很多关键的程序(系统运行所需的)。其他的应用都是不太关键的工具集，提供跟用户之间的多种多样的交互体验(以及用户交给计算的所有工作)，但是系统的基本形态和能力是由内核决定的。因此我们总是把“operating system”称为“kernel”的同义词。

操作系统要满足两个主要的目标

  • 跟硬件交互，服务于包含在硬件平台的所有底层可编程元素
  • 提供可执行环境

一些操作系统允许所有的用户程序直接跟硬件交互(例如MS-DOS)。相反，类Unix操作系统隐藏了用户执行程序的所有的底层细节(计算的物理成分)。当一个程序想使用硬件资源的时候，必须向操作系统提交一个请求。内核评估这个请求，如果选择授权这个资源，以用户程序的方式跟完整的硬件组件进行交互。

为了强化这个机制，现代操作系统依靠特殊硬件的可利用性特征(禁止用户程序直接跟底层硬件交互 或者访问任意的内存地址)。特别的，硬件引入至少两种不同的CPU执行模式：用户程序的非特权模式，内核的特权模式。Unix叫做用户模式和内核模式。

余下章节，将介绍Unix、Linux和其他操作系统设计的一些基本概念。Linux用户可能对这些概念比较熟悉，这些章节将试图更深入的探究。

Multiuser Systems

多用户系统 能并发地、独立地执行多个用户的不同应用。并发 意味着应用能同时启动并且竞争多种资源，例如CPU、内存、硬盘等。独立 意味着每个应用能执行自己的任务 而不关心其他用户程序。当然用户程序间的切换也会降低他们的速度，影响用户直观的响应时间。现代操作系统的很多复杂性(本文将会讨论的)，都是为了最小化每个程序执行的延迟，提供给用户最快的响应。

多用户操作系统必须包括下列特性：

  • 验证用户身份的认证机制
  • 保护机制 防止恶意用户程序阻塞其他程序的运行
  • 保护机制 防止恶意程序干涉或者收集其他用户的行为
  • 记账机制 限制每个用户使用的资源数量

为了强化安全保护机制，操作系统必须使用跟CPU特权模式关联的硬件保护，否则用户程序能直接访问系统单元，并且克服强加的限制。Unix是多用户系统，必须强化系统资源的硬件保护。

Users and Groups

在多用户系统里，每个用户在机器上都有一个私有的空间。

操作系统需要保证用户的私有空间只能被他自己看到。特别的，操作系统要保证没有用户能利用系统应用侵犯其他用户的私有空间。

每个用户使用独有的号码 User ID 或者 UID 来标示。用户通过用户名，密码 保护隐私。

为了有选择的跟其他用户共享资源，每个用户都可以成为一个或多个用户组 user groups 的成员。每个文件跟一个用户组关联。这样就可以设置 拥有者具有读写权限，组成员具有只读权限，其他人没有权限 拒绝访问。

任何类Unix操作系统都有一个特殊用户 即 root 或者 superuser 。系统管理员必须以root身份登陆才能管理用户账号、执行维护任务 如：系统备份和程序升级等等。root用户几乎可以做所有的事情，因为操作系统不会在root账号上施加常规的保护机制。特别的，root用户能访问系统上任意文件，能操作每个运行的用户程序。

Processes

所有的操作系统都有一个基础的抽象概念：进程。进程定义为“一个程序在执行过程中的实例”或者“一个运行程序的执行上下文”。传统的操作系统里，进程在一个地址空间里执行单一的指令序列，地址空间是进程被允许使用的内存地址。现代操作系统允许具有多个指令流的进程(也就是多线程程序)，多个指令序列在同一个地址空间执行。

允许并发的执行程序的系统被称为“多进程”。要将程序和进程区别开来哦，有些进程能并发的执行相同的程序，一个进程也能执行多个程序。

在单处理器系统上，只有一个CPU，所以每次只能执行一个进程。事实上，CPU数量总是很有限，因此某一时刻只有一小部分进程能执行。操作系统就有相应的调度器 scheduler ，选择可以执行的进程。有些系统只允许 nonpreemptable 非剥夺进程，也就是说只有当进程自愿放弃CPU的时候，调度器才会重新调度。但是多用户系统必须是可剥夺的 preemption(一般的，基于时间片和优先级进行抢占)，操作系统记录各个进程占有CPU的时间，然后阶段性的激活调度器。

Kernel Architecture

如前所述，大部分Unix内核是单内核的(Monolithic)：每个内核层次都被集成到整个内核程序里，并且以当前进程的形式在内核模式下运行。也就是所有的内核代码都在内核地址空间里以内核态的形式运行。

微内核(microkernel)操作系统需要一个很小的函数集合，一般包括同步原语、调度器、进程间通信机制。微内核上层的进程实现了其他操作系统层功能，例如内存分配、设备驱动、系统调用。

学术上看，微内核会因为层次间的消息传递损失部分性能，但也会因为层次化带来一系列好处，例如 开发出模块化的代码，定义清晰的软件接口，容易移植，能更好的使用RAM(random access memory) 因为会换出或者销毁不使用的系统进程。

综上，Linux内核虽然是单内核，但是使用模块(modules)来获得微内核的优点，内核运行时可动态加载/卸载模块代码。模块代码通常是文件系统，设备驱动，或者其他内核上层的特性。模块代码跟其他静态链接的内核函数一样，在内核态为当前进程服务。

模块化的主要优势：

A modularized approach

  • 模块访问的软件接口定义清晰。

Platform independence

  • 模块可能使用某些特殊的硬件特性，但却不依赖一个固定的硬件平台。例如 依赖于SCSI标准的磁盘驱动模块既可以在IBM兼容机上很好运行，又能在Hewlett-Packard的Alpha上。

节省主内存 Frugal main memory usage

  • 当某个模块的功能被使用的时候，就链接进来，当该功能不再被使用时，就从内核中卸载模块代码。对小的嵌入式系统特别有用。

No performance penalty

  • 一旦链接进内核之后，模块代码就跟静态链接的内核一样咯。因此模块函数被调用时，不需要明确的消息传递。优于微内核的实现

An Overview of the Unix Filesystem

Unix操作系统以文件系统为中心，文件系统中也包含一些有趣的特点。我们将回顾一些最重要的，后面章节会频繁的使用的。

Files

一个Unix文件是一个字节序列结构的信息容器，内核不解释文件的内容。很多应用程序库实现了更高层次的抽象，例如字段结构的记录。每个进程有一个当前工作目录字段(current working directory)，以此来使用相对路径。

文件夹里的一个文件名，就叫文件硬链接，简称链接。同一个文件可能会有位于多个文件夹下的链接。Unix命令 $ ln p1 p2 来创建一个新的硬链接p2.

硬链接有俩限制：

  • 不能给目录创建硬链接(环路问题)。
  • 只能在相同文件系统内创建硬链接。

为了克服上面的缺陷，引入了软连接(也叫符号链接 symbolic links)。符号链仅包含另一文件的任意路径名。这个路径名可以是任意文件系统下的任何文件或者目录地址，甚至是不存在的文件。Unix命令 $ ln -s p1 p2 来创建一个新的符号链接p2，任何对p2的引用都会自动转换为对p1的引用。

File Types

Unix文件有一下这些类型：

  • 常规文件
  • 字典
  • 符号链接
  • 面向块的设备文件
  • 面向字符的设备文件
  • 管道和命名管道(FIFO)
  • 套接字

前三个文件类型在任何Unix文件系统里都存在

设备文件都是跟I/O设备关联，为了把设备驱动集成到内核。例如 当一个程序访问一个设备文件的时候，就是直接跟设备文件关联的设备做交互

管道和套接字是做进程间通信使用的特殊文件

File Descriptor and Inode

Unix把文件的内容和文件信息分开。除了设备文件和特殊的系统文件之外，每个文件都是一个字节序列。文件不包含任何的控制信息，例如长度和EOF分隔符。

文件系统用来控制文件的所有信息都存在一个结构体inode里。每个文件都有自己的inode，用来唯一标示这个文件。

POSIX标准里规定Inode包含如下属性：

  • 文件类型 File type
  • 硬链接数
  • 文件的字节长度
  • 设备ID(包含这个文件的设备标示)
  • Inode编号，标示文件系统里的文件
  • 文件属主的UID
  • 文件属主所在组的GID
  • 一些时间戳，最后访问时间，最后修改时间
  • 访问权限和文件模型

Access Rights and File mode

文件的潜在用户可以分成三类：

  • 文件的拥有者(UID)
  • 文件所属用户组里的其他用户(GID)
  • 所有其他用户(others)

文件有三种访问权限：read, write, execute. 所有总共需要9个二进制位来表示三类用户的权限。此外还需要三个标示位 suid, sgid, sticky 来标示文件模式，具体含义如下：

suid(set User ID)

  • 进程执行一个文件的时候总是保持进程属主的UID，但如果可执行文件设置了suid标示，进程使用文件属主的UID。

sgid(set group ID)

  • 跟上面那个标识符含义类似

sticky

  • 如果可执行文件设置了sticky标示，内核会在这个程序执行完之后仍然保持这个程序。(过时了，现在使用共享代码页的方法，看第9章)

但用一个进程创建文件的时候，这个文件的属主ID是进程的UID，所属用户组ID既可以是创建这个文件的进程的GID，也可以是父目录的GID，取决于父目录的sgid标示。

File-Handling System Calls

所有的Unix内核都高度重视硬件块设备的处理速度。下面将讨论Linux处理文件的相关方法：

Opening a file

进程只能访问打开的文件，使用系统调用打开文件

// path: denotes the pathnameof the file to be opened
// flag: how the file be opend(e.g., read, write, read/write, append), or whether a nonexisting file should be created
// mode: the access rights of a newly created file
fd = open(path, flag, mode)

返回的fd叫文件描述符(file descriptor)，包含下面这些东西：

  • 一些文件处理的数据结构，例如标示集合表明文件被打开的状态，offset字段表示当前文件的偏移(也称为file opinter)，等等
  • 该进程能调用的文件操作类内核函数指针，有flag变量决定。

POSIX语法定义的一般特性：

  • 打开的文件-文件描述符-进程，同一个打开的文件对象可以在同一个进程中保有多个文件描述符。
  • 一些进程会并发的打开相同的文件。这时，会使用不同的文件描述符来区分。Unix文件系统没有提供I/O操作时的同步方法。但是有些系统调用如flock()能让进程对整个或者部分文件进行同步

Accessing an opended file

普通的顺序文件既可以顺序访问也可以随机访问，设备文件 命名管道(naming pipe/fifo)通常只能顺序访问。在打开的文件对象里存储有文件指针(file pointer, the current position at which the next read or write operation will take place)

默认都是进行顺序访问，read() write()系统调用总是对当前的文件指针位置进行操作。lseek()系统调用能改变文件指针的位置。文件被打开时，文件指针指向文件的第一个字节。

lseek()系统调用的用法：

// fd: 打开文件对象的文件描述符
// offset: 文件指针的偏移量
// whence: 指示偏移计算方法： 0 + offset(从文件头开始偏移)
//                         还是 current_file_pointer + offset(从当前位置开始偏移)
//                         还是 last_byte(直接偏移到文件尾)
newoffset = lseek(fd, offset, whence);

read()系统调用的用法，write()用法类似：

// fd: 打开文件对象的文件描述符
// buf: 进程地址空间里的缓存地址，用来缓存文件数据
// count: 指示要读取的字节个数
// nread: 实际读出来的字节数
nread = read(fd, buf, count);

Closing a file

当进程不在需要访问一个文件的时候，可以使用下面的系统调用res = close(fd);。当进程结束的时候，内核会关闭所有的打开的文件。

Renaming and deleting a file

重命名或者删除文件时，无需打开文件，事实上只在目录上做操作。

/**
* 重命名文件
*/
res = rename(oldpath, newpath);

/**
* 减少文件的链接次数，删除相应的目录结构。只有当引用次数为0的时候文件才会被删除。
*/
res = unlink(pathname)

An Overview of Unix kernels

内核实现一些服务和相应的接口，提供可执行环境供程序运行。程序使用这些接口从而无需直接跟硬件交互。

The Process/Kernel Model

前面已经提到了，CPU可以运行在内核态(Kernel Mode)或者用户态(User Mode)。事实上，某些CPU实现了多于两个的执行状态，但是Unix内核只使用内核态和用户态。

当一个程序以用户态运行的时候，不能直接访问核心数据结构或者内核程序，内核态进程没有这种限制。每个CPU都提供了内核态和用户态之间切换的指令。程序一开始以用户态运行，当需要请求内核服务的时候切换为内核态，内核完成用户请求之后再将进程切换为用户态。

进程是系统内有生命周期的动态实体，通过内核的一组程序控制进程的创建、消除、进程间同步。

内核本身不是一个进程，而是一个进程管理者。进程通过系统调用(system call)来请求一个内核服务。每个系统调用都会设置一组参数来标示进程的请求，然后执行硬件依赖的CPU指令将进程从用户态转换为内核态。

除了用户进程之外，Unix系统还包含一些特权进程叫内核线程(kernel threads)，特点如下：

  • 以内核态在内核地址空间运行
  • 不跟用户交互，所以不需终端设备
  • 一般在系统启动时创建，直到系统终止时结束

内核程序会通过以下方式激活：

  • 系统调用
  • 正在CPU执行的进程抛出异常(exception)信号，内核将代表抛出异常的进程 处理这个exception
  • 外围设备发出中断信号(interrupt signal)，提醒CPU事件的发生：一个需要注意的请求来了、一个状态转变了、I/O操作完成了等。每个中断信号都要由一个中断处理程序(interrupt handler)来处理。
  • 一个内核线程被执行。

Process Implementation

内核为了管理进程，使用进程描述符(process descripter)来代表进程，其中包含进程的当前状态信息。

当内核停止一个进程的执行时，会在进程描述符里保存当前寄存器的值，包括：

  • 程序计数器(program counter, PC)、栈指针(stack pointer, SP)
  • 通用寄存器
  • 浮点数寄存器
  • 处理控制寄存器(Processor Status Word, PSW)，包含CPU状态信息
  • 内存管理寄存器，跟踪RAM被进程访问情况

当内核重新执行这个进程的时候，会将进程描述的信息载入CPU寄存器。

Unix内核通过进程描述符队列来实现对不同事件的等待。每个队列等待一个特定的事件。

Reentrant kernels

Reentrant叫可重入，意思就是多个进程可以同时以内核态执行。

实现可重入的最简单方法是编写可重入的函数(reentrant functions)：这些函数只使用局部变量，不会修改全局数据结构。当然Unix内核不会做这样的限制(一些实时内核是这样做的)。

Unix内核可以包含非可重入的函数，并且使用锁机制保证一个非可重入函数在同一时间内只能被一个进程执行。每个内核态的进程只在自己的内存空间活动，不能干涉其他进程空间。

可重入的内核对硬件中断的处理很有优势。当一个设备发出一个中断信号，这个设备就会等待CPU处理这个中断。如果内核能快速响应，设备控制器就可以执行其他任务。内核的可重入性保证中断发生时，内核可立即停止正在执行的进程，转去处理中断请求。

内核控制路径(kernel control path)表示内核处理 系统调用、异常、中断时执行的指令序列。在下面几种情况下，内核控制路径会发生交织。

  • 一个用户进程发起了一个系统调用，而内核控制路径验证这个情况不能被立即满足；它会调用scheduler去选择一个新进程执行。这种情况下，两个控制路径以两个不同进程的方式被执行。
  • CPU在执行一个内核控制路径的时候，检测到异常，CPU暂停当前控制路径，开始执行一个合适的程序。例如异常情况是一个要访问的页面不在RAM中，CPU暂停当前控制路径，调用磁盘读写的程序从磁盘读取一个页面到RAM中。在这种情况下，两个控制路径以相同进程的方式被执行。
  • CPU在执行一个可中断的内核控制路径时发生了硬件中断。CPU暂停当前的控制路径转而执行其他的控制路径来处理这个中断。这种情况下，两个内核控制路径在同一个进程的可执行上下文里运行，并且消耗的CPU时间都算在这个进程里。然而，中断处理程序不必按当前进程的方式来运行。
  • 更高优先级的进程进来的时候，会暂停当前内核控制路径的执行，而去执行更高优先级的进程。当然内核需要在编译时支持抢占。

Process Address Space

每个进程在自己的私有地址空间运行。用户态的进程有私有的栈、数据、代码区域，当切换到内核态时，进程处理内核数据和代码，并且使用另外一个栈。

因为内核是可重入的，多个内核控制路径(each ralated to a different process)可能轮流执行。这样每个内核控制路径都应该使用自己的私有内核栈。

当一个程序被多个用户同时执行的时候，这个程序只会被载入内存一次，所有用户共享程序指令。但是程序数据不能被共享。这种类型的共享地址空间是内核为了节省内存自动进行的。

进程可以使用“shared memory”的技术，共享部分地址空间来进行进程间通信。

最后Linux还提供了mmap()系统调用，允许将一个文件或者设备内存映射到进程的部分地址空间。内存映射提供了读写方式之外的另一种传输数据方式。如果同一个文件被多个进程共享，每一个共享该文件的地址空间都包含该文件的内存映射。

Synchronization and Critical Regions

Critical Regions叫临界区：一个进程执行完之后其他进程才能进入的代码段。

要实现内核的可重入，必须使用同步：一个内核控制路径在操作一个内核数据结构时暂停了，那么其他内核控制路径不允许在这个数据结构上进行操作，除非这个结构被重置为一致状态。

Linux内核中的同步机制：原子操作、信号量、读写信号量和自旋锁，另外还有一些同步机制，如大内核锁、读写锁、大读写锁、RCU(Read-Copy Update)、顺序锁。

Kernel preemption disabling

彻底的简单的同步方法就是非剥夺的内核设计：一个处于内核态的进程不能被其他进程任意的暂停和代替。

内核态的进程可以自愿放弃CPU，但是该进程必须保证所有的数据结构一致性。

在多核心系统里，非剥夺的内核是无效的，因为运行在两个CPUs上的两个内核控制路径可以并发访问同一个数据结构。

Interrupt disabling

另外一个在单处理器里使用的同步机制是，进入临界区之前禁用所有的硬件中断，退出临界区的时候再启用中断。这个机制虽然简单，但远达不到最优。如果一个临界区很大，中断就会在一个相对长的时间内无效，潜在的造成所有的硬件冻结。

更重要的是，在多处理器系统里，这种机制根本无效。没有办法保证其他CPU访问被保护在临界区内的数据结构。

Semaphores

信号量机制，很有效的。信号量是一个跟一个数据结构关联的简单计数器，所有的内核线程在尝试访问这个数据结构之前检查这个信号量的值。每个信号量的组成如下：

  • 一个整数变量
  • 一个进程等待队列
  • 两个原子操作：down(), up()

down()方法减少信号量的值，当值小于0的时候，该方法将当前进程加入到等待队列并阻塞当前进程。up()方法增加信号量的值，当值>=0的时候，激活等待队列的一个或多个等待进程。

Spin locks

这叫自旋锁，Linux用的都是这种锁。用于临界区操作时间比较短的情况。这种情况下，如果用信号量来做同步，在信号量在将进程挂起，重新调度的过程中，其他内核控制路径已经做完临界区操作 并释放了信号量。因此，人们想到使用自旋锁，自旋锁没有等待队列，当锁被关闭的时候，进程会重复检查所状态，直到锁被动打开，然后执行。

当然自旋锁在单核环境下没有用。因为你在自旋的过程中，别的进程根本没法运行，也就不会释放锁咯。

Avoiding deadlocks

Linux使用数量非常有限的信号量类型，并以升序方式请求资源 来避免死锁发生。

Signals and Interprocess Communication

Unix信号，用来通知进程系统事件的发生。每个事件都有自己的信号值，通常用符号常量如SIGTERM表示。有如下两类系统事件：

  • Asynchronous notifications 例如：用户可以通过在terminal按中断键盘码(usually, CTRL-C)，来向前台进程发送中断信号SIGTERM。
  • Synchronous errors or exceptions 例如：当进程访问非法内存地址的时候，内核会向它发送SIGSEGV信号

POSIX标准定义了20来种不同的信号，其中两个是用户自定义的，可能被用于用户态进程以特权模式通信和同步。一般来说，进程会以一下两种方式处理信号：

  • 忽略
  • 异步执行特定的代码(信号处理程序)

如果进程没有指明处理方式，内核会以跟这个信号值相关联的默认行为处理。五种可能的默认行为如下：

  • 终止进程
  • 把执行上下文和地址空间内容写入文件(core dump)，然后终止进程
  • 忽略
  • 暂停该进程
  • 继续执行该进程，如果该进程停止的话

内核信号处理函数特别精巧，因为POSIX信号量允许进程暂时阻塞信号。另外，一些信号例如SIGKILL，SIGSTOP不能直接被进程处理也不能被忽略。

AT&T的Unix System V引入了较流行的 System V IPC 机制：semaphores, message queues, shared memory。用于用户态进程之间通信。

内核将这些实现作为IPC资源(IPC resources):进程通过系统调用shmget(), semget(), msgget()获得一个资源。跟文件一样，IPC资源也是持续存在的：必须被创建进程、当前用户或者超级用户进程 明确地释放。

共享内存交换和分享数据的速度最快。进程通过系统调用shmget()获得指定大小的共享内存。通过shmat()获得共享内存的开始地址。使用shmdt()从地址空间分离共享内存。

Process Management

Unix严格区分进程和进程执行的程序。使用fork(),exit()创建和终止进程；使用exec()系列命令加载一个新的程序。

调用fork()的进程作为父进程，而fork()函数创建的进程作为子进程。进程描述符里有指向父子进程的指针。

较原始的fork()函数会把父进程的数据和代码都复制给子进程，很耗时。现代的内核使用依赖硬件的写时拷贝方法，把页复制推迟到最后一刻(直到父进程或者子进程需要写页时)

exit()系统调用会终止当前进程，并释放当前进程占用的资源，向父进程发送SIGCHILD信号，并将进程置于zombie状态。等待父进程使用wait/waitpid获得zombie进程的状态之后，就可以彻底结束子进程。

Zombie Processes

wait()使进程等待子进程终止，返回终止的子进程的PID。

当执行这个进程调用的时候，内核首先检查是否有子进程终止。zombie状态来表示进程终止：进程会始终保持zombie状态，直到父进程调用wait()。wait()系统调用会从进程描述符里收集一些资源利用情况，收集完之后释放进程描述符。wait()系统调用会使父进程阻塞在wait状态。

很多内核还实现了waitpid()系统调用，允许当前进程等待特定子进程终止。还有一些其他的wait()的变体。

但是如果父进程终止了，并且没有调用wait会怎么样呢？就像我在shell启动一个后台进程，然后关闭shell，后台进程仍然运行。

解决方法是使用系统启动时创建的init系统进程。当进程终止时，内核将该进程的所有子进程的父指针指向init进程(寻找养父进程的机制似乎没有这么简单吧)。init进程监视他的所有子进程的执行 并周期性的执行wait()系统调用，从而消去所有的zombie进程。

Process groups and login sessions

现代操作系统包括进程组(process groups)、会话(login sessions)、守护进程等概念。

进程组是对一个任务(job)的抽象。例如，为了执行下面的命令行$ ls | sort | more，支持进程组的shell，例如bash，会给这三个相关进程ls,sort,more创建一个新的组。这样shell就把这三个进程当做一个任务。进程描述符包括一个process group ID字段。一个新创建的进程会放到父进程所在的组里。

非正式的说，会话包括在用户登陆后创建的第一个shell进程里创建的所有进程。一个进程组的所有进程必须在一个会话里。一个会话会包含多个同时活动的进程组。

Memory Management

内存管理是Unix系统最复杂的部分，本书超过1/3都是在描述Linux如何进行内存管理的。下面是一些主要的问题：

Virtual memory

虚拟内存作为应用程序内存请求与硬件内存管理单元之间逻辑层而存在。虚拟内存的意图和优势：

  • 多个进程可以并发执行
  • 可以运行所需内存超过可用物理内存的程序
  • 进程可以执行 仅部分代码被载入内存的程序
  • 每个进程都被允许访问可以物理内存的子集
  • 进程可共享一个库或程序的单个内存镜像
  • 程序可以浮动，即可被载入到物理内存的任何位置
  • 程序员可以写出独立于特定机器的代码，因为他们不需要关注于物理内存的组织方式

虚内存子系统的主要成分是虚拟地址空间。一个进程可用的内存集合不同于物理内存地址。内核和MMU负责将进程需要的虚拟地址转化为实际的物理地址。

如今的CPU包含硬件单元，可以直接将内存地址转为物理地址。为此RAM被分成大小为4或8KB的页(page frames)，使用页表来指明虚地址和实地址之间的关系。这个硬件单元使得内存分配更加容易，因为一个连续的虚地址块可以使用一组不连续的物理地址页表示。

Random access memory usage

所有Unix操作都将RAM分为两部分：几兆用于存储内核镜像，剩余的被虚拟内存系统管理，被用于下面三种情况：

  • 满足内核请求：buffers、descriptors、other dynamic kernel data structures
  • 满足进程的通用内存区域请求，对文件做内存映射
  • 通过caches优化磁盘和其他可缓存设备的体验

每个请求类型都很有价值，如何平衡各个类型的页面请求，内存不足时如何确定哪些页面最适合回收？没有简单的解决方案，也没有多少理论支撑，都是依靠经验对算法不断调整。

虚拟内存系统还要解决内存碎片(memory fragmentation)的问题。理想情况下，只有当页不足时，内存才会分配失败。但是内核总是强制使用物理上连续的内存区域，因此当可用内存足够大，却没有大的连续块的时候，内存分配也会失败。

Kernel memory allocator

内核内存分配器(KMA)是用来满足系统各部分内存区域请求的子系统。这些请求可能来自于其他内核子系统请求内核使用的内存，也可能来自于用户程序的系统调用 来增加用户程序的地址空间。一个好的KMA应该包含下面这些特性：

  • 一定要快
  • 最小化内存浪费
  • 尽量减少内存碎片
  • 能跟其他内存管理子系统协作，以便从他们中借入和释放页

基于几种不同算法技术的KMA：

  • Resource map allocator
  • Power-of-two free lists
  • McKusick-Karels allocator
  • Buddy system
  • Mach’s Zone allocator
  • Dynix allocator
  • Solaris’s Slab allocator

Linux在Buddy system上使用Slab分配器。

Process virtual address space handling

进程地址空间包括进程引用的所有虚拟内存地址。内核通常将进程的虚拟地址空间存放在链表memory area descriptors中。例如，exec()系列的系统调用开始执行一个程序的时候，内核分配给该进程的虚拟地址空间包括：

  • 程序的可执行代码
  • 程序的初始数据
  • 程序的未初始数据
  • 初始程序栈
  • 依赖的共享库的代码和数据
  • 堆内存(程序动态请求的内存)

所有最新的Unix系统都采用了这样的内存分配策略：请求分页(demand paging).使用请求分页，程序开始执行时可不包含任何物理内存页面。当程序访问一个不存在的页面时，MMU引起一个异常，异常处理者找到受影响的内存区域，分配一个页面，然后使用合适的数据初始这个页面。相似的，当程序运行时动态请求页面时，即使用malloc()/brk()系统调用时，内核仅仅更新进程堆内存区域的大小，等该虚拟内存页被访问时，产生异常，然后分配物理页，初始数据等。

虚地址也使写时拷贝(Copy On Write)成为可能。例如，一个新进程创建的时候，内核仅仅将父进程的页作为子进程的地址空间，但是大家都只能读。一旦父进程或者子进程尝试修改一个页的内容时，内核抛出异常，异常处理者分配一个新页给受影响的进程，然后以原始页的内容初始化这个新页。

Swapping and caching

为了扩大进程可用的虚拟内存地址 Unix系统使用磁盘交换分区。虚内存系统使用页作为基本交换单元，但进程引用一个换出的页(swapped-out)的时候，MMU抛出异常，异常处理者分配一个新页，并用磁盘上的内容初始化这个页。

为了提高系统的响应速度 Unix系统用物理内存作为硬盘和其他块设备的缓存(cache)。早期的Unix系统就实现了这种策略：尽可能的推迟回写到磁盘的时刻。sync()系统调用会强制进程磁盘同步，将所有的脏缓存回写到磁盘。另外为了避免数据丢失，系统也会阶段性的回写脏数据。

Device Drivers

内核通过设备驱动跟I/O设备交互。设备驱动包含在内核中，包括控制多个设备的数据结构和方法，例如硬盘、键盘、鼠标、显示器、网络接口和跟SCSI总线连接的设备。驱动都是通过特定的接口跟系统或者其他驱动交互，优势如下：

  • 专有设备可以被封装到专有模块里
  • 大家只需知道内核的一些接口，不用了解内核代码，就可以添加新的设备
  • 内核以统一的方式对待所有设备，并且通过相同的接口来访问
  • 使得动态加载和卸载设备驱动成为可能，以此来最小化RAM内核镜像的大小

参考：

  • Understanding the linux kernel 3E
  • Linux kernel development 3E
  • Advanced programing in the UNIX environment 3E
Creative Commons License
This work is licensed under a CC A-S 4.0 International License.