public static class Stack {
private final LinkedList<Integer> queue = new LinkedList<>();
public synchronized Integer pop() throws InterruptedException {
if (queue.size() <= 0) {
wait();
}
return queue.removeLast();
}
public synchronized void push(Integer integer) {
queue.addFirst(integer);
notify();
}
}
面试题..题目说这个栈在多线程中可能出现问题,请指出出现问题的情景...我想了半天也没想出来什么情景下回出问题,还请指教..
谢谢
1
Jooooooooo 2020-08-29 17:38:30 +08:00
pop 和 push 是可以并发的啊
线程 1 判断 if(queue.size() <= 0), 成功 线程 2 执行 push 并且 notify 线程 1 执行 wait |
2
Newyorkcity OP @Jooooooooo 额?你是说限制得过分了?
|
3
Jooooooooo 2020-08-29 18:34:26 +08:00
@Newyorkcity 线程 1 执行 wait 之后程序就死在那了
|
4
Newyorkcity OP @Jooooooooo 线程 1 判断 if(queue.size() <= 0) 成功,此时还没有执行 wait,线程 1 持有锁,线程 2 无法执行 push 方法的吧?
|
5
Jooooooooo 2020-08-29 19:05:07 +08:00
@Newyorkcity 记错了
这个我想了一下, 应该是 synchronized 只能作用在 stack 上而无法作用在 queue 上, 导致 queue 内部的行为无法遵守 happen before 原则. |
6
iseki 2020-08-29 19:19:46 +08:00 via Android
不是吧…synchronized 是锁 this 的我如果没记错,那么从并发安全上看应该没问题?
|
7
iseki 2020-08-29 19:20:04 +08:00 via Android
|
8
jimages 2020-08-29 19:28:20 +08:00 via iPhone
死锁,当 size 为 0 的时候,在里面 wait,但是此时已经拿了锁了。push 没有拿到锁,无法 push 。所以一个已经持有锁的线程在 wait,没有持有锁的线程想 push 得等锁,形成死锁。
|
9
Newyorkcity OP @jimages 额。。。wait 函数一旦执行,线程转入等待状态并会释放由于 synchronized 拿到的对象锁,所以生产者线程有机会生产出产品的吧。。
|
10
jimages 2020-08-29 19:43:40 +08:00 via iPhone
@Newyorkcity 哦哦哦,我看错了😂。那应该是两个 pop 线程一个 push 线程的问题,就比如一个在 wait 被卡住,一个在访问 pop 的时候被卡住。如果比如现在 push 了一个,然后 notify 。现在有两个线程需要锁,一个是 wait 那需要一个锁,一个是新进入的 pop 需要锁,假如是新来的那个 pop 拿到了锁,pop 出最后一个元素。然后是 wait 那个线程拿到元素。由于是 if 不是一个 while 判断。所以此时 pop 出一个,但此时 queue 已经没有元素了。
|
11
LinJunzhu 2020-08-29 19:55:52 +08:00 1
@jimages synchronized 的 monitor 中,线程 A 调用 notify() 后,默认策略是从 WaitSet 队列内拿出被堵塞的线程,插入 EntrySet 队列头,随后线程 A 执行完毕,便会去 EntrySet 拿出堵塞的线程来唤醒执行,所以不存在你说的被 [新来的 pop 线程] 拿到了锁
|
12
MoHen9 2020-08-29 21:15:39 +08:00 via Android
可能是执行效率低吧,你这是实现了个阻塞队列,面试官可能认为直接使用阻塞队列会更好。
|
13
leafre 2020-08-29 21:41:25 +08:00
我觉得没问题,有大佬找出问题 @我下
|
14
LinJunzhu 2020-08-30 00:57:13 +08:00 1
重新看了下 Monitor 的源码,更正一下,是会存在 @jimages 所说的, 当持有锁的线程 A(push 方法)调用 notify()后 并退出同步代码块时,会释放持有的锁,此时唤醒的堵塞线程 B (在 wait() 处的线程)重新争抢锁,是有可能会被新来的线程 C 调用 pop() 抢到锁的,此时 C 执行完毕后,锁释放,若恰好轮到线程 B 获得了锁,此时队列已经空了,不满足条件,执行则会报错,因此应该修改为:
while (queue.size() <= 0) { wait(); } 在该处进行死循环判断。 |
15
776491381 2020-08-30 09:56:54 +08:00 via Android
使用 notifyAll,不要使用 notify,可能会陷入死锁,具体可以自己分析一下多线程调用流程以及 notify 原理
|
16
776491381 2020-08-30 09:57:27 +08:00 via Android
同时需要使用 while 循环判断
|
17
Newyorkcity OP @776491381 额..就是想过了没想出所以然来....请具体说说?
|
18
falsemask 2020-08-30 11:30:39 +08:00 1
线程会被虚假唤醒,if 要改成 while
|