互斥

互斥的软件方法

问题:有两个并行进程P0和P1 ,互斥地共享单个资源(磁带机或某共享数据)。P0和P1是一个循环进程(即进程执行一个无限循环程序),每次只使用资源为一个有限的时间间隔。

解法1:用标志位flag[i]来标示进程i是否在临界段中执行,当flag[i]为真,则表示它正在执行临界段,反之不在临界段中执行;

存在的问题:当两个进程的标志位最初都为false,这时刚好两个进程同时都想进入临界段,并且同时发现对方标志位为false,于是两个进程同时进入了各自的临界段,违背了临界段设计原则,每次至多只允许一个进程进入临界段。(并发问题)
解法2:用一个指针turn来指示应该哪个进程进入临界段,若turn = i,则该进程Pi进入临界段;

存在的问题:强制两个进程以交替次序进入临界段,如果Pi进程的处理器速度要快得多,或者进程Pi的其他代码部分很长,那么进程Pi在进程Pj尚未进入临界段前要求再次进入临界段时,尽管此时临界段为空(无进程处于其中),进程Pi也无法进入临界段,从而使临界资源的使用率不高。
解法3:用flag[i]来表示进程i想要进入临界段,这是基于对解法1存在的问题:未表明自己想进入临界段的意向,而只检测对方是否已在临界段中,从而导致同时进入的情况的改进;

存在的问题:两个进程同时想进入临界段,于是把各自的标志位都置为true,并且同时检测对方的状态,发现对方也想进入(或已在临界段中),于是互相“谦让”而阻塞了自己,谁也进不了临界段,从而违反了临界段设计原则(2)。
解法4:为每个进程设置一个标志位flag[i],同样,当该位为真时,则表示该进程Pi要求进入临界段(或已在临界段中执行),反之为假,另外还设置了一个指针turn以指出应该由哪一个进程进入临界段,若turn=i则应该由进程Pi进入临界段。

引入硬件方法

分析临界区管理的尝试中的几种算法,问题出在管理临界区的标志时要用到两条指令,而这两条指令在执行过程中有可能被中断,从而导致了执行的不正确。
能否把标志看作为一个锁,开始时锁是打开的,在一个进程进入临界区时便把锁锁上以封锁其它进程进入临界区,直至它离开其临界区,再把锁打开以允许其它进程进入临界区。如果希望进入其临界区的一个进程发现锁未开,它将等待,直到锁被打开。
要进入临界区的每个进程必须首先测试锁是否打开,如果是打开的则应立即把它锁上,以排斥其它进程进入临界区。
测试和上锁这两个动作不能分开,以防两个或多个进程同时测试到允许进入临界区的状态。

互斥的硬件方法

中断屏蔽方法
在单处理器系统中,引起进程开关,使得当前运行进程交出处理器的唯一原因是中断;
屏蔽中断就能保证当前运行进程把临界段代码顺利地执行完,保证互斥实现,然后再开中断;
缺点:首先系统要付出较高代价;其次这种方法在多处理器系统中是不能保证进程间互斥的。
当进入锁测试之前关闭中断,直到完成锁测试并上锁之后再开中断。在这一短暂的期间,计算机系统不响应中断,因此不会转向调度,也就不会引起进程或线程切换,从而保证了锁测试和上锁操作的连续性和完整性,有效的实现了临界区管理。
但关中断时间过长会影响系统效率关中断方法也不适用于多CPU系统
硬件指令方法
TS(test-and-set)指令,又称检测和设置指令;
Swap指令,又称交换指令;
实现互斥的方法:为每个临界段或其他互斥的资源设置一个布尔变量,当其值为false则临界段未被使用,反之则说明正有进程在临界段中执行;
缺点:当进程正在临界段中执行时,其他想进入临界段的进程必须不断地检测布尔变量的值,即所谓“忙等待”,从而造成了处理器机时的浪费。

硬件指令实现互斥的优缺点

硬件指令方法实现互斥不但适用于单处理器情况,而且适用于共享主存的对称多处理器情况;
方法简单、行而有效;
可以被使用于多重临界段情况,每个临界段可以定义它自己的共享变量。
但,硬件指令方法一般采取“忙等待”的简单方法,进程不断地检测临界段状态,会造成处理器时间的浪费。