操作系统 - 用于进程同步的 Bakery 算法

Bakery 算法 是一种经典的基于软件的解决方案，用于实现多个进程之间的互斥和同步。它由 Leslie Lamport 于 1974 年提出。该算法的灵感来源于面包店中顾客取号并按号码顺序服务的机制。

阅读本章以了解 Bakery 算法的工作原理以及如何实现它来确保进程同步。

• Bakery 算法
• Bakery 算法的步骤
• Bakery 算法的实现
• Bakery 算法的优势

Bakery 算法

Bakery 算法的核心思想是为每个希望进入临界区的进程分配一个唯一的票号。票号表示进程进入临界区的顺序。票号最低的进程优先进入其临界区。有时如果两个进程的票号相同，则进程 ID 较低的进程优先。

为了实现 Bakery 算法，我们使用两个共享变量 −

• choosing[i](boolean)：存储进程 i 是否正在选择号码。
• number[i](integer)：保存分配给进程 i 的号码，这是进入临界区的令牌。

现在让我们进入实现 Bakery 算法的步骤。

Bakery 算法的步骤

以下是 Bakery 算法的步骤或流程 −

• 将 choosing[i] 设置为 true，表示进程 i 正在选择票号。
• 然后，将 number[i] 设置为所有进程中最大票号加 1。
• 接着，将 choosing[i] 设置为 false，表示进程 i 已完成票号选择。
• 对于每个进程 j，等待直到 choosing[j] 为 false（即进程 j 已完成票号选择）。
• 对于每个进程 j，等待直到 number[j] 为 0（即进程 j 不希望进入临界区）或者 (number[j], j) 大于 (number[i], i)（即进程 j 的票号更高，或者票号相同但进程 ID 更高）。
• 进入临界区。
• 将 number[i] 设置为 0，表示进程 i 已完成临界区。
• 剩余部分。

面包店算法的实现

下面的部分使用 C++ 实现了面包店算法。

#include <iostream>
#include <thread>
#include <vector>
#include <algorithm>
#include <atomic>

using namespace std;
const int NUM_PROCESSES = 5;
atomic<bool> choosing[NUM_PROCESSES];
atomic<int> number[NUM_PROCESSES];

void bakery_process(int i) {
    for (int iter = 0; iter < 5; iter++) {
        // 选择一个号码
        choosing[i] = true;
        number[i] = 1 + *max_element(number, number + NUM_PROCESSES);
        choosing[i] = false;

        // 等待其他进程
        for (int j = 0; j < NUM_PROCESSES; j++) {
            while (choosing[j]);
            while (number[j] != 0 && (number[j] < number[i] || (number[j] == number[i] && j < i)));
        }

        // 关键区
        cout << "Process " << i << " is in its critical section." << endl;

        // 退出区
        number[i] = 0;

        // 剩余区
        cout << "Process " << i << " is in its remainder section." << endl;
    }
}

int main() {
    vector<thread> processes;
    for (int i = 0; i < NUM_PROCESSES; i++) {
        choosing[i] = false;
        number[i] = 0;
    }
    for (int i = 0; i < NUM_PROCESSES; i++) {
        processes.push_back(thread(bakery_process, i));
    }
    for (auto &process : processes) {
        process.join();
    }
    return 0;
}

上述代码的输出将为 −

Process 0 is in its critical section.
Process 0 is in its remainder section.
Process 1 is in its critical section.
Process 1 is in its remainder section.
...

面包店算法的优势

由于以下优势，面包店算法在大多数情况下都是首选 −

• 无饥饿 − 保证每个进程最终都能有机会进入其关键区。因此不存在饥饿的可能性。
• 公平性 − 该算法确保进程按照其票号顺序得到服务。这确保了进程之间的公平性。
• 可扩展性 − 面包店算法可以为任意数量的进程实现，使其适用于进程数量变化的系统。
• 简单性 − 该算法相对简单易懂且易于实现。

结论

面包店算法是一种基于令牌的解决方案，用于实现多个进程之间的互斥和同步。其思想是为每个想要进入关键区的进程分配一个唯一的令牌号，拥有最低令牌号的进程被允许首先进入其关键区。该算法确保无饥饿、公平性、可扩展性和简单性。因此，该算法在操作系统中被广泛用于进程同步。