进程同步 petenson算法

进程同步,有一个敌人: race condition(竞争条件)

执行结果和进程中特定线程的执行顺序有关

为了避免这个问题,导出了一个著名的 临界区问题 (critial section)

临界区其实就是一段代码,此段代码能够修改公共的变量

而由此(临界区问题)引发了关于进程同步的三个问题:
1. 互斥性(mutual exclusion):A进程执行则此时B进程不能执行
2. 前进性(progress):当资源空闲时,等待进入的进程就要进入
3. 有限等待:进程可以等待,但等待的时间要有限的

关于进程同步,有一个著名解决二元进程问题的算法 peteson算法:
前提解释:

• 定义一个数据结构:

int turn ;//轮转令牌,指给谁谁进临界区
boolean flag[2]; //表示对应进程有想进入临界区的,赋值为true

• 有两个进程P_i和P_j :

do{
flag[i]=true;
turn=j ;//我称此行算法为礼让步骤,把令牌给对方
while(turn==j and flag[j]==true);//如果发现另一个进程也想进入临界区执行,则让对方执行,自己等待
/*终于轮到自己了! 执行邻接区算法*/
flag[i]=flase;//执行结束
}while(true)

注意:
若同时有两个进程要进入临界区,则flag[2]里的元素都为true
但 turn中不是,因为turn在内存中只有一份,后修改的turn为真正的值,毕竟底层CPU是轮流执行命令的—-所以满足互斥性

关于硬件同步问题

1. 单CPU的,可以用修改共享变量时禁止中断出现来解决临界区问题
2. 多CPU的就不能用1方法了,因为效率太低,消息要传递给所有的处理器,禁止中断就会很费时间