English | 中文版

进程

[TOC]

进程是系统进行资源分配和调度的一个独立单位，每个进程都有自己独立的内存空间，不同进程通过进程间通信来交流。比较heavy，上下文切换开销大，但是比线程稳定。

定义与特征

定义：

进程是程序的一次执行；
进程是一个程序及其数据在处理机上顺序执行时所发生的活动；
进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

特征：

动态性：进程的实质是进程实体的执行过程，因此，动态性就是进程的最基本的特征。
并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。
独立性：进程实体是一个能独立运行，独立获得资源和独立接受调查的基本单位。
异步性：进程是按异步方式运行的，即按各自独立的，不可预知的速度向前推进。

前趋图

前趋图（Precedence Graph） 指一个有向无循环图，可记为DAG(Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。

进程（或程序）之间的前趋关系可用“$\rightarrow$”来表示，如果进程$P_i$和$P_j$存在着前趋关系，可表示为$(P_i, P_j)\in \rightarrow$，也可写成$P_i \rightarrow P_j$，表示在$P_j$开始执行之前$P_i$必须完成。此时称$P_i$是$P_j$的直接前趋，而称$P_j$是$P_i$的直接后继。

执行顺序

顺序执行

![](https://g.gravizo.com/svg? digraph G{ nodesep=2; ranksep=1; rankdir=LR; S1 -> S2 -> S3; } )

上述语句中，存在着这样的前趋关系：$S_1 \rightarrow S_2 \rightarrow S_3$。
并发执行

![](https://g.gravizo.com/svg? digraph G{ nodesep=2; ranksep=1; rankdir=LR; S1 -> S3; S2 -> S3; S3 -> S4; } )

上述语句中，$S_3$必须在$S_1$和$S_2$被执行后方能执行；$S_4$必须在$S_3$之后执行；但$S_1$和$S_2$则可以并发执行，因为它们彼此互不依赖。

进程管理

数据结构

操作系统控制表的一般结构

进程控制块(Process Control Block, PCB)

作用：

作为独立运行基本单位的标志
能实现间断性运行方式
提供进程管理所需要的信息
提供进程调度所需要的信息
实现与其它进程的同步与通信

PCB组织方式：

线性方式

PCB线性表示示意图
链接方式

PCB链接队列示意图
索引方式

按索引方式组织PCB

状态管理

基本状态

就绪（Ready）状态
执行（Running）状态
阻塞（Block）状态
创建（Create）状态
终止（Stop）状态

进程的五种基本状态及转换

状态转换

具有创建，终止和挂起状态的进程状态图

创建
1. 申请空白PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB。
2. 为新进程分配其运行所需的资源，包括各种物理和逻辑资源，如内存，文件，I/O设备和CPU时间等。
3. 初始化进程控制块（PCB）包括：
  - 初始化标识信息
  - 初始化处理机状态信息
  - 初始化处理机控制信息
4. 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。
终止
1. 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；
2. 若被终止进程处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度；
3. 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防他们成为不可控的进程；
4. 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统；
5. 将被终止进程（PCB）从所在队列（或链表）中移出，等待其它程序来搜集信息。
阻塞
1. 立即停止执行，把进程控制块中的先行状态由执行“改为阻塞，并将PCB插入阻塞队列；
2. 如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞队列；
3. 进行重新调度，将处理机分配给另一就绪进程，并进行切换。
唤醒
1. 把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，并将该PCB插入到就绪队列中。
挂起
1. 若进程处于活动就绪状态，便将其改为静止就绪；
2. 对于活动阻塞状态的进程，则将之改为静止阻塞；
3. 为了方便用户或父进程考查该进程的运行情况，而把该进程的PCB复制到某指定的内存区域；
4. 若被挂起的进程正在执行，则转向调度程序重新调度。
激活
1. 将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞，便将之改为活动阻塞；
2. 假如采用的是抢占调度策略，则每当有静止就绪进程被激活而插入就绪队列时，便应检查是否要进行重新调度。

进程调度

非抢占方式(Nonpreemptive Mode)

一旦把处理机分配给某进程后，就一直让它运行下去，不会因为时钟中断或任何其它原因去抢占当前正在运行进程的处理机，直至该进程完成。
抢占方式(Preemptive Mode)

允许调度程序根据某种原则，去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一个进程。

轮转调度算法

将所有的就绪进程按FCFS策略排成一个就绪队列。设置每隔一定时间产生一次中断，去激活进程调度程序进程调度，把CPU分配给队首进程，并令其执行一个时间片。当它运行完毕后，又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。

时间片大小对响应时间的影响

优先级调度算法

非抢占式优先级调度算法

把处理机分配给就绪队列中优先级最高的进程后，该进程一直执行下去直至完成。
抢占式优先级调度算法

把处理机分配给就绪队列中优先级最高的进程，如果出现另一个优先级更高的进程，调度程序就将处理机分配给新到的优先级最高的进程。

多队列调度算法

多队列调度算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。

多级反馈队列(multileved feedback queue)调度算法

多级反馈队列调度算法

设置多个就绪队列。按照优先级依次降低的顺序给每个队列赋值;
每个队列都采用FCFS算法;
按队列优先级调度。

基于公平原则的调度算法

使所有用户能获得相同的处理机时间，或所要求的时间比例。

实时进程调度

非抢占式调度算法
- 非抢占式轮转调度算法
- 非抢占式优先调度算法
抢占式调度算法
- 基于时钟中断的抢占式优先级调度算法
  
  在实时任务到达后，如果其优先级高于当前任务优先级，不立即抢占当前人物的处理机，而是等时钟中断发生时，调度程序才剥夺当前人物的执行，将处理机分配给新到的高优先级任务。
- 立即抢占(Immediate Preemption)的优先级调度算法
  
  一旦出现外部中断，只要当前任务未处于临界区，便能立即剥夺当前任务的执行，把处理机分配给请求中断的紧迫任务。

最早截止时间优先EDF(Earliest Deadline First)算法

非抢占式调度方式用于非周期实时任务

EDF算法用于非抢占调度方式
抢占式调度方式用于周期实时任务

最早截止时间优先算法用于抢占调度方式之例

最低松弛度优先LLF(Least Laxity First)算法

根据任务的紧急（或松弛）程度，确定任务的优先级。

利用ELLF算法进行调度的情况

进程同步

同步机制应遵循的规则

空闲让进 当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
忙则等待 当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。
有限等待 对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
让权等待 当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

硬件同步机制

在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。

信号量(Semaphores)机制

整型信号量；
记录型信号量；
AND型信号量；
信号量集。

进程通信

共享存储器系统(Shared-Memory System)

TODO

管道(pipe)通信系统

建立一个连接读进程和写进程的管道以实现通信。

消息传递系统(Message passing system)

基于消息传递系统的通信方式属于高级通信方式。

客户机-服务器系统(Client-Server system)