面試手撕并發演算法題
固定列印順序
使用 wait-notify 實作以下功能：先列印 b，再列印 a
思路一
執行緒t1和t2同時運行，t1中列印 a，t2中列印 b，但 t1 列印得有個前提，就是 t1要在t2運行完釋放鎖了才能列印 a，如果t1先得到鎖，但t2沒有執行，還是得釋放鎖，讓t2得到鎖先列印b，t2執行完，喚醒t1再列印a，實作固定順序列印，
@Slf4j
public 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();
}
}
思路二
思路一有以下幾個問題需要注意：
- 需要保證先 wait 再 notify，否則 wait 執行緒永遠得不到喚醒，因此使用了『運行標記』來判斷該不該 wait；
- 如果有些干擾執行緒錯誤地 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 加鎖，
@Slf4j
public 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機制來處理條件不滿足時等待釋放鎖，滿足時列印并喚醒所有處于等待的執行緒；
@Slf4j
public 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 < loopNumber; i++) {
synchronized (obj) {
// 當前獲得鎖的執行緒狀態不是 state，等待釋放鎖
while(state != waitState) {
try {
obj.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
// 當前獲得鎖的執行緒狀態就是 state，列印要列印的字串
log.debug(str);
// 列印完，輪到下一個執行緒列印了，把狀態改成 nextState，確保下一次列印的執行緒的狀態一定是 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();
}
}
思路二：Lock條件變數
使用 ReentrantLock中的條件變數 Condition 實作等待喚醒機制，每次只會有一個執行緒在列印，而其他兩個執行緒在各自的休息室等待（可以把創建出來的Condition 物件 理解成執行緒休息室）；
剛開始運行時，三個執行緒都會在各自的休息室等待，所以這個時候需要有一個發起者，就讓主執行緒發起，喚醒a休息室中等待的執行緒 t1；
@Slf4j
public class AlternatePrint1 extends ReentrantLock {
private int loopNumber; // 回圈次數
public AlternatePrint1(int loopNumber) {
this.loopNumber = loopNumber;
}
/**
* @param cur 進入哪一件休息室等待
* @param next cur休息室的執行緒列印完后，要喚醒下一個休息室中等待的執行緒
* @param str 要列印的字串
*/
public void print(Condition cur, Condition next, String str) {
for (int i = 0; i < loopNumber; i++) {
this.lock();
try {
cur.await(); // 每個執行緒獲取鎖進來，直接去各自的休息室等待
log.debug(str);
next.signal(); // 喚醒下一間休息室的執行緒
} catch (InterruptedException e) {
e.printStackTrace();
} finally {
this.unlock();
}
}
}
public static void main(String[] args) throws InterruptedException {
// 創建物件，設定列印次數為5
AlternatePrint1 ap = new AlternatePrint1(5);
// 為三個執行緒分別創建三個休息室
Condition a = ap.newCondition();
Condition b = ap.newCondition();
Condition c = ap.newCondition();
new Thread(() -> {
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
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/502563.html
標籤：其他
下一篇：Chapter 1