阅读量:

2.3 进程同步

思维导图

一、进程同步的基本概念

在多道程序环境下，进程是并发执行的，不同进程之间存在着不同的制约关系。为了协调进程之间的相互制约的关系，引入进程同步的概念。

1. 临界资源

多个进程可以共享的各种资源，但是有的资源只能同时为一个进程服务，这样的资源就被称为临界资源。

对于临界资源的访问必须互斥地进行。在每个进程中，访问临界资源的代码称为临界区。为了确保临界资源的正确使用，可以将临界资源的访问分为四个过程：

• 进入区：为了进入临界区使用临界资源，在进入区要检查能否进入临界区。若能进入临界区，则应设置正在访问临界区的标志，以阻止其它进程同时进入临界区；
• 临界区：进程中访问临界资源的那段代码，又称临界段；
• 退出区：将正在访问临界区的标志清除；
• 剩余区：代码中的其余部分。

2. 同步

同步亦称直接制约关系。是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递消息所产生的制约关系。进程间的直接制约关系源于它们之间的相互合作。

例如输入进程 A 通过单缓冲向进程 B 提供数据。当该缓冲区为空时，进程 B 不能获得所需要的数据而阻塞，当进程 A 将数据输入缓冲区时，进程 B 被唤醒；当缓冲区为满时，进程 A 被阻塞，当 B 从缓冲区取走数据后，进程 A 被唤醒。

3. 互斥

互斥也称间接制约关系。当一个进程进入临界资源区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一个进程才允许去访问此资源。

为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

• 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区；
• 忙则等待：当已有进程进入临界区时，其它试图进入临界区的进程必须等待；
• 有限等待：对请求访问的资源，应保证能在有限时间内进入临界区；
• 让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

二、实现临界区互斥的基本方法

1. 软件实现方法

在进入区设置一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。

算法一：单标志法

该算法设置一个公用整型变量 turn，用于指示被允许进入临界区的进程编号。若 turn = 0，则允许 P0 进程进入临界区。那么谁来改变 turn 的值？如果是公共区域控制turn这个变量，那么 P0 不想进的时候，即使是 turn = 0 ,对于进程 P0 也是没有价值的。公共区域无法预测谁想要，所以这个控制权还是分权给进程来管理比较好一些。

Pi想进入时检测 turn 值是否是自己的 turn，如果不是，就需要等待，该算法可确保每次只允许一个进程进入临界区。两个进程必须交替进入临界区，一个进程进入临界区，使用完成后将 turn的值设置为另外一个进程。若某个进程不再进入临界区，则另一个进程也将无法进入临界区（违背“空闲让进”）。若 P0 顺利进入临界区并从临界区离开，则此时临界区是空闲的，但 P1 并没有进入临界区的打算，turn = 1一直成立，P0 就无法再次进入临界区（一直被 while 死循环困住）。

算法描述：

P0 进程：                                  P1 进程：
while (turn != 0);                        while (turn != 1);  // entry section
critical section;                         critical section;
turn  = 1;                                turn  = 0;  // exit section
remainder section;                        remainder section;

算法二：双标志法先检查

该算法的基本思想是在每个进程访问临界区之前，先检查临界区资源是否正在访问。若正在被访问，则该进程需等待；否则进程进入自己的临界区。为此设置一个数据 flag[i]， 如第 i 个元素为 FALSE，则表示 Pi 进程未进入临界区；值为 TRUE，表示 Pi 进程进入临界区。

优点：不要交替进入，可连续使用；

缺点：按 ①②③④ 执行时，Pi 和 Pj 会同时进入临界区（违背“忙则等待”）。这里问题出在检查和修改操作不能一次进行。

算法描述：

Pi 进程：                                  Pj 进程：
while (flag[j]);    ①                     while (flag[i]); ② // entry section
flag[i] = TRUE; ③                         flag[j] = TRUE; ④ // entry section
critical section;                         critical section; 
flag[i] = FALSE;                          flag[j] = FALSE;  // exit section
remainder section;                        remainder section; 

算法三：双标志法后检查

该算法先将自己的标志设置为 TRUE，再检测对方的状态标志，若对方标志为 TRUE 则进入等待；否则进入临界区。

缺点：两个进程同时想进入等待区时，它们分别将自己的标志 flag 设置为 TRUE，然后再进行检测时就会发生“饥饿”现象，双方都无法进入临界区。

算法描述：

Pi 进程：                                  Pj 进程：
flag[i] = TRUE;                           flag[j] = TRUE;  // entry section
while (flag[j]);                          while (flag[i]);  // entry section
critical section;                         critical section; 
flag[i] =FLASE;                           flag [j] = FLASE;  // exit section
remainder section;                        remainder section;

算法四：Peterson’s Algorithm

为了防止两个进程为进入临界区而无限期等待，又设置了变量 turn，每个进程在先设置自己的标志后再设置 turn 标志。这是，再同时检测另一个进程状态标志和不允许进入标志，以便保证两个进程同时要求进入临界区时，只允许一个进程进入临界区。

优点：利用 flag 解决临界资源互斥访问，利用 turn 解决“饥饿”现象；

缺点：未遵循“让权等待”。

算法描述：

Pi 进程：                                  Pj 进程：
flag[i] = TURE; turn = j;                 flag[j] = TRUE; turn = i;  // entry section
while (flag[j] && turn == j);             while (flag[i] && turn == i);  // entry section
critical section;                         critical section;
flag[i]=FLASE;                            flag[j] = FLASE;
remainder section;                        remainder section;

2. 硬件实现方法

计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或对两个字中的内容进行交换等。通过硬件支持实现临界段问题的方法称为低级方法或元方法。

（1）中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，防止其他进程进入临界区进行访问的最简方法就是禁止一切中断发生，或称为屏蔽中断、关闭中断。其原理为 CPU 在发生中断时切换进程，因此关闭中断就能让临界区代码顺利执行完成。其典型模式为：

...
关中断；
临界区代码；
开中断；
...

此种方法限制了处理机交替执行程序的能力，因此执行效率会明显降低。对内核而言，在它执行更新变量或列表的几条指令期间，关中断是很方便的。但是将关中断的权力移交给用户是很不明智的，若进程关中断后不再打开，很可能会让系统终止。

（2）硬件指令方法

TestAndSet 指令：该指令为原子操作，执行该代码时不允许被中断。其功能为读出指定标志后把该标志设置为真。

指令的功能描述如下：

boolean TestAndSet (boolean *lock) {
    boolean old;
    old = *lock;
    return old;
}

可以为每个临界资源设置一个共享布尔型变量 lock，表示资源的两种状态：true表示正被占用，初始值为false。在进程访问临界资源之前，利用 TestAndSet检查和修改标志 lock；若有进程在临界区，则反复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下：

while TestAndSet(&lock);
critical section;
lock = false;
remainder section;

Swap 指令：该指令的功能是交换两个字节的内容。

其功能描述如下：

Swap(boolean *a, boolean *b) {
    boolean temp;
    Temp = *a;
    *a = *b;
    *b = temp;
}

应为每个临界资源设置一个共享布尔型变量 lock，初值为 false；在每个进程中再设置一个局部布尔型变量 key，用于与 lock交换信息。在进入临界区前，先利用 Swap指令交换 lock 与 key 的内容，再检查 key 的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。利用 Swap 指令实现进程互斥的算法描述如下：

key = true;
while(key != false)
    Swap(&lock, &key);
critical section;
lock = false;
remainder section;

优点：适用于任意数目的进程，并且不管是单处理机还是多处理机都适用；简单、容易验证其正确性。可以支持进程内有多个临界区，只需要为每个临界区设立一个布尔型变量。

缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待队列中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

三、信号量

信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语wait(S)和signal(S)访问，也可记作“P操作”和“V操作”。

原语是指完成某种功能且不被分割、不被中断执行的操作序列。原语之所以不能被中断执行，是因为原语对变量的操作若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界问题。

1. 整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 S，wait 和 signal 操作可描述为：

wait(S) {
    while(S <= 0);
    S = S - 1;
}

signal(S) {
    S = S + 1;
}

wait 操作中，只要信号量 S <= 0，就会不断测试。因此该机制未遵循“让权等待”，而是使进程处于“忙等”的状态。

2. 记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除需要一个用于代表资源数目的整型变量 value 外，再增加一个进程链表 L，用于链接所有等待资源的进程。记录型信号量得名于采用了记录型的数据结构。记录型信号量可描述为：

typedef struct {
    int value;
    struct process *L;
} semaphore;

相应的 wait 和 signal 的操作如下：

void wait(semaphore S) {
    S.value--;
    if (S.value < 0) {
        add this process to S.L;
        blcok(S.L);
    }
}

wait操作，S.value--表示进程请求一个该类资源，当S.value < 0时，表示该类资源已经分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列S.L，可见该机制遵循了“让权等待”。

void signal(semaphore S) {
    S.value++;
    if (S.value <= 0) {
        remove a process P from S.L;
        wakeup(P);
    }
}

signal操作，表示进程释放一个资源，使进程中可分配的该类资源数加一，故有S.value++。若加一后S.value <= 0，则表示S.L中仍有等待该资源的进程被阻塞，故还应该调用wakeup原语，将S.L中的第一个等待进程唤醒。

3. 利用信号量实现同步

信号量机制能用于解决进程间的各种同步问题。设 S 为实现进程 P1、P2 同步的公共信号量，初始值为 0。进程 P2 中的语句 y 要使用进程 P1 中语句 x 的运行结果，所以只有当语句 x 执行完成之后语句 y 才可以执行。

其实现同步的算法如下：

semaphore S = 0;  // 初始化信号量
P1() {
    ...
    x;  // 语句 x
    V(S);  // 告诉进程 P2，语句 x 已经完成
    ...
}

P2() {
    ...
    P(S);  // 检查语句 x 是否完成
    y;  // 语句 y
    ...
}

若 P2 先执行到P(S)时，S = 0，执行 P 操作就会阻塞进程，并放入阻塞队列；当 P1 中 x 执行完后，执行 V 操作，把 P2 从阻塞队列放回就绪队列，当 P2 得到处理机时，就可以继续运行。

4. 利用信号量实现进程互斥

信号量机制也能很方便的解决进程互斥的问题。设 S 为实现进程 P1、P2 互斥的信号量，由于每次只允许一个进程进而临界区，所以 S 的初值为 1（即可用资源数为 1）。只需要把临界区置于 P(S) 和 V(S) 之间，即可实现两个进程对临界资源的互斥访问。其算法如下：

semaphore S = 1;  // 初始化信号量
P1() {
    ...
    P(S);  // 准备开始访问临界资源，加锁
    进程 P1 的临界区;
    V(S);  // 访问结束，解锁
    ...
}

P2() {
    ...
    P(S);  // 准备开始访问临界资源，加锁
    进程 P2 的临界区;
    V(S);  // 访问结束，解锁
    ...
}

当没有进程在临界区时，任意一个进程要进入临界区，都要执行 P 操作，把 S 的值减为 0，然后进入临界区；当有进程存在于临界区时，S 的值为 0，再有进程要进入临界区，执行 P 操作时将会被阻塞，直至在临界区中的进程退出，这样便实现了临界区的互斥。

在同步问题中，若某个行为要用到某种资源，则这个行为前面执行 P 操作；若某个行为会提供某种资源，则在该行为后面执行 V 操作。在互斥问题中，P、V 操作要紧夹使用互斥资源的行为，不能有冗余代码。

5. 利用信号量实现前驱关系

信号量也可用来描述程序之间或语句之间的前驱关系。

在上面的前驱图中，S1、S2...S6是最简单的程序段（只有一条语句）。为了使程序段能正确执行，需要设置若干初始值为 "0" 的信号量。

实现算法如下：

semaphore a1 = a2 = b1 = b2 = c1 = c2 = c3 = 0;  // 初始化信号量
S1() {
    ...;
    V(a1); V(a2);  // S1 已经完成
}

S2() {
    P(a1);  // 检查 S1 是否完成
    ...;
    V(b1); V(b2);  // S2 已经完成
}

S3() {
    P(a2);  // 检查 S1 是否已经完成
    ...;
    V(c1);  // S3 已经完成
}

S4() {
    P(b1);  // 检查 S2 是否已经完成
    ...;
    V(c2);  // S4 已经完成
}

S5() {
    P(b2);  // 检查 S2 是否已经完成
    ...;
    V(c3);  // S5 已经完成
}

S6() {
    P(c1); P(c2); P(c3);  // 检查S3、S4、S5 是否已经完成
}

6. 分析进程同步和互斥问题的方法步骤

• 关系分析：找出问题中的进程数，并分析它们之间的同步和互斥的关系；
• 整理思路：找出解决问题的关键点，根据进程的操作流程确定 P、V 的大致顺序；
• 设置信号量：根据需要的信号量，确定初值。

四、管程

1. 管程的定义

系统中的各种硬件资源和软件资源均可以用数据结构进行抽象的描述其资源特性。管程是由一组数据及定义在这对数据之上的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。

2. 管程的组成

• 局部于管程的共享变量；
• 对数据结构进行操作的一组过程；
• 对局部于管程的数据进行初始化的语句。

3. 管程的基本特性

• 局部于管程的数据只能被局部于管程内的过程访问；
• 一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
• 每次仅允许一个进程在管程内执行某个内部过程。

4. 管程的属性

• 共享性：管程可被系统范围内的进程互斥访问，属于共享资源；
• 安全性：管程的局部变量只能由管程的过程访问，不允许进程或其它管程直接访问，管程也不能访问非局部于它的变量；
• 互斥性：多个进程对管程的访问是互斥的。任一时刻，管程中只能有一个活跃进程；
• 封装性：管程内的数据结构是私有的，只能在管程内使用，管程内的过程也只能使用管程内的数据结构。进程通过调用管程的过程使用临界资源。

五、经典同步问题

1. 生产者-消费者问题

问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为 n 的缓冲区。只有缓冲区没满时生产者才能把消息放入缓冲区，否则必须等待；只有缓冲区不为空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入消息，只允许一个消费者从中取出消息。

问题分析：

• 关系分析：生产者和消费者对缓冲区访问是既是互斥关系又是同步关系；
• 整理思路：需要解决互斥和同步 PV 操作的位置；
• 信号量设置：信号量 mutex 作为互斥信号量，用于控制互斥访问缓冲池，互斥信号量为 1；信号量 full 用于记录当前缓冲池中的“满”缓冲区数，初值为 0；信号量 empty 用于记录当前缓冲池中“空”缓冲区数，初值为 n。

算法描述：

semaphore mutex = 1, empty = n, full = 0;  // 初始化信号量

producer() {
    while(1) {
        produce an item in nextp;  // 生产数据
        P(empty);  // （要用什么 P 什么）获取空缓冲单元
        P(mutex);  // （互斥夹紧）进入临界区
        add nextp to buffer;  // （行为）将数据放入缓冲区
        V(mutex);  // （互斥夹紧）离开临界区
        V(full);  // （提供什么 V 什么）满缓冲区加一
    }
}

consumer() {
    while(1) {
        P(full);  // 获取满缓冲区单元
        P(mutex);  // 进入临界区
        remove an item from buffer;  // 从缓冲区取出数据
        V(mutex);  // 离开临界区，释放互斥信号量
        V(empty);  // 空缓冲区数加一
        consume the item;  // 消费数据
    }
}

下面再来看一个较为复杂的生产者-消费者问题：

问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专门向盘子中放苹果，妈妈专门向进程中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可以向盘子中放水果，仅当盘子中有对应的水果时，儿子女儿才能从盘子中取出水果。

问题分析：

• 关系分析：爸爸和妈妈是互斥关系，爸爸和女儿、妈妈和儿子是同步关系，儿子和女儿没有关系。女儿或儿子拿走水果后才能释放盘子；
• 整理思路：四个进程可以抽象为两个生产者和两个消费者被连接到大小为 1 的缓冲区上；
• 信号量设置：信号量 plate 为互斥信号量，初值为 1；信号量 apple 表示盘子中是否有水果，初值为 0；信号量 orange 表示盘子中是否有橘子，初值为 0。

算法描述：

semaphore plate = 1, apple = 0, orange = 0;  // 初始化信号量

dad() {
    while(1) {
        prepare an apple;
        P(plate);  // 互斥向盘中取、放水果
        put the apple on the plate;  // 向盘中放水果
        V(apple);  // 允许取苹果
    }
}

mom() {
    while(1) {
        prepare an orange;
        P(plate);  // 互斥向盘中取、放水果
        put the orange on the plate;  // 向盘中放水果
        V(orange);  // 允许取橘子
    }
}

son() {
    while(1) {
        P(orange);  // 互斥向盘中取水果
        take an orange from plate;  // 取水果
        V(plate);  // 允许向盘子中取、放水果
        eat the orange;
    }
}

daughter() {
    while(1) {
        P(apple);  // 互斥向盘中取水果
        take an apple from plate;  // 取水果
        V(plate);  // 允许向盘子中取、放水果
        eat the apple;
    }
}

2. 读者-写者问题

问题描述：有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问数据时不会产生副作用。但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。

因此要求：

• 允许多个读者可以同时对文件执行读操作；
• 只允许一个写者往文件中写信息；
• 任意写者在完成操作前都不允许其他读者或写者工作；
• 写者操作前应该让已有的读者和写者退出。

问题分析：

• 关系分析：读者和写者是互斥的，写者和写者也是互斥的，读者和读者之间不存在互斥现象。
• 整理思路：写者和任何进程互斥，用 PV 操作即可。写者必须在实现与写者互斥的同时，实现与其他读者的同步。这里需要使用一个计数器，用来判断当前是否有读者读文件。当有读者时，写者是无法写文件的，读者会一直占用文件，当没有读者时，写者才可以写文件。同时不同读者对计数器的访问也是互斥的。
• 信号量设置：设置信号量 count 为计数器，用于记录当前读者的数量，初值为 0；设置 mutex 为互斥信号量，用于保护更新 count 变量时的互斥；设置互斥信号量 rw，用于保证读者和写者的互斥访问。

算法描述：

int count = 0;  // 用于记录当前的读者数量
semaphore mutex = 1, rw = 1;  // 用于保护更新 count 变量时的互斥和读者写者互斥地访问

writer() {
    while(1) {
        P(rw);  // 互斥访问共享文件
        writing;  // 写入
        V(rw);  // 释放共享文件
    }
}

reader() {
    while(1) {
        P(mutex);  // 互斥访问 count 变量
        if (count == 0)  // 当第一个读进程读共享文件时
            P(rw);  // 阻止写进程写
        count++;  // 读者计数器加一
        V(mutex);  // 释放互斥变量 count
        reading;  // 读取
        P(mutex);  // 互斥访问 count 变量
        count--;  // 读者计数器减一
        if(count == 0)  // 当最后一个读进程读完共享文件
            V(rw);  // 允许写进程
        V(mutex);  // 释放互斥变量 count
    }
}

在上面地算法中，读进程是优先的。当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”情况。

若希望写进程优先，即有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完成，立即让写进程执行，只有在无写进程执行的情况下允许读进程再次运行。为此需要增加一个信号量并在上面程序的write() 和 reader()函数中各增加一个 PV 操作，就可以得到写进程优先的解决程序。

算法实现：

int count = 0;  // 计数器初始化
semaphore mutex = 1, rw = 1, w = 1;  // 信号量初始化

writer() {
    while(1) {
        P(w);  // 在无写进程请求时进入
        P(rw);  // 互斥访问共享文化
        writing;  // 写入
        V(rw);  // 释放共享文件
        V(w);  // 恢复共享文件的访问
    }
}

reader() {
    while(1) {
        P(w);  // 在无写进程请求时进入
        P(mutex);  // 互斥访问 count 变量
        if (count == 0)  // 在第一个读进程共享文件时
            P(rw);  // 阻止写进程写
        count++;  // 读者计数器加一
        V(mutex);  // 释放互斥变量 count
        V(w);  // 恢复对共享文件的访问
        reading;  // 读取
        P(mutex);  // 互斥访问 count 变量
        count--;  // 读者计数器减一
        if (count == 0)  // 当最后一个读进程读完共享文件
            V(rw);  // 运行写进程写
        V(mutex);  // 释放互斥变量 count
    }
}

读者-写者问题有一个关键的特征：有一个互斥访问的 count 计数器。我们解决其他互斥问题时也可以尝试以下 count 计数器互斥。

3. 哲学家进餐问题

问题描述：一张圆桌上坐着五名哲学家，每两名哲学家之间的桌子上摆一根筷子，两根筷子中间是一碗米饭。哲学家在思考时，并不影响他人；当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿地哲学家只有同时拿到两根筷子才可以开始进餐，进餐完毕后继续思考。

问题分析：

• 关系分析：五名哲学家与左右邻居是互斥的关系。
• 整理思路：本问题的关键是如何让一名哲学家拿到左右两根筷子而不造成死锁现象。解决办法有两个：一是让他们同时拿到两根筷子；二是对每个哲学家的动作制定规则。
• 信号量设置：定义互斥信号量数组 chopstick[5] = {1, 1, 1, 1, 1}，用于五个筷子的互斥访问。哲学家按顺序标号 0~4，哲学家 i 左边筷子的编号为 i，哲学家右边筷子的编号为(i + 1) % 5。

算法实现：

semaphore chopstick[5] = {1, 1, 1, 1, 1};  // 定义信号量数组 chopstick[5]

Pi() {
    do {
        P(chopstick[i]);  // 取左边筷子
        P(chopstick[(i + 1) % 5]);  // 取右边筷子
        eat;  // 进餐
        V(chopstick[i]);  // 放回左边筷子
        V(chopstick[(i + 1) % 5]);  // 放回右边筷子
        think;  // 思考
    } while(1);
}

该算法存在以下问题：当五名哲学家都想要进餐并分别拿起左边筷子时（都恰好执行完wait(chopstick[i]);）筷子已经被拿完，等到他们再想拿右边筷子时就全部阻塞，因此出现了死锁。

为了防止死锁的发生，可对哲学家进餐施加一些限制条件：当左右两边筷子都可以用时，才允许他抓取筷子。

算法描述：

semaphore chopstick[5] = {1, 1, 1, 1, 1};  // 定义信号量数组 chopstick[5]
semaphore mutex = 1;  // 设置取筷子信号量

Pi() {
    do {
        P(mutex);  // 在取筷子前获得互斥量
        P(chopstick[i]);  // 取左边筷子
        P(chopstick[(i + 1) % 5]);  // 取右边筷子
        V(mutex);  // 释放取筷子信号量
        eat;  // 进餐
        V(chopstick[i]);  // 放回左边筷子
        V(chopstick[(i + 1) % 5]);  // 放回右边筷子
        think;  // 思考
    } while(1);
}

4. 吸烟者问题

问题描述：假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起并抽掉一支烟，抽烟者必须要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷起一根烟并抽掉它，并给供应者一个信号已完成，此时供应者就会将另外两种材料放到桌上，如此重复。

问题分析：

• 关系分析：供应者与三个抽烟者分别是同步关系。由于供应者同时只能满足一个抽烟者，因此三个抽烟者对抽烟这个动作互斥。
• 整理思路：供应者作为生产者向三个抽烟者提供材料。
• 信号量设置：信号量 offer1、offer2、offer3 分别表示三个吸烟者需要的资源组合。信号量 finish 用于互斥进行抽烟动作。

算法描述：

int random;  // 存储随机数
semaphore offer1 = offer2 = offer3 = finsh = 0;  

process P() {  // 供应者
    while(1) {
        random = 任意整数;
        random = random % 3;
        if (random == 0)
            V(offer1);
        else if (random == 1)
            V(offer2);
        else
            V(offer3);
        任意两种材料放在桌子上;
        P(finish);
    }
}

process C1() {  // 抽烟者1
    while(1) {
        P(offer1);
        抽烟;
        V(finish);
    }
}

process C2() {  // 抽烟者2
    while(1) {
        P(offer2);
        抽烟;
        V(finish);
    }
}

process C3() {  // 抽烟者3
    while(1) {
        P(offer3);
        抽烟;
        V(finish);
    }
}

评论