面试手撕并发算法题

面试手撕并发算法题

固定打印顺序

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

思路一

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

1. @Slf4j
2. public class OrderPrint {
4.     static Object obj = new Object();
5.     static boolean is2Run = false;        // t2 运行标记， 代表 t2 是否执行过
7.     public static void main(String[] args) {
8.         m1();
9.     }
11.     private static void m1() {
12.         Thread t1 = new Thread(() -> {
13.             synchronized (obj) {
14.                 // 如果 t2 没有执行过
15.                 while (!is2Run) {
16.                     try {
17.                         // t1 先等一会，释放锁
18.                         obj.wait();
19.                     } catch (InterruptedException e) {
20.                         e.printStackTrace();
21.                     }
22.                 }
23.             }
24.             log.debug("a");
25.         }, "t1");
27.         Thread t2 = new Thread(() -> {
28.             log.debug("b");
29.             synchronized (obj) {
30.                 is2Run = true;      // syn 自带可见性
31.                 obj.notifyAll();    // 通知 obj 上等待的线程
32.             }
33.         }, "t2");
35.         t1.start();
36.         t2.start();
37.     }
38. }

复制代码

思路二

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

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

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

1.     private static void m2() {
2.         Thread t1 = new Thread(() -> {
4.             try {
5.                 TimeUnit.SECONDS.sleep(1L);
6.             } catch (InterruptedException e) {
7.                 e.printStackTrace();
8.             }
9.             // 线程暂停
10.             LockSupport.park();
11.             log.debug("a");
12.         }, "t1");
14.         Thread t2 = new Thread(() -> {
15.             log.debug("b");
16.             // 唤醒线程
17.             LockSupport.unpark(t1);
18.         }, "t2");
19.         t1.start();
20.         t2.start();
21.     }

复制代码

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 加锁。

1. @Slf4j
2. public class AlternatePrint {
3.     // 初始状态为1
4.     private static int state = 1;
5.     private static int loopNumber = 5;
6.     private static int count;
8.     private static Object obj = new Object();
10.     public static void print(int waitState, int nextState, String str) {
11.         while (true) {
13.             synchronized (obj) {
14.                 // 当前获得锁的线程状态不是 state，等待释放锁
15.                 while (state != waitState) {
16.                     try {
17.                         obj.wait();
18.                     } catch (InterruptedException e) {
19.                         e.printStackTrace();
20.                     }
21.                 }
22.                 // 如果 count 达到了100，进入if的线程修改为下一状态，并唤醒另两个线程，本线程结束
23.                 // 另两个线程争夺锁，最终都会执行结束（可以分析一波）
24.                 if(count == 100) {
25.                     state = nextState;  // syn 保证可见性
26.                     obj.notifyAll();
27.                     break;
28.                 }
29.                 // 当前获得锁的线程状态就是 state，打印要打印的字符串
30.                 log.debug(str);
31.                 count++;
33.                 // 打印完，轮到下一个线程打印了，把状态改成 nextState
34.                 state = nextState;  // syn 保证可见性
35.                 obj.notifyAll();
36.             }
37.         }
38.     }
40.     public static void main(String[] args) {
41.         // t1线程，如果当前状态是1，就打印a，下一个线程的状态是2
42.         new Thread(() -> {
43.             print(1, 2, "a");
44.         }, "t1").start();
45.         // t2线程，如果当前状态是2，就打印b，下一个线程的状态是3
46.         new Thread(() -> {
47.             print(2, 3, "b");
48.         }, "t2").start();
49.         // t3线程，如果当前状态是3，就打印c，下一个线程的状态是1
50.         new Thread(() -> {
51.             print(3, 1, "c");
52.         }, "t3").start();
53.     }
54. }

复制代码

交替打印变式

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

思路一：wait - notify

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

1. @Slf4j
2. public class AlternatePrint {
3.     // 初始状态为1
4.     private static int state = 1;
5.     private static int loopNumber = 5;
7.     private static Object obj = new Object();
9.     public static void print(int waitState, int nextState, String str) {
10.         for (int i = 0; i < loopNumber; i++) {
11.             synchronized (obj) {
12.                 // 当前获得锁的线程状态不是 state，等待释放锁
13.                 while(state != waitState) {
14.                     try {
15.                         obj.wait();
16.                     } catch (InterruptedException e) {
17.                         e.printStackTrace();
18.                     }
19.                 }
20.                 // 当前获得锁的线程状态就是 state，打印要打印的字符串
21.                 log.debug(str);
22.                 // 打印完，轮到下一个线程打印了，把状态改成 nextState，确保下一次打印的线程的状态一定是 nextState
23.                 state = nextState;  // syn 保证可见性
24.                 obj.notifyAll();
25.             }
26.         }
27.     }
29.     public static void main(String[] args) {
30.         // t1线程，如果当前状态是1，就打印a，下一个线程的状态是2
31.         new Thread(() -> {
32.             print(1, 2, "a");
33.         }, "t1").start();
34.         // t2线程，如果当前状态是2，就打印b，下一个线程的状态是3
35.         new Thread(() -> {
36.             print(2, 3, "b");
37.         }, "t2").start();
38.         // t3线程，如果当前状态是3，就打印c，下一个线程的状态是1
39.         new Thread(() -> {
40.             print(3, 1, "c");
41.         }, "t3").start();
42.     }
43. }

复制代码

思路二：Lock条件变量

使用 ReentrantLock中的条件变量 Condition 实现等待唤醒机制，每次只会有一个线程在打印，而其他两个线程在各自的休息室等待（可以把创建出来的Condition 对象 理解成线程休息室）；
刚开始运行时，三个线程都会在各自的休息室等待，所以这个时候需要有一个发起者，就让主线程发起，唤醒a休息室中等待的线程 t1；

1. @Slf4j
2. public class AlternatePrint1 extends ReentrantLock {
4.     private int loopNumber;     // 循环次数
6.     public AlternatePrint1(int loopNumber) {
7.         this.loopNumber = loopNumber;
8.     }
10.     /**
11.      * @param cur  进入哪一件休息室等待
12.      * @param next        cur休息室的线程打印完后，要唤醒下一个休息室中等待的线程
13.      * @param str        要打印的字符串
14.      */
15.     public void print(Condition cur, Condition next, String str) {
16.         for (int i = 0; i < loopNumber; i++) {
17.             this.lock();
18.             try {
19.                 cur.await();    // 每个线程获取锁进来，直接去各自的休息室等待
20.                 log.debug(str);
21.                 next.signal();  // 唤醒下一间休息室的线程
22.             } catch (InterruptedException e) {
23.                 e.printStackTrace();
24.             } finally {
25.                 this.unlock();
26.             }
27.         }
28.     }
30.     public static void main(String[] args) throws InterruptedException {
31.         // 创建对象，设置打印次数为5
32.         AlternatePrint1 ap = new AlternatePrint1(5);
33.         // 为三个线程分别创建三个休息室
34.         Condition a = ap.newCondition();
35.         Condition b = ap.newCondition();
36.         Condition c = ap.newCondition();
38.         new Thread(() -> {
39.             ap.print(a, b, "a");
40.         }, "t1").start();
42.         new Thread(() -> {
43.             ap.print(b, c, "b");
44.         }, "t2").start();
46.         new Thread(() -> {
47.             ap.print(c, a, "c");
48.         }, "t3").start();
50.         // 以上三个线程都去各自的休息室等待去了，1s之后，主线程唤醒a休息室中的线程
51.         TimeUnit.SECONDS.sleep(1L);
52.         try {
53.             ap.lock();
54.             // 让主线程先唤醒在a休息室中等待的线程
55.             a.signal();
56.         } finally {
57.             ap.unlock();
58.         }
59.     }
60. }

复制代码

TODO


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！