Lamport 的面包店算法

在本文中，我们将详细了解 Lamport 的面包店算法。

Lamport 面包店算法是什么意思？

Lamport 提出了一种面包店算法，这是一种软件解决方案，用于解决 n 进程互斥问题。该算法遵循最公平的“先到先服务”原则，解决了关键问题。

为什么叫面包店算法？

该算法被称为面包店算法，因为这种调度方式在面包店中采用，面包店会发放令牌号码来设置顾客的顺序。当顾客进入面包店时，他会得到一个唯一的令牌号码。全局计数器显示当前正在服务的顾客数量，所有其他顾客必须在那时等待。一旦面包师服务完当前的顾客，就会显示下一个号码。拥有下一个令牌的顾客现在正在被服务。

类似地，在 Lamport 的面包店算法中，进程被视为顾客。在这种情况下，每个等待进入其临界区的进程都会获得一个令牌号码，拥有最小号码的进程进入临界区。如果两个进程具有相同的令牌号码，则进程 ID 较小的进程进入其临界区。

Lamport 面包店算法的算法

Lamport 面包店算法中进程 Pi 解决临界区问题的结构。

解释 -

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

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

当一个进程希望进入临界区时，它选择一个比任何早期号码都大的令牌号码。

假设进程 Pi 希望进入临界区，它将

entering[i] 设置为 true，以使其他进程知道它正在选择一个令牌号码。然后它选择一个比其他进程持有的令牌号码更大的号码，并写入其令牌号码。然后它在读取它们后将 entering[i] 设置为 false。然后它进入一个循环以评估其他进程的状态。它等待直到某些其他进程 Pj 正在选择其令牌号码。

Pi 然后等待，直到所有拥有较小令牌号码或相同令牌号码但优先级较高的进程都已快速服务。

当进程完成其临界区执行后，它将其号码变量重置为 0。

面包店算法满足临界区问题的所有要求。

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

Lamport 面包店算法的优点

• Lamport 面包店算法没有饥饿问题。
• Lamport 面包店算法遵循 FIFO。
• Lamport 面包店算法适用于原子寄存器。
• Lamport 面包店算法是解决 N 进程一般情况互斥问题已知最简单的解决方案之一。
• 该算法确保了多线程环境中共享资源的有效利用。

Lamport 面包店算法的缺点

• Lamport 面包店算法不可靠，因为任何一个进程的故障都会停止进展。它在进入/退出临界区时具有高消息复杂度，为 3(N - 1) 条消息。