操作系统 Lamport的糕点算法

在本文中，我们将详细了解Lamport的糕点算法。

什么是Lamport的糕点算法

Lamport提出了一种糕点算法，这是一个软件解决方案，用于n个进程的互斥问题。该算法根据公平、先来先服务的原则来解决一个关键问题。

为什么它被称为糕点算法

这个算法之所以被称为糕点算法，是因为这种调度方式被采用在面包店中，顾客会得到一个唯一的顺序号。当顾客进入面包店时，他会得到一个独特的顺序号。全局计数器显示当前正在接待的顾客数量，其他顾客此时必须等待。一旦面包师傅完成为当前顾客服务，下一个号码就会显示出来。现在正在为下一个顺序号的顾客提供服务。

同样，在Lamport的糕点算法中，进程被视为顾客。在此算法中，等待进入临界区的每个进程都会得到一个顺序号，具有最低编号的进程进入临界区。如果两个进程具有相同的顺序号，则具有较低进程ID的进程进入其临界区。

Lamport的糕点算法的算法

do
{
    entering[i] :=  true; // show interest in critical section
   // get a token number
    number[i] := 1 + max(number[0],  number[1], ..., number[n - 1]);   
    entering [i] :=  false;
for ( j :=  0 ;  j

Lamport的面点店算法用于临界区问题的进程Pi的结构。

说明 –

此算法使用以下两个布尔变量。

boolean entering[n];
int number[n];

所有输入变量都被初始化为false，n个整数变量numbers都被初始化为0。整数变量的值用于构成令牌号码。

当一个进程希望进入临界区时，它选择一个比之前的令牌号码大的数字。

考虑一个进程Pi希望进入临界区，它将entering[i]设置为true，以使其他进程意识到它正在选择一个令牌号码。然后选择一个比其他进程持有的令牌号码大的令牌号码，并写入其令牌号码。然后在读取后将entering[I]设置为false。然后进入一个循环来评估其他进程的状态。它等待直到另一个进程Pj选择它的令牌号码。

然后，Pi等待直到所有令牌号码较小或者令牌号码相同但优先级更高的进程先接待。

当进程在其临界区执行完毕后，它将其数字变量重新设置为0。

糕点算法满足临界区问题的所有要求。

互斥性： 我们知道，当没有进程在其临界区内执行时，允许具有最低数字的进程进入其临界区。假设有两个进程具有相同的令牌号码。在这种情况下，选择这些进程中进程ID较低的进程作为每个进程的进程ID，因此在特定的时间，只会有一个进程在其临界区内执行。因此，满足互斥性的要求。
进展性： 选择令牌后，等待进程会检查是否有其他等待进程具有更高的优先级进入其临界区。如果没有这样的进程，P将立即进入其临界区。从而满足进展要求。
有界等待： 在等待过程中，当没有其他进程在其临界区内，并且
- 如果其令牌号码是其他等待进程中最小的。
- 如果令牌号码相同，则具有其他等待进程中最低进程ID。