昨天面试的一道题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Java - 爪哇娇娃

昨天面试的一道题

昨天面试的一道题# Java - 爪哇娇娃

g*e2009-12-02 08:12

1 楼

class Num {
private Integer i = 0;
public synchronized void set(int i) {
this.i = i;
}
public synchronized int get() {
return i;
}
public synchronized void swap(Num other) {
//implement a thread safe swap method here.
}
}

g*g2009-12-02 08:12

2 楼

ahh, I don't know how to do this. Usually you either
compare the value of them and lock all of them in the
same order, or you can use ReentrantLock and do tryLock
until you can lock all of them. In swap, you already locks
one firmly and you call other.get, you deadlock already.
It seems you can only do
synchronized(Num.class) inside, and performance will suffer.
Edit: no, even that doesn't solve the problem. I don't know
a solution. I think once both instances get their own lock, there's
no solu

【在 g**e 的大作中提到】

: class Num {
: private Integer i = 0;
: public synchronized void set(int i) {
: this.i = i;
: }
: public synchronized int get() {
: return i;
: }
: public synchronized void swap(Num other) {
: //implement a thread safe swap method here.

g*e2009-12-02 08:12

3 楼

原来大牛也不会，我死而无憾了

【在 g*****g 的大作中提到】

: ahh, I don't know how to do this. Usually you either
: compare the value of them and lock all of them in the
: same order, or you can use ReentrantLock and do tryLock
: until you can lock all of them. In swap, you already locks
: one firmly and you call other.get, you deadlock already.
: It seems you can only do
: synchronized(Num.class) inside, and performance will suffer.
: Edit: no, even that doesn't solve the problem. I don't know
: a solution. I think once both instances get their own lock, there's
: no solu

h*j2009-12-02 08:12

4 楼

不考虑null或者同一个object
synchronized(other) {
Integer t = this.i;
this.i = other.i;
other.i = t;
}
行不？

【在 g**e 的大作中提到】

g*g2009-12-02 08:12

5 楼

No, let's say you have instance a and b.
if a.swap(b) and b.swap(a) are called at the same time,
sync(b) and sync(a) will block for ever waiting each other.
So you have to count on external logic to prevent deadlock.

【在 h**j 的大作中提到】

: 不考虑null或者同一个object
: synchronized(other) {
: Integer t = this.i;
: this.i = other.i;
: other.i = t;
: }
: 行不？

h*j2009-12-02 08:12

6 楼

那放一个synchronized(Number.class)在外面?

【在 g*****g 的大作中提到】

: No, let's say you have instance a and b.
: if a.swap(b) and b.swap(a) are called at the same time,
: sync(b) and sync(a) will block for ever waiting each other.
: So you have to count on external logic to prevent deadlock.

h*j2009-12-02 08:12

7 楼

还是不行

【在 h**j 的大作中提到】

: 那放一个synchronized(Number.class)在外面?

h*02009-12-02 08:12

8 楼

死锁吧……

【在 h**j 的大作中提到】

: 不考虑null或者同一个object
: synchronized(other) {
: Integer t = this.i;
: this.i = other.i;
: other.i = t;
: }
: 行不？

g*e2009-12-02 08:12

9 楼

好虫其实前面说的很对，我当时给的solution基本上跟哲学家吃饭那一套一样，只有同
时获得两个对象的锁才进行swap，不然立即wait放弃当前获得的lock并notifyAll。但
是面试的人说这样应该work，但不是他想要的答案...

【在 g*****g 的大作中提到】

c*t2009-12-02 08:12

10 楼

Hint:
public synchronized void swap(Num other)
{
synchronized (Num.class)
{
....
}
}

【在 g**e 的大作中提到】

h*02009-12-02 08:12

11 楼

再具体点？

【在 c*****t 的大作中提到】

: Hint:
: public synchronized void swap(Num other)
: {
: synchronized (Num.class)
: {
: ....
: }
: }

c*t2009-12-02 08:12

12 楼

Hint #2:
The synchronized functions are meant to confuse you. The problem is
equivalent without having synchronized on these functions.
You need a single lock to lock the critical section. Locking on
Num.class will create a lot of contentions, but avoids deadlock.
If can define other instance and class variables, a better solution
is to define a sequential ordering of objects using static counter and
and id. Another possible approach is to use the HashCode ordering
(assuming this function is

【在 h*****0 的大作中提到】

: 再具体点？

h*02009-12-02 08:12

13 楼

i'm totally lost...
in this problem it seems there is no way to prevent deadlock and at the same
time achieve atomic method.

【在 c*****t 的大作中提到】

: Hint #2:
: The synchronized functions are meant to confuse you. The problem is
: equivalent without having synchronized on these functions.
: You need a single lock to lock the critical section. Locking on
: Num.class will create a lot of contentions, but avoids deadlock.
: If can define other instance and class variables, a better solution
: is to define a sequential ordering of objects using static counter and
: and id. Another possible approach is to use the HashCode ordering
: (assuming this function is

g*g2009-12-02 08:12

14 楼

The thing is, once you get the lock, you can't release it.
You can get an extra lock on the class object but the instance
lock is not released.

【在 c*****t 的大作中提到】

k*r2009-12-02 08:12

15 楼

May the actor model prevail, to same the brain sells, hehe

d*t2009-12-02 08:12

16 楼

would two-phase locking help?

g*g2009-12-02 08:12

17 楼

This is a typical deadlock situation, and sun tutorial actually
gives a good example of how to resolve it using Lock.tryLock
above 1.5. For this particular question, it's dead end.

【在 d****t 的大作中提到】

: would two-phase locking help?

c*t2009-12-02 08:12

18 楼

My mistake, but you can release the lock through wait () function.
static Lock glock = ...
public void synchronized swap (Num other)
{
while (true)
{
if (glock.tryLock ())
{
synchronized (other)
{
//...
}
glock.unlock ();
return;
}
else
{
wait (1); // someone is trying to lock glock, must be
// doing swapping. Release the current monitor
// through wait so the other guy could p

【在 g*****g 的大作中提到】

: The thing is, once you get the lock, you can't release it.
: You can get an extra lock on the class object but the instance
: lock is not released.

m*t2009-12-02 08:12

19 楼

java.util.concurrent.Exchanger?

【在 g**e 的大作中提到】

F*n2009-12-02 08:12

20 楼

class Num {
private final Comparable lock; // define an ordered object as lock;
public synchronized void swap(Num other) {
Object firstLock = null;
Object secondLock = null;
if (this.lock.comparesTo(other.lock) > 0) {
firstLock = this.lock;
secondLock = other.lock;
}
else {
firstLock = other.lock;
secondLock = this.lock;
}
synchronized(firstLock) {
synchronized(

【在 g**e 的大作中提到】

h*02009-12-02 08:12

21 楼

没初始化lock，NullPointerException

【在 F****n 的大作中提到】

: class Num {
: private final Comparable lock; // define an ordered object as lock;
: public synchronized void swap(Num other) {
: Object firstLock = null;
: Object secondLock = null;
: if (this.lock.comparesTo(other.lock) > 0) {
: firstLock = this.lock;
: secondLock = other.lock;
: }
: else {

F*n2009-12-02 08:12

22 楼

There are many ways to define an ordered sequence, which is not my interest
and left to users.

【在 h*****0 的大作中提到】

: 没初始化lock，NullPointerException

h*02009-12-02 08:12

23 楼

it's not trivial, it also involves sychronize issue. you should define it in
this answer.

interest

【在 F****n 的大作中提到】

: There are many ways to define an ordered sequence, which is not my interest
: and left to users.

F*n2009-12-02 08:12

24 楼

It is trivial and you can define whatever ordering in initialization. It
only needs to be a full ordering. How does it involves synchronization issue?
Ordering locks is actually a classical solution to deadlock. So no argument on it, OK?

in

【在 h*****0 的大作中提到】

: it's not trivial, it also involves sychronize issue. you should define it in
: this answer.
:
: interest

h*02009-12-02 08:12

25 楼

your way is good. I'm not arguing that, hehe.
but if your initializations of the locks are not synchronized, they may end
up with equal locks instead of ordered lock.

issue?
argument on it, OK?

【在 F****n 的大作中提到】

: It is trivial and you can define whatever ordering in initialization. It
: only needs to be a full ordering. How does it involves synchronization issue?
: Ordering locks is actually a classical solution to deadlock. So no argument on it, OK?
:
: in

k*r2009-12-02 08:12

26 楼

Hehe. what's not fun with these problems is that even
if you think you've got a solution, there will be no
easy way of testing it :)

T*g2009-12-02 08:12

27 楼

public synchronized void swap(Num other) {
//implement a thread safe swap method here.
Integer temp;
temp = other.i;
other.i = this.i;
this.i = temp;
}
这样会引起死锁么？
假设 a.swap(b) 那么只需要a的锁，b.swap(a)只需要b的锁，为什么会死锁呢？

【在 g**e 的大作中提到】

h*02009-12-02 08:12

28 楼

这样当然不会死锁，只不过可能会出错。换到一半另一个线程来换，结果一些数据就乱
了。

【在 T*********g 的大作中提到】

: public synchronized void swap(Num other) {
: //implement a thread safe swap method here.
: Integer temp;
: temp = other.i;
: other.i = this.i;
: this.i = temp;
: }
: 这样会引起死锁么？
: 假设 a.swap(b) 那么只需要a的锁，b.swap(a)只需要b的锁，为什么会死锁呢？