2.6 进程同步

2.6.2 实现临界区互斥的基本方法

　　实现临界区互斥的基本方法包括软件实现方法和硬件实现方法两种。
　　1．进程互斥的软件方法
　　（1）算法一
　　该算法设置了一个公用整型变量turn，用于指示被允许进入临界区的进程编号，即若turn=0，表示允许Pi进程进入临界区。该算法可确保每次只允许一个进入临界区。但采用强制两个进程轮流进入临界区，很容易造成资源利用不充分。
　　算法描述如下：
　　
　　（2）算法二
　　该算法的基本思想是在每一个进程访问临界区资源之前，先查看一下临界资源是否正被访问，若正被访问，该进程需等待；否则，才进入自己的临界区。为此，设置了一个数据flag[0,1]，如第i个元素值为false，表示Pi进程未进入临界区；若值为true，表示Pi进程进入临界区。
　　算法描述如下：
　　
　　按（1）（2）（3）（4）（5）（6）的顺序执行，会出现Pi和Pj同时进入临界区的错误。
　　（3）算法三
　　算法二是先检测对方进程状态标志后，再置自己标志，由于在检测和放置中可插入另一个进程到达时的检测操作，会造成两个进程在分别检测后，同时进入临界区。为此，算法三采用先设置自己标志后，再检测对方状态标志，但也可能出现两个进程先后同时设置后再分别检测对方状态标志，造成对方都不能进入临界区，无限期等待。
　　算法描述如下：
　　
　　（4）算法四
　　该算法组合了算法一和算法三，为了防止两个进程为进入临界区而无限期等待，又设置变量turn，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn标志，不允许另一个进程进入。这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区，只允许一个进程进入临界区。
　　
　　2．进程互斥的硬件方法
　　完全用软件的方法来实现同步与互斥机制，有很大的局限性（如不适用于多进程），现在已很少采用。许多大型机和微型机中都提供了专用的硬件指令，这些指令允许对一个字中的全部内容进行检测和修正，或交换两个字的内容。特别要指出的是，这些操作都是在一个存储周期中完成的，或者说由一条指令来完成，用这些指令就可以解决临界区的问题，可以利用某些硬件指令，其读/写操作由一条指令完成，因而保证读操作与写操作不被打断。
　　（1）检测和设置（TS）指令
　　
　　用这些硬件指令可以简单有效地实现互斥。其方法是，为每个临界段或其他互斥资源设置一个布尔变量，例如称为lock，当其值为false，则临界区未被使用，反之，则说明正有进程在临界区中执行。于是，某进程用TS指令实现互斥的程序结构为（设为无限循环进程）：
　　
　　（2）swap指令（或exchange指令）
　　该指令的作用是交换两个字（字节）的内容：
　　
　　利用swap指令实现进程互斥：每个临界资源设置一个公共布尔变量lock，初值为false。每个进程设置一个私有布尔变量key。
　　
　　硬件方法有以下优点：
　　适用于任意数目的进程，不管是单处理器还是多处理器；
　　简单，容易验证其正确性；
　　可以支持进程内存在多个临界区，只需要为每个临界区设立一个布尔变量。
　　硬件方法的缺点是：
　　等待要耗费CPU时间，不能实现“让权等待”；
　　可能存在“饥饿”现象。从等待进程中，随即选择一个进入临界区，有的进程可能一直选不上；
　　可能会产生死锁。