进程同步和进程互斥

• 概念
• • 进程互斥的软件实现方法
  • • 单标志法
    • 双标志先检查法
    • 双标志后检查法
    • Peterson算法
  • 进程互斥的硬件实现方法
  • • 中断屏蔽方法
    • TestAndSet指令
    • Swap指令

概念

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

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调他们的工作次序而产生的制约关系。

进程的并发需要共享的支持，各个并发执行的进程不可避免的需要共享一些系统资源。

• 互斥共享方式
  • 系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。
• 同时共享方式
  • 系统中的某些资源，允许一个时间段内有多个进程”同时”对他们进行访问。

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

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

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

• 进入区。
  • 负责检查是否可进入临界区，若可进入则应设置正在访问临界资源的标志，以阻止其他进程同时进入临界区。
• 临界区
  • 访问临界资源的那段代码。
• 退出区
  • 负责解除正在访问临界资源的标志。
• 剩余区
  • 做其他处理。

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

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

进程互斥的软件实现方法

单标志法

两个进程在访问完临界区后，会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予。
可以实现同一时刻，最多只允许一个进程访问临界区。单标制法存在的主要问题是违背了”空闲让进”的原则。

双标志先检查法

设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，每个进程在进入临界区之前，先检查当前有没有别的进程进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

双标志先检查法的主要问题是违反”忙着等待”的原则。
原因在于进入区的检查和上锁两个处理不是一气呵成的。检查后，上锁前可能发生进程切换。

双标志后检查法

先上锁后检查。
双标志后检查法虽然解决了”忙则等待”的问题，但是又违背了”空闲让进”和”有限等待”原则，会因各进程都长期无法访问临界资源而产生”饥饿”现象。

Peterson算法

如果双方都争着想进入临界区，那可以让进程尝试”孔融让梨”，主动让对方先使用临界区。

依然未遵循让权等待的原则。

进程互斥的硬件实现方法

中断屏蔽方法

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

优点：简单、高效。

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

TestAndSet指令

简称TS指令或TSL指令。

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

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

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

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

Swap指令

也叫Exchange指令，或简称XCHG指令。

逻辑上看Swap和TSL并无太大区别。

优点和缺点也是一样的。