1114.按序打印

1114. 按序打印

给你一个类：

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

三个不同的线程 A、B、C 将会共用一个 Foo 实例。

线程 A 将会调用 first() 方法
线程 B 将会调用 second() 方法
线程 C 将会调用 third() 方法

请设计修改程序，以确保 second() 方法在 first() 方法之后被执行，third() 方法在 second() 方法之后被执行。

提示：

尽管输入中的数字似乎暗示了顺序，但是我们并不保证线程在操作系统中的调度顺序。
你看到的输入格式主要是为了确保测试的全面性。

示例 1：

输入：nums = [1,2,3]
输出："firstsecondthird"
解释：
有三个线程会被异步启动。输入 [1,2,3] 表示线程 A 将会调用 first() 方法，线程 B 将会调用 second() 方法，线程 C 将会调用 third() 方法。正确的输出是 "firstsecondthird"。

示例 2：

输入：nums = [1,3,2]
输出："firstsecondthird"
解释：
输入 [1,3,2] 表示线程 A 将会调用 first() 方法，线程 B 将会调用 third() 方法，线程 C 将会调用 second() 方法。正确的输出是 "firstsecondthird"。

提示：

nums 是 [1, 2, 3] 的一组排列

C++

互斥锁

针对这道题我们可以用两个互斥锁来阻塞 second 和 third 函数，分别在 first 和 second 执行结束后解锁。

class Foo {
    mutex mtx1, mtx2;
public:
    Foo() {
        mtx1.lock(), mtx2.lock();
    }

    void first(function<void()> printFirst) {
        printFirst();
        mtx1.unlock();
    }

    void second(function<void()> printSecond) {
        mtx1.lock();
        printSecond();
        mtx1.unlock();
        mtx2.unlock();
    }

    void third(function<void()> printThird) {
        mtx2.lock();
        printThird();
        mtx2.unlock();
    }
};

这段代码能够 AC，但实际上这种使用 mutex 的方法是错误的，因为根据 C++ 标准，在一个线程尝试对一个 mutex 对象进行 unlock 操作时，mutex 对象的所有权必须在这个线程上；也就是说，应该由同一个线程来对一个 mutex 对象进行 lock 和 unlock 操作，否则会产生未定义行为。

题目中提到了 first，second，third 三个函数分别是由三个不同的线程来调用的，但我们是在 Foo 对象构造时（可以是在 create 这几个线程的主线程中，也可以是在三个线程中的任意一个）对两个 mutex 对象进行 lock 操作的，因此，调用 first 和 second 函数的两个线程中至少有一个在尝试获取其他线程所拥有的 mutex 对象的所有权。

另外，如果非要讨论这个解法有什么优化的余地的话，因为 mutex 对象本身是不保护任何数据的，我们只是通过 mutex 的机制来保护数据被同时访问，所以最好使用 lock_guard 或者 unique_lock 提供的 RAII 机制来管理 mutex 对象，而不是直接操作 mutex 对象；其中 lock_guard 只拥有构造和析构函数，用来实现 RAII 机制，而 unique_lock 是一个完整的 mutex 所有权包装器，封装了所有 mutex 的函数：

class Foo {
    mutex mtx_1, mtx_2;
    unique_lock<mutex> lock_1, lock_2;
public:
    Foo() : lock_1(mtx_1, try_to_lock), lock_2(mtx_2, try_to_lock) {
    }

    void first(function<void()> printFirst) {
        printFirst();
        lock_1.unlock();
    }

    void second(function<void()> printSecond) {
        lock_guard<mutex> guard(mtx_1);
        printSecond();
        lock_2.unlock();
    }

    void third(function<void()> printThird) {
        lock_guard<mutex> guard(mtx_2);
        printThird();
    }
};

mutex对象mtx_1和mtx_2用于提供不同的互斥量，确保不同的线程对它们进行独占式访问。

unique_lock对象lock_1和lock_2用于在执行成员函数时锁定mtx_1和mtx_2。这些锁在类的构造函数中被创建，并使用try_to_lock参数进行初始化，该参数会尝试在不阻塞的情况下获取锁，如果锁不可用，则unique_lock将处于未锁定状态。

成员函数first接受一个函数printFirst作为其参数，仅调用此函数，然后解锁lock_1。

成员函数second首先使用lock_guard对象guard获取mtx_1的锁，guard对象在其作用域结束时会自动释放锁。然后调用函数printSecond，最后解锁lock_2。

成员函数third类似地使用lock_guard对象获取mtx_2的锁，调用函数printThird，然后返回。

信号量

#include <semaphore.h>
class Foo {
private:
    sem_t sem_1, sem_2;

public:
    Foo() {
        sem_init(&sem_1, 0, 0), sem_init(&sem_2, 0, 0);
    }

    void first(function<void()> printFirst) {
        printFirst();
        sem_post(&sem_1); // V;
    }

    void second(function<void()> printSecond) {
        sem_wait(&sem_1); // P
        printSecond();
        sem_post(&sem_2); // V
    }

    void third(function<void()> printThird) {
        sem_wait(&sem_2); // P
        printThird();
    }
};

原子操作

我们平时进行的数据修改都是非原子操作，如果多个线程同时以非原子操作的方式修改同一个对象可能会发生数据争用，从而导致未定义行为；而原子操作能够保证多个线程顺序访问，不会导致数据争用，其执行时没有任何其它线程能够修改相同的原子对象。

针对这道题，我们可以让 second 和 third 函数等待原子变量被修改为某个值后再执行，然后分别在 first 和 second 函数中来修改这个原子变量。

C++ 11 提供了 std::atomic 模板类来构造原子对象：

class Foo {
    std::atomic<bool> a{ false };
    std::atomic<bool> b{ false };
public:
    void first(function<void()> printFirst) {
        printFirst();
        a = true;
    }

    void second(function<void()> printSecond) {
        while (!a) this_thread::sleep_for(chrono::milliseconds(1));
        printSecond();
        b = true;
    }

    void third(function<void()> printThird) {
        while (!b) this_thread::sleep_for(chrono::milliseconds(1));
        printThird();
    }
};

异步操作

异步操作是一种，在不需要等待被调用方返回结果之前，就让操作继续进行下去的方法。针对这道题可以使用基于 future/promise 的异步编程模型。

future 和 promise 起源于函数式编程，其目的是将值（future）和计算方式（promise）分离，使得 promise 可以异步地修改 future，从而提高代码的可读性，并减少通信延迟。

std::future 是用来获取异步操作结果的模板类；std::packaged_task, std::promise, std::async 都可以进行异步操作，并拥有一个 std::future 对象，用来存储它们所进行的异步操作返回或设置的值（或异常），这个值会在将来的某一个时间点，通过某种机制被修改后，保存在其对应的 std::future 对象中：

对于 std::promise，可以通过调用 std::promise::set_value 来设置值并通知 std::future 对象：

class Foo {
    promise<void> pro1, pro2;

public:
    void first(function<void()> printFirst) {
        printFirst();
        pro1.set_value();
    }

    void second(function<void()> printSecond) {
        pro1.get_future().wait();
        printSecond();
        pro2.set_value();
    }

    void third(function<void()> printThird) {
        pro2.get_future().wait();
        printThird();
    }
};

这段代码定义了一个名为 Foo 的类，其中包含三个方法 first、second 和 third，以及两个 promise 对象 pro1 和 pro2。

这个类的设计目的是：让三个方法 first、second 和 third 按照固定的顺序依次执行，并且在 first 方法执行后，才能执行 second 方法，second 方法执行后，才能执行 third 方法。

具体来说，first 方法接收一个函数 printFirst，并立即调用该函数。然后，它调用 pro1.set_value() 方法，将 pro1 对象的值设置为已完成状态。

second 方法接收一个函数 printSecond，并在 pro1 对象的值被设置为已完成状态后（即 pro1.get_future().wait() 返回）才能执行。然后，它调用 printSecond() 方法，将 pro2 对象的值设置为已完成状态。

third 方法接收一个函数 printThird，并在 pro2 对象的值被设置为已完成状态后（即 pro2.get_future().wait() 返回）才能执行。然后，它调用 printThird() 方法。

这个类的主要目的是为了演示如何使用 promise 和 future 实现多线程编程中的同步操作，保证多个线程按照预定的顺序依次执行。

条件变量

std::condition_variable 是一种用来同时阻塞多个线程的同步原语（synchronization primitive），**std::condition_variable 必须和 std::unique_lock 搭配使用**：

class Foo {
    condition_variable cv;
    mutex mtx;
    int k = 0;
public:
    void first(function<void()> printFirst) {
        printFirst();
        k = 1;
        cv.notify_all();    // 通知其他所有在等待唤醒队列中的线程
    }

    void second(function<void()> printSecond) {
        unique_lock<mutex> lock(mtx);   // lock mtx
        cv.wait(lock, [this](){ return k == 1; });  // unlock mtx，并阻塞等待唤醒通知，需要满足 k == 1 才能继续运行
        printSecond();
        k = 2;
        cv.notify_one();    // 随机通知一个（unspecified）在等待唤醒队列中的线程
    }

    void third(function<void()> printThird) {
        unique_lock<mutex> lock(mtx);   // lock mtx
        cv.wait(lock, [this](){ return k == 2; });  // unlock mtx，并阻塞等待唤醒通知，需要满足 k == 2 才能继续运行
        printThird();
    }
};

其中，first 函数首先被调用，然后将 k 的值设置为 1，并使用 cv.notify_all() 通知其他正在等待唤醒的线程。

second 函数首先获取 mtx 的独占锁，然后使用 cv.wait() 阻塞当前线程，并等待满足 k == 1 的条件，当条件满足时，打印 printSecond 并将 k 的值设置为 2，并使用 cv.notify_one() 随机通知一个正在等待唤醒的线程。

third 函数也获取 mtx 的独占锁，然后使用 cv.wait() 阻塞当前线程，并等待满足 k == 2 的条件，当条件满足时，打印 printThird。

unique_lock<mutex> lock(mtx);  
cv.wait(lock, [this](){ return k == 1; });

首先创建了一个 unique_lock 对象 lock 并使用 mtx 作为其构造函数的参数，从而对 mtx 加锁。

然后，cv.wait(lock, [this](){ return k == 1; }); 在 cv（条件变量）上等待，此时当前线程会释放 mtx，并阻塞在条件变量上，直到条件函数 [this](){ return k == 1; } 返回 true 或者被唤醒。条件函数的含义是，只有在 k 的值等于 1 时，才允许线程继续往下执行

等待期间，unique_lock 对象 lock 保持着 mtx 的独占锁，避免了其他线程的干扰。当满足条件后，wait() 函数会重新对 mtx 加锁，并将 lock 对象的所有权从等待线程转移给当前线程，从而使当前线程可以安全地访问共享资源。

需要注意的是，在等待期间，wait() 函数会释放 mtx，以便其他线程可以访问临界区，这也是条件变量的基本机制之一，可以避免死锁和资源浪费。