• 该系列博文主要是针对操作系统课程中的一些知识点进行梳理。
• 更多地是介绍相关概念，后续会结合部分代码介绍
• 操作系统系列之二

第二章 进程的描述与控制

2.1 程序执行

2.1.1 程序顺序执行

• 特征：
  • 顺序性：处理机的操作严格按照程序所规定的顺序执行。
  • 封闭性：程序运行时独占全机资源，程序一旦开始执行，其执行结果不受外界因素影响。
  • 可再现性：只要程序执行时的环境和初始条件相同，都将获得相同的结果。
    （不论它是从头到尾不停顿地执行，还是“停停走走”地执行）

2.1.2 程序并发执行

• 特征：
  • 间断性：程序并发执行是，由于共享系统资源，这些程序形成相互制约的关系，具有“执行-暂停-执行”特征。
  • 失去封闭性：程序并发执行时，多个程序共享系统资源，因而这些资源的状态将由多个程序来改变，从而导致程序的运行失去封闭性。
  • 不可再现性：程序并发执行，由于失去了封闭性，从而也失去了可再现性。

2.2 进程的描述

2.2.1 进程的定义和特征

2.2.1.1 典型的进程定义有：

• 进程是程序的一次执行。

• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

2.2.1.2 进程的结构

• 为使程序（含数据）能独立运行，应为之配置一进程控制块，即PCB（程序控制块）
• 由程序段、相关的数据段和PCB三部分便构成了进程实体（又称进程映像）。
• 所谓创建进程，实质上是创建进程实体中的PCB；而撤消进程，实质上是撤消进程的PCB。

PCB本质为一个结构体（eg:Linux中的PCB）：
struct task_struct{
...
unsigned short uid; // 用户标识
int pid;            // 进程标识
int processor;//标识用户正在使用的CPU,以支持对称多处理机方式
...
volatile long state; // 标识进程的状态
long prority;        // 表示进程的优先级
unsighed long rt_prority;//表示实时进程的优先级，对于普通进程无效
long counter//进程动态优先级计数器，用于进程轮转调度算法
unsigned long flags;
unsigned long policy;//进程调度策略
...
struct task_struct *next_task, *prev_task;
struct task_struct *next_run,*prev_run;
struct task_struct *p_opptr,*p_pptr,*p_cptr,*pysptr,*p_ptr;
...
};

2.2.1.3 进程的特征 (重要)

• 动态性：（状态在不断地发生改变）
  • 进程的实质是进程实体的一次执行过程，因此，动态性是进程的最基本的特征。
  • 动态性表现：“它由创建而产生，由调度而执行，由撤消而消亡”。可见，进程实体有一定的生命期。
  • 程序是一组有序指令的集合，其本身并不具有运动的含义，因而是静态的。
• 并发性：
  • 多个进程实体同存于内存中，且能在一段时间内同时运行。
• 独立性：
  • 进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。
• 异步性：
  • 进程按各自独立的、不可预知的速度向前推进，或说进程实体按异步方式运行。

2.2.2 进程的基本状态及转换 （重要）

• 进程的三种基本状态：

  • 就绪（Ready）状态：当进程已分配到除CPU以外的所有必要资源后，只要再获得CPU，便可立即执行。
  • 执行（Running）状态：进程已获得CPU，其程序正在执行。单处理机系统中，只有一个进程处于执行状态，多处理机系统中，则有多个进程处于执行状态。
  • 阻塞（Block）状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，把这种暂停状态称为阻塞状态，有时也称为等待状态。根据阻塞原因，系统中设置多个阻塞队列。

• 三种基本状态的转换
  

  • 进程状态转换过程既有主动原因，也有被动原因

• 创建状态和终止状态

  • 创建状态：如果进程所需资源尚不能得到满足，如无足够的内存空间，创建工作将无法完成，进程不能被调度，此时的进程状态为创建状态。
  • 终止状态：一个进程到达了自然结束点，或者出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。

2.2.3 挂起操作和进程状态的转换

• 挂起状态 使执行的进程暂停执行，静止下来，我们把这种静止状态成为挂起状态

  • 引入挂起状态的原因：

    • 1. 终端用户的请求用户；（发现程序运行有问题，将其暂停）
    • 2. 父进程请求；(挂起子进程，协调子进程的活动)
    • 3. 负荷调节的需要。当实时系统中的工作负荷较重，把一些不重要的进程挂起，以保证系统能正常运行。
    • 4. 操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

  • 进程挂起状态的转换
    

  • 有挂起状态的进程转换
    
    

  • 挂起状态的思考

    • 就绪/挂起（静止就绪）可以从活动就绪因为挂起操作转变为静止就绪状态，也可以从执行状态因为某些原因挂起转变为静止就绪状态
    • 就绪/挂起状态无法直接进入执行状态
    • 挂起状态无法直接进入执行状态
    • 挂起进程无法自我激活，但是进程可以自我挂起（只要已知进程ID等有效信息）

2.2.4 进程管理中的数据结构

2.2.4.1 进程控制块的作用

• 独立运行基本单位的标志。
• 能实现间断性运行方式。（保护CPU现场）
• 提供进程管理所需要的信息。（OS通过PCB对进程- 实施控制和管理。）
• 提供进程调度所需要的信息。（提供进程状态、优先级等信息）
• 实现与其它进程的同步与通信。（消息队列指针，信号量等）

2.2.4.2 进程控制块的内容

• 进程标识符信息
• 处理器状态信息
• 进程调度信息
• 进程控制信息

1. 进程标识符信息:进程标识符用于惟一地标识一个进程。一个进程通常有两种标识符：

   1. 内部标识符。为每一个进程赋予一个惟一的数字标识符，通常是进程的序号(Pid)。设置内部标识符主要是为了方便操作系统使用。
   2. 外部标识符。它由创建者提供(进程的名字)，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。

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

   1. 通用寄存器，又称为用户可视寄存器。
   2. 指令计数器（PC），其中存放了要访问的下一条指令的地址。
   3. 程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等
   4. 用户栈指针(SP)，用于存放系统调用参数及调用地址。栈指针指向该栈的栈顶。

• 这些都是中断和进程切换时需要保护的内容！

3. 进程调度信息:在PCB中还存放一些与进程调度和进程切换有关的信息。

   1. 进程状态。指明进程的当前状态。
   2. 进程优先级。
   3. 进程调度所需的其它信息。如：进程已等待CPU的时间总和、进程已执行的时间总和等；
   4. 事件。是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。

4. 进程控制信息

   1. 程序和数据的地址，是指进程的程序和数据所在的内存或外存地址。
   2. 进程同步和通信机制，指实现进程同步和通信时必需的机制，如消息队列指针、信号量等，他们可能全部或部分的放在PCB中。
   3. 资源清单。进程所需的全部资源及已经分配到该进程的资源的清单；
   4. 链接指针。本进程所在队列的下一个进程的PCB的首地址。

2.2.4.3 进程控制块的组织方式

• 链接方式：把具有同一状态的PCB，用其中的链接字链接成一个队列。
  
• 索引方式：相同状态进程的PCB组织在一张表格中，系统根据所有进程的状态建立几张索引表，系统分别记载各PCB表格的起始地址。
  
• 多级队列：按照进程状态不同分别组织PCB队列，同一状态进程PCB按照优先级高低（或者到达的先后顺序）用链接指针连接起来。
  

2.3 进程控制

• 进程控制：
  • 创建一个新进程，终止进程
  • 进程运行中的状态转换。
• 进程控制一般是由OS内核中的一组原语来实现的。

2.3.1 原语

• 什么是原语？

原语是由若干条指令组成的，用于完成一定功能的一个过程。是“原子操作”，即一个操作中的所有动作要么全做，要么全不做，换言之，是一个不可分割的基本单位，在执行过程中不允许被中断。

2.3.2 进程的创建

2.3.2.1 进程图（Process Graph）

• 进程图是用于描述一个进程的家族关系的有向树。
• 子进程可以继承父进程所拥有的资源。
• 当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程。
• 在撤消父进程时，也必须同时撤消其所有的子进程。
  

2.3.2.2 引起创建进程的事件

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

  • （1）用户登录。分时系统中，用户通过终端登录成功后，系统将为用户建立一个进程。
  • （2）作业调度。将作业调入内存后，创建进程。
  • （3）提供服务。例如：I/O请求，打印进程等。
  • （4）应用请求。基于应用进程的需求，由它自己创建一个新进程，以便使新进程以并发运行方式完成特定任务。

• 调用进程创建原语步骤：

  • （1）申请空白PCB。
  • （2）为新进程分配资源。
  • （3）初始化进程控制块。
    • ① 初始化标识信息。
    • ② 初始化处理机状态信息。使程序计数器指向程序的入口地址，使栈指针指向栈顶；
    • ③ 初始化处理机控制信息：进程的状态、优先级。
  • （4）将新进程插入就绪队列，启动调度。

2.3.3 进程的终止

• （1）正常结束。

• （2）异常结束：

  • ① 越界错误。
  • ② 保护错。
  • ③ 非法指令。
  • ④ 特权指令错。
  • ⑤ 运行超时。
  • ⑥ 等待超时。
  • ⑦ 算术运算错、被0除：
  • ⑧ I/O故障。

• （3）外界干预

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

  • ① 操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；
  • ② 父进程请求终止该进程；
  • ③ 当父进程终止时，OS也将他的所有子孙进程终止。

• （4） 进程的终止过程

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

2.3.4 进程的阻塞与唤醒

• 引起进程阻塞和唤醒的事件

  • 1）向系统请求共享资源失败。
  • 2）等待某种操作的完成：如I/O操作时进程进入阻塞状态，I/O完成后，被中断处理程序唤醒。
  • 3）新数据尚未到达。处理数据的进程A阻塞，输入数据的进程B完成后去唤醒A。
  • 4）无新工作可做, 如此时使用sleep（）进入休眠

• 进程阻塞过程

  • ① 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞；
  • ② 把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列；
  • ③ 转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换。

• 进程唤醒过程

  • ① 当被阻塞进程所期待的事件出现时，则由有关进程（比如，用完并释放了该I/O设备的进程）调用唤醒原语wakeup()，将等待该事件的进程唤醒。
  • ② 唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。

2.3.5 进程的挂起和激活

• 进程的挂起：当出现了引起进程挂起的事件时（比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起），系统将利用挂起原语suspend()将指定进程挂起或处于阻塞状态的进程挂起。

• 进程挂起的过程：

  • 挂起原语的执行过程是：
    • 1、首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞；
    • 2、然后将被挂起进程的PCB复制到指定的内存区域。

• 进程的激活过程

  • ① 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，系统将利用激活原语active()将指定进程激活。
  • ② 系统利用激活原语active()将指定进程激活：
    激活原语检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；
    若为静止阻塞，便将之改为活动阻塞。

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

时机：假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，都应检查是否要进行重新调度。
创建、终止（自己）、挂起（自己）、激活、阻塞、唤醒都可能会产生新的调度。

2.4 进程的同步

2.4.1 进程的同步的基本概念

进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好的相互合作，从而使程序的执行具有可再现性。

• 间接相互制约关系 并发执行的进程在使用共享资源时的关系，资源的互斥。
• 直接相互制约关系 多个进程为完成同一项任务而相互合作的关系。

2.4.2