# 深入分析 Linux 内核源代码阅读笔记

《深入分析 Linux 内核源代码》陈莉君 编著

<!-- TOC -->

- [深入分析 Linux 内核源代码阅读笔记](#深入分析linux内核源代码阅读笔记) - [第一章 走进 Linux](#第一章-走进-linux) - [第二章 Linux 运行的硬件基础](#第二章-linux-运行的硬件基础) - [i386 的寄存器：](#i386-的寄存器) - [内存地址：](#内存地址) - [段机制和描述符](#段机制和描述符) - [分页机制](#分页机制) - [Linux 中的分页机制](#linux-中的分页机制) - [Linux 中的汇编语言](#linux-中的汇编语言) - [第三章 中断机制](#第三章-中断机制) - [中断基本知识](#中断基本知识) - [中断描述符表的初始化](#中断描述符表的初始化) - [异常处理](#异常处理) - [中断处理](#中断处理) - [中断的后半部分处理机制](#中断的后半部分处理机制) - [第四章 进程描述](#第四章-进程描述) - [Linux 中的进程概述](#linux-中的进程概述) - [task_struct 结构描述](#task_struct-结构描述) - [task_struct 结构在内存中的存放](#task_struct-结构在内存中的存放) - [进程组织方式](#进程组织方式) - [内核线程 && 进程的权能和同步](#内核线程--进程的权能和同步) - [总结](#总结) - [第五章 进程调度与切换](#第五章-进程调度与切换) - [Linux 时间系统](#linux-时间系统) - [时钟中断](#时钟中断) - [Linux 实现时钟中断的全过程](#linux-实现时钟中断的全过程) - [Linux 的调度程序—Schedule（ ）](#linux-的调度程序schedule-)

<!-- /TOC -->

## 第一章 走进 Linux

Linux 内核具有下列基本特征：

- Linux 内核的组织形式为整体式结构
- Linux 的进程调度方式简单而有效
- Linux 支持内核线程（或称守护进程）
- Linux 支持多种平台的虚拟内存管理
- Linux 内核另一个独具特色的部分是虚拟文件系统（VFS Virtul File Systen）
- Linux 的模块机制使得内核保持独立而又易于扩充
- 增加系统调用以满足特殊的需求
- 网络部分面向对象的设计思想使得 Linux 内核支持多种协议、多种网卡驱动程序变得容易

本书所分析的 Linux 内核版本是 2.4 版的 2.4.16 版。

Linux 操作系统由 4 个部分组成：

- 用户进程：用户应用程序是运行在 Linux 操作系统最高层的一个庞大的软件集合
- 系统调用接口：在应用程序中，可通过系统调用来调用操作系统内核中特定的过程，以实现特定的服务
- Linux 内核：内核实际是抽象的资源操作到具体硬件操作细节之间的接口
- 硬件：包括了 Linux 安装时需要的所有可能的物理设备

其中，Linux 内核由 5 个主要的子系统组成

- 进程调度（SCHED）控制着进程对 CPU 的访问
- 内存管理（MM）允许多个进程安全地共享主内存区域
- 虚拟文件系统（Virtul File System，VFS）隐藏了各种不同硬件的具体细节
- 网络接口（NET）提供了对各种网络标准协议的存取和各种网络硬件的支持
- 进程间通信（IPC） 支持进程间各种通信机制

各个子系统之间相互依赖。

## 第二章 Linux 运行的硬件基础

操作系统是横跨软件和硬件的桥梁。

与硬件相关的代码全部放在 arch（architecture 一词的缩写，即体系结构相关）目录下。

### i386 的寄存器：

- 通用寄存器：8 个通用寄存器
- 段寄存器：6 个 16 位的段寄存器
- 状态和控制寄存器：标志寄存器（EFLAGS）、指令指针（EIP）和 4 个控制寄存器组成
- 系统地址寄存器： 4 个系统地址寄存器
- 调试寄存器： 8 个 32 位的调试寄存器 DR0~DR7
- 测试寄存器：两个 32 位的测试寄存器 TR6 和 TR7

### 内存地址：

在 8086 的实模式下，把某一段寄存器左移 4 位，然后与地址 ADDR 相加后被直接送到内存总线上，这个相加后的地址就是内存单元的`物理地址`，而程序中的这个地址就叫`逻辑地址`（或叫虚地址）。在 80386 的保护模式下，这个逻辑地址不是被直接送到内存总线，而是被送到`内存管理单元`（MMU）。

区分以下 3 种不同的地址:

- 逻辑地址：机器语言指令仍用这种地址指定一个操作数的地址或一条指令的地址
- 线性地址：线性地址是一个 32 位的无符号整数，可以表达高达 2^32（4GB）的地址
- 物理地址: 物理地址是内存单元的实际地址，用于芯片级内存单元寻址

### 段机制和描述符

在 80386 的段机制中，逻辑地址由两部分组成，即段部分（选择符）及偏移部分。

- 段是形成逻辑地址到线性地址转换的基础，包含：
  - 段的基地址（Base Address）
  - 段的界限（Limit）
  - 段的属性（Attribute）

描述符（Descriptor）：描述段的属性的一个 8 字节存储单元。

- 用户段描述符
- 系统段描述符

门也是一种描述符,有调用门、任务门、中断门和陷阱门 4 种门描述符。

各种各样的用户描述符和系统描述符，都放在对应的描述符表中。描述符表（即段表）定义了 386 系统的所有段的情况。

- 全局描述符表（GDT）
- 中断描述符表（IDT）
- 局部描述符表（LDT）

在实模式下，段寄存器存储的是真实的段地址，在保护模式下，16 位的段寄存器无法放下 32 位的段地址，因此，它们被称为选择符，即段寄存器的作用是用来选择描述符。

选择符有 3 个域：

- 索引域：用于指向全局描述符表中相应的描述符
- 选择域：局部还是全局
- 特权级：请求者特权级 RPL

386 的每一个段选择符都有一个程序员不可见（也就是说程序员不能直接操纵）的 88 位宽的段描述符高速缓冲寄存器与之对应。当选择符的值改变时，处理器自动装载不可见部分。

在没有分页操作时，寻址一个存储器操作数的步骤：

1.  在段选择符中装入 16 位数，同时给出 32 位地址偏移量（比如在 ESI、EDI 中等）。
2.  根据段选择符中的索引值、TI 及 RPL 值，再根据相应描述符表寄存器中的段地址和段界限，进行一系列合法性检查（如特权级检查、界限检查），该段无问题，就取出相应的描述符放入段描述符高速缓冲寄存器中。
3.  将描述符中的 32 位段基地址和放在 ESI、EDI 等中的 32 位有效地址相加，就形成了 32 位物理地址。

在保护模式下，32 位段基地址不必向左移 4 位，而是直接和偏移量相加形成 32 位物理地址（只要不溢出）

描述符投影寄存器：

每个段寄存器都有与之相联系的描述符投影寄存器。在这些寄存器中，容纳有由段寄存器中的选择符确定的段的描述符信息。段寄存器对编程人员是可见的，而与之相联系的容纳描述符的寄存器，则对编程人员是不可见的，故称之为投影寄存器。

Linux 中的段：

- Linux 内核的设计并没有全部采用 Intel 所提供的段方案，仅仅有限度地使用了一下分段机制。
- Linux 让所有的进程（或叫任务）都使用相同的逻辑地址空间，因此就没有必要使用局部描述符表 LDT。
- Linux 在启动的过程中设置了段寄存器的值和全局描述符表 GDT 的内容
- Linux 内核不区分数据段和堆栈段
- 内核代码段和数据段具有最高特权，因此其 RPL 为 0，而用户代码段和数据段具有最低特权，因此其 RPL 为 3

GDT 放在数组变量 gdt_table 中

```s
ENTRY(gdt_table)
	.quad 0x0000000000000000	/* NULL descriptor */
	.quad 0x0000000000000000	/* not used */
	.quad 0x00cf9a000000ffff	/* 0x10 kernel 4GB code at 0x00000000 */
	.quad 0x00cf92000000ffff	/* 0x18 kernel 4GB data at 0x00000000 */
	.quad 0x00cffa000000ffff	/* 0x23 user   4GB code at 0x00000000 */
	.quad 0x00cff2000000ffff	/* 0x2b user   4GB data at 0x00000000 */
	.quad 0x0000000000000000	/* not used */
	.quad 0x0000000000000000	/* not used */
	/*
	 * The APM segments have byte granularity and their bases
	 * and limits are set at run time.
	 */
	.quad 0x0040920000000000	/* 0x40 APM set up for bad BIOS's */
	.quad 0x00409a0000000000	/* 0x48 APM CS    code */
	.quad 0x00009a0000000000	/* 0x50 APM CS 16 code (16 bit) */
	.quad 0x0040920000000000	/* 0x58 APM DS    data */
	.fill NR_CPUS*4,8,0		/* space for TSS's and LDT's */
```

- 段的基地址全部为 0x00000000；
- 段的上限全部为 0xffff；
- 段的粒度 G 为 1，即段长单位为 4KB；
- 段的 D 位为 1，即对这 4 个段的访问都为 32 位指令；
- 段的 P 位为 1，即 4 个段都在内存。

这样 Linux 巧妙地绕过了逻辑地址到线性地址的映射

### 分页机制

分页机制在段机制之后进行，以完成线性—物理地址的转换过程。

- 分页机制由 CR0 中的 PG 位启用。如 PG=1，启用分页机制
- 分页机制管理的对象是固定大小的存储块，称之为页（page）
- 80386 使用 4K 字节大小的页

线性—物理地址的转换，可将其意义扩展为允许将一个线性地址标记为无效：

- 线性地址是操作系统不支持的地址
- 在虚拟存储器系统中，线性地址对应的页存储在磁盘上

分页机构：

两级页表结构，第一级称为页目录，第二级称为页表

页目录项：

- 第 31~12 位是 20 位页表地址
- 第 0 位是存在位
- 第 1 位是读/写位
- 第 2 位是用户/管理员位
- 第 3 位是 PWT（Page Write-Through）位
- 第 4 位是 PCD（Page Cache Disable）位
- 第 5 位是访问位
- 第 7 位是 Page Size 标志，只适用于页目录项

页面项：

第 6 位是页面项独有的，当对涉及的页面进行写操作时，D 位被置 1

线性地址到物理地址的转换：

1. 第一步，CR3 包含着页目录的起始地址，用 32 位线性地址的最高 10 位 A31~A22 作为页目录的页目录项的索引，将它乘以 4，与 CR3 中的页目录的起始地址相加，形成相应页表的地址。
2. 第二步，从指定的地址中取出 32 位页目录项，它的低 12 位为 0，这 32 位是页表的起始地址。用 32 位线性地址中的 A21~A12 位作为页表中的页面的索引，将它乘以 4，与页表的起始地址相加，形成 32 位页面地址。
3. 第三步，将 A11~A0 作为相对于页面地址的偏移量，与 32 位页面地址相加，形成 32 位物理地址。

扩展分页：它允许页的大小为 4MB

页面高速缓存：

为了提高速度，在 386 中设置一个最近存取页面的高速缓存硬件机制，它自动保持 32 项处理器最近使用的页面地址，因此，可以覆盖 128K 字节的存储器地址。有些书上也把页面高速缓存叫做 “联想存储器” 或 “转换旁路缓冲器（TLB）”

### Linux 中的分页机制

Linux 主要采用分页机制来实现虚拟存储器管理，原因如下：

- Linux 设计目标之一就是能够把自己移植到绝大多数流行的处理器平台
- Linux 的分段机制使得所有的进程都使用相同的段寄存器值

为了保持可移植性，Linux 采用三级分页模式而不是两级，为此，Linux 定义了 3 种类型的页表：

- 总目录 PGD（Page Global Directory）
- 中间目录 PMD（Page Middle Derectory）
- 页表 PT（Page Table）

尽管 Linux 采用的是三级分页模式，但我们的讨论还是以 Intel 奔腾处理器的两级分页模式为主，因此，Linux 忽略中间目录层，以后，我们把总目录就叫页目录。

与页相关的数据结构及宏的定义：

- 表项的定义

  PGD、PMD 及 PT 表的表项:

  ```c
  #if CONFIG_X86_PAE
  typedef struct { unsigned long pte_low, pte_high; } pte_t;
  typedef struct { unsigned long long pmd; } pmd_t;
  typedef struct { unsigned long long pgd; } pgd_t;

  ```

  Linux 没有把这几个类型直接定义长整数而是定义为一个结构，这是为了让 gcc 在编译时进行更严格的类型检查。定义了几个宏来访问这些结构的成分:

  ```c
  #define pte_val（x） （（x）.pte_low）
  #define pmd_val（x）（（x）.pmd）
  #define pgd_val（x） （（x）.pgd）

  ```

  一个页面保护结构 pgprot_t 和一些宏，字段 pgprot 的值与图 2.24 页面项的低 12 位相对应，其中的 9 位对应 0 ～ 9 位:

  ```c

  typedef struct { unsigned long pgprot; } pgprot_t;
  #define pgprot_val（x） （（x）.pgprot）

  ```

  ```c
  #define _PAGE_PRESENT 0x001
  #define _PAGE_RW 0x002
  #define _PAGE_USER 0x004
  #define _PAGE_PWT 0x008
  #define _PAGE_PCD 0x010
  #define _PAGE_ACCESSED 0x020
  #define _PAGE_DIRTY0x040
  #define _PAGE_PSE 0x080 /* 4 MB （or 2MB） page, Pentium+, if present.. */
  #define _PAGE_GLOBAL 0x100 /* Global TLB entry PPro+ */

  ```

  页目录表及页表在 pgtable.h 中定义。

- 线性地址域的定义

  其中 PAGE_SHIFT 宏定义了偏移量的位数为 12，因此页大小 PAGE_SIZE 为 212 ＝ 4096 字节；PTRS_PER_PTE 为页表的项数；最后 PAGE_MASK 值定义为 0xfffff000，用以屏蔽掉偏移量域的所有位（12 位）。

  GDIR_SHIFT 是页表所能映射区域线性地址的位数，它的值为 22（12 位的偏移量加上 10 位的页表）；PTRS_PER_PGD 为页目录目录项数；PGDIR_SIZE 为页目录的大小,为 222，即 4MB；PGDIR_MASK 为 0xffc00000，用于屏蔽偏移量位与页表域的所有位。

  PMD_SHIFT 为中间目录表映射的地址位数，其值也为 22。

  ```c
  #define PAGE_SHIFT 12
  #define PAGE_SIZE （1UL << PAGE_SHIFT）
  #define PTRS_PER_PTE 1024
  #define PAGE_MASK （~（PAGE_SIZE-1））

  #define PGDIR_SHIFT22
  #define PTRS_PER_PGD 1024
  #define PGDIR_SIZE （1UL << PGDIR_SHIFT）
  #define PGDIR_MASK （~（PGDIR_SIZE-1））

  #define PMD_SHIFT 22
  #define PTRS_PER_PMD 1
  ```

- 对页目录及页表的处理

  在 page.h，pgtable.h 及 pgtable-2level.h3 个文件中还定义有大量的宏，用以对页目录、页表及表项的处理

  - pgd_none（）函数直接返回 0，表示尚未为这个页目录建立映射，所以页目录项为空。
  - pgd_present（）函数直接返回 1，表示映射虽然还没有建立，但页目录所映射的页表肯定存在于内存（即页表必须一直在内存）
  - pte_present 宏的值为 1 或 0，表示 P 标志位。
  - pgd_clear 宏实际上什么也不做
  - pte_clear 就是把 0 写到页表表项中
  - 对页表表项标志值进行操作的宏：这些宏的代码在 pgtable.h 文件中

### Linux 中的汇编语言

AT&T 的 386 汇编语言

- 在 AT&T 中，寄存器前冠以“％”，而立即数前冠以“\$”
- 在 AT&T 中，十六进制立即数前冠以“0x“
- Intel 与 AT&T 操作数的方向正好相反，在 AT&T 中，第一个数是源操作数，第二个数是目的操作数。
- 在 AT&T 中，内存单元操作数用“（）”括起来。
- AT&T 间接寻址方式可能更晦涩难懂一些：%segreg:disp（base,index,scale）。这种寻址方式常常用在访问数据结构数组中某个特定元素内的一个字段，其中，base 为数组的起始地址，scale 为每个数组元素的大小，index 为下标。如果数组元素还是一个结构，则 disp 为具体字段在结构中的位移。
- AT&T 的操作码后面有一个后缀，其含义就是指出操作码的大小。
- 以.S 为扩展名的文件是“纯”汇编语言的文件。

一些 AT&T 汇编语言的相关：

- GNU 汇编程序 GAS（GNU Assembly）和连接程序
- AT&T 中的节（Section）：至少需要有以下 3 种节
  - section .data
  - .section .bss
  - section .text
- 汇编程序指令（Assembler Directive）：以句点（.）为开头，后跟指令名（小写字母）
  - .ascii "string"...
  - .byte 表达式
  - .fill 表达式
  - .globl symbol
  - .quad bignums
  - .rept count
  - .space size , fill
  - .word expressions
  - .long expressions
  - .org new-lc , fill
- gcc 嵌入式汇编：`__asm__ __volatile__ （"<asm routine>" : output : input : modify）;`
  - `"<asm routine>"`为汇编指令部分
  - 输出部分（output），用以规定对输出变量（目标操作数）如何与寄存器结合的约束（constraint）
  - 输入部分（Input）：输入部分与输出部分相似，但没有“＝”。
  - 修改部分（modify）:这部分常常以“memory”为约束条件，以表示操作完成后内存中的内容已有改变
  - 指令部分为必选项，而输入部分、输出部分及修改部分为可选项
- 一些常用的 386 汇编指令及其功能:
  - 位操作指令
  - 控制转移类指令
  - 数据传输指令
  - 标志控制类指令
  - 逻辑类指令
  - 串操作指令
  - 多段类操作指令
  - 操作系统类指令

## 第三章 中断机制

中断控制是计算机发展中一种重要的技术，最初它是为克服对 I/O 接口控制采用程序查询所带来的处理器低效率而产生的。

- 外部中断（或硬件中断）
- 内部中断（或叫异常）

本章主要讨论在 Intel i386 保护模式下中断机制在 Linux 中的实现。

### 中断基本知识

实模式和保护模式最本质的差别就是在保护模式引入的中断描述符表。

中断向量：

Intel x86 系列微机共支持 256 种向量中断。

- 异常：既不使用中断控制器，又不能被屏蔽
  - 故障（Fault）
  - 陷阱（Trap）
- 中断
  - 外部可屏蔽中断（INTR）
  - 外部非屏蔽中断（NMI）

Linux 对 256 个向量的分配如下：

- 从 0~31 的向量对应于异常和非屏蔽中断
- 32~47 的向量（即由 I/O 设备引起的中断）分配给屏蔽中断。
- 剩余的从 48~255 的向量用来标识软中断。
- 128 用来实现系统调用。

- 外设可屏蔽中断：

  Intel x86 通过两片中断控制器 8259A 来响应 15 个外中断源。

  中断控制器 8259A 执行如下操作：

  1. 监视中断线，检查产生的中断请求（IRQ）信号。
  2. 如果在中断线上产生了一个中断请求信号。
  3. 把接受到的 IRQ 信号转换成一个对应的向量。
  4. 把这个向量存放在中断控制器的一个 I/O 端口，从而允许 CPU 通过数据总线读此向量
  5. 把产生的信号发送到 CPU 的 INTR 引脚——即发出一个中断
  6. 等待，直到 CPU 确认这个中断信号，然后把它写进可编程中断控制器（PIC）的一个 I/O 端口；此时，清 INTR 线
  7. 返回到第一步

- 异常及非屏蔽中断

  异常就是 CPU 内部出现的中断，也就是说，在 CPU 执行特定指令时出现的非法情况。非屏蔽中断就是计算机内部硬件出错时引起的异常情况。Intel 把非屏蔽中断作为异常的一种来处理。

  当某个异常被响应后，CPU 清除 eflag 的中 IF 位，禁止任何可屏蔽中断。

  Intel x86 处理器发布了大约 20 种异常（具体数字与处理器模式有关）。每个异常都由专门的异常处理程序来处理。

* 中断描述符表

  在实地址模式中，CPU 把内存中从 0 开始的 1K 字节作为一个中断向量表。

  改叫做中断描述符表 IDT，其中的每个表项叫做一个门描述符（Gate Descriptor）

  - 任务门（Task gate）
  - 中断门（Interrupt gate）：关中断
  - 陷阱门（Trap gate）：不关中断
  - 系统门（System gate）：这是 Linux 内核特别设置的，用来让用户态的进程访问 Intel 的陷阱门

  CPU 中增设了一个中断描述符表寄存器 IDTR，用来存放中断描述符表在内存的起始地址

相关汇编指令：

- 调用过程指令 CAL
- 调用中断过程指令 INT
- 调用中断过程指令 INT
- 中断返回指令 IRET
- 加载中断描述符表的指令 LIDT

### 中断描述符表的初始化

Linux 内核在系统的初始化阶段要进行大量的初始化工作，其与中断相关的工作有：

- 初始化可编程控制器 8259A
- 将中断向量 IDT 表的起始地址装入 IDTR 寄存器，并初始化表中的每一项。

外部中断向量的设置：

8259A 中断控制器的初始化

```c
void __init init_8259A(int auto_eoi)
{
	unsigned long flags;

	spin_lock_irqsave(&i8259A_lock, flags);

	outb(0xff, 0x21);	/* mask all of 8259A-1 */
	outb(0xff, 0xA1);	/* mask all of 8259A-2 */

	/*
	 * outb_p - this has to work on a wide range of PC hardware.
	 */
	outb_p(0x11, 0x20);	/* ICW1: select 8259A-1 init */
	outb_p(0x20 + 0, 0x21);	/* ICW2: 8259A-1 IR0-7 mapped to 0x20-0x27 */
	outb_p(0x04, 0x21);	/* 8259A-1 (the master) has a slave on IR2 */
	if (auto_eoi)
		outb_p(0x03, 0x21);	/* master does Auto EOI */
	else
		outb_p(0x01, 0x21);	/* master expects normal EOI */

	outb_p(0x11, 0xA0);	/* ICW1: select 8259A-2 init */
	outb_p(0x20 + 8, 0xA1);	/* ICW2: 8259A-2 IR0-7 mapped to 0x28-0x2f */
	outb_p(0x02, 0xA1);	/* 8259A-2 is a slave on master's IR2 */
	outb_p(0x01, 0xA1);	/* (slave's support for AEOI in flat mode
				    is to be investigated) */

	if (auto_eoi)
		/*
		 * in AEOI mode we just have to mask the interrupt
		 * when acking.
		 */
		i8259A_irq_type.ack = disable_8259A_irq;
	else
		i8259A_irq_type.ack = mask_and_ack_8259A;

	udelay(100);		/* wait for 8259A to initialize */

	outb(cached_21, 0x21);	/* restore master IRQ mask */
	outb(cached_A1, 0xA1);	/* restore slave IRQ mask */

	spin_unlock_irqrestore(&i8259A_lock, flags);
}
```

中断描述符表 IDT 的预初始化：

1. 中断描述表寄存器 IDTR 的初始化
2. 把 IDT 表的起始地址装入 IDTR
3. 用 setup_idt()函数填充 idt_table 表中的 256 个表项
   - 在对 idt_table 表进行填充时，使用了一个空的中断处理程序 ignore_int()。
   - setup_idt()函数对 IDT 表进行填充

中断向量表的最终初始化：

在对中断描述符表进行预初始化后, 内核将在启用分页功能后对 IDT 进行第二遍初始化，也就是说，用实际的陷阱和中断处理程序替换这个空的处理程序。

- IDT 表项的设置是通过\_set_gate()函数实现的:
  - set_intr_gate
  - set_trap_gate
  - set_system_gate
- 对陷阱门和系统门的初始化:
  - trap_init()函数就是设置中断描述符表开头的 19 个陷阱门
- 中断门的设置: 由 init_IRQ（ ）函数中的一段代码完成的

### 异常处理

Linux 利用异常来达到两个截然不同的目的:

- 给进程发送一个信号以通报一个反常情况
- 处理请求分页

内核对异常处理程序的调用有一个标准的结构，它由以下 3 部分组成：

- 在内核栈中保存大多数寄存器的内容（由汇编语言实现）；
- 调用 C 编写的异常处理函数；
- 通过 ret_from_exception()函数从异常退出

进入异常处理程序的汇编指令在 arch/I386/kernel/entry.S 中.

中断请求队列的初始化:

让每个中断源都必须占用一条中断线是不现实的，在 Linux 设计中，专门为每个中断请求 IRQ 设置了一个队列，这就是我们所说的中断
请求队列。

- 中断线是中断请求的一种物理描述
- 中断线逻辑上对应一个中断请求号（或简称中断号）
- 第 n 个中断号（IRQn）的缺省中断向量是 n+32。

对于每个 IRQ，Linux 都用一个 irq_desc_t 数据结构来描述，我们把它叫做 IRQ 描述符；

- 在系统初始化期间，init_ISA_irqs()函数对 IRQ 数据结构（或叫描述符）的域进行初始化
- 中断控制器描述符 hw_interrupt_type 包含一组指针，指向与特定中断控制器电路（PIC）打交道的低级 I/O 例程
- 中断服务例程描述符 irqaction 是为多个设备能共享一条中断线而设置的一个数据结构。
- 中断服务例程 例如网卡和图形卡分别有其相应的中断服务例程。

在 IDT 表初始化完成之初，每个中断服务队列还为空。因此，在设备驱动程序的初始化阶段，必须通过 request_irq() 函数将对应的中断服务例程挂入中断请求队列。其中主要语句就是对 setup_irq()函数的调用，该函数才是真正对中断请求队列进行初始化的函数。

### 中断处理

本节要关心的主要内容是如何执行中断处理程序。

中断和异常处理的硬件处理：

- 在对下一条指令执行前，CPU 先要判断在执行当前指令的过程中是否发生了中断或异常：
- 如果发生了一个中断或异常，那么 CPU 将做以下事情：
  - 确定所发生中断或异常的向量 i（在 0 ～ 255 之间）。
  - 通过 IDTR 寄存器找到 IDT 表，读取 IDT 表第 i 项（或叫第 i 个门）。
  - 分两步进行有效性检查：
    - “段”级检查
    - “门”级检查
  - 检查是否发生了特权级的变化

Linux 对中断的处理：

Linux 把一个中断要执行的操作分为下面的 3 类：

- 紧急的（Critical）
- 非紧急的（Noncritical）
- 非紧急可延迟的（Noncritical deferrable）：由一些被称为“下半部分”（bottom halves）的函数来执行

所有的中断处理程序都执行 4 个基本的操作：

- 在内核栈中保存 IRQ 的值和寄存器的内容；
- 给与 IRQ 中断线相连的中断控制器发送一个应答，这将允许在这条中断线上进一步发出中断请求
- 执行共享这个 IRQ 的所有设备的中断服务例程（ISR）；
- 跳到 ret_from_intr（ ）的地址后终止。

与堆栈有关的常量、数据结构及宏：

- 常量
- 存放在栈中的寄存器结构 pt_regs
- 保存现场的宏 SAVE_ALL
- 恢复现场的宏 RESTORE_ALL
- 将当前进程的 task_struct 结构的地址放在寄存器中 GET_CURRENT（reg）

中断处理程序的执行：

假定外设的驱动程序都已完成了初始化工作，并且已把相应的中断服务例程挂入到特定的中断请求队列。又假定当前进程正在用户空间运行（随时可以接受中断），且外设已产生了一次中断请求。

1. 这个中断请求通过中断控制器 8259A 到达 CPU 的中断请求引线 INTR
2. CPU 在执行完当前指令后来响应该中断
3. CPU 从中断控制器的一个端口取得中断向量 I
4. 根据 I 从中断描述符表 IDT 中找到相应的表项
5. 从这个中断门获得中断处理程序的入口地址
6. 进行堆栈的切换
7. 禁用中断线
8. IRQn_interrupt
9. do_IRQ()
10. handle_IRQ_event（）
11. 中断服务例程

从中断返回：

中断、异常及系统调用的返回是放在一起实现的：

- ret_from_intr() 终止中断处理程序。
- ret_from_sys_call（ ）终止系统调用
- ret_from_exception（ ） 终止除了 0x80 的所有异常

### 中断的后半部分处理机制

内核的目标就是尽可能快地处理完中断请求，尽其所能把更多的处理向后推迟：内核把中断处理分为两部分：前半部分（top half）和后半部分（bottom half），前半部分内核立即执行，而后半部分留着稍后处理。

- 软中断（softirq）机制
- bottom half（简称 bh）机制
- Tasklet 机制

## 第四章 进程描述

本章将对进程进行全面的描述。

进程定义：所谓进程是由正文段（Text）、用户数据段（User Segment）以及系统数据段（System Segment）共同组成的一个执行环境。它代表程序的执行过程，是一个动态的实体。

程序定义：程序只是一个普通文件，是一个机器代码指令和数据的集合。程序是一个静态的实体。

进程实体由 3 个独立的部分组成：

- 正文段（Text）：存放被执行的机器指令。
- 用户数据段（User Segment）：存放进程在执行时直接进行操作的所有数据
- 系统数据段（System Segment）：该段有效地存放程序运行的环境

### Linux 中的进程概述

Linux 中的每个进程由一个 task_struct 数据结构来描述，任务（Task）和进程（Process）是两个相同的术语，task_struct 其实就是通常所说的“进程控制块”即 PCB。

- Linux 支持多处理机（SMP）
- Linux 也支持两种进程：普通进程和实时进程

task_struct 数据结构按其功能可做如下划分：

- 进程状态（State）；
- 进程调度信息（Scheduling Information）；
- 各种标识符（Identifiers）；
- 进程通信有关信息（IPC，Inter_Process Communication）；
- 时间和定时器信息（Times and Timers）；
- 进程链接信息（Links）；
- 文件系统信息（File System）；
- 虚拟内存信息（Virtual Memory）；
- 页面管理信息（page）；
- 对称多处理器（SMP）信息；
- 和处理器相关的环境（上下文）信息（Processor Specific Context）
- 其他

### task_struct 结构描述

进程执行时，它会根据具体情况改变状态；

- 可运行状态：要么正在运行、要么正准备运行。
- 等待状态：可中断的等待状态和不可中断的等待状态。
- 暂停状态
- 僵死状态

进程调度信息：调度程序利用这部分信息决定系统中哪个进程最应该运行

标识符（Identifiers）：每个进程有进程标识符、用户标识符、组标识符

进程通信有关信息（IPC，Inter_Process Communication）

进程链接信息（Links）：程序创建的进程具有父/子关系。

时间和定时器信息（Times and Timers）：实时定时器、虚拟定时器和概况定时器

虚拟内存信息（Virtual Memory）

页面管理信息：当物理内存不足时，Linux 内存管理子系统需要把内存中的部分页面交换到外存

对称多处理机（SMP）信息、和处理器相关的环境（上下文）信息（Processor Specific Context）

task_struct 结构是进程实体的核心，Linux 内核通过该结构来控制进程：首先通过其中的调度信息决定该进程是否运行；当该进程运行时，根据其中保存的处理机状态信息来恢复进程运行现场，然后根据虚拟内存信息，找到程序的正文和数据；通过其中的通信信息和其他进程实现同步、通信等合作。

task_struct 结构是一个进程存在的唯一标志。

### task_struct 结构在内存中的存放

task_struct 结构在内存的存放与内核栈是分不开的。

在／include/linux/sched.h 中定义了如下一个联合结构：

```c
union task_union {
  struct task_struct task;
  unsigned long stack[2408];
};
```

进程的 task_struct 结构所占的内存是由内核动态分配的.

当前进程（current 宏）:

```c
static inline struct task_struct * get_current（void）
{
  struct task_struct *current;
  __asm__（"andl %%esp,%0; ":"=r" （current） : "0" （~8191UL））;
  return current;
}
```

### 进程组织方式

为了对系统中的很多进程及处于不同状态的进程进行管理，Linux 采用了如下几种组织方式:

- 哈希表 pidhash 根据进程的 pid 可以快速地找到对应的进程
- 双向循环链表 反映进程创建的顺序，进程之间的亲属关系
  - 链表的头和尾都为 init_task
- 运行队列 runqueue 处于可运行状态的进程
- 等待队列 (通用双向链表) wait_queue
  - sleep_on( )
  - interruptible_sleep_on( )
  - try_to_wake_up（ ）

### 内核线程 && 进程的权能和同步

内核线程（thread）或叫守护进程（daemon）它们周期性地执行，例如，磁盘高速缓存的刷新，网络连接的维护，页面的换入换出等。

- 内核线程执行的是内核中的函数，而普通进程只有通过系统调用才能执行内核中的函数。
- 内核线程只运行在内核态，而普通进程既可以运行在用户态，也可以运行在内核态。
- 因为内核线程指只运行在内核态，因此，它只能使用大于 PAGE_OFFSET（3G）的地址空间。

Linux 用“权能（capability）”表示一进程所具有的权力。一种权能仅仅是一个标志，它表明是否允许进程执行一个特定的操作或一组特定的操作。

内核同步

- 信号量:

  进程间对共享资源的互斥访问是通过“信号量”机制来实现的。Linux 内核中提供了两个函数 down()和 up（），分别对应于操作系统教科书中的 P、V 操作。

- 原子操作:

  避免干扰的最简单方法就是保证操作的原子性，即操作必须在一条单独的指令内执行。有两种类型的原子操作，即位图操作和数学的加减操作:

- 自旋锁、读写自旋锁和大读者自旋锁：

  - 在单 CPU 上，可以用 cli/sti 指令来保护临界区的使用
  - 所谓自旋锁，就是当一个进程发现锁被另一个进程锁着时，它就不停地“旋转”，不断执行一个指令的循环直到锁打开。自旋锁只对 SMP 有用，对单 CPU 没有意义。
  - 有 3 种类型的自旋锁：基本的、读写以及大读者自旋锁。

### 总结

- 进程是由正文段（Text）、用户数据段（User Segment）以及系统数据段（System Segment）共同组成的一个执行环境。
- Linux 中用 task_struct 结构来描述进程，相对独立的内容为进程的状态
- task_struct 结构与内核栈存放在一起，占 8KB 的空间
- 当前进程就是在某个 CPU 上正在运行的进程，Linux 中用宏 current 来描述，也可以把 curennt 当作一个全局变量来用。
- 为了把内核中的所有进程组织起来，Linux 提供了几种组织方式，其中哈希表和双向循环链表方式是针对系统中的所有进程（包括内核线程），而运行队列和等待队列是把处于同一状态的进程组织起来
- Linux 2.4 中引入一种通用链表 list_head

## 第五章 进程调度与切换

本章首先讨论与时间相关的主题，然后才讨论进程的调度，最后介绍了 Linux 中进程是如何进行切换的。

### Linux 时间系统

操作系统建立的时间系统是整个操作系统活动的动力。

时间系统通常又被简称为时钟，它的主要任务是维持系统时间并且防止某个进程独占 CPU 及其他资源，也就是驱动进程的调度。

时钟硬件：

两个时钟源：

- RTC 时钟：也叫做 CMOS 时钟，它是 PC 主机板上的一块芯片
- OS（操作系统）时钟，产生于 PC 主板上的定时/计数芯片，只在开机时才有效，而且完全由操作系统控制

时钟运作机制：

RTC 和 OS 时钟之间的关系通常也被称作操作系统的时钟运作机制。

一般来说，RTC 是 OS 时钟的时间基准，操作系统通过读取 RTC 来初始化 OS 时钟，此后二者保持同步运行，共同维持着系统时间。在 Linux 中，RTC 处于最底层，提供最原始的时钟数据。OS 时钟建立在 RTC 之上，初始化完成后将完全由操作系统控制，和 RTC 脱离关系。

Linux 时间基准：

不同的操作系统采用不同的“时间基准”。定义“时间基准”的目的是为了简化计算，这样计算机中的时间只要表示为从这个时间基准开始的时钟滴答数就可以了。

Linux 的时间基准是 1970 年 1 月 1 日凌晨 0 点。

Linux 的时间系统：

Linux 中用全局变量 jiffies 表示系统自启动以来的时钟滴答数目。

`unsigned long volatile jiffies`

### 时钟中断

inux 的 OS 时钟的物理产生原因是可编程定时/计数器产生的输出脉冲，这个脉冲送入 CPU，就可以引发一个中断请求信号，我们就把它叫做时钟中断。系统利用时钟中断维持系统时间、促使环境的切换，以保证所有进程共享 CPU；利用时钟中断进行记帐、监督系统工作以及确定未来的调度优先级等工作。

### Linux 实现时钟中断的全过程

1. 可编程定时/计数器的初始化
2. 与时钟中断相关的函数
   - timer_interrupt（ ）
   - do_timer_interrupt()
   - do_timer（ ）
   - setup_irq（ ）
   - setup_irq（ ）
3. 系统调用返回函数
   - ret_from_sys_call（ ）

从总体上浏览一下时钟中断：

- 每个时钟滴答，时钟中断得到执行
- 时钟中断的主要工作是处理和时间有关的所有信息、决定是否执行调度程序以及处理下半部分
- 和时间有关的所有信息包括系统时间、进程的时间片、延时、使用 CPU 的时间、各种定时器
- 进程更新后的时间片为进程调度提供依据，然后在时钟中断返回时决定是否要执行调度程序
- 时钟中断要绝对保证维持系统时间的准确性，而下半部分这种机制的提供不但保证了这种准确性，还大幅提高了系统性能

### Linux 的调度程序—Schedule（ ）

调度的实质就是资源的分配。系统通过不同的调度算法（Scheduling Algorithm）来实现这种资源的分配。

一个好的调度算法应当考虑以下几个方面：

- 公平：保证每个进程得到合理的 CPU 时间。
- 高效：使 CPU 保持忙碌状态，即总是有进程在 CPU 上运行。
- 响应时间：使交互用户的响应时间尽可能短
- 周转时间：使批处理用户等待输出的时间尽可能短。
- 吞吐量：使单位时间内处理的进程数量尽可能多。

主要的调度算法及其基本原理：

1. 时间片轮转调度算法
2. 优先权调度算法
   - 非抢占式优先权算法（又称不可剥夺调度，Nonpreemptive Scheduling）
   - 抢占式优先权调度算法（又称可剥夺调度，Preemptive Scheduling）Linux 也采用这种调度算法。
3. 多级反馈队列调度
4. 实时调度

Linux 进程调度时机：

- 进程状态转换的时刻：进程终止、进程睡眠，进程要调用 sleep()或 exit()等函数进行状态转换，这些函数会主动调用调度程序进行进程调度
- 当前进程的时间片用完时（current->counter=0），由于进程的时间片是由时钟中断来更新的，因此，这种情况和时机 4 是一样的。
- 设备驱动程序，当设备驱动程序执行长而重复的任务时，直接调用调度程序。
- 进程从中断、异常及系统调用返回到用户态时， 如前所述，不管是从中断、异常还是系统调用返回，最终都调用ret_from_sys_call()，由这个函数进行调度标志的检测，如果必要，则调用调用调度程序。


每个时钟中断（timer interrupt）发生时，由 3 个函数协同工作，共同完成进程的选择和切换：

- schedule()：进程调度函数，由它来完成进程的选择（调度）。
- do_timer()：暂且称之为时钟函数，该函数在时钟中断服务程序中被调用
- ret_from_sys_call()：系统调用返回函数。

进程调度的依据：在每个进程的 task_struct 结构中有如下 5 项

- need_resched: 在调度时机到来时，检测这个域的值，如果为 1，则调用 schedule()
- counter: 进程处于运行状态时所剩余的时钟滴答数
- nice: 进程的“静态优先级”
- rt_priority: 实时进程的优先级
- policy: 从整体上区分实时进程和普通进程

进程可运行程度的衡量：

函数 goodness()就是用来衡量一个处于可运行状态的进程值得运行的程度。该函数综合使用了上面我们提到的 5 项，给每个处于可运行状态的进程赋予一个权值（weight），调度程序以这个权值作为选择进程的唯一依据。

进程调度的实现： void schedule（void）

- 如果当前进程既没有自己的地址空间，也没有向别的进程借用地址空间，那肯定出错。另外，如果 schedule()在中断服务程序内部执行,那也出错。
- 对当前进程做相关处理，为选择下一个进程做好准备。
- 从运行队列中选择最值得运行的进程，也就是权值最大的进程。
- 如果已经选择的进程其权值为 0，重新计算所有进程的时间片
- 进程地址空间的切换。
- 用宏 switch_to()进行真正的进程切换

### 进程切换

为了控制进程的执行，内核必须有能力挂起正在 CPU 上运行的进程，并恢复以前挂起的某个进程的执行。这种行为被称为进程切换，任务切换，或上下文切换。

硬件支持：

Intel i386 体系结构包括了一个特殊的段类型，叫任务状态段（TSS）。

每个任务包含有它自己最小长度为 104 字节的 TSS 段，在/include/ i386/processor.h 中定义为 tss_struct 结构；每个 TSS 有它自己 8 字节的任务段描述符。

另外一个数据结构，这就是 thread_struct 结构；

任务门中包含有 TSS 段的选择符。当 CPU 因中断而穿过一个任务门时，就会将任务门中的段选择符自动装入 TR 寄存器，使 TR 指向新的 TSS，并完成任务切换。在 Linux内核中，TSS 并不是属于某个进程的资源，而是全局性的公共资源，只更换 TSS 中的 SS0 和 ESP0，而不更换 TSS 本身，也就是根本不更换 TR 的内容。

进程切换：

前面所介绍的 schedule() 中调用了 switch_to 宏，这个宏实现了进程之间的真正切换。