本文共 4597 字，大约阅读时间需要 15 分钟。

1.进程同步

1.1进程同步

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

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1.空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

2.忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

3.有限等待。对请求访问的进程，应保证能在有限时间内进入临界区。

4.让权等待。当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。

1.2进程互斥

互斥亦称间接制约关系。进程互斥指当一个进程访问某临界资源 时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后， 另一个进程才能去访问临界资源。

1.3临界区

我们把一个时间段内只允许一个进程使用的资源称为临界资源。

1.进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。

2.临界区。进程中访问临界资源的那段代码，又称临界段。

3.退出区。将正在访问临界区的标志清除。

4.剩余区。代码中的其余部分。

2.进程互斥的软件实现方法

2.1单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予

优点:可以实现“同一时刻最多只允许一个进程访问临界区” 缺点：违背“空闲让进、让权等待”原则

2.2双标志先检查

算法思想：设置一个布尔型数组 flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如 “flag[0] = ture”意味着 0 号进程 P0 现在想要进入临界区。每个进程在进入临界区之前先检查当前有 没有别的进程想进入临界区，如果没有，则把自身对应的标志 flag[i] 设为 true，之后开始访问临界区。

缺点：违反“忙则等待、让权等待”原则。进入区的“检查”和“上锁” 两个处理不是一气呵成的。“检查”后，“上锁”前可能发 生进程切换。P0 和 P1 将会同时访问临界区

2.3双标志后检查

算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又 无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查” 的方法，来避免上述问题。

缺点：违背了“空闲让进”和“有限等待”、让权等待 原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。 两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。

2.4Peterson 算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。

缺点：违背了“让权等待” 原则

3.进程互斥的硬件实现方法

3.1中断屏蔽方法

利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为 止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况）

优点：简单、高效 缺点：违背了让权等待、不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令 只能运行在内核态，这组指令如果能让用户随意使用会很危险）

3.2TestAndSet指令

简称 TS 指令，也有地方称为 TestAndSetLock 指令，或 TSL 指令

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑： 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从 而导致“忙等”。

3.3Swap指令

有的地方也叫 Exchange 指令，或简称 XCHG 指令。

Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑： 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境 缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从 而导致“忙等”。

4.信号量机制

信号量其实就是一个变量 ，可以用一个信号量 来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为 1 的信号量。

wait(S) 原语和 signal(S) 原语，可以把原语理解为我们自己写的函数，函数名分别为 wait和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为 P、V操作（来自荷兰语 proberen 和 verhogen）。因此，做题的时候常把wait(S)、signal(S) 两个操作分别写为 P(S)、V(S)

4.1整形信号量

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。与普通整数变量的区别：对信号量的操作只有三种， 即初始化、P操作、V操作

缺点：不满足“让权等待” 原则，会发生“忙等”

4.2记录型信号量

即用记录型数据结构表 示的信号量。

5.生产者消费者问题

5.1问题分析

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者 进程每次从缓冲区中取出一个产品并使用。（注：这里的“产品”理解为某种数据） 生产者、消费者共享一个初始为空、大小为n的缓冲区。

5.2关系分析

找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

5.2.1同步

只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。

只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。

5.2.2互斥

缓冲区是临界资源，各进程必须互斥地访问。

5.3整理思路

根据各进程的操作流程确定P、V操作的大致顺序。

5.4设置信号量

根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初 始值要看对应资源的初始值是多少）

5.5能否改变相邻P、V操作的顺序？

实现互斥的P操作一定要在实现同步的P操作之后。

V操作不会导致进程阻塞，因此两个V操作顺序可以交换。

6.多生产者多消费者问题（缓冲区大小为1，不用互斥信号量）

6.1问题分析

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放 橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才 可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。

6.2关系分析

6.2.1同步

1. 父亲将苹果放入盘子后，女儿才能取苹果
2. 母亲将橘子放入盘子后，儿子才能取橘子
3. 只有盘子为空时，父亲或母亲才能放入水果

6.2.2互斥

对缓冲区（盘子）的访问要互斥地进行

6.3整理思路

根据各进程的操作流程确定P、V操作的大致顺序。

6.4设置信号量

根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初 始值要看对应资源的初始值是多少）

7.吸烟者问题（缓冲区大小为1，不用互斥信号量）

7.1问题分析

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷 起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、 第二个拥有纸、第三个拥有胶水。供应者进程无限地ᨀ供三种材料，供应者每次将两种材料放桌 子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者进程一个信号告诉完成了，供 应者就会放另外两种材料再桌上，这个过程一直重复（让三个抽烟者轮流地抽烟）

7.2关系分析

7.2.1同步

桌上有组合一 → 第一个抽烟者取走东西

桌上有组合二 → 第二个抽烟者取走东西 桌上有组合三 → 第三个抽烟者取走东西 发出完成信号 → 供应者将下一个组合放到桌上

7.2.2互斥

桌子可以抽象为容 量为1的缓冲区， 要互斥访问

7.3整理思路

根据各进程的操作流程确定P、V操作的大致顺序。

7.4设置信号量

根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初 始值要看对应资源的初始值是多少）

8.读者-写者问题

8.1问题分析

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不 会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致 数据不一致的错误。因此要求：①允许多个读者可以同时对文件执行读操作；②只允许一个写者 往文件中写信息；③任一写者在完成写操作之前不允许其他读者或写者工作；④写者执行写操作 前，应让已有的读者和写者全部退出。

8.2关系分析

8.2.1互斥

写进程—写进程、写进程—读进程。

8.3整理思路

根据各进程的操作流程确定P、V操作的大致顺序。

8.4设置信号量

根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初 始值要看对应资源的初始值是多少）

8.4.1读优先

8.4.2读写公平

9.哲学家进餐问题

9.1问题分析

一张圆桌上坐着5名哲学家，每两个哲学家之间的桌上摆一根筷子，桌子的中间是一碗米饭。哲学 家们倾注毕生的精力用于思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时， 才试图拿起左、右两根筷子（一根一根地拿起）。如果筷子已在他人手上，则需等待。饥饿的哲 学家只有同时拿起两根筷子才可以开始进餐，当进餐完毕后，放下筷子继续思考。

9.2关系分析

9.2.1方式1

①可以对哲学家进程施加一些限制 条件，比如最多允许四个哲学家同 时进餐。这样可以保证至少有一个 哲学家是可以拿到左右两只筷子的

9.2.2方式2

②要求奇数号哲学家先拿左边的筷子，然后再拿右边的 筷子，而偶数号哲学家刚好相反。用这种方法可以保证 如果相邻的两个奇偶号哲学家都想吃饭，那么只会有其 中一个可以拿起第一只筷子，另一个会直接阻塞。这就 避免了占有一支后再等待另一只的情况。

9.2.3方式3

③仅当一个哲学家左右两支筷子都 可用时才允许他抓起筷子。

9.3整理思路

根据各进程的操作流程确定P、V操作的大致顺序。

9.4设置信号量（以方式3为例）

根据题目条件确定信号量初值。（互斥信号量初值一般为1，同步信号量的初 始值要看对应资源的初始值是多少）

10.补充

1. 临界资源与共享资源的区别在于，在一段时间内能否允许被多个进程访问（并发使用)
2. P、V操作是一种低级的进程通信原语,它是不能被中断的。
3. 用V操作唤醒一个等待进程时，被唤醒进程变为就绪态,
4. 对于管程，若进程A执行了x.wait()操作，则该进程会阻塞，并挂到条件变量x对应的阻塞队列上。若进程B执行了x.signal（）操作，则会唤醒x对应的阻塞队列的队首进程。在Pascal 语言的管程中，规定只有一个进程要离开管程时才能调用signal()操作。

转载地址：http://gzmzi.baihongyu.com/