进程同步

发表于   |   分类于   |  

本文摘自汤小丹主编《计算机操作系统》（第三版）2.3 进程同步

在 OS 中引入进程后,虽然提高了资源的利用率和系统的吞吐量,但由于进程的异步性, 也会给系统造成混乱,尤其是在他们争用临界资源时。例如,当多个进程去争用一台打印 机时,有可能使多个进程的输出结果交织在一起,难于区分;而当多个进程去争用共享变 量、表格、链表时,有可能致使数据处理出错。进程同步的主要任务是对多个相关进程在 执行次序上进行协调,以使并发执行的诸进程之间能有效地共享资源和相互合作,从而使 程序的执行具有可再现性。

涉及概念

进程同步，临界资源，临界区，信号量，进程互斥，前趋关系，管程

进程同步的基本概念

两种形式的制约关系

在多道程序环境下,当程序并发执行时,由于资源共享和进程合作,使同处于一个系 统中的诸进程之间可能存在着以下两种形式的制约关系。

  1. 间接相互制约关系。同处于一个系统中的进程,通常都共享着某种系统资源,如共 享 CPU、共享 I/O 设备等。所谓间接相互制约即源于这种资源共享,例如,有两个进程 A 和 B,如果在 A 进程提出打印请求时,系统已将惟一的一台打印机分配给了进程 B,则此 时进程 A 只能阻塞;一旦进程 B 将打印机释放,则 A 进程才能由阻塞改为就绪状态。
  2. 直接相互制约关系。这种制约主要源于进程间的合作。例如,有一输入进程 A 通过 单缓冲向进程 B 提供数据。当该缓冲空时,计算进程因不能获得所需数据而阻塞,而当进 程 A 把数据输入缓冲区后,便将进程 B 唤醒;反之,当缓冲区已满时,进程 A 因不能再向 缓冲区投放数据而阻塞,当进程 B 将缓冲区数据取走后便可唤醒 A。

临界资源

在第一章中我们曾经介绍过,许多硬件资源如打印机、磁带机等,都属于临界资源 (Critical Resouce),诸进程间应采取互斥方式,实现对这种资源的共享。下面我们将通过一 个简单的例子来说明这一过程。

生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是:有一 群生产者进程在生产产品,并将这些产品提供给消费者进程去消费。为使生产者进程与消 费者进程能并发执行,在两者之间设置了一个具有 n 个缓冲区的缓冲池,生产者进程将它 所生产的产品放入一个缓冲区中;消费者进程可从一个缓冲区中取走产品去消费。尽管所 有的生产者进程和消费者进程都是以异步方式运行的,但它们之间必须保持同步,即不允 许消费者进程到一个空缓冲区去取产品,也不允许生产者进程向一个已装满产品且尚未被 取走的缓冲区中投放产品。

我们可利用一个数组来表示上述的具有 n 个(0,1,…,n-1)缓冲区的缓冲池。用输入 指针 in 来指示下一个可投放产品的缓冲区,每当生产者进程生产并投放一个产品后,输入 指针加 1;用一个输出指针 out 来指示下一个可从中获取产品的缓冲区,每当消费者进程取 走一个产品后,输出指针加 1。由于这里的缓冲池是组织成循环缓冲的,故应把输入指针加 1 表示成 in:= (in+1)mod n; 输出指针加 1 表示成 out:= (out+1) mod n。当 (in+1) mod n=out 时表示缓冲池满;而 in=out 则表示缓冲池空。此外,还引入了一个整型变量 counter,其初 始值为 0。每当生产者进程向缓冲池中投放一个产品后,使 counter 加 1;反之,每当消费 者进程从中取走一个产品时,使 counter 减 1。生产者和消费者两进程共享下面的变量:

1
2
3
4
Var n,integer;
type item=...;
var buffer: array[0,1,...,n-1] of item; in,out: 0,1,...,n-1;
counter: 0,1,...,n;

指针 in 和 out 初始化为 1。在生产者和消费者进程的描述中,noop 是一条空操作指令, while condition do no-op 语句表示重复的测试条件(condication),重复测试应进行到该条件变 为 false(假),即到该条件不成立时为止。在生产者进程中使用一局部变量 nextp,用于暂时 存放每次刚生产出来的产品;而在消费者进程中,则使用一个局部变量 nextc,用于存放每 次要消费的产品。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
producer: 
	repeat
		...
		produce an item in nextp; 
		...
		while counter=n do no-op; 
		buffer[in]:=nextp; 
		in:=in+1 mod n; 
		counter:=counter+1;
	until false;

consumer: 
	repeat
		while counter=0 do no-op; 
		nextc:=buffer[out]; 
		out:=(out+1) mod n; 
		counter:=counter-1; 
		consumer the item in nextc;
	until false;

虽然上面的生产者程序和消费者程序在分别看时都是正确的,而且两者在顺序执行时
其结果也会是正确的,但若并发执行时就会出现差错,问题就在于这两个进程共享变量 counter。生产者对它做加 1 操作,消费者对它做减 1 操作,这两个操作在用机器语言实现 时, 常可用下面的形式描述:

1
2
3
register1:=counter; register2:=counter; 
register1:=register1+1; register2:=register2-1; 
counter:=register1; counter:=register2;

假设 counter 的当前值是 5。如果生产者进程先执行左列的三条机器语言语句,然后消 费者进程再执行右列的三条语句,则最后共享变量 counter 的值仍为 5; 反之,如果让消费 者进程先执行右列的三条语句,然后再让生产者进程执行左列的三条语句,则 counter 值也 还是 5,但是,如果按下述顺序执行:

1
2
3
4
5
6
register1:=counter;			(register1=5) 
register1:=register1+1;   	(register1=6)
register2:=counter;			(register2=5)
register2:=register2-1; 	(register2=4)
counter:=register1; 		(counter=6) 
counter:=register2;			(counter=4)

正确的 counter 值应当是 5,但现在是 4。读者可以自己试试,倘若再将两段程序中各语句 交叉执行的顺序改变,将可看到又可能得到 counter=6 的答案,这表明程序的执行已经失去 了再现性。为了预防产生这种错误,解决此问题的关键是应把变量 counter 作为临界资源处 理,亦即,令生产者进程和消费者进程互斥地访问变量 counter。

临界区

由前所述可知,不论是硬件临界资源,还是软件临界资源,多个进程必须互斥地对它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区(critical section)。显然, 若能保证诸进程互斥地进入自己的临界区,便可实现诸进程对临界资源的互斥访问。为此, 每个进程在进入临界区之前,应先对欲访问的临界资源进行检查,看它是否正被访问。如 果此刻该临界资源未被访问,进程便可进入临界区对该资源进行访问,并设置它正被访问 的标志;如果此刻该临界资源正被某进程访问,则本进程不能进入临界区。因此,必须在 临界区前面增加一段用于进行上述检查的代码,把这段代码称为进入区(entry section)。相应 地,在临界区后面也要加上一段称为退出区(exit section)的代码,用于将临界区正被访问的 标志恢复为未被访问的标志。进程中除上述进入区、临界区及退出区之外的其它部分的代 码,在这里都称为剩余区。这样,可把一个访问临界资源的循环进程描述如下:

1
2
3
4
5
6
repeat
	|entry section|
	critical section;
	|exit section|
	remainder section;
until false;

同步机制应遵循的规则

为实现进程互斥地进入自已的临界区,可用软件方法,更多的是在系统中设置专门的 同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则:

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

信号量机制

1965 年,荷兰学者 Dijkstra 提出的信号量(Semaphores)机制是一种卓有成效的进程同步 工具。在长期且广泛的应用中,信号量机制又得到了很大的发展,它从整型信号量经记录 型信号量,进而发展为“信号量集”机制。现在,信号量机制已被广泛地应用于单处理机 和多处理机系统以及计算机网络中。

整型信号量

最初由 Dijkstra 把整型信号量定义为一个用于表示资源数目的整型量 S,它与一般整型 量不同,除初始化外,仅能通过两个标准的原子操作(Atomic Operation) wait(S)和signal(S) 来访问。很长时间以来,这两个操作一直被分别称为 P、V 操作。Wait(S)和 signal(S)操作可 描述为:

1
2
3
wait(S):	while S<=0 do no-op;
				  S:=S-1; 				  
signal(S): 		  S:=S+1;

wait(S)和 signal(S)是两个原子操作,因此,它们在执行时是不可中断的。亦即,当一个 进程在修改某信号量时,没有其他进程可同时对该信号量进行修改。此外,在 wait 操作中, 对 S 值的测试和做 S:=S-1 操作时都不可中断。

记录型信号量

在整型信号量机制中的 wait 操作,只要是信号量 S≤0,就会不断地测试。因此,该机 制并未遵循“让权等待”的准则,而是使进程处于“忙等”的状态。记录型信号量机制则 是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后,又会出 现多个进程等待访问同一临界资源的情况。为此,在信号量机制中,除了需要一个用于代 表资源数目的整型变量 value 外,还应增加一个进程链表指针 L,用于链接上述的所有等待 进程。记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数 据项可描述为:

1
2
3
4
type semaphore=record
			   value: integer;
			   L: list of process;
			   end

相应地,wait(S)和 signal(S)操作可描述为:

1
2
3
4
5
6
7
8
9
10
11
12
13
procedure wait(S)
	var S:semaphore;
	begin
		S.value:=S.value-1;
		if S.value<0 then block(S.L);
	end 

procedure signal(S)
	var S: semaphore; 
	begin
		S.value:=S.value+1;
		if S.value<=0 then wakeup(S.L); 
	end

在记录型信号量机制中,S.value 的初值表示系统中某类资源的数目,因而又称为资源 信号量。对它的每次 wait 操作,意味着进程请求一个单位的该类资源,使系统中可供分配 的该类资源数减少一个,因此描述为 S.value:=S.value-1;当 S.value<0 时,表示该类资源已 分配完毕,因此进程应调用 block 原语,进行自我阻塞,放弃处理机,并插入到信号量链表 S.L 中。可见,该机制遵循了“让权等待”准则。此时 S.value 的绝对值表示在该信号量链 表中已阻塞进程的数目。对信号量的每次 signal 操作,表示执行进程释放一个单位资源,使 系统中可供分配的该类资源数增加一个,故 S.value:=S.value+1 操作表示资源数目加 1。若 加 1 后仍是 S.value≤0,则表示在该信号量链表中,仍有等待该资源的进程被阻塞,故还应 调用 wakeup 原语,将 S.L 链表中的第一个等待进程唤醒。如果 S.value 的初值为 1,表示只允许一个进程访问临界资源,此时的信号量转化为互斥信号量,用于进程互斥。

AND 型信号量

上述的进程互斥问题,是针对各进程之间只共享一个临界资源而言的。在有些应用场 合,是一个进程需要先获得两个或更多的共享资源后方能执行其任务。假定现有两个进程 A 和 B,他们都要求访问共享数据 D 和 E。当然,共享数据都应作为临界资源。为此,可为 这两个数据分别设置用于互斥的信号量 Dmutex 和 Emutex,并令它们的初值都是 1。相应地, 在两个进程中都要包含两个对 Dmutex 和 Emutex 的操作,即

process A: process B:
wait(Dmutex); wait(Emutex);
wait(Emutex); wait(Dmutex);

若进程 A 和 B 按下述次序交替执行 wait 操作

1
2
3
4
5
6
7
process A: wait(Dmutex); 	于是 Dmutex=0

process B: wait(Emutex); 	于是 Emutex=0

process A: wait(Emutex); 	于是 Emutex=-1 A 阻塞 

process B: wait(Dmutex); 	于是 Dmutex=-1 B 阻塞

最后,进程 A 和 B 处于僵持状态。在无外力作用下,两者都将无法从僵持状态中解脱 出来。我们称此时的进程 A 和 B 已进入死锁状态。显然,当进程同时要求的共享资源愈多 时,发生进程死锁的可能性也就愈大。

AND 同步机制的基本思想是:将进程在整个运行过程中需要的所有资源,一次性全部 地分配给进程,待进程使用完后再一起释放。只要尚有一个资源未能分配给进程,其它所 有可能为之分配的资源也不分配给它。亦即,对若干个临界资源的分配,采取原子操作方 式:要么把它所请求的资源全部分配到进程,要么一个也不分配。由死锁理论可知,这样 就可避免上述死锁情况的发生。为此,在 wait 操作中,增加了一个“AND”条件,故称为 AND 同步,或称为同时 wait 操作,即 Swait(Simultaneous wait)定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Swait(S1,S2,...,Sn)
	if Si>=1 and ... and Sn>=1 then
		for i:=1 to n do 
		Si:=Si-1; 
		endfor
	else
	place the process in the waiting queue associated with the first Si found with Si<1,and set the program count of this process to the beginning of Swait operation
	endif

Ssignal(S1,S2,...,Sn) 
for i:=1 to n do
	Si:=Si+1;
Remove all the process waiting in the queue associated with Si into the ready queue.
endfor;

信号量集

在记录型信号量机制中,wait(S)或 signal(S)操作仅能对信号量施以加 1 或减 1 操作,意 味着每次只能获得或释放一个单位的临界资源。而当一次需要 N 个某类临界资源时,便要 进行 N 次 wait(S)操作,显然这是低效的。此外,在有些情况下,当资源数量低于某一下限 值时,便不予以分配。因而,在每次分配之前,都必须测试该资源的数量,看其是否大于 其下限值。基于上述两点,可以对 AND 信号量机制加以扩充,形成一般化的“信号量集” 机制。Swait 操作可描述如下,其中 S 为信号量,d 为需求值,而 t 为下限值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Swait(S1,t1,d1,...,Sn,tn,dn) 
	if Si>=t1 and ... and Sn>=tn then
		for i:=1 to n do 
			Si:=Si-di;
	endfor 
else
Place the executing process in the waiting queue of the first Si with Si<ti and set its program counter to the beginning of the Swait Operation.
endif


Ssignal(S1,d1,...,Sn,dn) 
	for i:=1 to n do
		Si:=Si+di;
Remove all the process waiting in the queue associated with Si into the ready queue 
endfor;

下面我们讨论一般“信号量集”的几种特殊情况:

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

信号量的应用

利用信号量实现进程互斥

为使多个进程能互斥地访问某临界资源,只须为该资源设置一互斥信号量 mutex,并设 其初始值为 1,然后将各进程访问该资源的临界区 CS 置于 wait(mutex)和 signal(mutex)操作 之间即可。这样,每个欲访问该临界资源的进程在进入临界区之前,都要先对 mutex 执行 wait 操作,若该资源此刻未被访问,本次 wait 操作必然成功,进程便可进入自己的临界区, 这时若再有其他进程也欲进入自己的临界区,此时由于对 mutex 执行 wait 操作定会失败,因而该进程阻塞,从而保证了该临界资源能被互斥地访问。当访问临界资源的进程退出临 界区后,又应对 mutex 执行 signal 操作,以便释放该临界资源。利用信号量实现进程互斥的 进程可描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Var mutex: semaphore:=1; 
	begin
	parbegin
		process 1: begin
						repeat 
							wait(mutex); 
							critical section 
							signal(mutex); 
							remainder seetion
						until false; 
					end
					
		process 2: begin 
						repeat
							wait(mutex); 
							ritical section 
							signal(mutex); 
							remainder section
						until false; 
					end
	parend

在利用信号量机制实现进程互斥时应注意,wait(mutex)和 signal(mutex)必须成对地出现。缺少 wait(mutex)将会导致系统混乱,不能保证对临界资源的互斥访问;而缺少 signal(mutex) 将会使临界资源永远不被释放,从而使因等待该资源而阻塞的进程不能被唤醒。

利用信号量实现前趋关系

还可利用信号量来描述程序或语句之间的前趋关系。设有两个并发执行的进程 P1 和 P2。 P1 中有语句 S1;P2 中有语句 S2。我们希望在 S1 执行后再执行 S2。为实现这种前趋关系, 我们只须使进程 P1 和 P2 共享一个公用信号量 S,并赋予其初值为 0,将 signal(S)操作放在 语句 S1 后面;而在 S2 语句前面插入 wait(S)操作,即

  • 在进程 P1 中,用 S1;signal(S);

  • 在进程 P2 中,用 wait(S);S2;

  • 由于 S 被初始化为 0,这样,若 P2 先执行必定阻塞,只有在进程 P1 执行完 S1;signal(S);操作后使 S 增为 1 时, P2 进程方能执行语句 S2 成功。同样,我们可以利用信号 量,按照语句间的前趋关系(见图),写出一个更为复 杂的可并发执行的程序。
    前趋关系图

图示是一个前趋图,其中 S1,S2,S3,…,S6 是最简单的程序段(只有一条语句)。 为使各程序段能正确执行,应设置若干个初始值为“0”的信号量。如为保证 S1→S2,S1→S3 的前趋关系,应分别设置信号量 a 和 b,同样,为了保证 S2→S4,S2→S5,S3→S6,S4→S6 和 S5→S6,应设置信号量 c,d,e,f,g。

1
2
3
4
5
6
7
8
9
10
11
Var a,b,c,d,e,f,g:semaphore: =0,0,0,0,0,0,0; 
	begin
		parbegin
			begin S1; signal(a); signal(b); end;
			begin wait(a); S2; signal(c); signal(d); end; 
			begin wait(b); S3; signal(e); end;
			begin wait(c); S4; signal(f); end;
			begin wait(d); S5; signal(g); end;
			begin wait(e); wait(f); wait(g); S6; end;
		parend 
	end

管程机制

虽然信号量机制是一种既方便、又有效的进程同步机制,但每个要访问临界资源的进 程都必须自备同步操作 wait(S)和 signal(S)。这就使大量的同步操作分散在各个进程中。这 不仅给系统的管理带来了麻烦,而且还会因同步操作的使用不当而导致系统死锁。这样, 在解决上述问题的过程中,便产生了一种新的进程同步工具——管程(Monitors)。

管程的定义

系统中的各种硬件资源和软件资源,均可用数据结构抽象地描述其资源特性,即用少 量信息和对该资源所执行的操作来表征该资源,而忽略了它们的内部结构和实现细节。例 如,对一台电传机,可用与分配该资源有关的状态信息(busy 或 free)和对它执行请求与释放 的操作,以及等待该资源的进程队列来描述。又如,一个 FIFO 队列,可用其队长、队首和 队尾以及在该队列上执行的一组操作来描述。

利用共享数据结构抽象地表示系统中的共享资源,而把对该共享数据结构实施的操作 定义为一组过程,如资源的请求和释放过程 request 和 release。进程对共享资源的申请、释 放和其它操作,都是通过这组过程对共享数据结构的操作来实现的,这组过程还可以根据 资源的情况,或接受或阻塞进程的访问,确保每次仅有一个进程使用共享资源,这样就可 以统一管理对共享资源的所有访问,实现进程互斥。

代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的资源 管理程序,共同构成了一个操作系统的资源管理模块,我们称之为管程。管程被请求和释放 资源的进程所调用。Hansan 为管程所下的定义是:“一个管程定义了一个数据结构和能为并 发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据”。

由上述的定义可知,管程由四部分组成:1 管程的名称;2 局部于管程内部的共享 数据结构说明;3 对该数据结构进行操作的一组过程;4 对局部于管程内部的共享数据 设置初始值的语句。图是一个管程的示意图。

管程示意图

管程的语法描述如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	type monitor_name = MONITOR;
<共享变量说明>;
define <(能被其他模块引用的)过程名列表>; 
use <(要调用的本模块外定义的)过程名列表>; 
procedure <过程名>(<形式参数表>);
	begin
		M
	end;
		M
function <函数名>(<形式参数表>):值类型; 
	begin
		M
	end; 
		M
begin 
	<管程的局部数据初始化语句序列>;
end

需要指出的是,局部于管程内部的数据结构,仅能被局部于管程内部的过程所访问, 任何管程外的过程都不能访问它;反之,局部于管程内部的过程也仅能访问管程内的数据 结构。由此可见,管程相当于围墙,它把共享变量和对它进行操作的若干过程围了起来, 所有进程要访问临界资源时,都必须经过管程(相当于通过围墙的门)才能进入,而管程每次 只准许一个进程进入管程,从而实现了进程互斥。

管程是一种程序设计语言结构成分,它和信号量有同等的表达能力,从语言的角度看, 管程主要有以下特性:

  1. 模块化。管程是一个基本程序单位,可以单独编译。
  2. 抽象数据类型。管程中不仅有数据,而且有对数据的操作。
  3. 信息掩蔽。管程中的数据结构只能被管程中的过程访问,这些过程也是在管程内部 定义的,供管程外的进程调用,而管程中的数据结构以及过程(函数)的具体实现外部不可见。

管程和进程不同,主要体现在以下几个方面:

  1. 虽然二者都定义了数据结构,但进程定义的是私有数据结构 PCB,管程定义的是公 共数据结构,如消息队列等;
  2. 二者都存在对各自数据结构上的操作,但进程是由顺序程序执行有关的操作,而管 程主要是进行同步操作和初始化操作;
  3. 设置进程的目的在于实现系统的并发性,而管程的设置则是解决共享资源的互斥使 用问题;
  4. 进程通过调用管程中的过程对共享数据结构实行操作,该过程就如通常的子程序一 样被调用,因而管程为被动工作方式,进程则为主动工作方式;
  5. 进程之间能并发执行,而管程则不能与其调用者并发;
  6. 进程具有动态性,由“创建”而诞生,由“撤销”而消亡,而管程则是操作系统中 的一个资源管理模块,供进程调用。

条件变量

在利用管程实现进程同步时,必须设置同步工具,如两个同步操作原语 wait 和 signal。 当某进程通过管程请求获得临界资源而未能满足时,管程便调用 wait 原语使该进程等待, 并将其排在等待队列上,如管程示意图所示。仅当另一进程访问完成并释放该资源之后,管程 才又调用 signal 原语,唤醒等待队列中的队首进程。

但是仅仅有上述的同步工具是不够的。考虑一种情况:当一个进程调用了管程,在管 程中时被阻塞或挂起,直到阻塞或挂起的原因解除,而在此期间,如果该进程不释放管程, 则其它进程无法进入管程,被迫长时间地等待。为了解决这个问题,引入了条件变量 condition。通常,一个进程被阻塞或挂起的条件(原因)可有多个,因此在管程中设置了多个 条件变量,对这些条件变量的访问,只能在管程中进行。

管程中对每个条件变量都须予以说明,其形式为:Var x,y:condition。对条件变量的 操作仅仅是 wait 和 signal,因此条件变量也是一种抽象数据类型,每个条件变量保存了一个 链表,用于记录因该条件变量而阻塞的所有进程,同时提供的两个操作即可表示为 x.wait 和 x.signal,其含义为:

  1. x.wait:正在调用管程的进程因x条件需要被阻塞或挂起,则调用x.wait将自己插 入到 x 条件的等待队列上,并释放管程,直到 x 条件变化。此时其它进程可以使用该管程。
  2. x.signal:正在调用管程的进程发现x条件发生了变化,则调用x.signal,重新启动 一个因 x 条件而阻塞或挂起的进程。如果存在多个这样的进程,则选择其中的一个,如果 没有,则继续执行原进程,而不产生任何结果。这与信号量机制中的 signal 操作不同,因为 后者总是要执行 s:=s+1 操作,因而总会改变信号量的状态。

如果有进程 Q 因 x 条件处于阻塞状态,当正在调用管程的进程 P 执行了 x.signal 操作后, 进程 Q 被重新启动,此时两个进程 P 和 Q,如何确定哪个执行,哪个等待,可采用下述两 种方式之一进行处理:

  1. P等待,直至Q离开管程或等待另一条件。
  2. Q等待,直至P离开管程或等待另一条件。

采用哪种处理方式,当然是各执一词。Hoare 采用了第一种处理方式,而 Hansan 选择了两者的折衷,他规定管程中的过程所执行的 signal 操作是过程体的最后一个操作,于是, 进程 P 执行 signal 操作后立即退出管程,因而进程 Q 马上被恢复执行。

热评文章