进程互斥

由于各进程要求使用共享资源（变量、文件等），而这些资源需要排他性使用，各进程之间竞争使用这些资源，这一关系称为进程互斥。

临界资源与临界区

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量。

而各个进程中对某个临界资源（共享变量）实施操作的程序片段称为临界区或互斥区。

临界区的使用原则

  • 没有进程在临界区时，想进入临界区的进程可进入
  • 不允许两个进程同时处于其临界区中
  • 临界区外运行的进程不得阻塞其他进程进入临界区
  • 不得使进程无限期等待进入临界区

进程互斥的软件解决方案

错误解法

考虑两个进程p和q，pturn与qturn表示哪个进程要进入临界区，P进入临界区的条件为pturn && not qturn，而Q进入临界区的条件为not pturn && qturn:

1
2
3
4
5
//进程p：
pturn = true;     
while (qturn) ;          
visit();   	//访问临界区
pturn = false;
1
2
3
4
5
//进程q：
qturn = true;     
while (pturn) ;          
visit();   	//访问临界区
qturn = false;

如果由于CPU调度使得两个进程都执行完了第一行语句，也就是pturn和qturn都为true了，那么就都会在下一行while语句上死循环，互相都在谦让对方执行，也就不满足了临界区的使用原则—不得使进程无限期等待进入临界区。

Dekker算法

Dekker互斥算法是由荷兰数学家Dekker提出的一种解决并发进程互斥与同步的软件实现方法。假设有p和q两个进程，变量pturn、qturn表示p和q进程是否想要资源（可以想象为举手示意想要），变量turn表示安排资源给谁：

1
2
3
4
5
6
7
8
9
10
11
12
//进程P：
pturn = true; 	//进程p举手示意想要访问
while (qturn) { 	//如果进程q也举手了
     if (turn == 2) {   //资源被安排给了q
	     pturn = false;   //进程p把手放下
	     while (turn == 2);   //资源安排给q的时候一直等待
	     pturn = true;    //此时资源安排给了自己，进程p再举手
	 }
}
visit();	//访问临界区
turn = 2;   //进程p使用完了，安排资源给q
pturn = false;	//进程p把手放下
1
2
3
4
5
6
7
8
9
10
11
12
//进程q：
qturn = true; 
while (pturn) { 
     if (turn == 1) { 
	     qturn = false; 
	     while (turn == 1); 
	     qturn = true; 
	 }
}
visit();	//访问临界区
turn = 1;
qturn = false;

如果两个进程都执行完了第一行语句，也就是pturn和qturn都为true了，那么会根据变量turn进一步查看究竟是把资源安排给了谁，如果安排给了另一个进程，那么自己就先把手放下，等待安排资源给自己。

与之前的错误解法相比，可以发现Dekker算法就是在原本的while死循环上做了进一步的判断，引入的turn变量总是会安排一个进程访问临界区。

Peterson算法

Peterson算法是另一种解决并发进程互斥与同步的软件实现方法，而且克服了强制轮流法的缺点。其使用十分方便，只需要向如下这样调用即可:

1
2
3
enter_region(i);
visit();	//访问临界区
leave_region(i);

其中的enter_region方法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#define FALSE 0
#define TRUE 1
#define N 2 //进程的个数
int turn;   //轮到谁
int interested[N];   //兴趣数组，初始值均为FALSE
 
void enter_region(int process) // process = 0 或 1
{
	int other;     // 另外一个进程的进程号
	other = 1 - process;
	interested[process] = TRUE;  // 表明本进程感兴趣
	turn = process;  // 设置标志位         
	while(turn == process && interested[other] == TRUE); 
}

如果有两个进程都要执行的话，turn会被设置成后一个进程的进程号，这时候因为要按照先来后到的规矩，后一个进程在判断while条件的时候turn == process成立，也就进行循环等待，而先进入的进程可以访问临界区。当先进入的进程离开了临界区，就调用leave_region方法，将自己的兴趣设为FALSE，后一个进程判断interested[other] == TRUE不成立时就可以跳出while循环进入临界区了。

1
2
3
void leave_region(int process){
	interested[process] = FALSE;   // 本进程已离开临界区
}

进程互斥的硬件解决方案

“测试并加锁”指令

TSL

“交换”指令

XCHG

进程同步

进程同步指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。
具体地说，一个进程运行到某一点时， 要求另一伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态，获得消息后被唤醒进入就绪态。

信号量及PV操作

信号量是一个特殊变量，用于进程间传递信息的一个整数值，定义如下：

1
2
3
4
5
struct semaphore
{  
	int count;
	queueType queue;
}

可以对其执行down和up操作，也就是常见的P和V操作（PV操作均为原语操作），定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
P(semaphore s) 
{
	s.count--;
	if (s.count < 0)
	{
		//该进程状态置为阻塞状态；
		//将该进程插入相应的等待队列s.queue末尾;
		//重新调度；
	}
}

V(semaphore s) {   
	s.count++;   
	if (s.count <= 0)   
	{      
		//唤醒相应等待队列s.queue中等待的一个进程；      
		//改变其状态为就绪态，并将其插入就绪队列；    
	} 
}

用PV操作解决进程间互斥问题

  • 分析并发进程的关键活动，划定临界区
  • 设置信号量 mutex，初值为1
  • 在临界区前实施 P(mutex)
  • 在临界区之后实施 V(mutex)

用信号量解决生产者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

这里使用三个信号量，其中mutex用于解决互斥问题，empty和full用于解决同步问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#define N 100	//缓冲区个数
typedef int semaphore;	//信号量是一种特殊的整型数据
semaphore mutex = 1;	//互斥信号量：控制对临界区的访问
semaphore empty = N;	//空缓冲区个数，初始为N
semaphore full = 0;		//满缓冲区个数，初始为0

void producer() {
    while(TRUE) {
        int item = produce_item();
        p(&empty);
        p(&mutex);
        insert_item(item);
        v(&mutex);
        v(&full);
    }
}

void consumer() {
    while(TRUE) {
        p(&full);
        p(&mutex);
        int item = remove_item();
        v(&mutex);
        v(&empty);
        consume_item(item);
    }
}

注意：不能交换p(&empty);和p(&mutex);的顺序，否则会导致死锁。

用信号量解决读者-写者问题

问题描述：多个进程共享一个数据区，这些进程分为只读数据区中的数据的读者进程和只往数据区中写数据的写者进程。允许多个读者同时执行读操作，不允许多个写者同时操作，不允许读者、写者同时操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
typedef int semaphore;
semaphore count_mutex = 1;	//对count加锁
semaphore data_mutex = 1;	//对读写的数据加锁
int count = 0;	//对数据进行读操作的进程数量

void reader() {
    while(TRUE) {
        p(&count_mutex);
        count = count + 1;
        if(count == 1) p(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        v(&count_mutex);
        read();
        p(&count_mutex);
        count = count - 1;
        if(count == 0) v(&data_mutex);
        v(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        p(&data_mutex);
        write();
        v(&data_mutex);
    }
}

管程

由于信号量机制程序编写困难、易出错，所以在程序设计语言中引入管程。

管程是一个抽象数据类型，由关于共享资源的数据结构及在其上操作的一组过程组成，进程只能通过调用管程中的过程来间接地访问管程中的数据结构。

互斥/同步

互斥：管程是互斥进入的，管程的互斥性是由编译器负责保证的。

同步：管程中设置条件变量及等待/唤醒操作以解决同步问题，可以让一个进程或线程在条件变量上等待（此时，应先释放管程的使用权），也可以通过发送信号将等待在条件变量上的进程或线程唤醒。

Hoare管程

因为管程是互斥进入的，所以当一个进程试图进入一个已被占用的管程时，应当在管程的入口处等待，为此，管程的入口处设置一个进程等待队列，称作入口等待队列。

如果进程P唤醒进程Q，则P等待Q执行；如果进程Q执行中又唤醒进程R，则Q等待R执行；如此， 在管程内部可能会出现多个等待进程。在管程内需要设置一个进程等待队列，称为紧急等待队列，紧急等待队列的优先级高于入口等待队列的优先级。

Hoare管程

条件变量

条件变量是在管程内部说明和使用的一种特殊类型的变量，对于条件变量，可以执行wait和signal操作：

  • wait(c)：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程进入c链末尾。
  • signal(c)：如果c链为空，则相当于空操作，执行此操作的进程继续执行；否则唤醒第一个等待者，执行此操作的进程进入紧急等待队列的末尾。

用管程解决生产者-消费者问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//管程
monitor ProducerConsumer     
	condition full, empty;  //条件变量
	integer count;      
	    
	procedure insert (item: integer);     
	begin         
		if count == N then wait(full);         
		insert_item(item); count++;         
		if count ==1 then signal(empty);     
	end;          
	
	function remove: integer;     
	begin         
		if count==0 then wait(empty);         
		remove = remove_item; count--;         
		if count==N-1 then signal(full);     
	end;          
	count:=0; 
end monitor; 

//生产者
procedure producer; 
begin     
	while true do     
	begin           
		item = produce_item;         
		ProducerConsumer.insert(item);     
	end 
end; 
 
//消费者
procedure consumer; 
begin     
	while true do     
	begin         
		item=ProducerConsumer.remove;         
		consume_item(item);          
	end 
end;

MESA管程

Hoare管程有个缺点就是会有两次额外的进程切换，因此MESA管程将原本的signal操作变为notify操作：当一个正在管程中的进程执行notify(x)时，它使得x条件队列得到通知，发信号的进程继续执行，而位于条件队列头的进程在将来合适的时候且当处理器可用时恢复执行。

由于收到通知时并未执行，且对等待进程在notify之后何时运行没有任何限制，所以当进程真正被调度时，条件不一定成立，因而这个进程必须重新检查条件，也就是用while循环取代if语句。

IPC（进程间通信）

进程间通信（IPC，InterProcess Communication）是指在不同进程之间传播或交换信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

进程通信的方式通常有管道（包括无名管道和命名管道）、消息队列、信号量、共享存储、Socket、Streams等。其中 Socket和Streams支持不同主机上的两个进程IPC。

管道

管道，通常指无名管道，是 UNIX 系统IPC最古老的形式。

管道是通过调用 pipe 函数创建的，当一个管道建立时，它会创建两个文件描述符：fd[0]为读而打开，fd[1]为写而打开，要关闭管道只需将这两个文件描述符关闭即可。

管道

单个进程中的管道几乎没有任何用处。所以，通常调用 pipe 的进程接着调用 fork，这样就创建了父进程与子进程之间的 IPC 通道。若要数据流从父进程流向子进程，则关闭父进程的读端（fd[0]）与子进程的写端（fd[1]）；反之，则可以使数据流从子进程流向父进程。

特点:

  • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
  • 它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。

FIFO

FIFO也称为命名管道，它是一种文件类型，可以在无关的进程之间交换数据，与无名管道不同。

FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。

FIFO

消息队列

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。

  • 消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
  • 消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
  • 消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

信号量

信号量是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

共享内存

共享内存指两个或多个进程共享一个给定的存储区，因为数据不需要在进程之间复制，所以这是最快的一种 IPC。由于多个进程可以同时操作，所以信号量与共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

套接字

与其它通信机制不同的是，它可用于不同机器间的进程通信。

参考资料