笙亿网络策划

操作系统怎么实现软件-based解决方案？

约 15 分钟读完 7 阅
文章导读
Previous Quiz Next 在多任务操作系统中，为了解决进程同步问题，我们可以实现基于软件的解决方案或基于硬件的解决方案。基于软件的解决方案指的是在进程内部使用的算法和编程技术，用于实现同步，而无需使用任何特殊的硬件指令。
📋 目录
  1. Ⅰ Peterson's Algorithm
  2. Ⅱ Dekker's Algorithm
  3. Ⅲ Bakery Algorithm
  4. Ⅳ Peterson's Algorithm 与 Bakery Algorithm 与 Dekker's Algorithm
  5. Ⅴ 结论
A A

操作系统 基于软件的进程同步解决方案

Previous
Quiz
Next

在多任务操作系统中，为了解决进程同步问题，我们可以实现基于软件的解决方案或基于硬件的解决方案。基于软件的解决方案指的是在进程内部使用的算法和编程技术，用于实现同步，而无需使用任何特殊的硬件指令。

在本章中，我们将重点了解可以实现多个进程之间互斥和同步的基于软件的解决方案。以下是一些提供进程同步基于软件解决方案的流行算法：

  • Peterson's Algorithm
  • Dekker's Algorithm
  • Bakery Algorithm

Peterson's Algorithm

Peterson's Algorithm 是实现两个进程之间互斥的经典解决方案。其思想是使用两个共享变量：

  • flag[i] − 表示进程 i 是否想要进入其临界区。
  • turn − 表示轮到谁进入临界区。

该算法的工作方式如下：

  • 将 flag[i] 改为 true（表示进程 i 想要进入其临界区）。
  • 将 turn 设置为 j，表示轮到另一个进程。
  • 当 flag[j] 为 true（另一个进程想要进入其临界区）且 turn 等于 j（轮到另一个进程）时，等待。
  • 进入临界区。
  • 将 flag[i] 设置为 false，表示进程 i 已完成其临界区。

Example

以下是 Peterson's Algorithm 的 C++ 实现

#include <iostream>
#include <thread>
#include <atomic>
using namespace std;

atomic<bool> flag[2] = {false, false};
atomic<int> turn;

void peterson_process(int i) {
    int j = 1 - i;
    while (true) {
        // 表示进程 i 想要进入其临界区
        flag[i] = true;
        // 将 turn 设置为另一个进程
        turn = j;
        // 等待直到另一个进程不感兴趣或轮到此进程
        while (flag[j] && turn == j) {
            // 忙等待
        }
        // 临界区
        cout << "Process " << i << " in critical section" << endl;
        // 退出区
        flag[i] = false;
        // 剩余区
        cout << "Process " << i << " in remainder section" << endl;
    }
}

int main() {
    thread t1(peterson_process, 0);
    thread t2(peterson_process, 1);
    t1.join();
    t2.join();
    return 0;
}

上述代码的输出将为：

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

Dekker's Algorithm

In Dekker's Algorithm，使用两个标志和一个 turn 变量来实现两个进程之间的互斥访问。每个进程都有自己的标志，用于指示是否想要进入其临界区。turn 变量用于指示轮到谁进入临界区。

该算法的工作方式如下 −

  • 创建一个 turn 变量来指示谁可以先进入。
  • 进入时：设置 flag[i] = true。
  • 当另一个 flag[j] 为 true 且 turn == j 时，设置 flag[i] = false 并等待轮到自己；当 turn != j 时，再次设置 flag[i] = true。
  • 进入临界区。
  • 退出后：设置 turn = j 和 flag[i] = false。

Example

以下是 Dekker's Algorithm 在 C++ 中的实现

#include <iostream>
#include <thread>
#include <atomic>
#include <chrono>

std::atomic<bool> want1{false};
std::atomic<bool> want2{false};
std::atomic<int> favoured{1};
const int ITERATIONS = 10;

void thread1() {
    for (int i = 0; i < ITERATIONS; ++i) {
        // 表示意图进入
        want1.store(true);

        // 进入段：当 thread 2 想要进入时等待
        while (want2.load()) {
            if (favoured.load() == 2) {
                // 让给 thread 2 并等待 favoured 改变
                want1.store(false);
                while (favoured.load() == 2) {
                    std::this_thread::yield();
                }
                want1.store(true);
            }
        }

        // 临界区
        std::cout << "Thread 1 entering critical section (iteration " << i << ")" << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        std::cout << "Thread 1 leaving critical section (iteration " << i << ")" << std::endl;

        // 让给另一个线程并退出
        favoured.store(2);
        want1.store(false);

        // 剩余段
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
    }
}

void thread2() {
    for (int i = 0; i < ITERATIONS; ++i) {
        // 表示意图进入
        want2.store(true);

        // 进入段：当 thread 1 想要进入时等待
        while (want1.load()) {
            if (favoured.load() == 1) {
                // 让给 thread 1 并等待 favoured 改变
                want2.store(false);
                while (favoured.load() == 1) {
                    std::this_thread::yield();
                }
                want2.store(true);
            }
        }

        // 临界区
        std::cout << "Thread 2 entering critical section (iteration " << i << ")" << std::endl;
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
        std::cout << "Thread 2 leaving critical section (iteration " << i << ")" << std::endl;

        // 让给另一个线程并退出
        favoured.store(1);
        want2.store(false);

        // 剩余段
        std::this_thread::sleep_for(std::chrono::milliseconds(50));
    }
}

int main() {
    std::thread t1(thread1);
    std::thread t2(thread2);

    t1.join();
    t2.join();

    std::cout << "Both threads completed." << std::endl;
    return 0;
}

上述代码的输出将为 −

Thread 1 entering critical section (iteration 0)
Thread 1 leaving critical section (iteration 0)
Thread 2 entering critical section (iteration 0)
Thread 2 leaving critical section (iteration 0)
Thread 1 entering critical section (iteration 1)
....
Both threads completed.

Bakery Algorithm

Bakery Algorithm 是实现多个进程间互斥的另一种解决方案。该算法借鉴了面包店为顾客分配号码牌的想法，来决定服务的顺序。

为了实现进程同步的 Bakery Algorithm，我们使用两个共享数组 −

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

算法的工作流程如下 −

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

Example

下面的代码用 C++ 实现了 Bakery Algorithm。

#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)));
        }

        // Critical Section
        cout << "Process " << i << " is in its critical section." << endl;

        // Exit Section
        number[i] = 0;

        // Remainder Section
        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.
...

Peterson's Algorithm 与 Bakery Algorithm 与 Dekker's Algorithm

以下是基于各种因素对 Peterson's Algorithm、Bakery Algorithm 和 Dekker's Algorithm 的比较 −

因素 Peterson's Algorithm Bakery Algorithm Dekker's Algorithm
算法背后的思想 使用两个标志和一个 turn 变量，在两个进程之间实现互斥。 使用票号系统为进程分配号码，类似于面包店中的顾客。 使用两个标志和一个 turn 变量。但比 Peterson's algorithm 更复杂。
进程数量 仅两个进程 多个进程（N 个进程） 仅两个进程
复杂度 简单且易于实现 由于票号机制而更复杂 由于多个标志和 turn 变量而复杂
公平性 公平，因为使用了 turn 变量 公平，因为使用了票号 公平，但在某些情况下可能导致饥饿
性能 对两个进程高效 由于票号开销而效率较低 由于忙等待和复杂度而效率较低
使用场景 适用于两个进程的同步场景 适用于多进程的同步场景 主要具有理论意义；实践中很少使用

结论

有三种流行的算法用于实现进程同步。这些也被称为基于软件的进程同步解决方案。Peterson's Algorithm 是一种经典算法，对两个进程简单且高效。Dekker's Algorithm 是 Peterson's algorithm 的更复杂版本。Bakery Algorithm 是一种更通用的解决方案，可用于超过两个进程。