第二章：深入理解Linux编程 - 进程工作原理：剖析进程定义与特性、状态转换、关键数据结构、从创建到结束的过程、睡眠与唤醒机制、暂停与重启操作，以及处理器调度的核心概念

???????? 博主 libin9iOak带您 Go to New World.✨????

???? 个人主页——libin9iOak的博客????
???? 《面试题大全》 文章图文并茂????生动形象????简单易学！欢迎大家来踩踩~????
???? 《IDEA开发秘籍》学会IDEA常用操作，工作效率翻倍~????
???????? 希望本文能够给您带来一定的帮助????文章粗浅，敬请批评指正！????????

第二章 进程运行与调度

学习目的

要求学生了解进程的定义与特征、进程的状态与切换、进程管理的数据结构、进程的创建与终止、阻塞与唤醒、挂起与激活以及处理机调度的相关概念。

学习要求

了解：进程并发、进程调度方式、同步与互斥、实时（分时）操作系统调度。处理机调度的层次。

理解：进程概念：进程的定义与特征、进程的基本状态、进程的挂起状态、进程控制块、进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活。

掌握：进程的定义与特征、进程的基本状态、进程控制块、操作系统内核、进程的创建、进程的终止、进程的阻塞与唤醒、进程的挂起与激活、线程与进程、进程调度算法。进程调度的概念、调度队列模型、各种进程调度算法。

学习方法

许多概念十分抽象，需要同学具有抽象思维能力。处理机调度算法属于重难点问题，需要同学动手实践，帮助更好地理解原理。

概念和原理

2.1 进程的描述与特征

典型的进程定义有：（1）进程是程序的一次执行。（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动。（3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

PCB：为使程序（含数据）能独立运行，应为之配置一个专门的数据结构即进程控制块（PCB）；由程序段、相关的数据段和PCB三部分构成了进程实体。创建进程，实质上是创建进程实体中的PCB；撤消进程，实质上是撤消进程的PCB。

2.1.1 进程的定义

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

2.1.2 程序和进程的区别

(1) 程序是永存的；进程是暂时的，是程序在数据集上的一次执行，有创建有撤销，存在是暂时的；

(2) 程序是静态的观念，进程是动态的观念；

(3) 进程具有并发性，而程序没有；

(4) 进程是竞争计算机资源的基本单位，程序不是。

(5) 进程和程序不是一一对应的：

▪ 一个程序可对应多个进程即多个进程可执行同一程序；

▪ 一个进程可以执行一个或几个程序。

2.1.3 进程的特征

(1) 动态性

▪ 进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。

▪ 动态性表现：“它由创建而产生，由调度而执行，由撤消而消亡”。可见，进程实体有一定的生命期。

▪ 程序是一组有序指令的集合，其本身并不具有运动的含义，因而是静态的。

(2) 并发性

多个进程实体同存于内存中，且能在一段时间内同时运行。

(3) 独立性

进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。

(4) 异步性

进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。

2.2 进程的状态与转换

2.2.1 进程的状态

(1) 三种基本状态

▪ 就绪（Ready）状态

当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。

▪ 执行状态

进程已获得CPU，其程序正在执行。

▪ 阻塞状态

正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。

图2-1 三种基本状态的转换

(2) 五种状态

在三种基本状态基础上引入下面两种状态：

▪ 创建状态

当一个新进程刚刚建立，还未将其放入就绪队列时的状态，称为创建状态。

▪ 终止状态

当一个进程已经正常结束或异常结束，操作系统已将其从系统队列中移出，但尚未撤消，这时称为终止状态。

图2-2 五种状态的转换

2.2.2 挂起状态

当出现了引起进程挂起的事件时，用户请求将自己挂起，或者父进程请求挂起自己的子进程，这时使用挂起原语suspend( )。挂起原语检查进程状态，如果处于活动就绪状态就改为静止就绪；如果处于活动阻塞就改为静止阻塞。

当发生激活事件后，系统利用激活原语active( ) 将指定进程激活。激活原语将进程从外存调入内存，然后检查进程状态。

(1) 造成挂起状态的原因

▪ 终端用户的请求。

▪ 父进程请求。

▪ 负荷调节的需要。

当实时系统中的工作负荷较重，把一些不重要的进程挂起，以保证系统能正常运行。

▪ 操作系统的需要

操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

(2) 被挂起进程的特征

▪ 不能立即执行

▪ 可能是等待某事件发生，若是，则阻塞条件独立于挂起条件，即使阻塞事件发生，该进程也不能执行

▪ 使之挂起的进程为：自身、其父进程、OS

▪ 只有挂起它的进程才能使之由挂起状态转换为其他状态

(3) 进程挂起状态的转换

图2-3 进程挂起状态的转换

2.2.3 进程状态的切换

图2-4 进程状态的切换

▪ 挂起原语

活动就绪 à 静止就绪

活动阻塞 à 静止阻塞

▪ 激活原语

静止就绪 à 活动就绪

静止阻塞 à 活动阻塞

2.3 进程管理的数据结构

2.3.1 进程和进程映像

▪ 进程是操作系统中最基本、最重要的概念，多道程序出现后为了刻画程序执行的动态情况，描述运行程序的活动规律而引入进程。

▪ 进程最少必须包括一个或一组被执行的程序，以及与这些程序相关联的局部变量、全局变量和任何已定义的常量的数据单元。

▪ 属于一个进程的程序、数据、栈和属性的集合称为进程映像。

2.3.2 进程控制块的作用

进程控制块的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位—进程。

在进程的整个生命期中，操作系统总是通过PCB对进程进行控制的。

所以说，PCB是进程存在的唯一标志。

OS是根据PCB来对并发执行的进程进行控制和管理的，如：

- 进程创建：分配进程控制块

- 进程调度：保存和读取进程控制块

- 进程撤销：回收进程控制块

2.3.3 进程控制块中的信息

(1) 进程标识符信息

进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符：

▪ 内部标识符：为每一个进程赋予一个唯一的数字标识符，通常是进程的序号。设置内部标识符主要是为了方便操作系统使用。

▪ 外部标识符：它由创建者提供，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。

(2) 处理机状态信息

处理机状态信息主要是由处理机的各种寄存器的内容组成的。

▪ 通用寄存器：又称为用户可视寄存器。

▪ 指令计数器（PC）：其中存放了要访问的下一条指令的地址。

▪ 程序状态字PSW：其中含有状态信息，如条件码、执行方式、中断屏蔽标志等

▪ 用户栈指针(SP)：用于存放系统调用参数及调用地址。栈指针指向该栈的栈顶。

(3) 进程调度信息

在PCB中还存放一些与进程调度和进程对换有关的信息

▪ 进程状态：指明进程的当前状态。

▪ 进程优先级。

▪ 进程调度所需的其它信息，如：进程已等待CPU的时间总和、进程已执行的时间总和等；

▪ 事件：是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

(4) 进程控制信息

▪ 程序和数据的地址：

进程的程序和数据所在的内存或外存地址。

▪ 进程同步和通信机制：

实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等。

▪ 资源清单：

进程所需的全部资源及已经分配到该进程的资源的清单；

▪ 链接指针：

本队列下一个进程的PCB的首地址。

2.3.4 进程控制块的组织方式

(1) 线性方式

把系统中所有的PCB都组织在一张线性表中。

(2) 链接方式

把具有同一状态的PCB，用其中的链接指针链接成一个队列。

(3) 索引方式

相同状态的进程PCB组织在一张表格中，系统根据所有进程的状态建立几张索引表，系统分别记载各PCB表格的起始地址。

▪ 系统根据所有进程的状态建立相应的索引表，并将每个索引表的首地址记录在内存中的专用单元中。

▪ 每个索引表的表目记录一个PCB在系统PCB表中的位置。

比较以上两种方式的特点，链接方式是插入和删除操作很方便，查找速度慢；索引方式查找速度快，但因为索引表是线性的，因此插入和删除操作麻烦。

因为进程的主要操作就是插入和删除，因此，链接方式使用更多一些。

2.4 进程的创建与终止

2.4.1 操作系统对进程的控制

进程控制一般是由OS内核中的一组原语来实现的

(1) 原语

▪ 操作系统内核提供核外调用的过程或函数称为原语

▪ 原语是由若干条指令构成，用于完成特定功能的一段程序。

▪ 原语在执行过程不允许被中断。

(2) 原子操作

▪ 执行中不能被其它进程（线程）打断的操作就叫原子操作。

▪ 当该次操作不能完成的时候，必须回到操作之前的状态，原子操作不可拆分。

2.4.2 操作系统内核

内核是计算机硬件的第一层扩充软件，为系统对进程控制、存储器管理等提供有效的机制。

(1) CPU的工作模式

▪ 特权模式：只有操作系统能够工作在特权模式上，这个模式可以直接访问硬件，执行特权指令。

▪ 用户模式：用户程序都工作在用户模式，在这种模式工作的CPU只能执行基本的指令，当用户程序想干些关键的操作时，他会向操作系统请求，由操作系统帮他完成，即“系统服务” 。

(2) CPU的执行状态

▪ 用户态：用户程序执行的状态，只能执行规定的指令，访问规定的寄存器和存储区。

▪ 系统态：也称“核心态”或“管态”，OS运行的状态，能执行一切指令，访问所有的寄存器和存储区。

2.4.3 进程创建

(1) 进程图

进程图是用于描述一个进程的家族关系的有向树。

(2) 进程之间的关系

▪ 子进程可以继承父进程所拥有的资源。

▪ 当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。

▪ 在撤消父进程时，也必须同时撤消其所有的子进程。

(3) 引起进程创建的事件

导致一个进程去创建另一个进程的典型事件，可以有下四类：

1. 用户登录。
2. 作业调度。
3. 提供服务。例如：I/O请求
4. 应用请求。基于应用进程的需求，由它自己创建一个新进程，以便使新进程以并发运行方式完成特定任务。

(4) 调用进程创建原语步骤

1. 申请空白PCB。
2. 为新进程分配资源。
3. 初始化进程控制块。

▪ 初始化标识信息。

▪ 初始化处理机状态信息。使程序计数器指向程序的入口地址，使栈指针指向栈顶；

▪ 初始化处理机控制信息：进程的状态、优先级。

4. 将新进程插入就绪队列，启动调度。

2.4.4 进程终止

(1) 引起进程终止的事件

1）正常结束。

2）异常结束：

a) 越界错误。

b) 保护错。

c) 非法指令。

d) 特权指令错。

e) 运行超时。

f) 等待超时。

g) 算术运算错、被0除：

h) I/O故障。

3）外界干预：外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终止运行。

a) 操作员或操作系统干预：

由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；

b) 父进程请求终止该进程；

c) 当父进程终止时，OS也将他的所有子孙进程终止。

(2) 进程的终止过程

1. 根据被终止进程的PID找到它的PCB，从中读出该进程的状态。
2. 若被终止进程正处于执行状态，应立即终止该进程的执行，重新进行调度。
3. 若该进程还有子孙进程，立即将其所有子孙进程终止。
4. 将被终止进程所拥有的全部资源，归还给其父进程，或者归还给系统。
5. 将被终止进程的PCB从所在队列中移出。

2.5 进程的阻塞与唤醒

2.5.1 进程的阻塞

一个进程因为等待某一事件发生而暂时停止运行，这时称该进程处于阻塞状态。由于无法继续执行，于是进程便通过调用阻塞原语block()把自己阻塞。阻塞是主动行为

(1) 引起进程阻塞的事件

1. 请求系统服务。
2. 启动某种操作：如I/O操作。
3. 新数据尚未到达。
4. 无新工作可做

(2) 进程的阻塞过程

1. 找到要阻塞进程对应的PCB；
2. 保护进程运行现场，把PCB中的现行状态由“执行”改为“阻塞”，暂时停止进程运行；
3. 将PCB插入相应事件的阻塞队列；
4. 转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。

2.5.2 进程的唤醒

当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup( )，将等待该事件的进程唤醒。唤醒是一种被动行为。

(1) 进程的唤醒过程

1. 在等持该事件的阻塞队列中找到PCB
2. 把阻塞进程的PCB从阻塞队列中移出，并将其PCB中的现行状态由“阻塞”改为“就绪”
3. 将该PCB插入到就绪队列中，等待被CPU调度

2.5.3 进程的阻塞与唤醒的转换

图2-5 进程的阻塞与唤醒的转换

2.6 进程的挂起与激活

2.6.1 进程的挂起

当出现了引起进程挂起的事件时，系统将利用挂起原语suspend( )将指定进程挂起或处于阻塞状态的进程挂起。挂起是主动行为

(1) 挂起原语的执行过程

1. 检查将要被挂起的进程的状态
2. 若状态为：

▪ 执行 à 静止就绪，设置CPU调度标志为“真”

▪ 活动就绪 à 静止就绪

▪ 活动阻塞 à 静止阻塞

3. 将被挂起进程的PCB复制到指定的内存区域。
4. 若处于运行状态，则转向调度程序重新调度

(2) 挂起和阻塞的区别

阻塞：正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行。此时引起进程调度，OS把处理机分配给另一个就绪进程，而让受阻进程处于暂停状态，一般将这种状态称为阻塞状态。

挂起：由于系统和用户的需要引入了挂起的操作，进程被挂起意味着该进程处于静止状态。如果进程正在执行，它将暂停执行，若原本处于就绪状态，则该进程此时暂不接受调度。

挂起和阻塞的不同点：

1. 对系统资源占用不同：阻塞的进程仍处于内存中，而挂起的进程通过“对换”技术被换出到外存（磁盘）中。
2. 发生时机不同：阻塞一般在进程等待资源（IO资源、信号量等）时发生；而挂起是由于用户和系统的需要。
3. 恢复时机不同：

- 阻塞要在等待的资源得到满足（例如获得了锁）后，才会进入就绪状态，等待被调度而执行；

- 被挂起的进程由将其挂起的对象（如用户、系统）在时机符合时（调试结束、被调度进程选中需要重新执行）将其激活。

2.6.2 进程的激活

当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，系统将利用激活原语active( )将指定进程激活。（激活是被动行为）。系统利用激活原语active( )将指定进程激活：

(1) 激活原语的执行过程

1. 检查将要被激活的进程的状态：

▪ 静止就绪 à 活动就绪

▪ 静止阻塞 à 活动阻塞

2. 检查是否要进行重新调度

2.6.3 挂起与激活原语

▪ suspend()挂起原语

活动就绪 à 静止就绪

活动阻塞 à 静止阻塞

▪ active()激活原语

静止就绪 à 活动就绪

静止阻塞 à 活动阻塞

进程控制原语可能引起的调度：

时机：假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，都应检查是否要进行重新调度。

创建、终止（自己）、挂起（自己）、激活、阻塞、唤醒都可能会产生新的调度。

2.7 处理机调度

2.7.1 处理机调度的基本概念

(1) 为什么要有处理机调度

▪ 处理机是计算机系统中的重要资源

▪ 在多道程序环境下，进程数目通常多于处理机的数目

▪ 系统必须按一定方法动态地把处理机分配给就绪队列中的一个进程

▪ 处理机的利用率和系统性能（吞吐量、响应时间）在很大程度上取决于处理机调度

(2) 什么是处理机调度

无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。

(3) 作业

作业是用户在一次算题过程中或一次事务处理中，要求计算机系统所做的工作的集合。

- 计算机完成作业是通过执行一系列有序的工作步骤进行的，每个步骤完成作业的一部分特定工作。

- 把计算机系统完成一个作业所需的一系列有序的相对独立的工作步骤称为作业步。

- 作业的各个作业步虽然功能相对独立，但它们之间相互关联，往往是一个作业步的执行需要使用上一个作业步的执行结果

(4) 引起处理机调度的因素

▪ 正在执行的进程执行完毕，或因发生某事件而不能再继续执行（包括：当前执行进程被中断、时间片用完了、挂起自己、退出等）；

▪ 执行中的进程因提出I／O请求而暂停执行；

▪ 在进程通信或同步过程中执行了某种原语操作，如P、V操作原语，block原语， wakeup原语等。

(5) 调度时机

▪ 非抢占系统

- 当前进程主动放弃CPU时

▪ 可抢占系统

- 中断请求被服务例程响应完成时

- 当前进程被抢占

(6) 进程切换

▪ 当一个进程占用处理机执行完（或不能继续执行），则换另一个进程占用处理机执行，称为进程切换。

▪ 把处理机分配给不同的进程占用执行，称为进程调度。

▪ 实现分配处理机的程序称为调度程序。

▪ 在进程切换时，要保护执行现场。

▪ 执行现场称为进程的上下文。

图2-6 进程切换过程

基本步骤

1. 保存进程上下文环境
2. 更新当前运行进程的控制块内容，将其状态改为就绪或阻塞状态
3. 将进程控制块移到相应队列（就绪队列或阻塞队列）
4. 改变需投入运行进程的控制块内容，将其状态变为运行状态
5. 恢复需投入运行进程的上下文环境

2.7.2 处理机调度的层次

(1) 高级调度

1. 定义

又称作业调度、长程调度或接纳调度，其主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存。批处理系统需要有作业调度，分时和实时系统无需此调度。

2. 目标

主要用于批处理系统。其设计目标是最大限度地发挥各种资源的利用率和保持系统内各种活动的充分并行

3. 性能评价

▪ 多道程序度：即允许多少个作业同时在内存中运行。

▪ 周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。

▪ 吞吐量：是指在单位时间内系统所完成的作业数。

▪ 相应比 = (等待时间+要求服务时间) / 要求服务时间 = 响应时间/要求服务时间

(2) 低级调度

1. 定义

低级调度又称为进程调度或短程调度，它所调度的对象是进程。三种类型OS都必须配置这级调度。（最基本调度）

低级调度用于决定就绪队列中的哪个进程应获得处理机，然后再由分派进程执行把处理机分配给该进程的具体操作

2. 三个基本机制

a) 排队器

为了提高进程调度的效率，应事先将系统中所有的就绪进程按照一定的方式排成一个或多个队列。

b) 分派器(调度程序)

分派器把由进程调度程序所选定的进程从就绪队列中取出，然后进行上下文切换，将处理机分配给它。

c) 上下文切换机制

当对处理机进行切换时，会发生两对上下文切换操作。

3. 低级调度功能

a) 按某种算法选取进程（调度）。

b) 保存处理机的现场信息（上下文切换第一步骤）

c) 把处理器分配给进程（上下文切换第二步骤）。

4. 低级调度方式

a) 非抢占方式：进程占用处理机直至自愿放弃或发生某事件被阻塞时，在把处理机分配给其他进程。

b) 抢占方式：允许暂停某个正在执行的进程，将处理机重新分配给另一个进程。抢占原则有：

▪ 时间片原则

▪ 优先权原则

▪ 短作业（进程）优先原则

(3) 中级调度

1. 定义

又称中程调度，在存储器管理中对换。

2. 主要目的

为了提高内存利用率和系统吞吐量。

3. 具体实现

▪ 使那些暂时不能运行的进程不再占用宝贵的内存资源，而将其调至外存去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。

▪ 当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的那些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。

(4) 三级调度的比较