leetcode题记-1114.按序打印

题目

我们提供了一个类：

public class Foo {
  public void one() { print("one"); }
  public void two() { print("two"); }
  public void three() { print("three"); }
}

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

线程 A 将会调用 one() 方法
线程 B 将会调用 two() 方法
线程 C 将会调用 three() 方法
请设计修改程序，以确保 two() 方法在 one() 方法之后被执行，three() 方法在 two() 方法之后被执行。

示例 1:

输入: [1,2,3]
输出: “onetwothree”
解释:
有三个线程会被异步启动。
输入 [1,2,3] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 two() 方法，线程 C 将会调用 three() 方法。
正确的输出是 “onetwothree”。

示例 2:

输入: [1,3,2]
输出: “onetwothree”
解释:
输入 [1,3,2] 表示线程 A 将会调用 one() 方法，线程 B 将会调用 three() 方法，线程 C 将会调用 two() 方法。
正确的输出是 “onetwothree”。

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

来源：力扣（LeetCode）

题解

因为是第一次做多线程的题目，之前对操作系统的锁之类的东西也没有好好学，这次做下来这题（包括看了其他人的题解）也算是复习了以下多线程的基础。

Naive

一开始并不知道锁要怎么实现（体现了我的菜），所以就用了几个bool和while实现了简单的阻塞（我并不知道线程的阻塞是怎么实现的），结果运行结果一出来就傻眼了（太菜了）。

class Foo {
public:
    Foo() {
        f = s = t = false;
    }

    void first(function<void()> printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        f = true;
    }

    void second(function<void()> printSecond) {
        while (!(f && !s));
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        s = true;
    }

    void third(function<void()> printThird) {
        while (!(f && s && !t));
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
        t = true;
    }
private:
    bool f, s, t;
};

结果1

执行用时 : 1484 ms, 在所有 C++ 提交中击败了5.01%的用户
内存消耗 : 9 MB, 在所有 C++ 提交中击败了100.00%的用户

当然我也不知道为啥我的占用总是超过了100%的人。

Use mutex

看过了别人的题解之后，我发现了多数人用了std::mutex和std::condition_variable这两个库用于互斥锁的实现。因为mutex比较简单，所以就顺便学了以下（还不是因为太菜）。

先来看看 std::mutex 的介绍：

构造函数，std::mutex不允许拷贝构造，也不允许 move 拷贝，最初产生的 mutex 对象是处于 unlocked 状态的。

lock()，调用线程将锁住该互斥量。线程调用该函数会发生下面 3 种情况：

如果该互斥量当前没有被锁住，则调用线程将该互斥量锁住，直到调用 unlock之前，该线程一直拥有该锁。

如果当前互斥量被其他线程锁住，则当前的调用线程被阻塞住。

如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)。

unlock()，解锁，释放对互斥量的所有权。

try_lock()，尝试锁住互斥量，如果互斥量被其他线程占有，则当前线程也不会被阻塞。线程调用该函数也会出现下面 3 种情况，(1). 如果当前互斥量没有被其他线程占有，则该线程锁住互斥量，直到该线程调用 unlock 释放互斥量。(2). 如果当前互斥量被其他线程锁住，则当前调用线程返回 false，而并不会被阻塞掉。(3). 如果当前互斥量被当前调用线程锁住，则会产生死锁(deadlock)。

reference:C++11 并发指南三(std::mutex 详解)

从用法中可以看出来，在互斥量被锁住的时候，线程执行lock()函数是会被阻塞的，只有在互斥量被unlock()之后，lock()函数才会被执行。所以可以通过设置两个互斥锁分别对second和third进行锁定。

class Foo {
public:
    Foo() {
        smx.lock();
        tmx.lock();
    }

    void first(function<void()> printFirst) {
        // printFirst() outputs "first". Do not change or remove this line.
        printFirst();
        smx.unlock();
    }

    void second(function<void()> printSecond) {
        smx.lock();
        // printSecond() outputs "second". Do not change or remove this line.
        printSecond();
        tmx.unlock();
    }

    void third(function<void()> printThird) {
        tmx.lock();
        // printThird() outputs "third". Do not change or remove this line.
        printThird();
    }
private:
    mutex smx, tmx;
};

结果2

执行用时 : 40 ms, 在所有 C++ 提交中击败了31.67%的用户
内存消耗 : 9.2 MB, 在所有 C++ 提交中击败了100.00%的用户

这次的结果就好了许多。