题目描述

假设有这么一个类：

class ZeroEvenOdd {
  public ZeroEvenOdd(int n) { ... }      // 构造函数
  public void zero(printNumber) { ... }  // 仅打印出 0
  public void even(printNumber) { ... }  // 仅打印出 偶数
  public void odd(printNumber) { ... }   // 仅打印出 奇数
}

相同的一个 ZeroEvenOdd 类实例将会传递给三个不同的线程：

线程 A 将调用 zero()，它只输出 0 。
线程 B 将调用 even()，它只输出偶数。
线程 C 将调用 odd()，它只输出奇数。
每个线程都有一个 printNumber 方法来输出一个整数。请修改给出的代码以输出整数序列 010203040506... ，其中序列的长度必须为 2n。

样例

示例 1：

输入：n = 2
输出："0102"
说明：三条线程异步执行，其中一个调用 zero()，另一个线程调用 even()，最后一个线程调用odd()。正确的输出为 "0102"。
示例 2：

输入：n = 5
输出："0102030405"

算法1

(互斥量)

互斥量定义：mutex m_zero,m_odd,m_even
初始化：将m_odd,m_even锁住

函数1（输出0）：遍历1-n，拿到m_zero的锁，输出0，根据当前遍历的是奇数还是偶数，去释放相应的锁（m_odd或m_even）
函数2（输出奇数）：遍历1-n中的所有奇数，拿到m_odd的锁,输出当前数字，释放m_zero的锁
函数3（输出偶数）：遍历1-n中的所有偶数，拿到m_even的锁,输出当前数字，释放m_zero的锁

C++ 代码

class ZeroEvenOdd {
private:
    int n;
    mutex m_zero,m_even,m_odd;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        m_even.lock();
        m_odd.lock();
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        for(int i=1;i<=n;i++){
            m_zero.lock();
             printNumber(0);
             if(i%2!=0){
                 m_odd.unlock();
             }
             else m_even.unlock();
        }
    }

    void even(function<void(int)> printNumber) {
        for(int i=2;i<=n;i+=2){
            m_even.lock();
            printNumber(i);
            m_zero.unlock();
        }
    }

    void odd(function<void(int)> printNumber) {
        for(int i=1;i<=n;i+=2){
            m_odd.lock();
            printNumber(i);
            m_zero.unlock();
        }
    }
};

算法2

(信号量)

对比算法1，使用0-1信号量来代替互斥量

C++ 代码

#include <semaphore.h>
class ZeroEvenOdd {
private:
    int n;
    sem_t zero_sem;
    sem_t odd_sem;
    sem_t even_sem;
public:
    ZeroEvenOdd(int n) {
        this->n = n;

        sem_init(&zero_sem, 0, 1); //初始化一个0
        sem_init(&odd_sem, 0, 0);
        sem_init(&even_sem, 0, 0);     
    }

    // printNumber(x) outputs "x", where x is an integer.
    void zero(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i++) {
            sem_wait(&zero_sem);
            printNumber(0);
            if(i & 1) sem_post(&odd_sem);
            else sem_post(&even_sem);
        }
    }

    void even(function<void(int)> printNumber) {
        for(int i = 2; i <= n; i+=2) {
            sem_wait(&even_sem);
            printNumber(i);
            sem_post(&zero_sem); 
        }
    }

    void odd(function<void(int)> printNumber) {
        for(int i = 1; i <= n; i+=2) {
            sem_wait(&odd_sem);
            printNumber(i);
            sem_post(&zero_sem); 
        }  
    }
};

算法3

(条件变量)

C++ 代码

class ZeroEvenOdd {
private:
    int n;
    bool terminate;
    int sequence;
    std::mutex mutex;
    std::condition_variable cv0,cv1;

public:
    ZeroEvenOdd(int n) {
        this->n = n;
        sequence = 1;
        terminate = false;
    }

    void zero(function<void(int)> printNumber) {
        while(sequence <= n) {
            std::unique_lock<std::mutex> l(mutex);
            printNumber(0);
            cv1.notify_all();
            cv0.wait(l);
        }
        terminate = true;
        cv1.notify_all();
    }

    void even(function<void(int)> printNumber) {
        while(sequence <= n) {
            std::unique_lock<std::mutex> l(mutex);
            cv1.wait(l, [ this ] { return sequence % 2 == 0; });
            if (!terminate)
                printNumber(sequence);
            sequence++;
            cv0.notify_one();
        }
    }

    void odd(function<void(int)> printNumber) {
        while(sequence <= n) {
            std::unique_lock<std::mutex> l(mutex);
            cv1.wait(l, [ this ] { return sequence % 2 != 0; });
            if (!terminate)
                printNumber(sequence);
            sequence++;
            cv0.notify_one();
        }
    }
};