leetcode题记-1114.按序打印

题目

我们提供了一个类:

1
2
3
4
5
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实现了简单的阻塞(我并不知道线程的阻塞是怎么实现的),结果运行结果一出来就傻眼了(太菜了)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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::mutexstd::condition_variable这两个库用于互斥锁的实现。因为mutex比较简单,所以就顺便学了以下(还不是因为太菜)。

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

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

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

    1. 如果该互斥量当前没有被锁住,则调用线程将该互斥量锁住,直到调用 unlock之前,该线程一直拥有该锁。
    2. 如果当前互斥量被其他线程锁住,则当前的调用线程被阻塞住。
    3. 如果当前互斥量被当前调用线程锁住,则会产生死锁(deadlock)。
  • unlock(), 解锁,释放对互斥量的所有权。

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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%的用户

这次的结果就好了许多。

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/08/21/leetcode-1114-Foo-Bar/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,