[每日一题] 第二十二题:按序打印

题目描述

我们提供了一个类:

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
链接:leetcode-cn.com/problems/print-in-...
来源:力扣(LeetCode)

并发问题

并发问题来自并发计算的场景,该场景下,程序在多线程(或多进程)中 同时 执行。

同时进行并不是完全指进程或线程在不同的物理 CPU 上独立运行,更多情况下,是在一个物理 CPU 上交替执行多个线程或进程。并发即可在线程中,也可在进程中。

并发主要为多任务情况设计。但如果应用不当,可能会引发一些漏洞。按照情况不同,可以分为三种:

  • 竞态条件:由于多进程之间的竞争执行,导致程序未按照期望的顺序输出。
  • 死锁:并发程序等待一些必要资源,导致没有程序可以执行。
  • 资源不足:进程被永久剥夺了运行所需的资源。

此题中存在竞态条件。下面展示一个竞态条件的例子。

假设有一个方法 withdraw(amount),如果请求量小于当前余额,则从当前余额中减去请求量,然后返回余额。方法定义如下:

int balance = 500;
int withdraw(int amount) {
  if (amount < balance) {
    balance -= amount;
  }
  return balance;
}

我们期望该方法执行后余额永远不会为负。

但是有可能出现竞态条件,使得余额变为负数。假设两个线程同时使用不同的参数执行该方法。例如:线程 1 执行 withdraw(400),线程 2 执行 withdraw(200)。这两个线程的执行顺序如下图所示。在每个时刻只执行一条语句。

[每日一题] 第二十二题:按序打印

上述流程执行结束后,余额变成负数,这并不是期望的输出。

无竞争并发

并发问题有一个共同特征:多个线程/进程之间共享一些资源(例如:余额)。由于无法消除资源共享的约束,防止并发问题就变成了资源共享的协调问题。

根据这个思路,如果可以确保程序中 关键部分代码的独占性(例如:检查和减少余额),就可以防止程序进入不一致的状态。

竞争条件的解决方案为:需要某些关键部分代码具有排他性,即在给定的时间内,只有一个线程可以进入关键部分代码。

可以将这种机制看做限制关键部分代码访问的锁。在前面示例的关键部分代码加锁,即检查余额和减少余额的语句。然后重新运行两个线程,会有下图的执行顺序:

[每日一题] 第二十二题:按序打印

在该机制下,一旦一个线程进入关键部分,它就可以阻止其它线程进入该关键部分。例如:在时间点 3 ,线程 2 进入关键部分,那么在时间点 4,如果没有锁保护,线程 1 就可能进入关键部分。嘴鸥胡两个线程同时运行,保证系统的一致性,并确保余额正确。

如果该线程未被授权进入关键代码,可以认为该线程被阻塞或进入睡眠状态。例如:线程 1 在时间点 4 被阻塞,之后关键代码部分被释放,可以通知其它等待线程。线程 2 在时间点 5 释放了关键部分,就可以通知 线程 1 进入。

这种机制还具有唤醒其它等待线程的功能。

题解

方法一:使用 synchronization

思路

题目要求按顺序依次执行三个方法,且每个方法都在单独的线程中运行。为了保证线程的执行顺序,可以在方法之间创建一些依赖关系,即第二个方法必须在第一个方法之后执行,第三个方法必须在第二个之后执行。

方法对之间的依赖关系形成了所有方法的特定的执行顺序。例如 A < BB < C,则所有方法的执行顺序为 A < B < C

[每日一题] 第二十二题:按序打印

依赖关系可以通过并发机制实现。使用一个共享变量 firstJobDone 协调第一个方法与第二个方法的执行顺序,使用另一个共享变量 secondJobDone 协调第二个方法与第三个方法的执行顺序。

算法

  • 首先初始化共享变量 firstJobDonesecondJobDone,初始值表示所有方法未执行。
  • 方法 first() 没有依赖关系,可以直接执行。在方法最后更新变量 firstJobDone 表示该方法执行完成。
  • 方法 second() 中,检查 firstJobDone 的状态。如果未更新则进入等待状态,否则执行方法 second()。在方法末尾,更新变量 secondJobDone 表示方法 second() 执行完成。
  • 方法 third() 中,检查 secondJobDone 的状态。与方法 second() 类似,执行 third() 之前,需要先等待 secondJobDone 的状态。

[每日一题] 第二十二题:按序打印

代码

使用互斥和信号量来实现。

class Foo {

  private AtomicInteger firstJobDone = new AtomicInteger(0);
  private AtomicInteger secondJobDone = new AtomicInteger(0);

  public Foo() {}

  public void first(Runnable printFirst) throws InterruptedException {
    // printFirst.run() outputs "first".
    printFirst.run();
    // mark the first job as done, by increasing its count.
    firstJobDone.incrementAndGet();
  }

  public void second(Runnable printSecond) throws InterruptedException {
    while (firstJobDone.get() != 1) {
      // waiting for the first job to be done.
    }
    // printSecond.run() outputs "second".
    printSecond.run();
    // mark the second as done, by increasing its count.
    secondJobDone.incrementAndGet();
  }

  public void third(Runnable printThird) throws InterruptedException {
    while (secondJobDone.get() != 1) {
      // waiting for the second job to be done.
    }
    // printThird.run() outputs "third".
    printThird.run();
  }

个人理解

  1. AtomicInteger:一个提供原子操作的 Integer 类。在 Java 语言中。++i 和 i++ 操作并不是线程安全的,在使用的时候,不可避免的会用到 synchronized 关键字。而 AtomicInteger 则通过一种线程安全的加减操作接口。
  2. 实现两个信号量。

来源

作者:LeetCode
链接:leetcode-cn.com/problems/print-in-...
来源:力扣(LeetCode)

方法二:构造执行屏障实现

解题思路

这是一个典型的执行屏障的问题,可以通过构造屏障来实现。

如下图,我们需要构造 2 道屏障,second 线程等待 first 线程屏障,third 线程等待 second 线程 屏障:

dd61551a1d5013142e5a9a215bd14a2d.png

first 线程会释放 first 屏障,而 second 线程会释放 second 屏障。

Java 中,我们使用线程等待的方式实现执行屏障,使用释放线程等待的方式实现屏障消除。

代码

class Foo {

    private boolean firstFinished;
    private boolean secondFinished;
    private Object lock = new Object();

    public Foo() {

    }

    public void first(Runnable printFirst) throws InterruptedException {

        synchronized (lock) {
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            firstFinished = true;
            lock.notifyAll(); 
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {

        synchronized (lock) {
            while (!firstFinished) {
                lock.wait();
            }

            // printSecond.run() outputs "second". Do not change or remove this line.
            printSecond.run();
            secondFinished = true;
            lock.notifyAll();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {

        synchronized (lock) {
           while (!secondFinished) {
                lock.wait();
            }

            // printThird.run() outputs "third". Do not change or remove this line.
            printThird.run();
        } 
    }
}

个人理解

  1. wait()/notify()/notifyAll():在 Object 对象中有这三个方法。既然是 Object 中的方法,那每个对象自然都是有的。
  2. wait():wait() 方法的作用是使当前执行代码的线程进行等待,将当前线程置入”预执行队列“中,并且 wait() 所在的代码处停止执行。知道接到通知或被中断。在调用 wait() 之前,线程必须获取该对象的锁,因此只能在同步方法/同步代码块中调用 wait() 方法
  3. notify():notify() 方法的作用是,如果有多个线程等待,那么线程规划器随机挑选出一个 wait 的线程,对其发出通知 notify(),并使它等待获取该对象的对象锁。注意 等待获取该对象的对象锁,这意味着,即时收到了通知,wait 的线程也不会马上获取对象锁,必须等待 notify() 方法的线程释放锁才可以,和 wait() 一样,notify() 也要在同步方法/同步代码块中调用
  4. wait() 使线程停止运行,notify() 使停止运行的线程继续运行
  5. notifyAll():notifyAll() 方法会使所以正在等待队列中等待同一共享资源的全部线程从等待状态中退出,进入可运行状态。

来源

作者:pulsaryu
链接:leetcode-cn.com/problems/print-in-...
来源:力扣(LeetCode)

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!