操作系统-实现临界区互斥的基本办法

1、软件实现方法

在进入区设置并检查一些标志来标明是否有进程在临界区，若已有进程在临界区，则在进入区循环检查进行等待，进程离开临界区后则在退出区修改标志。

1.1 算法一：单标志法（违背空闲让进）

设两个进程P0和P1，以及一个标志量（turn）。

turn的初始化

规定turn = 0 时，允许P0访问临界区；turn = 1 时，允许P1访问临界区

P0进程

P1进程

算法思想

规定turn = 0 时，允许P0访问临界区；turn = 1 时，允许P1访问临界区。

缺点

（1）只能由两个进程共用一个标质量，无法完成多个进程互斥
（2）两个进程必须交替进入临界区，若P1进入临界区并退出将turn=0，之后P0一直未进入临界区，那么由于turn1!=1,所以P1再次向进入临界区的时候就会被一直阻塞。

1.2 算法二：双标志先检查法（违背忙则等待）

设两个进程P0和P1，以及两个标志量（flag0、flag1）。

flag0、flag1的初始化

规定flag0 = true时，表示P0正在访问临界区，flag0 = false时，P0没有在访问临界区；
规定flag1 = true时，表示P1正在访问临界区，flag1 = false时，P1没有在访问临界区；

P0进程

P1进程

算法思想

先检查对方是否正在临界区，若对方没有正在访问临界区，则自己进入临界区

缺点

(1)如果按照1??3??2??4??的顺序执行，则P1、P2进程会一起进入临界区，违背了忙则等待。
疑问：为什么不会出现算法1中的缺点（1）
答：这个代码可以改造一下，将flag0和flag1改成数组，稍微改变一下进入区的代码就可以解决这个问题，甚至我们可以用一个二进制数来表示
所以说算法二解决了算法一的缺点

1.3 算法三：双标志后检查法（违背空闲让进、有限等待）

设两个进程P0和P1，以及两个标志量（flag0、flag1）。

flag0、flag1的初始化

规定flag0 = true时，表示P0正在访问临界区，flag0 = false时，P0没有在访问临界区；
规定flag1 = true时，表示P1正在访问临界区，flag1 = false时，P1没有在访问临界区；

P0进程

P1进程

算法思想

算法三采用后检查的方法确实可以解决算法的二的缺点，不会出现两个进程同时进入进入临界区，但是却出现了新问题（饥饿）

缺点

(1)如果按照1??3??2??4??的顺序执行，则P1、P2进程都无法进入临界区，从而造成了“饥饿”现象，从而违反了空闲让进和有限等待。
同样算法三也可以像多算法二一样改造，从而满足多进程互斥

1.4 算法四：Peterson’s Alogorithm(皮特森算法）

设一个flag数组和一个标志量（turn）

flag数组、turn的初始化

规定若flag[i] = true，表示进程i想要访问临界区；
turn = i时，表示进程i有权进入临界区

Pi进程

Pj进程

算法思想

本算法是算法一和算法三的结合（标志量turn的应用、标志后检查），采用一种互相谦让的方式，其方式为：谦让方表示自己想进入临界区（假设进程i为谦让方，则将flag[i] = true），然后将临界区的进入权让给别人（假设进程j为被谦让方，则将turn = j）。自己模拟一下就会发现先谦让方将先进入临界区，后谦让方将后进入临界区。

缺点

这个算法没有明显的缺点除了，除了不能让权等待。

同样这个算法也可以改造成多个进程互斥，只需要让这些进程按照一定的顺序谦让，并形成一个环即可。

2、硬件实现方法

2.1 中断屏蔽方法

当一个进程正在使用处理机执行它的临界区代码时，防止其他进程进入其临界区的进行访问的最简单的方法是：禁止一切中断发生，称之为屏蔽中断或关中断。
因为CPU只在发生中断时引起进程切换，因此屏蔽中断能够保证当前运行的进程可以一直占据处理机直到临界区代码执行完，从而完成了互斥访问临界区。
典型模式为：关中断、临界区、开中断

缺点

这种方法限制了处理机交替执行程序的能力，因此系统并发度和吞吐量都会下降。而且将关中断的权利交给用户则很不明智，若一个进程关中断以后，不再开中断，系统可能会因此终止。

2.2 硬件指令方法

计算机提供特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者对两个字进行交换等。通过硬件实现临界段问题的方法为低级方法，或称元方法。

TestAndSet指令

这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。其指令的功能描述如下：

可以为每一个临界资源设置一个共享布尔变量lock，表示该资源的两种状态：true表示被占用，false表示空闲，其初值为flase。
利用TestAndSet检查和修改标志lock，若有进程在临界区，则重复检查，知道进程时间片消耗完。其指令实现进程互斥的算法描述如下：

Swap指令

该指令的功能是交换两个字（字节）的内容，其功能描述如下：

注意：以上TestAndSet和Swap指令功能描述仅仅是代码逻辑，而非软件实现的，事实上，他们是有硬件逻辑直接实现，不会被中断。

应为每一个临界资源设置一个共享布尔变量lock，初始值为false；在每一个进程进程中设置一个局部变量key，用于与lock交换信息。该指令的算法描述如下：

2.3 硬件方法的优缺点

硬件方法优点：

适用于任意数目的进程，而不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每一个临界区设立一个布尔变量。

硬件方法缺点：

（1）进程等待进入临界区要耗费处理机时间，不能实现让权等待。
（2）从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致饥饿。

以上无论是软件方法还是硬件方法其实都无法满足让权等待（当进程不能进入临界区时，应立即释放处理机，防止进程忙等），而是忙等直至消耗完时间片。

来源：dawuga