进程同步

一、进程同步、互斥

1. 进程同步的概念

进程同步指的是协调多个并发执行进程的工作先后次序

2. 进程互斥的概念

临界资源：一个时间段内只允许一个进程使用的资源

进程互斥指的是当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待， 当前访问临界资源的进程访问结束，释放该资源后，另一个进程才能去访问临界资源

3. 访问临界资源

对临界资源的互斥访问，可在逻辑上分为如下四个部分：

4. 访问临界资源需要遵循的原则

(1) 空闲让进

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

(2) 忙则等待

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

(3) 有限等待

对请求访问的进程，应保证能在有限时间内进入临界区 (保证不会饥饿)

(4) 让权等待

当进程不能进入临界区，应当立即释放处理机，防止进程忙等待 (不应该让他占用处理机 一直执行循环无法前进，应当得知无法进入临界区时不执行循环，直接切换进程)

5. 知识回顾

二、进程互斥的软件实现方法

1. 单标志法

思想：一个进程访问完临界区后会把使用临界区的权限交给另一个进程，即每个进程进入临界 区的权限只能被另一个进程赋予

过程：

若P0要访问临界区，turn变为0，P1会一直在⑤循环，无法向下进行，P0访问完，将 turn改为1，P1跳出循环，P1可访问临界区

注意：
(1) 该算法可以实现同一时刻最多只允许一个进程访问临界区
(2) 如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么此时虽然临界区 空闲，但一直不允许P1访问，因此，单标志法存在的问题是：违背空闲让进原则

2. 双标志先检查法

思想：设置一个布尔数组flag[]，数组中各元素标记各进程是否想进入临界区，true表示想进入， false表示不想进入；每个进程在进入临界区之前先检查当前有没有别的进程想进入临界 区，如果没有，把自身对应的标志flag[i]改为true，之后开始访问临界区

过程：

存在的问题：P0进程进入之后，在修改P0为true之前，切换到P1，P1检查无别的进程 想进入临界区，故会将P1改为true，导致两个进程都为true，会同时访问

注意：
(1) 双标志先检查法存在的问题是：违背忙则等待原则
(2) 出现的原因：进入区的检查和上锁不是一气呵成的

3. 双标志后检查法

思想：双标志先检查法的改版，先上锁后检查，谁想进谁直接将自身改为true，不关心其他进 程，改为true之后，再检查有没有其他进程想访问

过程：

存在的问题：P0想进入，P0改为true，在检查之前切换到P1，P1想进入，改为true，					  导致两个进程都为true，谁都无法访问临界区，产生饥饿现象

注意：
(1) 双标志后检查法解决了忙则等待的问题，但是又违背了空闲让进和有限等待原则
(2) 出现的原因：进入区的检查和上锁不是一气呵成的

4. Peterson算法

思想：双标志后检查法的改版，若两个进程都想进入临界区，可以主动让对方优先访问临界区

过程：

进入区做了三件事：1. 主动争取 2. 主动谦让 3. 检查对方

注意：
Peterson算法解决了空闲让进，忙则等待，有限等待三个原则，但违背了让权等待原则

5. 知识回顾

三、进程互斥的硬件实现方法

1. 中断屏蔽方法

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

优点：简单、高效

缺点：不适用于多处理机；只适用于内核进程，不适用于用户进程

2. TestAndSet指令(TS指令)

又称为TestAndSetLock指令(TSL指令)

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成，如图：

若刚开始lock是false(没有进程访问临界区)，则TSL返回值是false，不会卡在while循环，此 进程可以访问临界区；若刚开始是true(有进程在访问临界区)，TSL返回值是true，会卡在while 循环，直到正在访问临界区的进程访问结束，将lock值改为false，此进程才可进入临界区

优点：实现简单，适用于多处理机环境

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

3. Swap指令

又称为Exchange指令(XCHG指令)

Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成，如图：

当lock为false(无进程访问临界区时)才可以跳出循环，访问临界区

优点：实现简单，适用于多处理机环境

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

4. 知识回顾

四、信号量机制

1. 产生原因

进程互斥的四种软件实现方法、三种硬件实现方法都无法实现让权等待，也就是进程无法进入 临界区时，会占用处理机一直循环(因为并没有必要一直循环，可以直接切换进程)

2. 介绍

(1) 信号量就是一个变量，表示系统中某种资源的数量
(2) 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作
(3) 一对原语是：wait(S)原语和signal(S)原语，S是信号量 (将此对原语理解为函数)
(4) 通常将wait(S)称为P操作，写为P(S)；通常将signal(S)称为V操作，写为V(S)

3. 整型信号量

用一个整数型变量作为信号量，用来表示系统中某种资源的数量，如下：

4. 记录型信号量

在整型信号量(不满足让权等待)的基础上进行改进，使用记录型数据结构表示信号量，如下：

举个例子：
计算机有两台打印机，需要分配给不同的进程使用，value初始值为2，等待队列为空：

(1) P0进程使用打印机，执行wait，value–，value值成为1
(2) P1进程使用打印机，执行wait，value–，value值成为0 (无打印机可用)
(3) P2进程使用打印机，执行wait，value–，value值成为-1，value < 0，执行block，成为等 待队列的队首 (无法使用时，不会占用处理机执行循环，未出现忙等现象)
(4) P3进程使用打印机，执行wait，value–，value值成为-2，value < 0，执行block，成为等 待队列的第二个进程
(5) 切换到P0，P0使用完打印机，执行signal，value++，value值成为-1，value <= 0，执行 wakeup，唤醒等待队列的队首进程(P2进程)，P2移出等待队列，P2使用打印机
(6) 切换到P2，P2使用完打印机，执行signal，value++，value值成为-1，value <= 0，执行 wakeup，唤醒等待队列的队首进程(P3进程)，P3移出等待队列，P3使用打印机

5. 知识回顾

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

1. 信号量机制实现进程互斥

设置互斥信号量mutex，初值为1，如图：

注意：
(1) 对不同的临界资源需要设置不同的互斥信号量
(2) P、V操作必须成对出现，缺少P无法保证互斥访问，缺少V无法唤醒等待进程

2. 信号量机制实现进程同步

实现进程同步，必须保证进程的执行是有先后次序的，即一前一后

(1) 设置同步信号量S，初值为0 (理解为刚开始没有资源，P1进程想使用必须通过P2产生资源)
(2) 在前进程之后执行V(S)
(3) 在后进程之前执行P(S)

3. 信号量机制实现前驱关系

4. 知识回顾

六、生产者 – 消费者问题

1. 问题分析

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费 者进程每次从缓冲区中取出一个产品并使用，生产者、消费者共享一个初始为空、大小为n的 缓冲区
2. 关系分析

(1) 同步关系

i. 缓冲区满时，生产者需要等消费者取走产品
ii. 缓冲区空时，消费者需要等生产者放入产品

(2) 互斥关系

i. 生产者与消费者要互斥访问缓冲区 (缓冲区是临界资源)
ii. 生产者与生产者要互斥访问缓冲区 (两个生产者可能会覆盖数据)
iii. 消费者与消费者要互斥访问缓冲区 (两个消费者可能有一个读的是空数据)

3. 实现