面试手撕并发算法题固定打印顺序

使用 wait-notify 实现以下功能：先打印 b，再打印 a

思路一

线程t1和t2同时运行，t1中打印 a，t2中打印 b，但 t1 打印得有个前提，就是 t1要在t2运行完释放锁了才能打印 a。如果t1先得到锁，但t2没有执行，还是得释放锁，让t2得到锁先打印b，t2执行完，唤醒t1再打印a，实现固定顺序打印。

@Slf4jpublic class OrderPrint {    static Object obj = new Object();    static boolean is2Run = false;// t2 运行标记， 代表 t2 是否执行过    public static void main(String[] args) {        m1();    }    private static void m1() {        Thread t1 = new Thread(() -> {            synchronized (obj) {                // 如果 t2 没有执行过                while (!is2Run) {                    try {                        // t1 先等一会，释放锁                        obj.wait();                    } catch (InterruptedException e) {                        e.printStackTrace();                    }                }            }            log.debug("a");        }, "t1");        Thread t2 = new Thread(() -> {            log.debug("b");            synchronized (obj) {                is2Run = true;      // syn 自带可见性                obj.notifyAll();    // 通知 obj 上等待的线程            }        }, "t2");        t1.start();        t2.start();    }}

思路二

思路一有以下几个问题需要注意：

  1. 需要保证先 wait 再 notify，否则 wait 线程永远得不到唤醒。因此使用了『运行标记』来判断该不该 wait；
  2. 如果有些干扰线程错误地 notify 了 wait 线程，条件不满足时还要重新等待，因此使用了 while 循环来解决此问题；

可以使用 LockSupport 类的 park 和 unpark 来简化上面的题目：

    private static void m2() {        Thread t1 = new Thread(() -> {            try {                TimeUnit.SECONDS.sleep(1L);            } catch (InterruptedException e) {                e.printStackTrace();            }            // 线程暂停            LockSupport.park();            log.debug("a");        }, "t1");        Thread t2 = new Thread(() -> {            log.debug("b");            // 唤醒线程            LockSupport.unpark(t1);        }, "t2");        t1.start();        t2.start();    }

park 和 unpark 比较灵活，有以下特点：

  • park 和 unpark 不需要先获取锁，这一点和Object中的wait-notify，Condition接口提供的await-signal都不同。
  • 唤醒方法 unpark 在 等待方法 park 之前或之后运行，线程都能够被唤醒，这一点其他两种机制都不行，Object 和 Condition 中的唤醒必须在等待之后调用，线程才能被唤醒；

交替打印

准备三个线程t1、t2和t3，其中 t1 线程打印a，t2 线程打印 b，t3 线程打印 c，交替打印 ABCABC，打印100个字符。

思路：可以使用一个状态变量来表示打印abc，如 state=1 代表打印 a， state=2代表打印 b，state=3代表打印 c；使用synchronized 加锁。

@Slf4jpublic class AlternatePrint {    // 初始状态为1    private static int state = 1;    private static int loopNumber = 5;    private static int count;    private static Object obj = new Object();    public static void print(int waitState, int nextState, String str) {        while (true) {            synchronized (obj) {                // 当前获得锁的线程状态不是 state，等待释放锁                while (state != waitState) {                    try {                        obj.wait();                    } catch (InterruptedException e) {                        e.printStackTrace();                    }                }                // 如果 count 达到了100，进入if的线程修改为下一状态，并唤醒另两个线程，本线程结束                // 另两个线程争夺锁，最终都会执行结束（可以分析一波）                if(count == 100) {                    state = nextState;  // syn 保证可见性                    obj.notifyAll();                    break;                }                // 当前获得锁的线程状态就是 state，打印要打印的字符串                log.debug(str);                count++;                // 打印完，轮到下一个线程打印了，把状态改成 nextState                state = nextState;  // syn 保证可见性                obj.notifyAll();            }        }    }    public static void main(String[] args) {        // t1线程，如果当前状态是1，就打印a，下一个线程的状态是2        new Thread(() -> {            print(1, 2, "a");        }, "t1").start();        // t2线程，如果当前状态是2，就打印b，下一个线程的状态是3        new Thread(() -> {            print(2, 3, "b");        }, "t2").start();        // t3线程，如果当前状态是3，就打印c，下一个线程的状态是1        new Thread(() -> {            print(3, 1, "c");        }, "t3").start();    }}

交替打印变式

准备三个线程t1、t2和t3，其中 t1 线程打印a，t2 线程打印 b，t3 线程打印 c，交替打印 abcabc…

思路一：wait – notify

定义一个全局变量 state 来实现按顺序打印，使用wait - notify机制来处理条件不满足时等待释放锁，满足时打印并唤醒所有处于等待的线程；

@Slf4jpublic class AlternatePrint {    // 初始状态为1    private static int state = 1;    private static int loopNumber = 5;    private static Object obj = new Object();    public static void print(int waitState, int nextState, String str) {        for (int i = 0; i  {            print(1, 2, "a");        }, "t1").start();        // t2线程，如果当前状态是2，就打印b，下一个线程的状态是3        new Thread(() -> {            print(2, 3, "b");        }, "t2").start();        // t3线程，如果当前状态是3，就打印c，下一个线程的状态是1        new Thread(() -> {            print(3, 1, "c");        }, "t3").start();    }}

思路二：Lock条件变量

使用 ReentrantLock中的条件变量 Condition 实现等待唤醒机制，每次只会有一个线程在打印，而其他两个线程在各自的休息室等待（可以把创建出来的Condition 对象 理解成线程休息室）；

刚开始运行时，三个线程都会在各自的休息室等待，所以这个时候需要有一个发起者，就让主线程发起，唤醒a休息室中等待的线程 t1；

@Slf4jpublic class AlternatePrint1 extends ReentrantLock {    private int loopNumber;     // 循环次数    public AlternatePrint1(int loopNumber) {        this.loopNumber = loopNumber;    }    /**     * @param cur  进入哪一件休息室等待     * @param nextcur休息室的线程打印完后，要唤醒下一个休息室中等待的线程     * @param str要打印的字符串     */    public void print(Condition cur, Condition next, String str) {        for (int i = 0; i  {            ap.print(a, b, "a");        }, "t1").start();        new Thread(() -> {            ap.print(b, c, "b");        }, "t2").start();        new Thread(() -> {            ap.print(c, a, "c");        }, "t3").start();        // 以上三个线程都去各自的休息室等待去了，1s之后，主线程唤醒a休息室中的线程        TimeUnit.SECONDS.sleep(1L);        try {            ap.lock();            // 让主线程先唤醒在a休息室中等待的线程            a.signal();        } finally {            ap.unlock();        }    }}

TODO