Perteson互斥算法的理解

您所在的位置：网站首页 › cmu15440 › Perteson互斥算法的理解

Perteson互斥算法的理解

2022-12-16 17:02| 来源: 网络整理| 查看: 265

引用自计算机系统核心概念及软硬件实现

第一次尝试实现互斥 #尝试编程实现互斥 #进程1 do while (turn != 1) ; //nothing cirtical section turn = 2; remainder section while ( ! done1); #进程2 do while (turn != 2) ; //nothing critical section turn = 1; remainder section while (! done2);

此算法保证了互斥，但要求进程严格交替执行do循环，存在问题：如果一直想执行进程1而不执行进程2，那么此实现时无法做到的

第二次尝试实现互斥 #编程实现互斥的另一次尝试 #进程1 do enter1 = TRUE; while (enter2) ; //nothing critical section enter1 = FALSE; remainder section while (! done1); #进程2 do enter2 = TRUE; while (enter1) ; //nothing critical section enter2 = FALSE; remainder section while (! done2);

此算法保证了互斥，也能够实现：某一进程多次执行而另一线程不被执行。但，此算法有死锁：进程1设置enter1为TRUE后，调度进程2，进程2设置enter2为TRUE，然后进程2判断while (enter1)，此循环耗尽时间片（进程2无法进入临界区、后续执行代码），调度进程1，进程1判定while (enter2)条件也成立，循环而无法进入临界区、执行后续代码，死锁形成。

Perterson互斥算法 #Perterson互斥算法 #进程1 do enter1 = TRUE; turn = 2; while (enter2 && (turn == 2)) ; //nothing critical section enter1 = FALSE; remainder section while (! dine1); #进程2 do enter2 = TRUE; turn = 1; while (enter1 && (turn == 1)) ; //nothing critical section enter2 = FALSE; remainder section while (! done2);

直接理解Peterson算法，可能略显晦涩，不好区分enter和turn的含义，梳理Peterson算法的逻辑含义。

怎么理解Perterson算法呢？我们给出一个与上述算法类似的编码实现，对比方便理解：

#Perterson算法的类比编码实现 /*此实现直观地结合了“第一次尝试实现互斥”和“第二次尝试实现互斥”*/ #进程1 do enter1 = TRUE; while (enter2 && (turn == 2)) ; //nothing critical section enter1 = FALSE; turn = 2; remainder section while ( !done1); #进程2 do enter2 = TRUE; while (enter1 && (turn == 1)) ; //nothing critical section enter2 = FALSE; turn = 1; remainder section while (! done2)

上面这个编码实现，结合了前两种编码实现方式（第一次尝试实现互斥、第二次尝试实现互斥），可以达到互斥、某一线程持续调度、无死锁的设计【不具体分析各场景，可参考计算机系统核心概念及软硬件实现】。

我们的编码实现是什么含义呢？

enter1 = TRUE表示进程1准备进入临界区，enter1 = FALSE；turn = 2表示进程1离开临界区，进程2可以进去临界区。进程2在临界区中时，进程1无法进入临界区（while (enter2 && (turn == 2)）。进程1执行完毕临界区代码后，才允许进程2进入临界区（turn = 2）。

基于上面的理解，我们这样理解Peterson算法：

enter理解为，进程有进入临界区的意图（enter1 = TRUE表示进程1有意图进入临界区）； turn理解为，并发系统允许进入临界区的进程（turn = 1表示并发控制系统判定进程1可以进入临界区）；进程有进入临界区的意图，并且，系统允许其进入临界区的进程，才可以进入临界区（enter1 && (turn == 1)）；对进程1，如果互斥的进程（进程2）满足上述第3点，那么进程1循环等待，以礼让进程2先进入临界区（while (enter2 && (turn == 2); //nothing）。进程1是这样礼让进程2的，turn = 2，turn是可以理解为并发控制系统允许进入临界区的进程。

最后，比较我们编写的实现方式和Peterson算法，我们编写的方式虽然效果与Perterson算法相同，但有缺陷：

系统最初运行时，需要一个turn值，此turn值即并发系统允许运行的第一个进程（不具体分析场景），此设计可以理解为硬编码，人为干预并发系统调度，不好；进程离开临界区后修改turn值，这个turn值决定了下一次进程并发时哪一个进程可以继续执行，这就导致了，并发调度结果取决于上一次并发执行的顺序，每次并发调度不是独立的，不好。

【本文地址】

Perteson互斥算法的理解

Perteson互斥算法的理解

今日新闻

推荐新闻