文章目录

• 1. 进程同步与互斥
• 2.进程互斥的软件实现方式
• • Ⅰ单标志法
  • Ⅱ 双标志先检查法
  • Ⅲ 双标志后检查法
  • Ⅳ peterson算法
• 3.进程互斥的硬件实现方法
• • Ⅰ中断屏蔽法
  • Ⅱ TestAndSet指令
  • Ⅲ Swap指令

1. 进程同步与互斥

同步：

首先进程具有异步特性，异步性是指：并发的进程各自是独立的，运行速度是不可预知的。

操作系统提供了同步的机制来控制进程运行的先后顺序。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
eg：管道文件的读取进程需要等待写进程写入才可以读取。

互斥：

临界资源：只允许一个进程使用的资源称为临界资源

临界区（临界段）：进程中访问临界资源的代码段
进入区：实现互斥的代码段（上锁）
退出区：实现互斥的代码段（解锁）

对临界资源的访问必须互斥的访问，互斥又称为间接制约关系。

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

为了保证性能：

1. 如果临界区没有进程，则申请临界区的进程可以立即进去临界区
2. 如果临界区中有进程访问，则其他申请临界区的进程需要等待
3. 对于所有申请访问临界区的进程，需要保证在有限的时间内让其进入临界区，防止饥饿问题
4. 如果进程无法进入临界区，应该立即脱离CPU调度。防止CPU处于忙等待状态

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

Ⅰ单标志法

思路：
每个进程访问临界区的权限只能由另一个进程提供。保证了任意时刻临界区只有一个进程访问资源
伪代码如下：

缺点：

1. 这个算法在并发情况下可能出现问题。
   p0进程在①②两步才会申请到锁，这两个操作不是原子的，如果p0进程在①步执行完后发生进程切换。
   CPU开始调度p1进程，因为p0进程还没有把flag[0]设置为true，所以进程p1也会进入临界区。
   这样就导致临界区有两个进程，会出现数据不一致问题。

Ⅲ 双标志后检查法

具体思路与双标志先检查法类似，这里直接列出伪代码：

1. 声明自己要进入临界区
2. 允许对方进程优先进入临界区

在并发场景下分析不同执行步骤：
①②③⑥⑦⑧ p0进程进入临界区
①⑥②③ p0进程进入临界区
①⑥②⑦⑧ p0进程进入临界区
都不会发生多个进程出现在临界资源上

缺点：

1. 进程如果没有进入临界区，这个进程没有脱离CPU，CPU处于忙等状态。

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

Ⅰ中断屏蔽法

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

优点：

1. 简单，高效

缺点

1. 不适合多处理器的场景
2. 关中断，开中断指令只能在内核态使用，不能在用户态使用。只有内核进程才可以使用。

Ⅱ TestAndSet指令

TestAndSet指令又称为TSL指令。
TSL指令由硬件实现，执行过程中不允许被打断

分析：
若刚开始 lock是false，则TSL返回的old值为 false，while循环条件不满足，直接跳过循环，进入临界区，此时锁的值变为true。若刚开始lock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，直到当前访问临界区的进程在退出区进行“解锁”。

相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成

优点：

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

缺点：

1. 临界资源上锁时，进程不能及时解除CPU调度，CPU会出现忙等状态。

Ⅲ Swap指令

Swap指令是用硬件实现的，执行的过程不允许被中断

Swap指令作用是交换两个变量的值，但是这个交换是原子的。

如果old为lock为true，则进程会一直循环处理。直到lock为false才会跳出循环执行临界区代码段。

文章知识点与官方知识档案匹配，可进一步学习相关知识Java技能树Java异步任务线程与进程91536 人正在系统学习中