第二章 进程的描述与控制(2)

2.3 进程控制

何谓进程控制？我们要控制进程，就一定要对进程有操作，而这个操作，就是由OS内核中的原语来实现的。

那么先不说原语是什么，就这个OS内核是个什么？

2.3.1 操作系统内核及其功能

现代的操作系统一般是将OS划分为若干个层次，再将其不同的功能设置在不同的层次中。而通常将一些与硬件紧密相关的模块、各种常用设备的驱动程序以及运行频率较高的模块都安排在紧靠硬件的软件层次中，将它们常驻内存，即通常被称为的OS内核。简单来说就是靠近硬件的模块。

那么为什么要将这些模块放在靠近硬件的层次呢？其目的是为了保护这些软件，防止遭受其他应用程序的破坏，相应地，通常也将处理机的执行状态分为系统态和用户态两种：

1. 系统态：也称为管态、内核态。能执行一切指令，访问所有寄存器和存储区。
2. 用户态：又称目态。仅能执行规定的指令，访问指定的寄存去和存储区。

一般情况下，应用程序只能在用户态运行，从而防止其对OS的破坏。

不同OS的内核有一定差异，但大多数都有以下两大方面的内容

1. 支撑功能

什么是支撑？就是在一定基础上维持某些模块的运行和工作。

1. 中断处理
2. 时钟管理：如在时间片轮转调度中，每当时间片用完，始终管理便产生一个中断信号，促使调度程序重新进程调度。
3. 原语操作：所谓原语，就是由若干条指令的一个封装，要执行一个原语，就要全部语句执行，要么就不执行，也就是说，原语在执行过程中不允许被中断。

2. 资源管理功能

1. 进程管理。
2. 存储器管理
3. 设备管理

将它们放在内核中，完全是为提高OS的性能

2.3.2 进程的创建 1. 进程的层次结构

在OS中，允许一个进程创建另一个进程，创建进程的进程就是父进程，被创建的进程就是子进程。子进程也可继续创建孙进程。

子进程可以继承父进程所拥有的资源。子进程被撤销时，应将其从父进程获得的资源归还给父进程。在撤销父进程时，也必须同时撤销其所有的子进程。进程不能拒绝其子进程的继承权。

需要注意的是：在Windows中不存在任何进程层次结构的概念，所有的进程都具有相同的地位。如果一个进程创建另外的进程时创建进程获得了一个句柄，其作用相当于一个令牌，可以用来控制被创建的进程。但是这个句柄可以传递，也就是说，获得了句柄的进程就拥有控制其他进程的权力。

2. 进程图

所谓进程图就是用于描述进程间关系的一棵有向树。如下图，结点代表进程。

3. 引起进程创建进程的事件

1. 用户登录
2. 作业调度
3. 提供服务
4. 应用请求

4. 进程的创建

1. 申请空表PCB，为新进程申请获得唯一的数字标识符，并从PCB集合中索取一个空白PCB
2. 为新进程分配其运行所需的资源
3. 初始化进程控制块

• 初始化标识信息
• 初始化处理机状态信息
• 初始化处理机控制信息

4. 如果进程就绪队列能接纳新进程，便将新进程插入就绪队列

2.3.3 进程的终止 1. 引起进程终止的事件

1. 正常结束，标识进程的任务已经完成，准备退出运行。
2. 异常结束

• 越界错
• 保护错：指进程试图区访问一个不允许访问的资源或文件，或者以不适当的方式进行访问。
• 非法指令
• 特权指令错
• 运行超时
• 等待超时
• 算术运算错
• I/O故障

3. 外界干预

• 操作员或操作系统干预
• 父进程请求
• 父进程终止

2. 进程的终止过程

1. 根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态
2. 若被终止进程处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
3. 若该进程还有子孙进程，还应将其所有子孙进程也都予以终止
4. 将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统
5. 将被终止进程从所在队列中移除，等待其他程序来搜集信息

2.3.4 进程的阻塞与唤醒 1. 进程的阻塞与唤醒

1. 向系统请求共享资源失败，此时进程因不能继续运行而转变为阻塞状态
2. 等待某种操作的完成。
3. 新数据尚未到达
4. 等待新任务的到达

2. 进程阻塞过程

阻塞是进程自身的一种主动行为。
进入block过程后，由于该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。最后，转调度程序进程重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态，按新进程的PCB中的处理机状态设置CPU环境。

3. 进程唤醒过程

当被阻塞进程所期待的事件发生时，比如它所启动的I/O操作已完成，或其所期待的数据已到达，则由有关进程调用唤醒原语wakeup，将等待该事件的进程唤醒。
wakeup执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。
需要注意的是，block和wakeup原语必须成对使用。

2.3.5 进程的挂起与激活 1. 进程的挂起

当系统中出现了引起进程挂起的事件时，OS用挂起原语suspend将指定进程或处于阻塞状态的进程挂起。suspend的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞；为了方便用户或父进程考查该进程的运行情况，而把该进程的PCB复制到某指定的内存区域；最后，若被挂起的进程正在执行，则转向调度程序重新调度。

2. 进程的激活

激活进程原语active，先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，则将之改为活动就绪等。假如采用的是抢占调度策略，则每当有静止就绪进程被激活而插入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活的进程与当前进程两者的优先级进行比较，如果被激活的进程优先级低，就不必重新调度，否则，立即剥夺当前进程的运行，把处理机分配给刚刚被激活的进程。

2.4 进程同步

对于多个进程的运行，如果不采取一定的管理，必然会因为这些进程对系统资源的无序争夺给系统造成混乱，致使每次处理的结果存在着不确定性，即显现出不可再现性。
为保证多个进程能有条不紊地运行，在多道程序系统中，必须引入进程同步机制。

2.4.1 进程同步的基本概念

进程同步机制主要是对多个相关程序在执行次序上进行协调，使并发执行的进程之间能按照一定的规则共享系统资源。

1. 两种形式的制约关系

1. 间接相互制约关系

对于像打印机、磁带机这样的临界资源，必须保证多个进程对之只能互斥地访问。对于系统中的这类资源，必须由系统实施统一分配，即用户在要使用之前，应先提出申请，而不允许用户进程直接使用。

2. 直接相互制约关系

进程间的直接制约关系就是源于它们之间的相互合作。例如输入进程A和计算进程B，它们之间共享一个缓冲区。
A通过缓冲区向B提供数据。B从缓冲中取出数据，并对数据进程处理。但如果该缓冲空时，B因不能获得所需数据而被阻塞。一旦A把数据输入缓冲区后便将进程B唤醒；反之，当缓冲区已满，A因不能再向缓冲区投放数据而被阻塞，当B将缓冲区数据取走后便可唤醒A。

在多道程序唤醒下， 由于存在着上述两类相互制约的关系，进程在运行过程中是否能获得处理机运行与以怎样的速度运行，并不能由进程自身控制，此即进程的异步性。

2. 临界资源

前面提到过，临界资源就是在一段时间内只允许一个进程访问的资源。

3. 临界区

由前述可知，不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进程访问。人们把在每个进程中访问临界资源的那段代码称为临界区。

显然，若能保证诸进程互斥地进入自己的临界区，便可实现诸进程对临界资源的互斥访问。为此，每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看他是否正被访问。如果此刻临界资源未被访问，进程便可进入临界区对该资源进程访问，并设置它正被访问的标志；如果此刻该临界资源正被某进程访问，则本进程不能进入临界区。因此，必须在临界区前面增加一段用于进程上述检查的代码，称为进入区。相应地，在临界区后面也要加上一段称为退出区，用于将临界区正被访问的标志恢复为未被访问的标志。

4. 同步机制应遵循的规则

1. 空闲让进
2. 忙则等待
3. 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。
4. 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

2.4.2 硬件同步机制

虽然可以利用软件方法解决诸进程互斥进入临界区的问题，但有一定难度，并且存在很大的局限性，故而现在已很少使用。相应地，目前许多计算机已提供了一些特殊的硬件指令，允许对一个字的内容进行检测或修正，或者是对两个字的内容进行变换等。可用这些特殊的指令来解决临界区问题。

1. 关中断

关中断，也就是关—中断。顾名思义，在进入锁测试之前关闭中断，直到完成锁测试并上锁之后才能打开中断。这样，进程在临界区执行期间，计算机系统不响应中断，从而不会引发调度，也就不会发生进程或线程切换。
但是这个方法也有许多缺点：

1. 滥用关中断权力可能导致严重后果
2. 关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能力
3. 关中断方法也不适用于多CPU系统，因为在一个处理器上个关中断并不能防止进程在其它处理器上执行相同的临界段代码

2. 利用Test-and-Set指令实现互斥

这是一种借助一条硬件指令——“测试并建立”指令TS以实现互斥的方法。这种指令的一般性描述如下：

boolean TS(boolean *lock)
{
	boolean old;
	old=*lock;
	*lock=TRUE;
	return old;
}

这条指令可以看作一个函数过程，其执行过程是不可分割的，即是一条原语。其中，lock有两种状态；当*lock=FALSE时，表示该资源空闲；当*lock=TURE时，表示该资源正在使用。

用TS指令管理临界区时，为每个临界资源设置一个布尔变量lock，由于变量lock代表了该资源的状态，故可把它看成一把锁。lock初值为FALSE，表示该临界资源空闲。进程在进入该临界区之前，首先用TS测试lock，如果其值为FALSE，则表示没有进程在临界区内，可以进入，并将TRUE值赋给lock，这就相当于关闭了临界资源，使任何进程都不能进入临界区，否则必须循环测试知道TS(s)为TRUE。利用TS指令实现互斥的循环进程结构可描述如下：

do{
	...
	while TS(&lock);
	critical section;
	lock=FALSE;
	remainder section;
	}while(TRUE);

3. 利用Swap执行实现进程互斥

该指令称为对换指令，用于交换两个字的内容。其处理过程描述如下：

void swap(boolean *a,boolean *b)
{
	boolean temp;
	temp=*a;
	*a=*b;
	*b=temp;
}

用对换指令可以简单有效地实现互斥，方法是为每个临界资源设置一个全局的布尔变量lock，其初值为FLASE，在每个进程中再利用一个局部布尔变量key。利用Swap指令实现进程互斥的循环进程可描述如下：

do{
	key=TRUE;
	do{
		swap(&lock,&key);
	}while(key!=FALSE;
	临界区操作;
	lock=FALSE;
	...
}while(TRUE);

利用上述硬件指令能有效地实现进程互斥，但当临界资源忙碌时，其它访问进程必须不断地进程测试，处于一种“忙等”状态，不符合“让权等待”的原则，造成处理机时间的浪费，同时也很难将它们用于解决复杂的进程同步问题。

2.4.3 信号量机制

信号量机制是一种卓有成效的进程同步工具。现在已被广泛地应用于单处理机和多处理机系统以及计算机网络中。

1. 整型信号量

整型信号量被定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问，其操作可描述如下：

wait(S)
{
	while(S<=0);
	s--;
}
signal(S)
{
	s++;
}

2. 记录型信号量

在整型信号量机制中的wait操作，只要是信号量 S < = 0 S<=0 S<=0，就会不断测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。而记录型信号量机制中，增加了有一个整型变量value表示资源数目，还增加了一个进程链表指针list，用于链接上述的所有等待进程。它所包含的上述两个数据项可描述如下：

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-
	s->value++;
	if(S->value<=0)
		wakeup(S->list);
}

在记录型信号量机制中，S->value的初值表示系统中某类资源的数目，又称资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，使系统中可供分配的该类资源数减少一个，因此S->value–；当S->value<0时，表示该类资源以分配完毕，因此进程应调用block原语进程自我阻塞，放弃处理机，并插入到信号量链表S->list中。此时，S->value的绝对值表示在该信号量链表中已阻塞进程的数目。

对信号量的每次signal操作表示执行进程释放一个单位资源，使系统中可供分配的该类资源数增加一个。若加1后仍是S->value<=0，则表示该信号量链表中仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S->list链表中的第一个等待进程唤醒。如果S->value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转换为互斥信号量，用于进程互斥。

3. AND型信号量

前面所述的进程互斥问题针对的是多个并发进程仅共享一个临界资源的情况。在有些应用场合，是一个进程往往需要获得两个更多的共享资源后方能执行其任务。

AND同步机制的基本思想是：将进程在整个允许过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。**亦即，对若干个临界资源的分配采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。

4. 信号量集

在前面所述的记录型信号量机制中，wait(S)或signal(S)操作仅能对信号量施以加1或减1操作，意味着每次只能对某类临界资源进行一个单位的申请或释放。当依次需要N个单位时，便要进行N次wait(S)操作，这显然是低效的，甚至会增加死锁的概率。

此外，在有些情况下， 为确保系统的安全性，当所申请的资源数量低于某一下限值时，还必须进行管制，不予以分配。因此，当进程申请某类临界资源时，在每次分配之前，都必须测试资源的数量，判断是否大于可分配的下限值，决定是否予以分配。

基于上述两点，可以对AND信号机制加以扩充，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。进程对信号量 S i S_{i} Si​的测试值不再是1，而是该资源的分配下限值 t i t_{i} ti​，即要求 S i ≥ t i S_{i}geq t_{i} Si​≥ti​，否则不予以分配。一旦允许分配，进程对该资源的需求之为 d i d_{i} di​，即表示资源占用量，进行 S i = S i − d i S_{i}=S_{i}-d_{i} Si​=Si​−di​操作，而不是简单的 S i = S i − 1 S_{i}=S_{i}-1 Si​=Si​−1。**由此形成一般化的“信号量集”机制。对应的Swait和Ssignal格式为：
S w a i t ( S 1 , t 1 , d 1 , . . . , S n , t n , d n ) Swait(S_{1},t_{1},d_{1},...,S_{n},t_{n},d_{n}) Swait(S1​,t1​,d1​,...,Sn​,tn​,dn​)
S s i g n a l ( S 1 , t 1 , d 1 , . . . , S n , t n , d n ) Ssignal(S_{1},t_{1},d_{1},...,S_{n},t_{n},d_{n}) Ssignal(S1​,t1​,d1​,...,Sn​,tn​,dn​)
一般“信号量集”还有下面几种特殊情况：

1. S w a i t ( S , d , d ) Swait(S,d,d) Swait(S,d,d)。此时在信号集中只有一个信号量S，但允许它每次申请d个资源，当现有资源少于d时，不予以分配。
2. S w a i t ( S , 1 , 1 ) Swait(S,1,1) Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量或互斥信号量。
3. S w a i t ( S , 1 , 0 ) Swait(S,1,0) Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当 S ≥ 1 Sgeq1 S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。