深入分析Linux内核源代码阅读笔记 第四章、第五章

我的GIS/CS学习笔记：https://github.com/yunwei37/ZJU-CS-GIS-ClassNotes <一个浙江大学本科生的计算机、地理信息科学知识库 >

第四章 进程描述

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

进程定义：所谓进程是由正文段（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 中定义了如下一个联合结构：

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

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

当前进程（current 宏）:

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 宏，这个宏实现了进程之间的真正切换。