进程同步的概念及其术语

进程间两种形式的制约关系

直接制约关系

进程间的相互联系是有意识的安排的。

间接制约关系

进程间要通过某种中介发生联系，是无意识安排的。

进程的同步

一般来说，一个进程相对另一个进程的运行速度是不确定的。也就是说，进程之间是在异步环境下运行的，每个进程都以各自独立的、不可预知的速度向运行的终点推进。
但是，相互合作的几个进程需要在某些确定点上协调其工作。一个进程到达了这些点后，除非另一进程已完成了某些操作，否则就不得不停下来等待这些操作的结束。
所谓进程同步是指多个相互合作的进程，在一些关键点上可能需要互相等待或互相交换信息，这种相互制约关系称为进程同步。

进程的互斥

由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。
其实互斥是进程同步的一种特殊情况，互斥也是为了达到让进程之间协调推进的目的。

临界区和临界资源

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

在进程中涉及到临界资源的程序段叫临界区

多个进程的临界区称为相关临界区

进程须在临界区前面增加一段用于进行上述检查的代码，称为进入区(entry section)。在临界区后面加上一段称为退出区(exit section)的代码。

1
2
3
4
5
6
7
8
While (1)
{
   进入区代码;
   临界区代码;
   退出区代码;
   其余代码 ;
}

互斥区原则

  • 空闲让进:当无进程在互斥区时，任何有权使用互斥区的进程可进入
  • 忙则等待:不允许两个以上的进程同时进入互斥区
  • 有限等待:任何进入互斥区的要求应在有限的时间内得到满足
  • 让权等待:处于等待状态的进程应放弃占用CPU,以使其他进程有机会得到CPU的使用权

忙等待

  • 硬件方法 ：中断禁用
  • 软件方法:
    • 锁变量
    • 严格轮换法
    • Peterson方法

硬件方法 ：中断禁用

为保证互斥，只需保证进程不被中断就可以了，通过系统内核为启用中断和禁用中断定义的原语实现。进程结构：

1
2
3
4
5
6
7
8
While(true)
 { 
    禁用中断;     
    临界区; 
    启用中断; 
    其余部分;
 }

这个方案并不好，因为把屏蔽中断的权力交给用户进程是不明智的。设想一下，若一个进程屏蔽中断后不再打开中断，其结果将会如何？整个系统可能会因此终止。

而且，如果系统是多处理器（有两个或可能更多的处理器），则屏蔽中断仅仅对执行disable指令的那个CPU有效。其他CPU仍将继续运行，并可以访问共享内存。

所以结论是：屏蔽中断对于操作系统本 身而言是一项很有用的技术，但对于用户进程则不是一种合适的通用互斥机制。

单标志-锁方法

设置一个公用整形变量lock，用来指示临界区内是否有进程在运行。0表示空闲，没有进程。1表示忙，有进程。

进程进入临界区前，检查lock,若为0，进入临界区，同时把lock置为1。

若lock为1，进程等待直到lock值变为0。

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
int lock=0；
 
//第一个程序
 P0:{
   Do{
 While(lock!=0); 
 lock=1;
 进入 P0 的临界区代码 CS0; 
 lock=0;
 进入 P0 的其他代码;
}
   While(true)
  }
  
 //第二个程序
 P1:{
  Do{
 While(lock!=0);
 lock=1;
 进入 P1 的临界区代码 CS1; 
 lock=0;
 进入 P1的其他代码;
}
   While(true)
  }

假设P0 进程读出锁变量的值发现它为0， 而恰好在它将其值设置为1之前，P1 进程被调度运行，发现它为0，将该锁变量设置为1，P1 进入临界区。

当P0 进程进程再次能运行时，它继续将该锁设置为1，并进入临界区

P0 ，P1 两个进程同时进入临界区中。违背了临界区的访问规则“忙则等待”。

单标志-改进-严格轮换法

设置一个公用整形变量 turn，用来指示允许进入临界区的进程标识。若 turn 为 0，则允许进程 P0 进入临界区；否则循环检查该变量，直到 turn 变为本进程标识；在退出区，修改允许进入进程的标识 turn 为1。进程 P1 的算法与此类似。两个进程的程序结构如下：

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
int turn=0；

//程序0
 P0: {
   Do{
 While(turn!=0); 
 进入 P0 的临界区代码 CS0; 
 turn=1;
 进入 P0 的其他代码;
}
    While(true)
}


//程序1
 P1: {
   Do{
 While(turn!=1); 
 进入 P1 的临界区代码 CS1; 
 turn=0;
 进入 P1的其他代码;
}
    While(true)
}

此方法可保证互斥访问临界资源，但存在问题是强制两个进程交替进入临界区，造成资源浪费。

例如，当进程P0 退出临界区后将 turn 置为 1，以便允许进程P1 进入临界区。但如果进程 P1 暂时并未要求访问该临界资源，而 P0 又想再次访问临界资源，P1没有把标志位恢复为0，则P0将无法进入临界区。

可见，此算法不能保证实现“空闲让进”准则。

改进-双标志先检查

设置标志数组 flag[]表示进程是否在临界区中执行，初值均为假。在每个进程访问该临界资源之前，先检查另一个进程是否在临界区中，若不在则修改本进程的临界区标志为真并进入临界区，在退出区修改本进程临界区标志为假。两进程的程序结构如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
boolean flag[2]={false,false};
P0:{
	Do{
    While flag[1];
    flag[0]=true;
    进程 P0 的临界区代码 CS0; 
    flag[0]=false;
    进程 P0 的其他代码;
	}
	While(true)
}
P1:{
	Do{
    While flag[0];
    flag[1]=true;
    进程 P1 的临界区代码 CS1; 
    flag[1]=false;
    进程 P1 的其他代码;
	}
	While(true)
}


此算法解决了“空闲让进”的问题，但又出现了新问题。

当两个进程都未进入临界区时，它们各自的访问标志都为 false，若此时刚好两个进程同时都想进入临界区，并且都发现对方的标志值为 false（当两进程交替执行了检查语句后，都满足 flag[]=false 的条件）， 于是两个进程同时进入了各自的临界区。

违背了临界区的访问规则“忙则等待”。

改进-双标志后检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
boolean flag[2]={false,false};
P0:{
	Do{
	  flag[0]=true;
      While flag[1]; 
      进程 P0 的临界区代码 CS0; 
      flag[0]=false;
      进程 P0 的其他代码;
	}
	While(true)
}
P1:{
	Do{
	  flag[1]=true;
      While flag[0]; 
      进程 P0 的临界区代码 CS0; 
      flag[1]=false;
      进程 P1 的其他代码;
	}
	While(true)
}

此算法可以有效地防止两进程同时进入临界区，但存在两个进程都进不了临界区的问题。

即当两个进程同时想进入临界区时，它们分别将自己的标志位设置为 true，并且同时 去检查对方的状态，发现对方也要进入临界区，于是对方互相谦让，结果都无法进入临界区， 造成“死等”现象。

违背了“有限等待”的准则。

Peterson方法

1981年，G. L. Peterson 发现了一种简单得多的互斥算法。终于完美地解决了问题。

算法思想是算法3和算法1的结合。标志数组 flag[]表示进程是否希望进入临界区或是否在临界区中执行。此外，还设置了一个turn 变量，用于指示允许进入临界区的进程标识。两进程的程序结构如下：

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
boolean flag[2]={false,false};
int turn;
P0:{
    Do{
        flag[0]=true;
        turn=1; 
        While (flag[1] && turn==1);
        进程 P0 的临界区代码 CS0; 
        flag[0]=false;
        进程 P0 的其他代码;
      }
    While(true)
 }
   
P1:{
    Do{
      flag[1]=true;
      turn=0; 
      While (flag[0] && turn==0);
      进程 P1 的临界区代码 CS1; 
      flag[1]=false;
      进程 P1的其他代码;
      }
    While(true)
}


一开始，没有任何进程处于临界区中，现在P0进程执行。它通过设置其数组元素和将turn置为1, 并进入临界区执行。如果P1现在执行，P1将在此处挂起直到 flag[0]变成false，该事件只有在P0退出临界区时才会发生。

ü现在考虑两个进程几乎同时要进入临界区的情况。P0将turn 置为1，P1将turn置为0。但只有后被保存进去的值才有效，前一个因被重写而丢失。假设P1是后存入的，则turn为0。当两个进程都运行到while语句时，P0将循环0次并进入临界区，而P1则将不停地循环且不能进入临界区，直到P0退出临界区为止。

至此，软件方法可以正确地解决上述同步问题。

缺点：**并不完美**

上述解法是正确的，但它们都有忙等待的缺点。这些解法在本质上是这样的：

“当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止”

睡眠与唤醒

sleep和wakeup原语

原语：由多条指令组成，是一种特殊的系统功能调用，它可以完成一个特定的功能。

原语的特点：

  • 执行时不可中断

  • 不可并发

  • 在管态下执行，常驻内存

现在来考察两条进程间通信原语：sleep和wakeup

它们一起合作，实现进程在无法进入临界区时阻塞，而不是忙等待。而当临界区可用时，可以通过wakeup唤醒相关阻塞的进程。

  • Sleep原语：不需要参数，调用时将使得调用进程进入阻塞状态，直到另外一个进程将其唤醒。

    1
    Sleep()

  • Wakeup原语：需要输入一个参数，即需要被**唤醒的指定进程。

    1
    Wakeup(process)

    生产者-消费者问题

    作为使用这些原语的一个例子，我们考虑生产者-消费者问题，也称作有界缓冲区问题。

    两个进程共享一个公共的固定大小的缓冲区。其中一个是生产者，将信息放入缓冲区；另一个是消费者，从缓冲区中取出信息。

    也可以把这个问题一般化为m个生产者和n 个消费者问题，但是我们只讨论一个生产者和一个消费者的情况，这样可以简化解决方案。

    同步问题
    • 生产进程不能往“满”的缓冲区中放产品
    • 消费进程不能从“空”的缓冲区中取产品

当缓冲区已满，而此时生产者还想向其中放入一个新的数据项的情况。其解决办法是让生产者睡眠，待消费者从缓冲区中取出一个或多个数据项时再唤醒它。

同样地，当消费者试图从缓冲区中 取数据而发现缓冲区为空时，消费者就睡眠，直到生产者向其中放入一些数据时再将其唤醒。

这个方法听起来简单，但它包含与前边问题一样的竞争条件。为了跟踪缓冲区中的数据项数，我们需要一个变量count。如果缓冲区最多存放N个数据项，则生产者代码将首先检查count是否达到N，若是，则生产者睡眠；否则生产者向缓冲区中放入一个数据项并增量count的值。

消费者的代码与此类似：首先测试count是否为0，若是，则睡眠；否则从中取走一个数据项并递减count 的值。

每个进程同时也检测另一个进程是否应被唤醒，若是则唤醒之。生产者和消费者的代码如图所示。

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
#defind N 100
int count = 0;
//生产者
void producer(void)
{
    int item;
    while (TRUE) {
           item=produce_item(); //产生下一个数据项
           if (count == N) 
           		sleep();   	//如果缓冲区满，则生产者睡眠，后续程序不执行
           insert_item(item);  //如果缓冲区不为满或者被唤醒，将数据项存入缓冲区
           count = count+1; //缓冲区数据项个数+1
           if (count == 1)   
           		wakeup(consumer);//如果缓冲区为空，唤醒消费者
    }
}

//消费者
void consumer(void)
{
    int item;
    while (TRUE) {
           if (count == 0) 
           		sleep();    //如果缓冲区为空，睡眠
           item=remove_item();  //如果缓冲区不为空或者被唤醒，睡眠取出来一个数据
           count = count-1;   //将缓冲区的数据项计数器减1 
           if (count == N-1) 
           		wakeup(producer);  //如果缓冲区为满，唤醒生产者。
           consume_item(item);  //消费一个数据项。
    }
}

问题：

这里有可能会出现竞争条件，其原因是对count的访问未加限制。可能出现以下情况：缓冲区为空，消费者刚刚读取count的值发现它为0。此时调度程序决定暂停消费者并启动运行生产者。生产者向缓冲区中加入一个数据项，count加1。现在count的值变成了1。它推断认为于count刚才为0，所以消费者此时一定在睡眠，于是生产者调用wakeup来唤醒消费者。

但是，消费者此时在逻辑上并未睡眠，所以wakeup信号丢失。当消费者下次运行时，它将测试先前读到的count值，发现它为0，于是睡眠。生产者迟早会填满整个缓冲区，然后睡眠。这样一来,两个进程都将永远睡眠下去。

问题的实质在于发给一个（尚)未睡眠进程的wakeup信号丢失了。如果它没有丢失，则一切都很正常。

信号量机制

1965年，由荷兰学者 迪科斯彻 Dijkstra 提出，是一种卓有成效的进程同步机制。

经历整型信号量、记录型信号量，发展为“信号量集”机制。

P、V操作是原语。

信号量的值除初始化外，只能由P、V原语修改。(wait、signal)

信号量是Dijkstra提出的一种方法，它使用一个整型变量来累计唤醒次数，供以后使用。在他的建议中引入了一个新的变量类型，称作信号量（semaphore）。

一个信号量的取值可以为0（表示没有保存下来的唤醒操作）或者为正值（表示有一个或多个唤醒操作）。Dijkstra建议设立两种操作：down和up（分别为一般化后的sleep和wakeup)。在Dijkstra 原来的论文中，他分别使用名称 P 和 V 而不是 down 和 up ，荷兰语中， Proberen的意思是尝试，Verhogen的含义是增加或升高。

  • 对一信号量执行 P (down) 操作，是检查其值是否大于0。若该值大于0，则将其值减1（即用掉一个保存的唤醒信号)并继续；若该值为0，则进程将睡眠，而且此时down操作并未结束。

    检查数值、修改变量值以及可能发生的睡眠操作均作为一个单一的、不可分割的原子操作完成。保证一旦一个信号量操作开始，则在该操作完 成或阻塞之前，其他进程均不允许访问该信号量。这种原子性对于解决同步问题和避免竞争条件是绝对必要的。所谓原子操作，是指一组相关联的操作要么都不间断地执行，要么都不执行

  • V (up) 操作对信号量的值增1。如果一个或多个进程在该信号量上睡眠，无法完成一个先前的down操作， 则由系统选择其中的一个（如随机挑选)并允许该进程完成它的down操作。于是，对一个有进程在其上睡眠的信号量执行一次up操作之后，该信号量的值仍旧是0，但在其上睡眠的进程却少了一个。信号 量的值增1和唤醒一个进程同样也是不可分割的。不会有某个进程因执行V而阻塞。

信号量的分类

  • 整型信号量
  • 记录型信号量
  • AND型信号量
  • 信号量集

整型信号量原语

1
2
3
4
5
P(S):
	while S<=0 do no-op;
		S:=S-1;
V(S):
	S:=S+1;

前驱关系用整型信号量实现

如果是下面的前驱关系

我们可以设置一个信号量S，其初值为0，

1
2
P1;
V(S);

和

1
2
P(S);
P2;

多个进程同步用整型信号量实现进程同步

image-20241110150155772

设5个信号量

semaphore fl=f2=f3=f4=f5=O

含义：分别表示进程S1、S2、S3、S4、S5是否执行完成。

PVcodes 前进程，后放V；后进程，前放P"

两个进程互斥用信号量实现

设 mutex=1

Process1:

1
2
3
4
5
6
7
8
while (true)
  {
    P(mutex);
    critical section;
    V(mutex);
    remainder  section;
  }

Process1:

1
2
3
4
5
6
7
8
while (true)
  {
    P(mutex);
    critical section;
    V(mutex);
    remainder  section;
  }

生产者-消费者问题用整型信号量实现

该解决方案使用了三个信号量：

  • full，用来记录充满的缓冲槽数目；

  • empty，记录空的缓冲槽总数；

  • mutex，用来确保生产者和消费者不会同时访问缓冲区。

full的初值为0，empty的初值为缓冲区中槽的数目，mutex初值为1。

供两个或多个进程使用的信号量，其初值为1，保证同时只有一个进程可以进入临界区，称作二元信号量。

如果每个进程在进入临界区前都执行一个P操作，并在刚刚退出时执行一个V操作，就能够实现互斥。

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
#define N 100  /* 缓冲区中的槽数目 */
typedef int semaphore;/* 信号量是一种特殊的整型数据 */
semaphore mutex=1 /* 控制对临界区的访问 */
semaphore empty=N/* 计数缓冲区的空槽数目 */
semaphore full =0/* 计数缓冲区的满槽数目 */

void producer(void)
{
    int item;

    while (TRUE) {
           item=produce_item();/* 产生放在缓冲区中的一些数据 */
           p(empty);/* 将空槽数目减1 */
           p(mutex);/* 进入临界区 */
           insert_item(item);/* 将新数据项放到缓冲区中 */
           v(mutex);/* 离开临界区 */
           v(full);/* 将满槽的数目加1 */
    }
}

void consumer(void)
{
    int item;

    while (TRUE) {
           p(full);/* 将满槽数目减1 */
           p(mutex);/* 进入临界区 */
           item=remove_item();/* 从缓冲区中取出数据项 */
           v(mutex);/* 离开临界区 */
           v(empty);/* 将空槽数目加1 */
           consume_item(item);
    }
}

记录型信号量

在整型信号量机制中的**wait操作，只要是信号量S<=0,就会不断测试。因此，该机制并未遵循“让权等待”准则，而是使进程处于“忙等”状态。记录型信号量机制则是一种不存在“忙等”的进程同步机制。**

但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一个临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量**value外，还增加一个进程链表指针L**，用于链接上述的所有等待进程。

记录型信号量是由于它采用了记录型的数据结构而得名的。

数据结构及P-V操作

记录型信号量的数据结构

1
2
3
4
5
type semaphore=record
     value: integer; /*初值为资源信号量的数目。*/
     L: list of process; /*链表L用于链接所有等待的进程。*/
end

记录型信号量的P-V操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* P操作：申请一个单位资源*/
P(s)
{
     s.value = s.value -1 ;
     if (s.value < 0)
    {
	    该进程状态置为等待状态
         将该进程的PCB插入相应的等待队列末尾s.queue;
    }
}
/* V操作：释放一个单位资源*/
V(s)
{
     s.value = s.value +1;
     if (s.value < = 0)
    {
        唤醒相应等待队列s.queue中等待的一个进程
        改变其状态为就绪状态,并将其插入就绪队列
     }
}

  • S.value>0: 系统中可利用的资源数量

  • S.value=0:资源恰好分配完毕

  • S.value<0:其绝对值表示在该信号量链表中已阻塞进程的数目。

AND型信号量

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

​ process A: process B:

​ P(Dmutex); P(Emutex);

​ P(Emutex); P(Dmutex);

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

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

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
P(S1,S2,…,Sn)
     if  S1≥1 and … and Sn≥1 then
         for i:=1 to n do
            Si:=Si-1;
         endfor
     else
           当发现有任何Si<1时，该进程状态置为等待状态
     endif
     
     
     
     
V(S1,S2,…,Sn)
     for i:=1 to n do
          Si:=Si+1;
           将与Si相关的所有等待进程移出到就绪队列
     endfor


信号量集

一次需要N个某类临界资源时，就要进行N次P操作——低效又可能死锁。

信号量集是指同时需要多种资源、每种占用的数目不同，且可分配的资源还存在一个临界值时的信号量处理。

一般信号量集的基本思路是：在AND型信号量的基础上进行扩充，在一次原语操作中完成所有的资源申请。

进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si >= ti；即当资源数量低于ti时，便不予分配）

占用值为di（表示资源的申请量，即Si=Si-di）

对应的P、V原语格式为：

  • P(S1, t1, d1; …; Sn,tn, dn);

  • V(S1, d1; …; Sn, dn);

实现方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
P(S1,t1,d1,…, Sn,tn,dn)
     if S1≥t1 and … and Sn≥tn then
         for i:=1 to n do
             Si:=Si-di;
         endfor
     else
           当发现有Si<ti时，该进程状态置为等待状态
     endif

V(S1, d1,…, Sn, dn)
    for i:=1 to n do
         Si:=Si+di;
          将与Si相关的所有等待进程移出	到就绪队列                      
    endfor