操作系统 - 进程互斥的硬件和软件实现（IV）

目录

一、进程同步互斥的基本概念

1、临界资源

2、同步

3、互斥

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

1、单标志法

2、双标志先检查法

3、双标志后检查法

4、Peterson算法

3 、进程互斥的硬件实现方法 --图

1、中断屏蔽方法

2、 TestAndSet方法

3 、Swap指令

---

一、进程同步互斥的基本概念

1、临界资源

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

对临界资源的访问，必须互斥地进行，在每个进程，访问临界资源的那段代码称为临界区

为了保证临界资源的正确使用，分为四个部分：

• 进入区   负责检查是否可以进入临界区，若可进入，则应设置正在访问临界资源的标志（可以理解为“上锁”），防止其他进程同时进入临界区
• 临界区   进程中访问临界资源的那段代码，又称临界段
• 退出区   将正在访问临界区资源的标志清除（可以理解为“解锁”）
• 剩余区   代码中的其余部分

2、同步

进程同步：让各并发进程按要求有序地推进

并发性带来了异步性，有时需要通过进程同步解决这种异步问题。进程之间需要相互配合完成工作，遵循一定的先后顺序

3、互斥

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

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

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

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

1、单标志法

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

该算法可以确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区，如果某个进程不再进入临界区，那么另个进程也将无法进入临界区（就违背了"空闲让进"原则）造成资源浪费

2、双标志先检查法

算法思想：在一个进程访问临界区资源之前，先查看以下临界区资源是否被访问，若被访问，该进程需等待;否则把自身对应的标志flag[i]设为true,才可以访问临界区。为此设置一个boolean类型的数组flag[i]，如果i为false,表示pi进程未进入临界区，值未true，表示pi进程进入临界区

3、双标志后检查法

算法思想：因为前一个算法，先检查，后上锁，两个操作无法一气呵成，导致了两个进程同时进入临界区的问题。因此人们又想到先上锁，后检查的方法。

 当两个进程集合同时想进入临界区时，它们都把自己的标志flag设hi为true,并且检测到对方的状态（while语句），发现对方也想进入临界区，于是互相谦让，结果都进不了临界区，从而导致“饥饿”现象。

4、Peterson算法

 算法思想：双标志后检查法中，两个进程都争着想进入临界区，但是谁也不让谁，最后谁都无法进入临界区。Gray L.Peterson 想到了一种方法，如果对方都争着想进入临界区，那可以让进程尝试 “孔融让梨”，主动让对方先使用临界区

 

3 、进程互斥的硬件实现方法 --图

1、中断屏蔽方法

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

2、 TestAndSet方法

3 、Swap指令

硬件方法优点：无论单处理机还是多处理机都适用;简单，容易验证其正确性

缺点：违背了 “让权等待”，会产生 “饥饿” 现象

无论硬件还是软件实现方法，只需理解执行过程，关键是软件实现方法