进程与线程 III（同步与互斥）

一、同步与互斥的基本概念

【总结】：

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

1. 临界资源

虽然多个进程可以共享系统中的各种资源，但其中许多资源一次只能为一个进程所用，我们将一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可把临界资源的访问过程分成 4 个部分：

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

2. 同步

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

例如，输入进程 A 通过单缓冲向进程 B 提供数据。当该缓冲区空时，进程 B 不能获得所需数据而阻塞，一旦进程 A 将数据送入缓冲区，进程 B 就被唤醒。反之，当缓冲区满时，进程 A 被阻塞，仅当进程 B 取走缓冲数据时，才唤醒进程 A 。

3. 互斥

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

例如，在仅有一台打印机的系统中，有两个进程 A 和进程 B ，若进程 A 需要打印时，系统已将打印机分配给进程 B ，则进程 A 必须阻塞。一旦进程 B 将打印机释放，系统便将进程 A 唤醒，并将其由阻塞态变为就绪态。

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

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

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

1. 软件实现方法

【总结】：

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

1）算法一：单标志法

该算法设置一个公用整型变量 turn ，用于指示被允许进入临界区的进程编号，即若 turn = 0 ，则允许 P₀ 进程进入临界区。

该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，若某个进程不再进入临界区，则另一个进程也将无法进入临界区（违背“空闲让进”)。这样很容易造成资源利用不充分。若 P₀ 顺利进入临界区并从临界区离开，则此时临界区是空闲的，但 P₁ 并没有进入临界区的打算，turn = 1 一直成立，P₀ 就无法再次进入临界区（一直被 while 死循环困住）。

2）算法二：双标志法先检查

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

• 优点：不用交替进入，可连续使用；
• 缺点：P_i 和 P_j 可能同时进入临界区。按序列 ①⑤②⑥ 执行时，会同时进入临界区（违背“忙则等待”）。即在检查对方的 flag 后和切换自己的 flag 前有一段时间，结果都检查通过。这里的问题出在检查和修改操作不能一次进行。

3）算法三：双标志法后检查

算法二（双标志法先检查）先检测对方的进程状态标志，再置自己的标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后同时进入临界区。为此，算法三（双标志法后检查）先将自己的标志设置为 TRUE ，再检测对方的状态标志，若对方标志为 TRUE ，则进程等待；否则进入临界区。

两个进程几乎同时都想进入临界区时，它们分别将自己的标志值 flag 设置为 TRUE ，并且同时检测对方的状态（执行 while 语句），发现对方也要进入临界区时，双方互相谦让，结果谁也进不了临界区，从而导致“饥饿”现象。

4）算法四： Peterson’s Algorithm

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

具体如下：考虑进程 P_i ，一旦设置 flag[i] = true ，就表示它想要进入临界区，同时 turn = j ，此时若进程 P_j 已在临界区中，符合进程 P_i 中的 while 循环条件，则 P_i 不能进入临界区。若 P_j 不想要进入临界区，即 flag[j] = false ，循环条件不符合，则 P_i 可以顺利进入，反之亦然。本算法的基本思想是算法一和算法三的结合。利用 flag 解决临界资源的互斥访问，而利用 turn 解决“饥饿”现象。

2. 硬件实现方法

【总结】：

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

1）中断屏蔽方法

当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简方法是关中断。因为 CPU 只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完，进而保证互斥的正确实现，然后执行开中断。

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

2）硬件指令方法

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

可以为每个临界资源设置一个共享布尔变量 lock ，表示资源的两种状态：true 表示正被占用，初值为 false 。进程在进入临界区之前，利用 TestAndSet 检查标志 lock ，若无进程在临界区，则其值为 false ，可以进入，关闭临界资源，把 lock 置为 true ，使任何进程都不能进入临界区；若有进程在临界区，则循环检查，直到进程退出。

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

用 Swap 指令可以简单有效地实现互斥，为每个临界资源设置一个共享布尔变量 lock ，初值为 false ；在每个进程中再设置一个局部布尔变量 key ，用于与 lock 交换信息。在进入临界区前，先利用 Swap 指令交换 lock 与 key 的内容，然后检查 key 的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。

注意：以上对 TestAndSet 和 Swap 指令的描述仅是功能实现，而并非软件实现的定义。事实上，它们是由硬件逻辑直接实现的，不会被中断。

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

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

三、互斥锁

解决临界区最简单的工具就是互斥锁（mutex lock）。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数 acquire() 获得锁，而函数 release() 释放锁。

每个互斥锁有一个布尔变量 available ，表示锁是否可用。如果锁是可用的，调用 acquire() 会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞，直到锁被释放。

需要连续循环忙等的互斥锁，都可称为自旋锁（spin lock），如 TSL 指令、swap 指令、单标志法。

acquire() 或 release() 的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用 acquire() 。当多个进程共享同一个 CPU 时，就浪费了 CPU 周期。因此， 互斥锁通常用于多处理器系统， 一个线程可以在一个处理器上等待，不影响其他线程的执行。

四、信号量

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

原语是指完成某种功能且不被分割、不被中断执行的操作序列，通常可由硬件来实现。例如，前述的 Test-and-Set 和 Swap 指令就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机上可由软件通过屏蔽中断方法实现。原语之所以不能被中断执行，是因为原语对变量的操作过程若被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。

1. 整型信号量

整型信号量被定义为一个用于表示资源数目的整型量 S

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

2. 记录型信号量

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

信号量的值 = 这种资源的剩余数量（信号量的值如果小于 0 ，说明此时有进程在等待这种资源）
P(S) → 申请一个资源 S ，如果资源不够就阻塞等待；
V(S) → 释放一个资源 S ，如果有进程在等待该资源，则唤醒一个进程。

【总结】：

3. 利用信号量实现同步

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

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

信号量机制也能很方便地解决进程互斥问题。设 S 为实现进程 P₁, P₂ 互斥的信号量，由于每次只允许一个进程进入临界区，所以 S 的初值应为 1（即可用资源数为 1）。只需把临界区置于 P(S) 和 V(S) 之间，即可实现两个进程对临界资源的互斥访问。

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

互斥是不同进程对同一信号量进行 P,V 操作实现的，一个进程成功对信号量执行了 P 操作后进入临界区，并在退出临界区后，由该进程本身对该信号量执行 V 操作，表示当前没有进程进入临界区，可以让其他进程进入。

下面简单总结一下 PV 操作在同步互斥中的应用： 在同步问题中，若某个行为要用到某种资源，则在这个行为前面 P 这种资源一下；若某个行为会提供某种资源，则在这个行为后面 V 这种资源一下。在互斥问题中， P, V 操作要紧夹使用互斥资源的那个行为，中间不能有其他冗余代码。

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

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

【总结】：

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

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

五、经典同步问题

1. 生产者-消费者问题

1）问题描述

2）问题分析

3）问题实现

4）思考

5）总结

PV 操作题目的解题思路：

• 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。
• 整理思路。根据各进程的操作流程确定 P、V 操作的大致顺序。
• 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。（互斥信号量初值一般为 1 ，同步信号量的初始值要看对应资源的初始值是多少）

生产者消费者问题是一个互斥、同步的综合问题。难点在于发现题目中隐含的两对同步关系。

有时候是消费者需要等待生产者生产，有时候是生产者要等待消费者消费，这是两个不同的 “一前一后问题” ，因此也需要设置两个同步信号量。

2. 多生产者-多消费者问题

1）问题描述

2）问题分析

3）问题实现

【结论】：即使不设置专门的互斥变量 mutex ，也不会出现多个进程同时访问盘子的现象。原因在于：本题中的缓冲区大小为 1 ，在任何时刻，apple、orange、plate 三个同步信号量中最多只有一个是 1 。因此在任何时刻，最多只有一个进程的 P 操作不会被阻塞，并顺利地进入临界区…

注：如果缓冲区大小大于 1 ，就必须专门设置一个互斥信号量 mutex 来保证互斥访问缓冲区。

4）总结

【总结】：在生产者-消费者问题中，如果缓冲区大小为 1 ，那么有可能不需要设置互斥信号量就可以实现互斥访问缓冲区的功能。当然，这不是绝对的，要具体问题具体分析。

【建议】：在考试中如果来不及仔细分析，可以加上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的 P 操作一定要在实现同步的 P 操作之后，否则可能引起 “死锁” 。

解决 “多生产者-多消费者问题” 的关键在于理清复杂的同步关系。在分析同步问题（一前一后问题）的时候不能从单个进程行为的角度来分析，要把 “一前一后” 发生的事看做是两种 “事件” 的前后关系。

比如，如果从单个进程行为的角度来考虑的话，我们会有以下结论：

• 如果盘子里装有苹果，那么一定要女儿取走苹果后父亲或母亲才能再放入水果
• 如果盘子里装有橘子，那么一定要儿子取走橘子后父亲或母亲才能再放入水果

这么看是否就意味着要设置四个同步信号量分别实现这四个 “一前一后” 的关系了？

正确的分析方法应该从 “事件” 的角度来考虑，我们可以把上述四对 “进程行为的前后关系” 抽象为一对 “事件的前后关系” ：盘子变空事件 → 放入水果事件。“盘子变空事件” 既可由儿子引发，也可由女儿引发；“放水果事件” 既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。

3. 吸烟者问题

1）问题描述

2）问题分析

3）问题实现

4）总结

吸烟者问题可以为我们解决 “可以生产多个产品的单生产者” 问题提供一个思路。

值得吸取的精华是：“轮流让各个吸烟者吸烟” 必然需要 “轮流的在桌上放上组合一、二、三” ，注意体会我们是如何用一个整型变量 i 实现这个 “轮流” 过程的。

若一个生产者要生产多种产品（或者说会引发多种前驱事件），那么各个 V 操作应该放在各自对应的 “事件” 发生之后的位置。

4. 读者-写者问题

1）问题描述

2）问题分析

3）问题实现

结论：在这种算法中，连续进入的多个读者可以同时读文件；写者和其他进程不能同时访问文件；写者不会饥饿，但也并不是真正的 “写优先” ，而是相对公平的先来先服务原则。

有的书上把这种算法称为 “读写公平法” 。

4）总结

读者 - 写者问题为我们解决复杂的互斥问题提供了一个参考思路。

其核心思想在于设置了一个计数器 count 用来记录当前正在访问共享文件的读进程数。我们可以用 count 的值来判断当前进入的进程是否是第一个 / 最后一个读进程，从而做出不同的处理。

另外，对 count 变量的检查和赋值不能一气呵成导致了一些错误，如果需要实现 “一气呵成” ，自然应该想到用互斥信号量。

5. 哲学家进餐问题

1）问题描述

2）问题分析

3）问题实现

如何防止死锁的发生呢？

• 可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的。
• 要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保证如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况。
• 仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。

更准确的说法应该是：各哲学家拿筷子这件事必须互斥的执行。这就保证了即使一个哲学家在拿筷子拿到一半时被阻塞，也不会有别的哲学家会继续尝试拿筷子。这样的话，当前正在吃饭的哲学家放下筷子后，被阻塞的哲学家就可以获得等待的筷子了。

4）总结

哲学家进餐问题的关键在于解决进程死锁。

这些进程之间只存在互斥关系，但是与之前接触到的互斥关系不同的是，每个进程都需要同时持有两个临界资源，因此就有 “死锁” 问题的隐患。

六、管程

【总结】：

在信号量机制中，每个要访问临界资源的进程都必须自备同步的 PV 操作，大量分散的同步操作给系统管理带来了麻烦，且容易因同步操作不当而导致系统死锁。于是，便产生了一种新的进程同步工具——管程。管程的特性保证了进程互斥，无须程序员自己实现互斥，从而降低了死锁发生的可能性。同时管程提供了条件变量，可以让程序员灵活地实现进程同步。

1. 管程的定义

系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性，即用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。

利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程（monitor）。管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程的定义描述举例如下：

熟悉面向对象程序设计的读者看到管程的组成后，会立即联想到管程很像一个类（class）。

• 管程把对共享资源的操作封装起来， 管程内的共享数据结构只能被管程内的过程所访问。一个进程只有通过调用管程内的过程才能进入管程访问共享资源。外部进程只能通过调用 take_away() 过程来申请一个资源；归还资源也一样。

• 每次仅允许一个进程进入管程，从而实现进程互斥。若多个进程同时调用 take_away() , give_back() ，则只有某个进程运行完它调用的过程后，下个进程才能开始运行它调用的过程。也就是说，各个进程只能串行执行管程内的过程，这一特性保证了进程 “互斥” 访间共享数据结构 S 。

2. 条件变量

当一个进程进入管程后被阻塞，直到阻塞的原因解除时，在此期间，如果该进程不释放管程，那么其他进程无法进入管程。为此，将阻塞原因定义为条件变量 condition 。通常，一个进程被阻塞的原因可以有多个，因此在管程中设置了多个条件变量。每个条件变量保存了一个等待队列，用于记录因该条件变量而阻塞的所有进程，对条件变量只能进行两种操作，即 wait 和 signal 。

• x.wait ：当 x 对应的条件不满足时， 正在调用管程的进程调用 x.wait 将自己插入 x 条件的等待队列， 并释放管程。此时其他进程可以使用该管程。

• x.signal ：x 对应的条件发生了变化，则调用 x.signal ，唤醒一个因 x 条件而阻塞的进程。

下面给出条件变量的定义和使用：

条件变量和信号量的比较：

• 相似点： 条件变量的 wait/signal 操作类似于信号量的 P/V 操作，可以实现进程的阻塞／唤醒。

• 不同点： 条件变量是 “没有值” 的，仅实现了 “排队等待” 功能；而信号量是 “有值” 的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。

七、小结

1、为什么要引入进程同步的概念？

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

2、不同的进程之间会存在什么关系？

进程之间存在同步与互斥的制约关系。

• 同步是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

• 互斥是指当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

3、当单纯用本节介绍的方法解决这些问题时会遇到什么新的问题吗？

当两个或两个以上的进程在执行过程中，因占有一些资源而又需要对方的资源时，会因为争夺资源而造成一种互相等待的现象，若无外力作用，它们都将无法推进下去。这种现象称为死锁，具体介绍和解决方案请参考后续内容。

原文地址：https://blog.csdn.net/weixin_49272453/article/details/143840968

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！