2.11 进程同步、进程互斥

2.11.1 进程同步

知识点回顾: 进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

进程同步： 需要按照可预知的顺序来执行进程。

例子

2.11.2 进程互斥

进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/0设备)

我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。

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

以 Java代码举例：

进入区理解为进入synchronized 同步代码块。获取锁

临界区理解为执行同步代码块中的代码，只允许一个线程执行

退出区理解为退出同步代码块，释放锁。

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

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

2.11.3 总结

2.12 进程互斥和软件实现方法

如果没有进程互斥？

2.12.1 单标志法

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

turn 的初值为0，即刚开始只允许P0进程进入临界区。若 P1 先上处理机运行，则会一直卡在 5 。直到 P1 的时间片用完，发生调度，切换 PO 上处理机运行代码 1 不会卡住 PO，PO 可以正常访问临界区，在 PO 访问临界区期间即时切换回 P1，P1依然会卡在5，只有 PO 在退出区将 turn 改为1后，P1才能进入临界区。

因此，该算法可以实现在同一时刻只有一个进程访问临界区资源。

但是如果P1进程让给P0进程执行，而P0进程不会去执行，那么P1也访问不到临界区资源。因此该算法也违反了 空闲让进原则

2.12.2 双标志先检查法

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

该算法违反了 “忙则等待” 的原则。

如果P0 和 P1 是并发执行，在执行while时，都是 false，然后同时往下执行…临界区就会有俩个进程同时执行。

2.12.3 双标志后检查法

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

该算法违反了 “空闲让进” 和 “优先等待” 的问题

如果是并发执行，在 P0 进程、P1进程同时执行完 1、5 时，然后进入while循环，造成死循环的状态。一个访问临界区的进程都没有。

2.12.4 Peterson 算法

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

这里的 turn 是一个全局变量，无论是否并发执行，turn 的值只能有一个，要不是0，要不是 1，最终只有一个进程进入 while 循环，一个进程进入临界区。

2.12.5 总结

2.13 进程互斥和硬件实现方法

2.13.1 中断屏蔽方法

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

优点: 简单、高效

缺点: 不适用于多处理机:只适用于操作系统内核进程，不适用于用户进程(因为开/关中断指今只能运行在内核态，这组指令如果能让用户随意使用会很危险)

2.13.2 TestAndSet 指令

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

TSL 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

若刚开始lock 是 false，则TSL 返回的 old 值为 false，while 循环条件不满足，直接跳过循环，进入临界区。若刚开始lock 是 true，则执行TLS 后old 返回的值为true，while 循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

优点: 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞:适用于多处理机环境

缺点: 不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

2.13.3 Swap 指令

有的地方也叫Exchange 指令，或简称XCHG 指令Swap 指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

old 用于记录是否有进程访问临界区，如果有标记为 true，相反则为 false。lock代表锁，false 释放锁，true上锁。

如果有进程访问临界区，其他进程则会进入 while 循环等待，当访问临界区的进程执行完，将 lock 设置为 false。通过 Swap 交换 lock 和 old，此时 old 为 false，lock为true，等待的进程进入临界区。

优点: 实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞:适用于多处理机环境

缺点: 不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”

2.13.4 补充知识&总结

进程互斥：锁

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

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

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

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

需要连续循环忙等的互斥锁，都可称为自旋锁 (spin ock) ，如TSL指令、swap指令、单标志法.【CAS】

特性:

需忙等，进稚时间片用完才下处理机，违反“让权等待"
优点: 等待期问不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区不太适用于单处理机系统，忙等的过程中不可能解锁

总结

2.14 信号量机制

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bWBGdfPr-1685426415780)(https://images-1313160403.cos.ap-beijing.myqcloud.com/MarkDown/image-20230514090134354.png)]

复习回顾+思考: 之前学习的这些进程互斥的解决方案分别存在哪些问题?

进程互斥的四种软件实现方式 (单标志法、双标志先检查、双标志后检查、Peterson算法) 进程互斥的三种硬件实现方式 (中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)

1. 在双标志先检查法中，进入区的“检查”、“上锁”操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题。
2. 所有的解决方案都无法实现“让权等待”

1965年，薇兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法–信号量机制

信号量机制

用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量 (可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如: 系统中只有一台打印机，就可以设置一个初值为 1的信号量

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决

方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，

使这些操作能“一气呵成”就能避免问题。

一对原语: wait(S) 原语和signal()原语，可以把原语理解为我们自己写的函数，函数名分别为 wait和 signal，括号里的信号量 S 其实就是函数调用时传入的一个参数。

wait、signal 原语常简称为 P、V操作 (来自荷兰语 proberen 和 verhogen)。因此，做题的时候常把wait(s)、

signal(S) 两个操作分别写为 P(S)、V(S)

2.14.1 整型信号量

2.14.2 记录型信号量

2.14.3 总结

2.15 用信号量实现进程互斥、同步、前驱关系

2.15.1 实现进程互斥

2.15.2 实现进程同步

进程同步：让各个进程按要求有序的推进

2.15.3 实现进程前驱关系

2.15.4 总结

2.16 生产者、消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)

PV操作题目分析步骤:

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系
2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

第一步：找到各个进程，分析同步、互斥关系

互斥关系：

临界区资源，也就是缓冲区

同步关系：

缓冲区空，生产产品

缓冲区非空，消费者消费

第二步：确定P、V操作的大致顺序

能否改变P、V的顺序？

2.17 多生产者、多消费者问题

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

多生产者、多消费者指的是多类，不是多个。

第一步：找出题目中的各个进程，以及同步、互斥关系

互斥关系：

一般来说，临界资源就是互斥关系，因此在这个题目中 盘子【缓冲区】 就是要互斥的进行

同步关系【一前一后】：

1、父亲将苹果放在盘子上，女儿才能取到苹果

2、母亲将橘子放在盘子上，儿子才能取到苹果

3、当儿子取出苹果时，父亲才能继续放苹果。当女儿取出橘子时，母亲才能继续放橘子。

第二步：确定P、V的大致顺序

考虑一下，可不可以不要互斥信号量？

分析:

刚开始，儿子、女儿进程即使上处理机运行也会被阻塞。如果刚开始是父亲进程先上处理机运行，则: 父亲 P(plate)，可以访问盘子母亲 P(plate)，阻塞等待盘子父亲放入苹果 V（apple)，女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源(盘子)女儿 P(apple)，访问盘子，V(plate)，等待盘子的母
亲进程被晚醒>母亲进程访问盘子(其他进程暂时都无法进入临界区。

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

2.18 吸烟者问题

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

第一步：找出各个进程，互斥关系，同步关系

互斥关系：

桌子可以抽象看成容量为1的缓冲器，要互斥的访问。这里设置为 1 将俩种材料看做是一种组合。一共有三种组合。

组合一：烟草+纸

组合二： 烟草+胶水

组合三：纸+胶水

同步关系：

生产组合一 ——》抽烟者 1抽调掉

生产组合二 ——》抽烟者 2抽调掉

生产组合三 ——》抽烟者 3抽调掉

抽烟者 1、2、3 抽完烟，发出完成信号 ——》供应者将下一个组合放到桌子上

第二步：确定P、V的大致顺序

实现

2.19 读者、写者问题

有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程(读进程或写进程) 同时访问共享数据时则可能导致数据不一致的错误。因此要求:、

（1）允许多个读者可以同时对文件执行读操作:

（2）只允许一个写者往文件中写信息:

（3）任一写者在完成写操作之前不允许其他读者或写者工作:

（4）写者执行写操作前，应让已有的读者和写者全部退出。

无论多少个读者都不影响文件的内容，因此可以并发读，但是在写者写文件时，就要保证写者的互斥性，不允许其他进程读或者写。

第一步：找出进程、以及同步、互斥关系

进程：读进程、写进程

互斥关系： 写进程——写进程, 写进程——读进程。读读不影响

第二步：确定P、V的顺序

使用一个 count 记录访问文件的进程数量， 只要进程数量不等于0，就不会执行P操作，也就不会进行加锁，同时达到多个读进程访问文件的效果，但是这是在理想状态下，若两个读进程并发执行，则 count=0时两个进程也许都能满足if 条件，都会执行P(rw)，从而使第二个读进程阻塞的情况。

出现以上问题的原因就是：对于count变量的检查和修改无法一气呵成，因此可以设置一个信号量保证count变量的互斥性。

潜在的问题: 只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”、因此，这种算法中，读进程是优先的

可以在使用一个变量实现写优先。

2.20 哲学家讲餐问题

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

如果5位哲学家都拿起了筷子，但是又不会主动释放自己手里面的筷子。就会造成死锁的问题。

解决方法：

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