[OS] 进程互斥

对互斥的正确软件实现算法（面包店算法）是非常耗时的，现代的计算机系统都会提供简单的硬件指令，使用这些指令能够有效地解决临界区问题。

硬件提供一个TestAndSet指令，来实现原子指令的功能：

 bool TestAndSet(bool *target)

 {

     bool rv = *target;

     *target = true;

     return rv;

 }

在执行上述TestAndSet()函数时是不可以被打断的，因此可以使用以下方法来实现进程的同步：

 do

 {

     //剩余区

     waiting[i] = true;//表示进程Pi处于等待获取锁的状态

     key = true;

     while(waiting[i]&&key)

         key=TestAndSet(lock);//如果进程Pi抢到了锁，记录key=false

     waiting[i]=false;

     //临界区

     j=(i+)%n;

     while(j!=i && !waiting[j])//进程Pj处于等待获取锁的状态

         j = (j+)%n;

     if(j==i)

         lock = false;

     else

         waiting[j] = false;

     //剩余区

 }

 while(true);

临界区条件1：互斥
第一个进入的进程Pi要等执行了TestAndSet之后才能进入，这时Pi的key=false,其他进程key=true;后续进入的进程Pi，只有在其他进程将waiting[i]设为false之后，才可能进入。
临界区条件2：空闲让进
初始，key和所有的waiting[i]都为True，lock=false,因此首次执行TestAndSet的进程会进入临界区。当进入临界区的进程Pi执行完临界区操作之后，在退出区，通过While循环扫描当前处于等待状态的进程j (j!=i)，如果找到j，那么waiting[j]被设为false,Pj会随后进入临界区如果没有找到j，那么lock被置为false。总之，只要临界区资源空闲，想进入临界区的进程（其waiting[j]=true）都会被放进临界区。
临界区条件3：有限等待
每个进程退出临界区的时候，总会按顺序执行一个扫描，这个循环扫描的过程保证一个进程最多等待n-1次即可进入临界区操作。

巴特西

[OS] 进程互斥

最新文章

热门文章