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

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

1、临界资源

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

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

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

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

2、同步

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

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

3、互斥

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

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

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

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

方法	实现	优点	缺点
中断屏蔽	利用“开/关中断指令”实现	简单，高效	1.不适用于多处理机的系统2.只适用于内核进程，不适用于用户进程
TesstAndSet指令（TS指令、TSL指令）	TSL指令使用硬件实现的，在执行过程中不允许被中断，只能一气呵成 代码片。	实现简单，无需检查逻辑漏洞，适用于多处理机	不满足 “让权等待”
swap指令	同上 代码片	同上	同上

bool TSL(bool *lock){
bool old;
old = *lock;
*lock=true;
return old;
}
while(TSL(&lock));
//临界区代码段
lock = false;
//剩余区代码段

Swap(bool *a,bool *b){

  bool temp;

  temp=*a;

  *a=*b;

  *b=temp;

}

 

bool old=true;

while(old==true):

  Swal(&lock,&old)

//临界区代码

lock=false;

//剩余区代码

方法	思想	缺点
单标志法	两个进程在访问完临界区后，会把使用临界区的权限交给另一个进程。每个进程进入临界区的权限只能被另一个进程赋予。	违背：空闲让进、让权等待
双标志先检查法	设置一个布尔型数组flag[]，数组中各元素用来标记进程想进入临界区的意愿，true表示想要进入。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身的flag设为true，之后开始访问临界区。 违背：忙则等待、让权等待
双标志后检查法	双标识后检查法的改进版。前一个算法的问题是先检查后上锁，但是这两个操作无法一气呵成，因此导致了两个进程可能同时进入临界区。所以改进为先上锁后检查来避免上述问题。	违背：空闲让进、有限等待、让权等待
Peterson算法	双标识后检查法中，两个进程都争着想要进入临界区，谁也不让谁，最后都无法进入临界区。Peterson算法使用了一种主动让对方先使用临界区的思想。	违背：让权等待