第2章 进程的描述与控制
2.1 复习笔记
一、前趋图和程序执行
1前趋图
（1）定义
前趋图是指一个有向无循环图，可记为DAG，它用于描述进程之间执行的先后顺序。
（2）图形表示
前趋图如图2-1所示。
图2-1 前趋图
2程序的执行
（1）程序顺序执行时的特征
①顺序性。
②封闭性。
③可再现性。
（2）程序并发执行时的特征
①间断性。
②失去封闭性。
③不可再现性。
二、进程的描述
1进程的定义和特征
（1）进程的定义
对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有：
①进程是程序的一次执行。
②进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
③进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。
（2）进程的特征
①动态性
动态性是进程的最基本的特征。
②并发性。
③独立性。
④异步性。
（3）进程实体
通常，进程实体由程序控制块（PCB）、程序段、数据段三部分组成。
2进程的状态及转换
（1）进程有三种基本状态：就绪状态、执行状态、阻塞（等待）状态。图2-2示出了基本状态的转换图。
图2-2 进程的三种基本状态及转换
（2）引入进程的创建状态和终止状态后，图2-3示出了进程的五种状态及转换关系图。
图2-3 进程的五种状态及转换
3挂起操作和进程状态的转换
（1）当挂起操作作用于某个进程时，该进程将被挂起，意味着此时该进程处于静止状态。如果进程正在执行，它将暂停执行。若原本处于就绪状态，则该进程此时暂不接受调度。与挂起操作对应的操作是激活操作。
（2）引入挂起原语操作后三个进程状态的转换
①活动就绪→静止就绪。
②活动阻塞→静止阻塞。
③静止就绪→活动就绪。
④静止阻塞→活动阻塞。
（3）引入挂起操作后五个进程状态的转换如图2-4所示。
图2-4 具有创建、终止和挂起状态的进程状态图
4进程控制块（PCB）
（1）概念
PCB是一记录型数据结构，它作为进程实体的一部分，记录了操作系统所需的、用于描述进程的当前情况以及管理进程运行的全部信息。
（2）进程控制块中的信息
（3）进程控制块的组织方式
①线性方式。
②链接方式。
③索引方式。
三、进程控制
进程控制是进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。
四、进程同步
1进程同步的基本概念
（1）进程同步机制的主要任务
对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。
（2）临界资源
一次仅允许一个进程使用的资源称为临界资源。
（3）临界区
将在每个进程中访问临界资源的那段代码称为临界区。
（4）同步机制应遵循的规则
①空闲让进。
②忙则等待。
③有限等待。
④让权等待。
2硬件同步机制
（1）关中断。
（2）利用Test-and-Set指令实现互斥。
（3）利用Swap指令实现进程互斥。
3信号量机制
（1）整型信号量
①定义
把整型信号量定义为一个用于表示资源数目的整型量S。
②描述
通过两个标准的原子操作wait（S）和signal（S）来访问S，两个操作一直被分别称为P、V操作。wait和signal操作可描述如下：
wait(S)
{
while(S<=0); /*do no-op*/
S--;
}
signal(S)
{
S++;
}
（2）记录型信号量
①定义
记录型信号量机制采用了记录型的数据结构，是一种不存在“忙等”现象的进程同步机制。
②描述
typedef struct
{
int value; //代表资源数目的整型变量
struct process_control_block *list; //一个链接所有等待进程的进程链表指针
}semaphore;
wait(S)和signal(S)操作可描述如下：
wait(semaphore *S)
{
S->value--;
if(S->value<0)
block(S->list);
}
signal(semaphore *S)
{
S->value++;
if(S->value<=0)
wakeup(S->list);
}
4经典同步问题-生产者-消费者问题
问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n个单元的缓冲区。只有当缓冲区没满时，生产者才可以把消息放入缓冲区，否则必须等待；只有当缓冲区不空时，消费者才可以从中取出消息，否则必须等待。由于缓冲区是临界资源，只允许一个生产者放入消息或者一个消费者从中取出消息，不允许同时访问缓冲区。
信号量设置：定义信号量mutex为互斥信号量，初值为1，用于表示互斥访问缓冲区；信号量empty用于表示当前缓冲区中可用空间大小，初值为n；信号量full用于表示当前缓冲区中已用空间大小，初值为0。
程序描述：
semaphore mutex=1;
semaphore empty=n;
semaphore full=0;
producer()
{ //生产者进程
while(true)
{
//生产一个消息
p(empty); //申请缓冲区中的一个空单元
p(mutex); //申请访问缓冲区
//将消息放入缓冲区
v(mutex); //释放互斥信号量
v(full); //缓冲区中满单元数加一
}
}
consumer()
{ //消费者进程
while(true)
{
p(full); //申请从缓冲区中的满单元取出消息
p(mutex); //申请访问缓冲区
//将消息取出缓冲区
v(mutex); //释放互斥信号量
v(empty); //缓冲区中空单元数加一
}
}
5管程机制
（1）定义
一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。
（2）组成
①管程的名称；
②局部于管程的共享数据结构说明；
③对该数据结构进行操作的一组过程；
④对局部于管程的共享数据设置初始值的语句。
五、进程通信
1进程通信的概念
（1）进程通信的定义
进程通信是指进程之间的信息交换。
（2）进程通信的分类
进程通信可分为高级进程通信和低级进程通信两种。
2高级进程通信的类型
（1）共享存储器系统
①基于共享数据结构的通信方式。
②基于共享存储区的通信方式。
（2）管道通信系统
（3）消息传递系统（Message passing system）
①直接通信方式。
②问接通信方式。
（4）客户机-服务器系统（Client-Server system）
六、线程的基本概念
1线程的引入
（1）进程的两个基本属性
①进程是一个可拥有资源的独立单位；
②进程同时又是一个可独立调度和分派的基本单位。
（2）线程引入原因
减少程序并发执行所需付出的时空开销，使操作系统具有更好的并发性。
2线程与进程的比较
（1）调度的基本单位
①在传统的OS中，进程是作为独立调度和分派的基本单位，因而进程是能独立运行的基本单位。
②而在引入线程的OS中，已把线程作为调度和分派的基本单位，因而线程是能独立运行的基本单位。
（2）并发性
不同进程之间、在一个进程中的多个线程之间或者不同进程中的线程之间都能并发执行。
（3）拥有资源
①进程是系统中拥有资源的一个基本单位。
②线程本身并不拥有系统资源，而是仅有一点必不可少的、能保证独立运行的资源。
（4）独立性
在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。
（5）系统开销
①创建或撤消进程时所付出的开销明显大于线程创建或撤消时所付出的开销。
②线程的切换代价也远低于进程的切换代价。
3线程的状态和线程控制块
（1）线程运行的三个状态：执行状态，就绪状态，阻塞状态。
（2）线程控制块TCB
线程控制块通常有这样几项信息：
①线程标识符；
②一组寄存器；
③线程运行状态；
④优先级；
⑤线程专有存储区；
⑥信号屏蔽；
⑦堆栈指针。
【说明】在多线程OS中，线程作为独立运行（或称调度）的基本单位；而进程仍是资源分配的基本单位。
七、线程的实现方式
1内核支持线程KST
2用户级线程ULT
3组合方式
组合方式下包括三种不同的模型，如图2-5所示。
图2-5 多线程模型