logo
Redian新闻
>未名空间
>Joke - 肚皮舞运动
>
红朝又一奇迹：钢筋混凝土桥靠木头支撑（图） (转载)
avatar
红朝又一奇迹：钢筋混凝土桥靠木头支撑（图） (转载)# Joke - 肚皮舞运动
p*o
1 楼
煮了顿饭，口感不错，比俺的旧锅强。
就是没看出来顶盖怎么洗。
另外这玩意儿能煮粥吗？
有经验的谈谈？
avatar
m*n
2 楼
原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
解供大家参考。
从Java的角度看这道题可以有三个考点：
对Java Synchronization and Concurrency的掌握
基本的Coding Style，要能扩展,不能写spaghetti code
有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
也行。
看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
。当然有人可能觉得这个考基本功非要你用那也没办法。
我的基本思路是：
- 用synchronousQueue去Block and release caller threads
- 用AtomicInterger计数
- Thread Synchronization下面再提。
- 扩展性通过把H和O抽象化来实现。
作concurrency的题要照顾到四点：
- 正确性的两点：有没有race，有没有deadlock
- 效率：有没有不必要的synchronization
- 公平：先来后到怎么处理。要求高的要FIFO，低的只要没有starvation就行。
这题最省事的就是加一个control thread。Caller和controller之间一个Semaphore就
够了，而且可以很好地照顾到公平。
如果不能有自己的Thread，那么中规中矩的办法就是用Lock。别的思路我也没有了。
下面贴几段Code。
第一段是helper，把计数和Thread Enqueue/Dequeue等等都包括了。因为要照顾下面最
复杂的解法，有的Code在其他地方可以去掉。
后面有三个例子：
- 用control thread
- 无extra thread用lock
- 无extra thread也不用lock。这个可以显示一下技能，但是没有什么实际意义。
后两个解法share一个bug，但是懒得改了：releaseAll()不应该简单地loop过去。对
caller自己的element应该挑出来最后call.而且releaseAll()在用Lock的解法里应该挪
到locked region之外。
avatar
d*w
3 楼
sfw的礼拜三，cvs的礼拜天。否则礼拜天到礼拜二cvs老是没有胖子。
avatar
a*g
4 楼
TSC EB2
PD: 03/2011
RD: 04/02/2015
FP: 04/27/2015
AD: 06/11/2015
没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
祝大家早绿！
PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
x*k
5 楼
Things at Home
August 16 (commentary)--It's always interesting to watch the camera race
from the local Japanese perspective. BCN publishes weekly information about
sales of cameras in Japan with interchangeable lenses and from time to time
summarizes them. Here's the first half of 2010 graphed versus the full 2009
year in terms of unit sales:
Yep. Nikon and Canon have switched places again in Japan. Canon's loses come
at the gains of Panasonic, Olympus, and Pentax. Sony also slid (this was
befor
avatar
w*p
6 楼
【 以下文字转载自 Military 讨论区 】
发信人: wokblack (书记), 信区: Military
标 题: 红朝又一奇迹：钢筋混凝土桥靠木头支撑（图）
发信站: BBS 未名空间站 (Fri Dec 7 02:03:39 2012, 美东)
大河网讯（记者 肖宏伟 通讯员 吴彦飞 李凯）12月6日中午12时23分，新浪微博博友
“@自由人重生”发布内容为：“信阳罗山县一座公路桥，以前桥墩一直被河水淹没。
现在河流干涸奇迹也就出现了：钢筋混凝土制的公路桥，竟然靠木头支撑”的微博，他
在微博中强调，该图没有经过任何处理。
随后，记者联系到了罗山县公路局，该局工作人员称刚从记者口中得知此事，会尽快调
查此事。截止到记者发稿时，该微博已经被转发401次 、评论124次。
——————————————
网易论坛：因为尚未垮掉，或至少没有“被超载”垮桥，这新闻和图片确实看起来有点
喜剧色彩，网民或许是看多了、或许是早已经麻木到无可奈何，愤怒之后多有调侃，好
多人都在寻问打探这牛B兮兮的木头到底是哪里出产的？长期泡在水里并经受着一天到
晚来往车...
avatar
x*u
7 楼
我昨天煮了一下，貌似要加好多水才能煮成粥
avatar
m*n
8 楼

public class ElementsImpl implements IElements {

private final int batchSize;
private final AtomicInteger counter = new AtomicInteger();

ElementsImpl(int i) {
batchSize = i;
}

public int getBatchSize() {
return batchSize;
}
@Override
public void inc() {
counter.incrementAndGet();
}
@Override
public boolean reserve() {
int val = counter.get();
return val >= batchSize && counter.compareAndSet(val, val -
batchSize);
}
@Override
public void cancel() {
counter.addAndGet(batchSize);
}
@Override
public void releaseQueued(SynchronousQueue queue,
boolean coversSelf) {
for (int i = 0; i < (!coversSelf? batchSize : batchSize - 1); i+
+) {
try {
queue.take();
} catch (InterruptedException ie) {
// Bug!
}
}
if (!coversSelf) {
return;
}
// Starvation prevention: should I wait or go?
if (queue.poll() != null) {
this.enqueue(queue);
}
// Otherwise I'm the last one and should go.
}
@Override
public void enqueue(SynchronousQueue queue) {
queue.offer(this);
}


}

public static enum WaterElements {
H(2), O(1);

private final IElements ele;
private WaterElements(int atomCount) {
this.ele = new ElementsImpl(atomCount);
}

public void inc() {
ele.inc();
}
public boolean reserve() {
return ele.reserve();
}
public void cancel() {
ele.cancel();
}
public void releaseQueued(WaterElements caller) {
ele.releaseQueued(waitQueue, caller == this);
}
public void enqueue() {
ele.enqueue(waitQueue);
}

private static final SynchronousQueue waitQueue =
new SynchronousQueue(true);

public static final int totalAtomsPerMolecule;

static {
int sum = 0;
for (WaterElements we : WaterElements.values()) {
sum += we.ele.getBatchSize();
}
totalAtomsPerMolecule = sum;
}

public static WaterElements reserveAll() {
for (WaterElements we : WaterElements.values()) {
if (!we.reserve()) return we;
}
return null;
}

public static void releaseAll(WaterElements caller) {
for (WaterElements we : WaterElements.values()) {
we.releaseQueued(caller); }
}

public static void cancelAll(WaterElements reserveFailure) {
WaterElements[] values = WaterElements.values();
for (int i = reserveFailure.ordinal() - 1; i >= 0; i--) {
values[i].cancel();
}
}
}
avatar
l*a
9 楼
nod，它两家老别着出

【在 d**w 的大作中提到】
: sfw的礼拜三，cvs的礼拜天。否则礼拜天到礼拜二cvs老是没有胖子。
avatar
m*d
10 楼
cong
avatar
x*c
11 楼
从没见过这么烂的图。

about
time
2009
come

【在 x***k 的大作中提到】
: Things at Home
: August 16 (commentary)--It's always interesting to watch the camera race
: from the local Japanese perspective. BCN publishes weekly information about
: sales of cameras in Japan with interchangeable lenses and from time to time
: summarizes them. Here's the first half of 2010 graphed versus the full 2009
: year in terms of unit sales:
: Yep. Nikon and Canon have switched places again in Japan. Canon's loses come
: at the gains of Panasonic, Olympus, and Pentax. Sony also slid (this was
: befor
avatar
r*e
12 楼
这木头太结识了,什么材料?

【在 w*p 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: wokblack (书记), 信区: Military
: 标 题: 红朝又一奇迹：钢筋混凝土桥靠木头支撑（图）
: 发信站: BBS 未名空间站 (Fri Dec 7 02:03:39 2012, 美东)
: 大河网讯（记者 肖宏伟 通讯员 吴彦飞 李凯）12月6日中午12时23分，新浪微博博友
: “@自由人重生”发布内容为：“信阳罗山县一座公路桥，以前桥墩一直被河水淹没。
: 现在河流干涸奇迹也就出现了：钢筋混凝土制的公路桥，竟然靠木头支撑”的微博，他
: 在微博中强调，该图没有经过任何处理。
: 随后，记者联系到了罗山县公路局，该局工作人员称刚从记者口中得知此事，会尽快调
: 查此事。截止到记者发稿时，该微博已经被转发401次 、评论124次。
avatar
s*8
13 楼
煮粥么，当然要加好多水罗。
avatar
m*n
14 楼
package test;
import java.util.concurrent.Semaphore;
import test.IElements.WaterElements;
public class H2OExtraThread {
private final Semaphore sema = new Semaphore(0);

private volatile boolean isRunning = true;

// Called by the control thread
private void controllerRun() {

while (isRunning) {
try {
sema.acquire(WaterElements.totalAtomsPerMolecule);
} catch (InterruptedException e) {
continue;
}
WaterElements failedAt = WaterElements.reserveAll();

if (failedAt == null) {
// Success
WaterElements.releaseAll(null);
} else {
WaterElements.cancelAll(failedAt);
sema.release(WaterElements.totalAtomsPerMolecule);
}
}

}
// Invoked by external caller.
public void addO() {
WaterElements.O.inc();
sema.release(1);
WaterElements.O.enqueue();
}

// Invoked by external caller
public void addH() {
WaterElements.H.inc();
sema.release(1);
WaterElements.H.enqueue();
}
}
avatar
g*n
15 楼
哈哈，他们故意的吧

【在 d**w 的大作中提到】
: sfw的礼拜三，cvs的礼拜天。否则礼拜天到礼拜二cvs老是没有胖子。
avatar
n*g
16 楼
Pai. Gxgx
avatar
c*y
17 楼
你要把那图当3D看，最好戴上3D眼镜。。。

【在 x****c 的大作中提到】
: 从没见过这么烂的图。
:
: about
: time
: 2009
: come
avatar
k*r
18 楼
水版这个帖子有专家解答了，很正常，属于外行看不懂。
avatar
b*t
19 楼
我不喜欢那种盖子，宁愿用一般透明盖
avatar
m*n
20 楼
package test;
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import test.IElements.WaterElements;
public class H2OWithLock {

private Lock lock = new ReentrantLock();

public void addO() {
WaterElements.O.inc();
checkMolecule(WaterElements.O);
}

private void checkMolecule(WaterElements we) {
lock.lock();
boolean shouldBlock = false;
try {
WaterElements failedAt = WaterElements.reserveAll();

if (failedAt == null) {
WaterElements.releaseAll(we);
} else {
WaterElements.cancelAll(failedAt);
shouldBlock = true;
}
} finally {
lock.unlock();
}
if (shouldBlock) {
we.enqueue();
}
}
}
avatar
b*9
21 楼
啥意思
北加sfw是周日到周六的循环？
avatar
E*a
22 楼
cong
avatar
x*c
23 楼
bso家里有3D电视当显示屏

【在 c********y 的大作中提到】
: 你要把那图当3D看，最好戴上3D眼镜。。。
avatar
c*k
24 楼
贴主可不是外行，哈哈。

【在 k***r 的大作中提到】
: 水版这个帖子有专家解答了，很正常，属于外行看不懂。
avatar
t*e
25 楼
这种锅很少有透明的盖子吧

【在 b****t 的大作中提到】
: 我不喜欢那种盖子，宁愿用一般透明盖
avatar
m*n
26 楼
package test;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import test.IElements.WaterElements;
public class H2OLockFree {
private final AtomicLong sequencer = new AtomicLong();
private final AtomicInteger contention = new AtomicInteger();
public void addO() {
addElements(WaterElements.O);
}

private void addElements(WaterElements ele) {
long id = sequencer.incrementAndGet();
contention.incrementAndGet();
ele.inc();
while (true) {
WaterElements failure = null;
next_ele:
for (WaterElements e : WaterElements.values()) {
while (id == sequencer.get() && contention.get() > 1) {
if (e.reserve()) continue next_ele;
try { Thread.sleep(1); } catch (Exception err) {}
}
failure = e;
break;
}

if (failure == null) {
// Success
WaterElements.releaseAll(ele);
contention.decrementAndGet();
} else {
// Failure
WaterElements.cancelAll(failure);
contention.decrementAndGet();
ele.enqueue();
}
}
}

}
avatar
l*a
27 楼
sfw 周三到周二cycle，但是每次报纸里广告周日出
cvs 周日到周六cycle，但是每次报纸里coupon周三出

【在 b*******9 的大作中提到】
: 啥意思
: 北加sfw是周日到周六的循环？
avatar
n*h
28 楼
gxgx！！！
avatar
c*y
29 楼
我怎么可能有

【在 x****c 的大作中提到】
: bso家里有3D电视当显示屏
avatar
a*5
30 楼
而且还是民国的桥

【在 k***r 的大作中提到】
: 水版这个帖子有专家解答了，很正常，属于外行看不懂。
avatar
c*t
31 楼
多谢！这么好的帖子，先mark后看。

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
p*e
32 楼
RD 2015年4月！
哇，cong!
avatar
G*U
33 楼
真要靠木头支撑上面灌水泥墩难度比正常造桥要大太多了。
这是水把底下的泥土砂石洗掉了。
想不这样就得维护桥墩。要不然大峡谷怎么形成的？

【在 w*p 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: wokblack (书记), 信区: Military
: 标 题: 红朝又一奇迹：钢筋混凝土桥靠木头支撑（图）
: 发信站: BBS 未名空间站 (Fri Dec 7 02:03:39 2012, 美东)
: 大河网讯（记者 肖宏伟 通讯员 吴彦飞 李凯）12月6日中午12时23分，新浪微博博友
: “@自由人重生”发布内容为：“信阳罗山县一座公路桥，以前桥墩一直被河水淹没。
: 现在河流干涸奇迹也就出现了：钢筋混凝土制的公路桥，竟然靠木头支撑”的微博，他
: 在微博中强调，该图没有经过任何处理。
: 随后，记者联系到了罗山县公路局，该局工作人员称刚从记者口中得知此事，会尽快调
: 查此事。截止到记者发稿时，该微博已经被转发401次 、评论124次。
avatar
f*t
34 楼
这个要认真看
avatar
x*u
35 楼
cong!zhan!

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
G*U
36 楼
真要靠木头支撑上面灌水泥墩难度比正常造桥要大太多了。
这是水把底下的泥土砂石洗掉了。
想不这样就得维护桥墩。要不然大峡谷怎么形成的？

【在 w*p 的大作中提到】
: 【 以下文字转载自 Military 讨论区 】
: 发信人: wokblack (书记), 信区: Military
: 标 题: 红朝又一奇迹：钢筋混凝土桥靠木头支撑（图）
: 发信站: BBS 未名空间站 (Fri Dec 7 02:03:39 2012, 美东)
: 大河网讯（记者 肖宏伟 通讯员 吴彦飞 李凯）12月6日中午12时23分，新浪微博博友
: “@自由人重生”发布内容为：“信阳罗山县一座公路桥，以前桥墩一直被河水淹没。
: 现在河流干涸奇迹也就出现了：钢筋混凝土制的公路桥，竟然靠木头支撑”的微博，他
: 在微博中强调，该图没有经过任何处理。
: 随后，记者联系到了罗山县公路局，该局工作人员称刚从记者口中得知此事，会尽快调
: 查此事。截止到记者发稿时，该微博已经被转发401次 、评论124次。
avatar
c*t
37 楼
lz能否把IElements interface的codes也发一下。

【在 m*****n 的大作中提到】
: package test;
: import java.util.concurrent.atomic.AtomicInteger;
: import java.util.concurrent.atomic.AtomicLong;
: import test.IElements.WaterElements;
: public class H2OLockFree {
: private final AtomicLong sequencer = new AtomicLong();
: private final AtomicInteger contention = new AtomicInteger();
: public void addO() {
: addElements(WaterElements.O);
: }
avatar
n*h
38 楼
gxgx！！！
avatar
l*k
39 楼
外行只看谁造的。

【在 k***r 的大作中提到】
: 水版这个帖子有专家解答了，很正常，属于外行看不懂。
avatar
c*t
40 楼
在无extra thread的情况下，我也觉得应该可以只用atomicInteger的。可是我写不出
，只写出用lock condition的。
能不能说说，你为什么说这题“理论上”只用AtomicInteger也行？

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
s*c
41 楼
gx
avatar
l*k
42 楼
造桥的这个比民国更牛更普世，再想想

【在 a****5 的大作中提到】
: 而且还是民国的桥
avatar
w*p
43 楼
收藏。等以后看。
avatar
v*6
44 楼
cong!
avatar
c*k
45 楼
发信人: Grace09 (Frank), 信区: WaterWorld
标 题: Re: 河干了，吓死你个小样的 ：）
发信站: BBS 未名空间站 (Thu Dec 6 21:05:43 2012, 美东)
呵呵，让我这个桥梁科班出身的来科普一下吧。这个东西叫做磨擦桩。一般来说墩台基
础应该建立在基岩之上，但是并不是在任何地质条件下，你都能找到基岩，特别是在沉
积层（土层）比较厚的情况下。这个时候，唯一的办法就是打密集的小桩子楔入土层，
靠桩壁的磨擦产生承载力。在江苏很多地方的土木建筑物，都是靠磨擦桩的方法建造的
。当然了，在施工成本够的情况下，优先考虑的是混凝土的磨擦桩了。
木质结构不是不可以，取决于木质。这个桥的结构还算可以，设计承载不高。估计设计
年限也不是考虑了很长，才采取木质磨擦桩的。没什么值得大惊小怪的。而且相信当年
的河床可能比现在要高，所以，在施工过程中，采取了下挖，然后打桩，建造墩台的。
但是随着河水的冲刷，河床下降。这个桥的安全性倒是需要重新检测才能继续使用。特
别是，承载到底多少。
偶们当年学道桥的，基本上都是第一志愿没录上被淘汰到这个专业的。估计北美这边的
达人中，学这个出身的很少。所以大家才会惊奇。

【在 G******U 的大作中提到】
: 真要靠木头支撑上面灌水泥墩难度比正常造桥要大太多了。
: 这是水把底下的泥土砂石洗掉了。
: 想不这样就得维护桥墩。要不然大峡谷怎么形成的？
avatar
v*n
46 楼
好贴啊！
avatar
l*d
47 楼
Cong!
chi

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
R*a
48 楼
这个东西一说我就有印象了，当年十万个为什么里看到过

【在 c******k 的大作中提到】
: 发信人: Grace09 (Frank), 信区: WaterWorld
: 标 题: Re: 河干了，吓死你个小样的 ：）
: 发信站: BBS 未名空间站 (Thu Dec 6 21:05:43 2012, 美东)
: 呵呵，让我这个桥梁科班出身的来科普一下吧。这个东西叫做磨擦桩。一般来说墩台基
: 础应该建立在基岩之上，但是并不是在任何地质条件下，你都能找到基岩，特别是在沉
: 积层（土层）比较厚的情况下。这个时候，唯一的办法就是打密集的小桩子楔入土层，
: 靠桩壁的磨擦产生承载力。在江苏很多地方的土木建筑物，都是靠磨擦桩的方法建造的
: 。当然了，在施工成本够的情况下，优先考虑的是混凝土的磨擦桩了。
: 木质结构不是不可以，取决于木质。这个桥的结构还算可以，设计承载不高。估计设计
: 年限也不是考虑了很长，才采取木质磨擦桩的。没什么值得大惊小怪的。而且相信当年
avatar
F*n
49 楼
public class H2O {
public static class ThreadHolder {
Thread thread;
ThreadHolder(Thread thread) {
this.thread = thread;
}
}
protected LinkedList hlist = new LinkedList();
protected LinkedList olist = new LinkedList();
public boolean h() {
ThreadHolder current = new ThreadHolder(Thread.currentThread());
synchronized (current) {
ThreadHolder[] threadsToWakeUp = null;
// updating the queues requires a global lock;
synchronized (this) {
this.hlist.add(current);
threadsToWakeUp = this.getThreadsToWakeUp();
}
// now the wait and wake up is only in the current lock;
boolean notInterrupted = this
.checkWaitAndWakeUp(current, threadsToWakeUp);
if (notInterrupted) {
this.doH();
}
return notInterrupted;
}
}
private ThreadHolder[] getThreadsToWakeUp() {
if (this.hlist.size() >= 2 && this.olist.size() >= 1) {
ThreadHolder[] holders = new ThreadHolder[3];
holders[0] = this.hlist.poll();
holders[1] = this.hlist.poll();
holders[2] = this.olist.poll();
return holders;
}
return null;
}
// return true if the wait is not interrupted.
private boolean checkWaitAndWakeUp(ThreadHolder current,
ThreadHolder[] threadsToWakeUp) {
boolean wait = true;
if (threadsToWakeUp != null) {
for (ThreadHolder threadToWakeUp : threadsToWakeUp) {
if (threadToWakeUp == current) {
wait = false;
} else {
// this lock ensures notify will only happen after the
// thread wait;
synchronized (threadToWakeUp) {
threadToWakeUp.notifyAll();
}
}
}
}
if (wait) {
try {
current.wait();
} catch (InterruptedException e) {
return false;
}
}
return true;
}
// similiar to h();
public boolean o() {
ThreadHolder current = new ThreadHolder(Thread.currentThread());
synchronized (current) {
ThreadHolder[] threadsToWakeUp = null;
// updating the queues requires a global lock;
synchronized (this) {
this.olist.add(current);
threadsToWakeUp = this.getThreadsToWakeUp();
}
// now the wait and wake up is only in the current lock;
boolean notInterrupted = this
.checkWaitAndWakeUp(current, threadsToWakeUp);
if (notInterrupted) {
this.doO();
}
return notInterrupted;
}
}
// Override this to extend the business logic
protected void doH() {
// business logic;
}
// Override this to extend the business logic
protected void doO() {
// business logic
}
}

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
D*7
50 楼
GXGX!!!
avatar
N*m
51 楼
当年学桥梁的同学，现在都富得流油
30年河东啊

【在 c******k 的大作中提到】
: 发信人: Grace09 (Frank), 信区: WaterWorld
: 标 题: Re: 河干了，吓死你个小样的 ：）
: 发信站: BBS 未名空间站 (Thu Dec 6 21:05:43 2012, 美东)
: 呵呵，让我这个桥梁科班出身的来科普一下吧。这个东西叫做磨擦桩。一般来说墩台基
: 础应该建立在基岩之上，但是并不是在任何地质条件下，你都能找到基岩，特别是在沉
: 积层（土层）比较厚的情况下。这个时候，唯一的办法就是打密集的小桩子楔入土层，
: 靠桩壁的磨擦产生承载力。在江苏很多地方的土木建筑物，都是靠磨擦桩的方法建造的
: 。当然了，在施工成本够的情况下，优先考虑的是混凝土的磨擦桩了。
: 木质结构不是不可以，取决于木质。这个桥的结构还算可以，设计承载不高。估计设计
: 年限也不是考虑了很长，才采取木质磨擦桩的。没什么值得大惊小怪的。而且相信当年
avatar
m*n
52 楼
纯Busy wait不主动yield, progress 不容易把握。

【在 c********t 的大作中提到】
: 在无extra thread的情况下，我也觉得应该可以只用atomicInteger的。可是我写不出
: ，只写出用lock condition的。
: 能不能说说，你为什么说这题“理论上”只用AtomicInteger也行？
:
: AtomicInteger
: date
avatar
z*3
53 楼


【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
a*5
54 楼
知道是谁，但说是民国时的桥没错

【在 l**k 的大作中提到】
: 造桥的这个比民国更牛更普世，再想想
avatar
f*d
55 楼
如果允许我大展身手的话。我会用EIP Aggregator pattern
http://www.eaipatterns.com/Aggregator.html
如果要考我java，我就用 new concurrent package, 简单明了
public class H2O {
private BlockingQueue hq = Queues.newArrayBlockingQueue();
private BlockingQueue oq = Queues.newArrayBlockingQueue();
public H2O H() {
CountDownLatch latch = new CountDownLatch(1);
hq.add(latch);
latch.await();
return this;
}
public H2O O() {
CountDownLatch latch = new CountDownLatch(1);
oq.add(latch);
latch.await();
return this;
}
public H2O() {
Executors.newSingleThreadPool().execute(new Runnable() {
void run() {
while(true) {
CountDownLatch o = oq.take();
CountDownLatch h1 =hq.take();
hq.take().countDown();
h1.countDown();
o.countDown();
}
}
}
}
}
avatar
d*6
56 楼
祝贺！

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
H*g
57 楼
军版回帖很精彩
avatar
f*d
58 楼
没有额外thread的版本
public class H2O {
private BlockingQueue hq = Queues.newArrayBlockingQueue();
public H2O H() {
CountDownLatch latch = new CountDownLatch(1);
hq.add(latch);
latch.await();
return this;
}
public H2O O() {
// this while is to make sure there is no such case where
// one O got one H and then being prempted, another O got the new H
// above situation will result 2O and 2H produces no H2O
while(true) {
CountDownLatch first = hq.take();
CountDownLatch second = hq.poll();
if (second == null) {
hq.add(first);
continue;
}
first.countDown();
second.countDown();
return this;
}
}
}
avatar
m*y
59 楼
congrats.

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
e*o
60 楼
威尼斯的房子全部是建在木桩上的
http://www.ask.com/answers/95379681/how-was-venice-constructed
Venice was constructed out of wooden piles, with the wood imported from the
mainland. Wood doesn't decay under water, so they placed wood piles under
the water, embedding them into the soft layers of sand and mud, deep enough
that they reached the harder layers of clay. The foundations of the
buildings are then built on the wood piles. For more information see here: http://en.wikipedia.org/wiki/Venice
avatar
f*d
61 楼
in a concurrent implementation, Thread.sleep is always a big NONO

【在 m*****n 的大作中提到】
: package test;
: import java.util.concurrent.atomic.AtomicInteger;
: import java.util.concurrent.atomic.AtomicLong;
: import test.IElements.WaterElements;
: public class H2OLockFree {
: private final AtomicLong sequencer = new AtomicLong();
: private final AtomicInteger contention = new AtomicInteger();
: public void addO() {
: addElements(WaterElements.O);
: }
avatar
j*0
62 楼
恭喜恭喜！
avatar
f*y
63 楼
你的意思是常凯申丧土失地其实是为了让日本人免费给我们搞国家基建？

【在 a****5 的大作中提到】
: 知道是谁，但说是民国时的桥没错
avatar
P*1
65 楼
PAI
avatar
a*5
66 楼
你这个逻辑很强大
仔细想想，似乎还有两分道理

【在 f****y 的大作中提到】
: 你的意思是常凯申丧土失地其实是为了让日本人免费给我们搞国家基建？
avatar
f*d
67 楼
这种题还有比较重要的是unit test，怎么在unit test模拟multi threading 的多种可
能出现的情况。
怎么assert
avatar
m*1
68 楼
congrats!
avatar
f*y
69 楼
哪里哪里，我就是顺着你的言语揣测一下

【在 a****5 的大作中提到】
: 你这个逻辑很强大
: 仔细想想，似乎还有两分道理
avatar
F*n
70 楼
你的都不对，
LZ的把简单问题复杂化了
要用java.util.concurrent这题其实很简单
一个ReentrantLock 两个Condition就行了

);

【在 f********d 的大作中提到】
: 没有额外thread的版本
: public class H2O {
: private BlockingQueue hq = Queues.newArrayBlockingQueue();
: public H2O H() {
: CountDownLatch latch = new CountDownLatch(1);
: hq.add(latch);
: latch.await();
: return this;
: }
: public H2O O() {
avatar
y*0
71 楼
cong! EB3吧？
avatar
d*r
72 楼
溜出去容易
得有本事拿回来啊

【在 a****5 的大作中提到】
: 你这个逻辑很强大
: 仔细想想，似乎还有两分道理
avatar
f*d
73 楼
I've passed the unit tests pretty well in different scenarios.
of course you can use ReentrantLock and 2 Conditions. And you need one more
thing which is the CyclicBarrier for the H(2)
Problem came when you implement.
When O came, you normally will signal the Condition for O. but what if there
's no H came before or only one came?
Now you need to await on H's condition.
Now you meet a pretty weird situation of signal first or await first.
normally the strategy to solve is using while(true) and keep trying to avoid
deadlocks.
That's fine the code can work. but can you think of any better way of
handling this and how can it be extended in the future?
First thing come into mind is, why I need that while(true)? because I dont
know whether the other side is waiting by Condition interface. What about
introduce one?
alright, now since you need a collection, what about a concurrent one to
help? BlockingQueue came into the door.
Now i still need condition to do await. now you could do lock and new
condition and await. but the question is, is there any class can do this job
much easier?
That's where the CountDownLatch kicks in.
okay, now back to the extensible question? what if you have C2H4O2? then you
code is pretty messy. using the first approach i gave.
in the process method, The runnable is actually describing how H2O or C2H4O2
. and you could make it better as a DSL and encapsulate and abstract to
Element and ElementDefintion.
in that way, you can loop thru all the ElementDefitions(a formula). now the
constructor can take a DSL of ElementDefinition.
Now to this point, it becomes a trival version of Aggregator in Camel or
Spring integration. now what's left over?
of course, Exception handlings.
There will be more considierations on that front, but this is also a test to
see how sophisticated the interviewee is.
btw, I used the same questioin in my interviews. very few people can go this
far.
avatar
c*d
74 楼
恭喜恭喜！
avatar
a*5
75 楼
这不早拿回来了嘛
不但分文没少，还有人背锅
常校长真是古今战略第一人

【在 d******r 的大作中提到】
: 溜出去容易
: 得有本事拿回来啊
avatar
f*d
76 楼
while(true) {
CountDownLatch o = oq.take(); // take an O
CountDownLatch h1 =hq.take(); // take an H
hq.take().countDown(); // take another H
h1.countDown(); // count down all the rest
o.countDown();
}
any new formula, you only need to make sure the first 3 lines reflects your
formula well. it becomes very extensible. and you can also do
Collection list = Lists.newArrayList();
for (ElementDefinition ed : defs) {
BlockingQueue queue = ed.getQueue();
for (int i =0; i < ed.getNumber() ; i++) {
list.add(queue.take());
}
}
for (CountDownLAtch latch : list) {
latch.countDown();
}
with DSL, you could
val H2 = new ElementDefinition(2);
val O = new ElementDefinition(1);
defs.add(H2);
defs.add(O);
void H() {
H2.await();
}
class ElementDefinition {
....
public void await() {
CountDownLatch latch = new CountDownLatch(1);
queue.add(latch);
latch.await();
}
....
}
this is synchronized implementaiton. you can also have interface Element to
replace CountDownLAtch.
for synchronized implementation, use ElementSychImpl with CountDownLatch.
for asycn, get a call back.
Now the codes will be quite extensible and easier to understand

more
there
avoid

【在 f********d 的大作中提到】
: I've passed the unit tests pretty well in different scenarios.
: of course you can use ReentrantLock and 2 Conditions. And you need one more
: thing which is the CyclicBarrier for the H(2)
: Problem came when you implement.
: When O came, you normally will signal the Condition for O. but what if there
: 's no H came before or only one came?
: Now you need to await on H's condition.
: Now you meet a pretty weird situation of signal first or await first.
: normally the strategy to solve is using while(true) and keep trying to avoid
: deadlocks.
avatar
c*d
77 楼
这个似乎是EB2吧，跟我的差不多情况啊
avatar
i*6
78 楼
My 5 cents:
import java.util.concurrent.*;
class MyO implements Runnable{
int index;
CountDownLatch lock;
public MyO (int index, CountDownLatch lock) {
this.index = index;
this.lock = lock;
}
public void run() {
try {
Thread.sleep((long) (Math.random() * 1000));
lock.await();
System.out.println("Take O:" + index + " to form an H2O!");
} catch (Exception e) {
e.printStackTrace();
}
}
}
class MyH implements Runnable{
int index;
CountDownLatch lock;
public MyH(int index, CountDownLatch lock) {
this.index = index;
this.lock = lock;
}
public void run() {
try {
hread.sleep((long) (Math.random() * 1000));
lock.await();
System.out.println("take H:"+index+" to form a H2O!");
} catch(Exception e) {
e.printStackTrace();
}
}
}
public class MyH2O {
private static BlockingQueue hq = new
LinkedBlockingQueue();
private static BlockingQueue oq = new
LinkedBlockingQueue();
public static void main(String args[]){
ExecutorService service = Executors.newCachedThreadPool();
service.submit(new Thread() {
public void run(){
try{
while (true) {
Thread.sleep((long) (Math.random() * 1000));
CountDownLatch firstH = hq.take();
CountDownLatch secondH = hq.poll();
CountDownLatch firstO = oq.take();
if (secondH == null) {
hq.add(firstH);
continue;
}
firstH.countDown();
secondH.countDown();
firstO.countDown();
System.out.println("A H2O created!");
break;
}
} catch(Exception e) {
e.printStackTrace();
}
}
});
for (int i=0;i<100;i++) {
CountDownLatch lock = new CountDownLatch(1);
int type = (int)(Math.random()*2);
if (type == 0){
hq.add(lock);
service.submit(new MyH(i+1,lock));
} else {
oq.add(lock);
service.submit(new MyO(i+1,lock));
}
}
service.shutdown();
}
}
avatar
d*l
79 楼
恭喜，排包子发包子
avatar
n*r
80 楼
mark一下。。学习了
avatar
B*o
81 楼
Congrats!
TSC, 2 months
再次证明移民局所谓的FIFO是“胡说八道”。
早交早点拿EAD/AP。但不见得会早拿绿卡。相反可能会多交体检费。
avatar
m*n
82 楼
我对CountDownLatch没太多想过。学习了。

);
);

【在 f********d 的大作中提到】
: 如果允许我大展身手的话。我会用EIP Aggregator pattern
: http://www.eaipatterns.com/Aggregator.html
: 如果要考我java，我就用 new concurrent package, 简单明了
: public class H2O {
: private BlockingQueue hq = Queues.newArrayBlockingQueue();
: private BlockingQueue oq = Queues.newArrayBlockingQueue();
: public H2O H() {
: CountDownLatch latch = new CountDownLatch(1);
: hq.add(latch);
: latch.await();
avatar
f*r
83 楼
恭喜。 EB3四月不能交吧。 应该EB2吧

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
z*3
84 楼
原题：
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
我随手写了一个，不想用synchronized关键字
这个要搞起来的确比较麻烦，想上java.util.concurrent
研究了一下copyonwritearraylist，还是不行，两个方法都得上synchronized
List l = new ArrayList();
public synchronized void h(){
if(l.size()>=2){
Thread hThread = l.get(0);
Thread oThread = l.get(l.size()-1);
if(hThread.isH() && oThread.isO()){
hThread.notify();
oThread.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(0,currentThread);
currentThread.wait();
}
public synchronized void o(){
if(l.size()>=2){
Thread hThread1 = l.get(0);
Thread hThread2 = l.get(1);
if(hThread1.isH() && hThread2.isH()){
hThread1.notify();
hThread2.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(currentThread);
currentThread.wait();
}
avatar
j*a
85 楼
cong!

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
z*3
86 楼
isH()和isO()要扩展一下，要额外加一个类
包装thread对象以及该thread读取的是o还是h
要不然thread本身是没有这个方法的
class ThreadInfo{
private Thread thread;
private boolean isH;
//setter/getter method
...
}
然后把l里面保存的全部换成ThreadInfo对象
avatar
s*n
87 楼
排!
avatar
z*3
88 楼
或者找个map寄存
不过增加的map自然增加了查找的时间
效率上不如包装类
List l= new ArrayList();
Map m= new HashMap();
public synchronized void h(){
if(l.size()>=2){
Thread hThread = l.get(0);
Thread oThread = l.get(l.size()-1);
if(m.get(hThread) && !m.get(oThread)){
hThread.notify();
oThread.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(0,currentThread);
m.put(currentThead, true);
currentThread.wait();
}
public synchronized void o(){
if(l.size()>=2){
Thread hThread1 = l.get(0);
Thread hThread2 = l.get(1);
if(m.get(hThread1) && m.get(hThread2)){
hThread1.notify();
hThread2.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(currentThread);
m.put(currentThread, false);
currentThread.wait();
}
avatar
o*o
89 楼
恭喜~
avatar
z*3
90 楼
汗，实验了一下，有三个小问题，看来多线程白板还是难以bug free，需要多练习
getCurrentThread() -> currentThread()
currentThread.wait() -> wait()
hThread.notify() -> synchronized(hThread){ hThread.notify();}
avatar
a*1
91 楼
恭喜恭喜！pai
avatar
z*3
92 楼
List l = new ArrayList();

public synchronized void h() throws InterruptedException {
if (l.size() >= 2) {
ThreadInfo hThread = l.get(0);
ThreadInfo oThread = l.get(l.size() - 1);
if (hThread.isH() && oThread.isO()) {
synchronized(hThread){hThread.notify();}
synchronized(oThread){oThread.notify();}
l.remove(hThread);
l.remove(oThread);
return;
}
}
Thread currentThread = Thread.currentThread();
ThreadInfo ti = new ThreadInfo();
ti.setH(true);
ti.setT(currentThread);
l.add(0, ti);
wait();
}
public synchronized void o() throws InterruptedException {
if (l.size() >= 2) {
ThreadInfo hThread1 = l.get(0);
ThreadInfo hThread2 = l.get(1);
if (hThread1.isH() && hThread2.isH()) {
synchronized(hThread1){hThread1.notify();}
synchronized(hThread2){hThread2.notify();}
l.remove(hThread1);
l.remove(hThread2);
return;
}
}
Thread currentThread = Thread.currentThread();
ThreadInfo ti = new ThreadInfo();
ti.setH(false);
ti.setT(currentThread);
l.add(ti);
wait();
}
avatar
f*r
93 楼
恭喜 沾。 难道tsc就是传说的按照PD批？

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
F*n
94 楼
不太对，
你的wait没有notify
而且h()和o()都全部synchronized
只用synchronized的解法我前面写过。

【在 z*******3 的大作中提到】
: List l = new ArrayList();
:
: public synchronized void h() throws InterruptedException {
: if (l.size() >= 2) {
: ThreadInfo hThread = l.get(0);
: ThreadInfo oThread = l.get(l.size() - 1);
: if (hThread.isH() && oThread.isO()) {
: synchronized(hThread){hThread.notify();}
: synchronized(oThread){oThread.notify();}
: l.remove(hThread);
avatar
l*n
95 楼
cong
avatar
z*3
96 楼
行不行直接开几个thread跑一下不就知道了
notify在中间
一旦执行notify就会return，不再执行wait
一旦执行wait，就压入l等待其他thread notify
并不是所有的thread都需要压入list
只要条件合适，有足够的h和o在list里面，就不需要压入，直接跑完线程
而且计算l.size()的mean应该在4左右
hhhhhhhhhh或者oooooooh的概率极低
大多数时候是hhhh或者oooh甚至更短，hh的来个o就清零了
这种长度还当成大list来做java.util.concurrent就搞笑了

【在 F****n 的大作中提到】
: 不太对，
: 你的wait没有notify
: 而且h()和o()都全部synchronized
: 只用synchronized的解法我前面写过。
avatar
b*0
97 楼
Cong
avatar
F*n
98 楼
你知道你的hThread.notify() notify不到 wait()把？？？

【在 z*******3 的大作中提到】
: 行不行直接开几个thread跑一下不就知道了
: notify在中间
: 一旦执行notify就会return，不再执行wait
: 一旦执行wait，就压入l等待其他thread notify
: 并不是所有的thread都需要压入list
: 只要条件合适，有足够的h和o在list里面，就不需要压入，直接跑完线程
: 而且计算l.size()的mean应该在4左右
: hhhhhhhhhh或者oooooooh的概率极低
: 大多数时候是hhhh或者oooh甚至更短，hh的来个o就清零了
: 这种长度还当成大list来做java.util.concurrent就搞笑了
avatar
y*0
99 楼
有道理！

【在 f***r 的大作中提到】
: 恭喜。 EB3四月不能交吧。 应该EB2吧
avatar
z*3
100 楼
而且我看了下，原来设计，没有循环语句
也就是说，无论l.size怎么变
执行的效率都是一样的，复杂度是O(1)常量
那这个时候做多线程的优化就没有必要了
完全可以把那一小段当成原子操作来执行
反正每次执行就那么点时间，无所谓
另外也没有侵入他人代码，不改写Thread之类的
更没有sleep这种可怕的方法，蛮好
avatar
z*d
101 楼
拍
avatar
z*3
102 楼
我都说了，你自己写个main试试不就知道了？

【在 F****n 的大作中提到】
: 你知道你的hThread.notify() notify不到 wait()把？？？
avatar
m*8
103 楼
pai
avatar
F*n
104 楼
你就解释一下为啥hThread.notify()能影响wait()吧

【在 z*******3 的大作中提到】
: 我都说了，你自己写个main试试不就知道了？
avatar
b*h
105 楼
Cong

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
z*e
106 楼
因为wait的monitor在l上，而不是在ti上
这个问题可以单独剥离出来看，如果写成一堆的话
那就非常不容易阅读了，这是代码
List l = new ArrayList();

public void h() throws InterruptedException {
ThreadInfo ti =null;

synchronized(l){
if (l.size() >= 2) {
ThreadInfo hThread = l.get(0);
ThreadInfo oThread = l.get(l.size() - 1);
if (hThread.isH() && oThread.isO()) {
synchronized(hThread){
hThread.notified();
hThread.notify();
}
synchronized(oThread){
oThread.notified();
oThread.notify();
}
l.remove(hThread);
l.remove(oThread);
System.out.println("1 h2o");
return;
}
}
Thread currentThread = Thread.currentThread();
ti = new ThreadInfo();
ti.setH(true);
ti.setT(currentThread);
l.add(0, ti);
}
synchronized(ti){
if(ti!=null && !ti.isNotified())
ti.wait();
}
}
public void o() throws InterruptedException {
ThreadInfo ti =null;
synchronized(l){
if (l.size() >= 2) {
ThreadInfo hThread1 = l.get(0);
ThreadInfo hThread2 = l.get(1);
if (hThread1.isH() && hThread2.isH()) {
synchronized(hThread1){
hThread1.notified();
hThread1.notify();
}
synchronized(hThread2){
hThread2.notified();
hThread2.notify();
}
l.remove(hThread1);
l.remove(hThread2);
System.out.println("1 h2o");
return;
}
}
Thread currentThread = Thread.currentThread();
ti = new ThreadInfo();
ti.setH(false);
ti.setT(currentThread);
l.add(ti);
}

synchronized(ti){
if(ti!=null && !ti.isNotified())
ti.wait();
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
测试结果
o
h
o
h
1 h2o
end .......,Thread[Thread-5,5,main]
end .......,Thread[Thread-3,5,main]
end .......,Thread[Thread-4,5,main]
h
h
1 h2o
end .......,Thread[Thread-2,5,main]
end .......,Thread[Thread-6,5,main]
end .......,Thread[Thread-1,5,main]
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
class ThreadInfo{
private boolean isNotified=false;
private Thread t;
private boolean isH;
public Thread getT() {
return t;
}
public void setT(Thread t) {
this.t = t;
}
public boolean isH() {
return isH;
}
public void setH(boolean isH) {
this.isH = isH;
}

public boolean isO() {
return !isH();
}

public void notified(){
this.isNotified = true;
}

public boolean isNotified(){
return this.isNotified;
}
}

【在 F****n 的大作中提到】
: 你就解释一下为啥hThread.notify()能影响wait()吧
avatar
s*d
107 楼
congrats
need baozi
thanks
avatar
F*n
108 楼
wait(); 的 monitor 怎么会在 l 上？
wait(); <=> this.wait();

【在 z****e 的大作中提到】
: 因为wait的monitor在l上，而不是在ti上
: 这个问题可以单独剥离出来看，如果写成一堆的话
: 那就非常不容易阅读了，这是代码
: List l = new ArrayList();
:
: public void h() throws InterruptedException {
: ThreadInfo ti =null;
:
: synchronized(l){
: if (l.size() >= 2) {
avatar
Y*X
109 楼
bless
avatar
m*n
110 楼
原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
解供大家参考。
从Java的角度看这道题可以有三个考点：
对Java Synchronization and Concurrency的掌握
基本的Coding Style，要能扩展,不能写spaghetti code
有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
也行。
看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
。当然有人可能觉得这个考基本功非要你用那也没办法。
我的基本思路是：
- 用synchronousQueue去Block and release caller threads
- 用AtomicInterger计数
- Thread Synchronization下面再提。
- 扩展性通过把H和O抽象化来实现。
作concurrency的题要照顾到四点：
- 正确性的两点：有没有race，有没有deadlock
- 效率：有没有不必要的synchronization
- 公平：先来后到怎么处理。要求高的要FIFO，低的只要没有starvation就行。
这题最省事的就是加一个control thread。Caller和controller之间一个Semaphore就
够了，而且可以很好地照顾到公平。
如果不能有自己的Thread，那么中规中矩的办法就是用Lock。别的思路我也没有了。
下面贴几段Code。
第一段是helper，把计数和Thread Enqueue/Dequeue等等都包括了。因为要照顾下面最
复杂的解法，有的Code在其他地方可以去掉。
后面有三个例子：
- 用control thread
- 无extra thread用lock
- 无extra thread也不用lock。这个可以显示一下技能，但是没有什么实际意义。
后两个解法share一个bug，但是懒得改了：releaseAll()不应该简单地loop过去。对
caller自己的element应该挑出来最后call.而且releaseAll()在用Lock的解法里应该挪
到locked region之外。
avatar
l*l
111 楼
原装？
恭喜

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
m*n
112 楼

public class ElementsImpl implements IElements {

private final int batchSize;
private final AtomicInteger counter = new AtomicInteger();

ElementsImpl(int i) {
batchSize = i;
}

public int getBatchSize() {
return batchSize;
}
@Override
public void inc() {
counter.incrementAndGet();
}
@Override
public boolean reserve() {
int val = counter.get();
return val >= batchSize && counter.compareAndSet(val, val -
batchSize);
}
@Override
public void cancel() {
counter.addAndGet(batchSize);
}
@Override
public void releaseQueued(SynchronousQueue queue,
boolean coversSelf) {
for (int i = 0; i < (!coversSelf? batchSize : batchSize - 1); i+
+) {
try {
queue.take();
} catch (InterruptedException ie) {
// Bug!
}
}
if (!coversSelf) {
return;
}
// Starvation prevention: should I wait or go?
if (queue.poll() != null) {
this.enqueue(queue);
}
// Otherwise I'm the last one and should go.
}
@Override
public void enqueue(SynchronousQueue queue) {
queue.offer(this);
}


}

public static enum WaterElements {
H(2), O(1);

private final IElements ele;
private WaterElements(int atomCount) {
this.ele = new ElementsImpl(atomCount);
}

public void inc() {
ele.inc();
}
public boolean reserve() {
return ele.reserve();
}
public void cancel() {
ele.cancel();
}
public void releaseQueued(WaterElements caller) {
ele.releaseQueued(waitQueue, caller == this);
}
public void enqueue() {
ele.enqueue(waitQueue);
}

private static final SynchronousQueue waitQueue =
new SynchronousQueue(true);

public static final int totalAtomsPerMolecule;

static {
int sum = 0;
for (WaterElements we : WaterElements.values()) {
sum += we.ele.getBatchSize();
}
totalAtomsPerMolecule = sum;
}

public static WaterElements reserveAll() {
for (WaterElements we : WaterElements.values()) {
if (!we.reserve()) return we;
}
return null;
}

public static void releaseAll(WaterElements caller) {
for (WaterElements we : WaterElements.values()) {
we.releaseQueued(caller); }
}

public static void cancelAll(WaterElements reserveFailure) {
WaterElements[] values = WaterElements.values();
for (int i = reserveFailure.ordinal() - 1; i >= 0; i--) {
values[i].cancel();
}
}
}
avatar
e*e
113 楼
cong!2个半月就绿了，赞

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
m*n
114 楼
package test;
import java.util.concurrent.Semaphore;
import test.IElements.WaterElements;
public class H2OExtraThread {
private final Semaphore sema = new Semaphore(0);

private volatile boolean isRunning = true;

// Called by the control thread
private void controllerRun() {

while (isRunning) {
try {
sema.acquire(WaterElements.totalAtomsPerMolecule);
} catch (InterruptedException e) {
continue;
}
WaterElements failedAt = WaterElements.reserveAll();

if (failedAt == null) {
// Success
WaterElements.releaseAll(null);
} else {
WaterElements.cancelAll(failedAt);
sema.release(WaterElements.totalAtomsPerMolecule);
}
}

}
// Invoked by external caller.
public void addO() {
WaterElements.O.inc();
sema.release(1);
WaterElements.O.enqueue();
}

// Invoked by external caller
public void addH() {
WaterElements.H.inc();
sema.release(1);
WaterElements.H.enqueue();
}
}
avatar
t*8
115 楼
pai
avatar
m*n
116 楼
package test;
import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import test.IElements.WaterElements;
public class H2OWithLock {

private Lock lock = new ReentrantLock();

public void addO() {
WaterElements.O.inc();
checkMolecule(WaterElements.O);
}

private void checkMolecule(WaterElements we) {
lock.lock();
boolean shouldBlock = false;
try {
WaterElements failedAt = WaterElements.reserveAll();

if (failedAt == null) {
WaterElements.releaseAll(we);
} else {
WaterElements.cancelAll(failedAt);
shouldBlock = true;
}
} finally {
lock.unlock();
}
if (shouldBlock) {
we.enqueue();
}
}
}
avatar
y*0
117 楼
cong
avatar
m*n
118 楼
package test;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicLong;
import test.IElements.WaterElements;
public class H2OLockFree {
private final AtomicLong sequencer = new AtomicLong();
private final AtomicInteger contention = new AtomicInteger();
public void addO() {
addElements(WaterElements.O);
}

private void addElements(WaterElements ele) {
long id = sequencer.incrementAndGet();
contention.incrementAndGet();
ele.inc();
while (true) {
WaterElements failure = null;
next_ele:
for (WaterElements e : WaterElements.values()) {
while (id == sequencer.get() && contention.get() > 1) {
if (e.reserve()) continue next_ele;
try { Thread.sleep(1); } catch (Exception err) {}
}
failure = e;
break;
}

if (failure == null) {
// Success
WaterElements.releaseAll(ele);
contention.decrementAndGet();
} else {
// Failure
WaterElements.cancelAll(failure);
contention.decrementAndGet();
ele.enqueue();
}
}
}

}
avatar
d*l
119 楼
恭喜恭喜， 排包子
avatar
c*t
120 楼
多谢！这么好的帖子，先mark后看。

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
j*u
121 楼
Cong!
avatar
f*t
122 楼
这个要认真看
avatar
m*e
123 楼
恭喜恭喜！！！
avatar
c*t
124 楼
lz能否把IElements interface的codes也发一下。

【在 m*****n 的大作中提到】
: package test;
: import java.util.concurrent.atomic.AtomicInteger;
: import java.util.concurrent.atomic.AtomicLong;
: import test.IElements.WaterElements;
: public class H2OLockFree {
: private final AtomicLong sequencer = new AtomicLong();
: private final AtomicInteger contention = new AtomicInteger();
: public void addO() {
: addElements(WaterElements.O);
: }
avatar
t*e
125 楼
恭喜恭喜! 希望沾些喜气，也早些绿
avatar
c*t
126 楼
在无extra thread的情况下，我也觉得应该可以只用atomicInteger的。可是我写不出
，只写出用lock condition的。
能不能说说，你为什么说这题“理论上”只用AtomicInteger也行？

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
c*t
127 楼
cong!

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
w*p
128 楼
收藏。等以后看。
avatar
d*y
129 楼
gxgx.
avatar
v*n
130 楼
好贴啊！
avatar
r*e
131 楼
Cong
avatar
F*n
132 楼
public class H2O {
public static class ThreadHolder {
Thread thread;
ThreadHolder(Thread thread) {
this.thread = thread;
}
}
protected LinkedList hlist = new LinkedList();
protected LinkedList olist = new LinkedList();
public boolean h() {
ThreadHolder current = new ThreadHolder(Thread.currentThread());
synchronized (current) {
ThreadHolder[] threadsToWakeUp = null;
// updating the queues requires a global lock;
synchronized (this) {
this.hlist.add(current);
threadsToWakeUp = this.getThreadsToWakeUp();
}
// now the wait and wake up is only in the current lock;
boolean notInterrupted = this
.checkWaitAndWakeUp(current, threadsToWakeUp);
if (notInterrupted) {
this.doH();
}
return notInterrupted;
}
}
private ThreadHolder[] getThreadsToWakeUp() {
if (this.hlist.size() >= 2 && this.olist.size() >= 1) {
ThreadHolder[] holders = new ThreadHolder[3];
holders[0] = this.hlist.poll();
holders[1] = this.hlist.poll();
holders[2] = this.olist.poll();
return holders;
}
return null;
}
// return true if the wait is not interrupted.
private boolean checkWaitAndWakeUp(ThreadHolder current,
ThreadHolder[] threadsToWakeUp) {
boolean wait = true;
if (threadsToWakeUp != null) {
for (ThreadHolder threadToWakeUp : threadsToWakeUp) {
if (threadToWakeUp == current) {
wait = false;
} else {
// this lock ensures notify will only happen after the
// thread wait;
synchronized (threadToWakeUp) {
threadToWakeUp.notifyAll();
}
}
}
}
if (wait) {
try {
current.wait();
} catch (InterruptedException e) {
return false;
}
}
return true;
}
// similiar to h();
public boolean o() {
ThreadHolder current = new ThreadHolder(Thread.currentThread());
synchronized (current) {
ThreadHolder[] threadsToWakeUp = null;
// updating the queues requires a global lock;
synchronized (this) {
this.olist.add(current);
threadsToWakeUp = this.getThreadsToWakeUp();
}
// now the wait and wake up is only in the current lock;
boolean notInterrupted = this
.checkWaitAndWakeUp(current, threadsToWakeUp);
if (notInterrupted) {
this.doO();
}
return notInterrupted;
}
}
// Override this to extend the business logic
protected void doH() {
// business logic;
}
// Override this to extend the business logic
protected void doO() {
// business logic
}
}

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
g*m
133 楼
GONGXI
avatar
m*n
134 楼
纯Busy wait不主动yield, progress 不容易把握。

【在 c********t 的大作中提到】
: 在无extra thread的情况下，我也觉得应该可以只用atomicInteger的。可是我写不出
: ，只写出用lock condition的。
: 能不能说说，你为什么说这题“理论上”只用AtomicInteger也行？
:
: AtomicInteger
: date
avatar
u*r
135 楼
恭喜！
avatar
f*d
136 楼
如果允许我大展身手的话。我会用EIP Aggregator pattern
http://www.eaipatterns.com/Aggregator.html
如果要考我java，我就用 new concurrent package, 简单明了
public class H2O {
private BlockingQueue hq = Queues.newArrayBlockingQueue();
private BlockingQueue oq = Queues.newArrayBlockingQueue();
public H2O H() {
CountDownLatch latch = new CountDownLatch(1);
hq.add(latch);
latch.await();
return this;
}
public H2O O() {
CountDownLatch latch = new CountDownLatch(1);
oq.add(latch);
latch.await();
return this;
}
public H2O() {
Executors.newSingleThreadPool().execute(new Runnable() {
void run() {
while(true) {
CountDownLatch o = oq.take();
CountDownLatch h1 =hq.take();
hq.take().countDown();
h1.countDown();
o.countDown();
}
}
}
}
}
avatar
l*0
137 楼
Eb3 吧？

【在 y******0 的大作中提到】
: cong! EB3吧？
avatar
f*d
138 楼
没有额外thread的版本
public class H2O {
private BlockingQueue hq = Queues.newArrayBlockingQueue();
public H2O H() {
CountDownLatch latch = new CountDownLatch(1);
hq.add(latch);
latch.await();
return this;
}
public H2O O() {
// this while is to make sure there is no such case where
// one O got one H and then being prempted, another O got the new H
// above situation will result 2O and 2H produces no H2O
while(true) {
CountDownLatch first = hq.take();
CountDownLatch second = hq.poll();
if (second == null) {
hq.add(first);
continue;
}
first.countDown();
second.countDown();
return this;
}
}
}
avatar
I*s
139 楼
怎么联系呢？用什么借口？RD4月的话，到现在才2个多月，完全没有超过processing
time呀。

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
f*d
140 楼
in a concurrent implementation, Thread.sleep is always a big NONO

【在 m*****n 的大作中提到】
: package test;
: import java.util.concurrent.atomic.AtomicInteger;
: import java.util.concurrent.atomic.AtomicLong;
: import test.IElements.WaterElements;
: public class H2OLockFree {
: private final AtomicLong sequencer = new AtomicLong();
: private final AtomicInteger contention = new AtomicInteger();
: public void addO() {
: addElements(WaterElements.O);
: }
avatar
s*z
141 楼
恭喜恭喜！
没有pass normal processing time也可以要求议员啊
谢谢！

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
T*s
143 楼
Pai
avatar
f*d
144 楼
这种题还有比较重要的是unit test，怎么在unit test模拟multi threading 的多种可
能出现的情况。
怎么assert
avatar
a*g
145 楼
联系议员不需要以processing time为理由，比如可以说我的GC从申请到现在已经很多
年了，这期间我被layoff过，遇到好的机会却苦于没有GC而不得不放弃等等，把自己这
些年来的苦难都说出来。

【在 I**********s 的大作中提到】
: 怎么联系呢？用什么借口？RD4月的话，到现在才2个多月，完全没有超过processing
: time呀。
avatar
F*n
146 楼
你的都不对，
LZ的把简单问题复杂化了
要用java.util.concurrent这题其实很简单
一个ReentrantLock 两个Condition就行了

);

【在 f********d 的大作中提到】
: 没有额外thread的版本
: public class H2O {
: private BlockingQueue hq = Queues.newArrayBlockingQueue();
: public H2O H() {
: CountDownLatch latch = new CountDownLatch(1);
: hq.add(latch);
: latch.await();
: return this;
: }
: public H2O O() {
avatar
m*z
147 楼
cong!
avatar
f*d
148 楼
I've passed the unit tests pretty well in different scenarios.
of course you can use ReentrantLock and 2 Conditions. And you need one more
thing which is the CyclicBarrier for the H(2)
Problem came when you implement.
When O came, you normally will signal the Condition for O. but what if there
's no H came before or only one came?
Now you need to await on H's condition.
Now you meet a pretty weird situation of signal first or await first.
normally the strategy to solve is using while(true) and keep trying to avoid
deadlocks.
That's fine the code can work. but can you think of any better way of
handling this and how can it be extended in the future?
First thing come into mind is, why I need that while(true)? because I dont
know whether the other side is waiting by Condition interface. What about
introduce one?
alright, now since you need a collection, what about a concurrent one to
help? BlockingQueue came into the door.
Now i still need condition to do await. now you could do lock and new
condition and await. but the question is, is there any class can do this job
much easier?
That's where the CountDownLatch kicks in.
okay, now back to the extensible question? what if you have C2H4O2? then you
code is pretty messy. using the first approach i gave.
in the process method, The runnable is actually describing how H2O or C2H4O2
. and you could make it better as a DSL and encapsulate and abstract to
Element and ElementDefintion.
in that way, you can loop thru all the ElementDefitions(a formula). now the
constructor can take a DSL of ElementDefinition.
Now to this point, it becomes a trival version of Aggregator in Camel or
Spring integration. now what's left over?
of course, Exception handlings.
There will be more considierations on that front, but this is also a test to
see how sophisticated the interviewee is.
btw, I used the same questioin in my interviews. very few people can go this
far.
avatar
n*1
149 楼
喜气

cong!

【在 m**********z 的大作中提到】
: cong!
avatar
f*d
150 楼
while(true) {
CountDownLatch o = oq.take(); // take an O
CountDownLatch h1 =hq.take(); // take an H
hq.take().countDown(); // take another H
h1.countDown(); // count down all the rest
o.countDown();
}
any new formula, you only need to make sure the first 3 lines reflects your
formula well. it becomes very extensible. and you can also do
Collection list = Lists.newArrayList();
for (ElementDefinition ed : defs) {
BlockingQueue queue = ed.getQueue();
for (int i =0; i < ed.getNumber() ; i++) {
list.add(queue.take());
}
}
for (CountDownLAtch latch : list) {
latch.countDown();
}
with DSL, you could
val H2 = new ElementDefinition(2);
val O = new ElementDefinition(1);
defs.add(H2);
defs.add(O);
void H() {
H2.await();
}
class ElementDefinition {
....
public void await() {
CountDownLatch latch = new CountDownLatch(1);
queue.add(latch);
latch.await();
}
....
}
this is synchronized implementaiton. you can also have interface Element to
replace CountDownLAtch.
for synchronized implementation, use ElementSychImpl with CountDownLatch.
for asycn, get a call back.
Now the codes will be quite extensible and easier to understand

more
there
avoid

【在 f********d 的大作中提到】
: I've passed the unit tests pretty well in different scenarios.
: of course you can use ReentrantLock and 2 Conditions. And you need one more
: thing which is the CyclicBarrier for the H(2)
: Problem came when you implement.
: When O came, you normally will signal the Condition for O. but what if there
: 's no H came before or only one came?
: Now you need to await on H's condition.
: Now you meet a pretty weird situation of signal first or await first.
: normally the strategy to solve is using while(true) and keep trying to avoid
: deadlocks.
avatar
p*o
151 楼
gxgx!

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
i*6
152 楼
My 5 cents:
import java.util.concurrent.*;
class MyO implements Runnable{
int index;
CountDownLatch lock;
public MyO (int index, CountDownLatch lock) {
this.index = index;
this.lock = lock;
}
public void run() {
try {
Thread.sleep((long) (Math.random() * 1000));
lock.await();
System.out.println("Take O:" + index + " to form an H2O!");
} catch (Exception e) {
e.printStackTrace();
}
}
}
class MyH implements Runnable{
int index;
CountDownLatch lock;
public MyH(int index, CountDownLatch lock) {
this.index = index;
this.lock = lock;
}
public void run() {
try {
hread.sleep((long) (Math.random() * 1000));
lock.await();
System.out.println("take H:"+index+" to form a H2O!");
} catch(Exception e) {
e.printStackTrace();
}
}
}
public class MyH2O {
private static BlockingQueue hq = new
LinkedBlockingQueue();
private static BlockingQueue oq = new
LinkedBlockingQueue();
public static void main(String args[]){
ExecutorService service = Executors.newCachedThreadPool();
service.submit(new Thread() {
public void run(){
try{
while (true) {
Thread.sleep((long) (Math.random() * 1000));
CountDownLatch firstH = hq.take();
CountDownLatch secondH = hq.poll();
CountDownLatch firstO = oq.take();
if (secondH == null) {
hq.add(firstH);
continue;
}
firstH.countDown();
secondH.countDown();
firstO.countDown();
System.out.println("A H2O created!");
break;
}
} catch(Exception e) {
e.printStackTrace();
}
}
});
for (int i=0;i<100;i++) {
CountDownLatch lock = new CountDownLatch(1);
int type = (int)(Math.random()*2);
if (type == 0){
hq.add(lock);
service.submit(new MyH(i+1,lock));
} else {
oq.add(lock);
service.submit(new MyO(i+1,lock));
}
}
service.shutdown();
}
}
avatar
u*0
153 楼
恭喜恭喜!
avatar
n*r
154 楼
mark一下。。学习了
avatar
H*m
155 楼
gxgx
avatar
m*n
156 楼
我对CountDownLatch没太多想过。学习了。

);
);

【在 f********d 的大作中提到】
: 如果允许我大展身手的话。我会用EIP Aggregator pattern
: http://www.eaipatterns.com/Aggregator.html
: 如果要考我java，我就用 new concurrent package, 简单明了
: public class H2O {
: private BlockingQueue hq = Queues.newArrayBlockingQueue();
: private BlockingQueue oq = Queues.newArrayBlockingQueue();
: public H2O H() {
: CountDownLatch latch = new CountDownLatch(1);
: hq.add(latch);
: latch.await();
avatar
n*r
157 楼
gxgx！！！
avatar
z*3
158 楼
原题：
3: 实现两个函数: H() and O(), 这两个函数会被多线程调用。当一个线程调用H或O时
，如果当前已经有至少两个线程call H和一个线程call O。那么让两个call H和一个
call O的线程返回（产生一个水分子），其他的都block。
我随手写了一个，不想用synchronized关键字
这个要搞起来的确比较麻烦，想上java.util.concurrent
研究了一下copyonwritearraylist，还是不行，两个方法都得上synchronized
List l = new ArrayList();
public synchronized void h(){
if(l.size()>=2){
Thread hThread = l.get(0);
Thread oThread = l.get(l.size()-1);
if(hThread.isH() && oThread.isO()){
hThread.notify();
oThread.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(0,currentThread);
currentThread.wait();
}
public synchronized void o(){
if(l.size()>=2){
Thread hThread1 = l.get(0);
Thread hThread2 = l.get(1);
if(hThread1.isH() && hThread2.isH()){
hThread1.notify();
hThread2.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(currentThread);
currentThread.wait();
}
avatar
M*r
159 楼
cong!
avatar
z*3
160 楼
isH()和isO()要扩展一下，要额外加一个类
包装thread对象以及该thread读取的是o还是h
要不然thread本身是没有这个方法的
class ThreadInfo{
private Thread thread;
private boolean isH;
//setter/getter method
...
}
然后把l里面保存的全部换成ThreadInfo对象
avatar
m*5
161 楼
Gong, pai
avatar
z*3
162 楼
或者找个map寄存
不过增加的map自然增加了查找的时间
效率上不如包装类
List l= new ArrayList();
Map m= new HashMap();
public synchronized void h(){
if(l.size()>=2){
Thread hThread = l.get(0);
Thread oThread = l.get(l.size()-1);
if(m.get(hThread) && !m.get(oThread)){
hThread.notify();
oThread.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(0,currentThread);
m.put(currentThead, true);
currentThread.wait();
}
public synchronized void o(){
if(l.size()>=2){
Thread hThread1 = l.get(0);
Thread hThread2 = l.get(1);
if(m.get(hThread1) && m.get(hThread2)){
hThread1.notify();
hThread2.notify();
return;
}
}
Thread currentThread = Thread.getCurrentThread();
l.add(currentThread);
m.put(currentThread, false);
currentThread.wait();
}
avatar
l*g
163 楼
恭喜！
avatar
z*3
164 楼
汗，实验了一下，有三个小问题，看来多线程白板还是难以bug free，需要多练习
getCurrentThread() -> currentThread()
currentThread.wait() -> wait()
hThread.notify() -> synchronized(hThread){ hThread.notify();}
avatar
l*g
165 楼
楼主虽然RD晚，但是PD早，FIFO 有两个，一个是按RD来，处理485CASE。
另一个是按PD来，领取绿卡名额。楼主背景调查等预处理快，就到第二个FIFO
队伍按PD领取绿卡了，不是很合理吗？
当然，误差是有的，而且还狠大，比如本人PD和RD比楼主都早的一大帮都在排，
这点来说楼主还是好运气。希望我们这些老PD早绿，好给后人开道。

【在 B*****o 的大作中提到】
: Congrats!
: TSC, 2 months
: 再次证明移民局所谓的FIFO是“胡说八道”。
: 早交早点拿EAD/AP。但不见得会早拿绿卡。相反可能会多交体检费。
avatar
z*3
166 楼
List l = new ArrayList();

public synchronized void h() throws InterruptedException {
if (l.size() >= 2) {
ThreadInfo hThread = l.get(0);
ThreadInfo oThread = l.get(l.size() - 1);
if (hThread.isH() && oThread.isO()) {
synchronized(hThread){hThread.notify();}
synchronized(oThread){oThread.notify();}
l.remove(hThread);
l.remove(oThread);
return;
}
}
Thread currentThread = Thread.currentThread();
ThreadInfo ti = new ThreadInfo();
ti.setH(true);
ti.setT(currentThread);
l.add(0, ti);
wait();
}
public synchronized void o() throws InterruptedException {
if (l.size() >= 2) {
ThreadInfo hThread1 = l.get(0);
ThreadInfo hThread2 = l.get(1);
if (hThread1.isH() && hThread2.isH()) {
synchronized(hThread1){hThread1.notify();}
synchronized(hThread2){hThread2.notify();}
l.remove(hThread1);
l.remove(hThread2);
return;
}
}
Thread currentThread = Thread.currentThread();
ThreadInfo ti = new ThreadInfo();
ti.setH(false);
ti.setT(currentThread);
l.add(ti);
wait();
}
avatar
l*e
167 楼
Cong

【在 a***g 的大作中提到】
: TSC EB2
: PD: 03/2011
: RD: 04/02/2015
: FP: 04/27/2015
: AD: 06/11/2015
: 没啥积蓄，转了40个包子到版上，请版主帮着发一下吧。谢谢！
: 祝大家早绿！
: PS 两三个星期前找了议员，至今没有接到他们的回音，不知道他们究竟知否帮着催了
: 。反正大家等的时候闲着也是闲着，可以联系一下议员试试看。
avatar
F*n
168 楼
不太对，
你的wait没有notify
而且h()和o()都全部synchronized
只用synchronized的解法我前面写过。

【在 z*******3 的大作中提到】
: List l = new ArrayList();
:
: public synchronized void h() throws InterruptedException {
: if (l.size() >= 2) {
: ThreadInfo hThread = l.get(0);
: ThreadInfo oThread = l.get(l.size() - 1);
: if (hThread.isH() && oThread.isO()) {
: synchronized(hThread){hThread.notify();}
: synchronized(oThread){oThread.notify();}
: l.remove(hThread);
avatar
m*0
169 楼
恭喜，今年的RD！！！
avatar
z*3
170 楼
行不行直接开几个thread跑一下不就知道了
notify在中间
一旦执行notify就会return，不再执行wait
一旦执行wait，就压入l等待其他thread notify
并不是所有的thread都需要压入list
只要条件合适，有足够的h和o在list里面，就不需要压入，直接跑完线程
而且计算l.size()的mean应该在4左右
hhhhhhhhhh或者oooooooh的概率极低
大多数时候是hhhh或者oooh甚至更短，hh的来个o就清零了
这种长度还当成大list来做java.util.concurrent就搞笑了

【在 F****n 的大作中提到】
: 不太对，
: 你的wait没有notify
: 而且h()和o()都全部synchronized
: 只用synchronized的解法我前面写过。
avatar
G*1
171 楼
恭喜，沾喜气
avatar
F*n
172 楼
你知道你的hThread.notify() notify不到 wait()把？？？

【在 z*******3 的大作中提到】
: 行不行直接开几个thread跑一下不就知道了
: notify在中间
: 一旦执行notify就会return，不再执行wait
: 一旦执行wait，就压入l等待其他thread notify
: 并不是所有的thread都需要压入list
: 只要条件合适，有足够的h和o在list里面，就不需要压入，直接跑完线程
: 而且计算l.size()的mean应该在4左右
: hhhhhhhhhh或者oooooooh的概率极低
: 大多数时候是hhhh或者oooh甚至更短，hh的来个o就清零了
: 这种长度还当成大list来做java.util.concurrent就搞笑了
avatar
Z*x
173 楼
恭喜啊，PD 和RD都和我差不多哦，希望我也快绿，
avatar
z*3
174 楼
而且我看了下，原来设计，没有循环语句
也就是说，无论l.size怎么变
执行的效率都是一样的，复杂度是O(1)常量
那这个时候做多线程的优化就没有必要了
完全可以把那一小段当成原子操作来执行
反正每次执行就那么点时间，无所谓
另外也没有侵入他人代码，不改写Thread之类的
更没有sleep这种可怕的方法，蛮好
avatar
x*l
175 楼
恭喜啦！！！
avatar
z*3
176 楼
我都说了，你自己写个main试试不就知道了？

【在 F****n 的大作中提到】
: 你知道你的hThread.notify() notify不到 wait()把？？？
avatar
h*l
177 楼
Congrats
avatar
F*n
178 楼
你就解释一下为啥hThread.notify()能影响wait()吧

【在 z*******3 的大作中提到】
: 我都说了，你自己写个main试试不就知道了？
avatar
c*x
179 楼
恭喜恭喜！
avatar
z*e
180 楼
因为wait的monitor在l上，而不是在ti上
这个问题可以单独剥离出来看，如果写成一堆的话
那就非常不容易阅读了，这是代码
List l = new ArrayList();

public void h() throws InterruptedException {
ThreadInfo ti =null;

synchronized(l){
if (l.size() >= 2) {
ThreadInfo hThread = l.get(0);
ThreadInfo oThread = l.get(l.size() - 1);
if (hThread.isH() && oThread.isO()) {
synchronized(hThread){
hThread.notified();
hThread.notify();
}
synchronized(oThread){
oThread.notified();
oThread.notify();
}
l.remove(hThread);
l.remove(oThread);
System.out.println("1 h2o");
return;
}
}
Thread currentThread = Thread.currentThread();
ti = new ThreadInfo();
ti.setH(true);
ti.setT(currentThread);
l.add(0, ti);
}
synchronized(ti){
if(ti!=null && !ti.isNotified())
ti.wait();
}
}
public void o() throws InterruptedException {
ThreadInfo ti =null;
synchronized(l){
if (l.size() >= 2) {
ThreadInfo hThread1 = l.get(0);
ThreadInfo hThread2 = l.get(1);
if (hThread1.isH() && hThread2.isH()) {
synchronized(hThread1){
hThread1.notified();
hThread1.notify();
}
synchronized(hThread2){
hThread2.notified();
hThread2.notify();
}
l.remove(hThread1);
l.remove(hThread2);
System.out.println("1 h2o");
return;
}
}
Thread currentThread = Thread.currentThread();
ti = new ThreadInfo();
ti.setH(false);
ti.setT(currentThread);
l.add(ti);
}

synchronized(ti){
if(ti!=null && !ti.isNotified())
ti.wait();
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
测试结果
o
h
o
h
1 h2o
end .......,Thread[Thread-5,5,main]
end .......,Thread[Thread-3,5,main]
end .......,Thread[Thread-4,5,main]
h
h
1 h2o
end .......,Thread[Thread-2,5,main]
end .......,Thread[Thread-6,5,main]
end .......,Thread[Thread-1,5,main]
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
class ThreadInfo{
private boolean isNotified=false;
private Thread t;
private boolean isH;
public Thread getT() {
return t;
}
public void setT(Thread t) {
this.t = t;
}
public boolean isH() {
return isH;
}
public void setH(boolean isH) {
this.isH = isH;
}

public boolean isO() {
return !isH();
}

public void notified(){
this.isNotified = true;
}

public boolean isNotified(){
return this.isNotified;
}
}

【在 F****n 的大作中提到】
: 你就解释一下为啥hThread.notify()能影响wait()吧
avatar
n*0
181 楼
恭喜楼主，跟楼主PD一样，RD晚几天，也是TSC，请问楼主找众议员还是参议员，我找
参议员就收了表格没信了，但是众议员回话说跟踪了，去了infopass，屁都没问出来，
就让等着，说EAD/AP都给了就当绿卡用。
avatar
F*n
182 楼
wait(); 的 monitor 怎么会在 l 上？
wait(); <=> this.wait();

【在 z****e 的大作中提到】
: 因为wait的monitor在l上，而不是在ti上
: 这个问题可以单独剥离出来看，如果写成一堆的话
: 那就非常不容易阅读了，这是代码
: List l = new ArrayList();
:
: public void h() throws InterruptedException {
: ThreadInfo ti =null;
:
: synchronized(l){
: if (l.size() >= 2) {
avatar
a*g
183 楼
我找的参议员。提交表格后给他们打了个电话,告诉我会跟tsc联系, 不知道他们是否联
系了。

【在 n******0 的大作中提到】
: 恭喜楼主，跟楼主PD一样，RD晚几天，也是TSC，请问楼主找众议员还是参议员，我找
: 参议员就收了表格没信了，但是众议员回话说跟踪了，去了infopass，屁都没问出来，
: 就让等着，说EAD/AP都给了就当绿卡用。
avatar
P*d
184 楼
MARK
avatar
c*0
185 楼
如果没理解错，直接用两个semaphore不行吗
public void H() {
p1.release(1);
p2.acquire(1);
}
public void O() {
p2.release(2);
p1.acquire(2);
}

AtomicInteger
date

【在 m*****n 的大作中提到】
: 原题见http://www.mitbbs.com/article_t/JobHunting/32331973.html
: 这道题不是单纯作对就好的。那里贴出的解法有些值得商榷的地方。我这里谈谈个人见
: 解供大家参考。
: 从Java的角度看这道题可以有三个考点：
: 对Java Synchronization and Concurrency的掌握
: 基本的Coding Style，要能扩展,不能写spaghetti code
: 有把握的话可以讨论一下Lock Free Synchronization. 这题理论上只用AtomicInteger
: 也行。
: 看到这道题之后首先应该和面试者交流一下，看是否一定要用synchronized-wait-
: notify. 如果不要求就不要用了，用这个既花时间又容易出错，还显得不够up to date
avatar
b*m
186 楼
I think mine is short, not tested.
public class PH2O {
private static final Object PLACE_HOLDER = new Object();
AtomicInteger extraH = new AtomicInteger();
BlockingQueue requiredO = new LinkedBlockingDeque();
BlockingQueue releasedH = new LinkedBlockingDeque();
public void h() throws InterruptedException {
while (true) {
if (extraH.compareAndSet(1, 0)) {
requiredO.add(new Object());
break;
}
if (extraH.compareAndSet(0, 1)) {
break;
}
}
releasedH.take();
}
public void o() throws InterruptedException {
requiredO.take();
releasedH.offer(PLACE_HOLDER);
releasedH.offer(PLACE_HOLDER);
}
}
avatar
b*m
187 楼
似乎没问题。

【在 c*****0 的大作中提到】
: 如果没理解错，直接用两个semaphore不行吗
: public void H() {
: p1.release(1);
: p2.acquire(1);
: }
: public void O() {
: p2.release(2);
: p1.acquire(2);
: }
:
avatar
w*s
188 楼
太复杂了，前面有人说了，一个Lock挂两个ConditionObject就直接搞定了

【在 b**m 的大作中提到】
: I think mine is short, not tested.
: public class PH2O {
: private static final Object PLACE_HOLDER = new Object();
: AtomicInteger extraH = new AtomicInteger();
: BlockingQueue requiredO = new LinkedBlockingDeque();
: BlockingQueue releasedH = new LinkedBlockingDeque();
: public void h() throws InterruptedException {
: while (true) {
: if (extraH.compareAndSet(1, 0)) {
: requiredO.add(new Object());
avatar
x*i
189 楼
O() can release 2 permits while there is only one H thread waiting. The H()
then is unblocked. 不符合题目要求把。

【在 c*****0 的大作中提到】
: 如果没理解错，直接用两个semaphore不行吗
: public void H() {
: p1.release(1);
: p2.acquire(1);
: }
: public void O() {
: p2.release(2);
: p1.acquire(2);
: }
:
avatar
m*h
190 楼
mark
avatar
p*3
191 楼
是不是可以这么做：
在两个类里分别维护两个static violate counter
H.currentCounter/H.bar
O.currentCounter/O.bar
每次一个H或者O线程创建的时候付一个id = currentCounter++;
每一个线程创建的时候check counter 和 bar看看是不是有满足构成H2O的3个线程存在
，如果自己是其中之一的话忽略(好像题目是这么要求的)， 如果有的话提高bar,H.bar
+= 2, O.bar += 1, 这段check和修改的代码要保护， 然后NotifyALL, 然后自己wait
。
其他线程从wait中醒来后check自己的id和bar, 如果bar > id, return 否则继续wait
相关阅读
如何做一个有文化的高贵神经病？(转载)不约而同你们见过啪啪啪时的龟鸟么？冷笑话集(转载)深圳市委书记:面对高房价 将填海55平方公里 (转载)索男离婚案例这个和博导比如何？办公室不宜奇葩人奇葩事One more reason to vote for Donald Trump纠纷多的人不要坐高档小汽车床破的手真的很小吗？ (转载)白女单身了六个月Re: 拿到米囯permanent resident的捷径是？ (转载)是否十年刑期，取决于这句英文我爱小小鱼：祖国你要强大！！！ (转载)2016世界小姐日本区冠军老图，有人据此推算方舟子的脑袋长达半米多世界头号毒枭不堪墨西哥监狱折磨要求引渡美国ZT 雪球上看到的一篇很有意思 (转载)谁偷的？
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。