请教一个多线程lock机制的问题 - 未名空间MITBBS历史存档

请教一个多线程lock机制的问题# Java - 爪哇娇娃

d*r2005-11-08 08:11

1 楼

请教一个多线程lock机制的问题
我有这样的一个method:
public void methodA(int i) {
Integer key = new Integer(i);

synchronized (key) {
.......... (codeXXX)
}
}
methodA将会被多线程调用。
但codeXXX部分的代码，我要求是对整数i这个参数synchronized的，
即：任何时间内，对同一个参数i,不可以同时执行代码段: codeXXX,
但对不同的整数i,则可以多线程同时执行。
请问我这样实现对不对？
如果不对，该如何实现？
多谢。

c*t2005-11-08 08:11

2 楼

You implementation is incorrect, since each method creates an Object
and you lock on it. Since this object is created a local scope and
never seen by other threads, there would be no synchronization at all.
One way doing so if the range of i is small (say max 65536), what you can
do is
public class Foo
{
public final static int LOCK_ARRAY_SIZE = 65536;
public final static Object[] LOCK_ARRAY;
static
{
Object[] lockArray = new Object[LOCK_ARRAY_SIZE];
for (int i = 0; i < LOCK_ARR

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

: 请教一个多线程lock机制的问题
: 我有这样的一个method:
: public void methodA(int i) {
: Integer key = new Integer(i);
:
: synchronized (key) {
: .......... (codeXXX)
: }
: }
: methodA将会被多线程调用。

d*r2005-11-08 08:11

3 楼

我本来也觉得我的方法有问题，就是没想清楚问题在哪。
多谢大侠指教，现在明白了。
看来似乎没有太好的办法，
我再考虑考虑看能不能改进我的需求。

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

: You implementation is incorrect, since each method creates an Object
: and you lock on it. Since this object is created a local scope and
: never seen by other threads, there would be no synchronization at all.
: One way doing so if the range of i is small (say max 65536), what you can
: do is
: public class Foo
: {
: public final static int LOCK_ARRAY_SIZE = 65536;
: public final static Object[] LOCK_ARRAY;
: static

p*p2005-11-08 08:11

4 楼

if only method working on i, so use synchronized method?

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

: 请教一个多线程lock机制的问题
: 我有这样的一个method:
: public void methodA(int i) {
: Integer key = new Integer(i);
:
: synchronized (key) {
: .......... (codeXXX)
: }
: }
: methodA将会被多线程调用。

m*t2005-11-08 08:11

5 楼

A few thoughts:
1. You might find this interesting:
Double-checked locking: Clever, but broken:
http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html
2. Without the double-checked locking technique, the code would have to
synchronize on every node on its traversal path. While admittedly that's still
far less contentious than a global lock on the whole tree/set, on the other
hand it requires more locking attempts, so it would still impact the
performance significantly.
3. The worst c

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

: You implementation is incorrect, since each method creates an Object
: and you lock on it. Since this object is created a local scope and
: never seen by other threads, there would be no synchronization at all.
: One way doing so if the range of i is small (say max 65536), what you can
: do is
: public class Foo
: {
: public final static int LOCK_ARRAY_SIZE = 65536;
: public final static Object[] LOCK_ARRAY;
: static

c*t2005-11-08 08:11

6 楼

The point of the tree is that locking can be avoided completely if the
tree has the item already. Locks only happen during insertion. For
HashSet, lock has to be placed no matter whether or not modification
is performed.
While traversing tree does have log(n) problem, usually it is significantly
smaller than context switch/blocking/locking etc.
Of course, I don't mean to say HashSet is that bad. It is for lazy people :)

sound

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

:
: A few thoughts:
: 1. You might find this interesting:
: Double-checked locking: Clever, but broken:
: http://www.javaworld.com/javaworld/jw-02-2001/jw-0209-double.html
: 2. Without the double-checked locking technique, the code would have to
: synchronize on every node on its traversal path. While admittedly that's still
: far less contentious than a global lock on the whole tree/set, on the other
: hand it requires more locking attempts, so it would still impact the
: performance significantly.

m*t2005-11-08 08:11

7 楼

I see you point on the custom tree idea and agree that practically it would
probably be faster than a regular, out of box hashset.
But is hashset that bad? I would think that modification only happens when
the first time a value is used. And, at any rate, both modification and
retrieving on a hashset is constant time, so even a global lock doesn't sound
that bad, I mean, looking at the price of writing a whole new custom tree
data type. Besides, don't forget (or unless I'm missing your point),

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

: The point of the tree is that locking can be avoided completely if the
: tree has the item already. Locks only happen during insertion. For
: HashSet, lock has to be placed no matter whether or not modification
: is performed.
: While traversing tree does have log(n) problem, usually it is significantly
: smaller than context switch/blocking/locking etc.
: Of course, I don't mean to say HashSet is that bad. It is for lazy people :)
:
: sound

c*t2005-11-08 08:11

8 楼

You implementation is incorrect, since each method creates an Object
and you lock on it. Since this object is created a local scope and
never seen by other threads, there would be no synchronization at all.
One way doing so if the range of i is small (say max 65536), what you can
do is
public class Foo
{
public final static int LOCK_ARRAY_SIZE = 65536;
public final static Object[] LOCK_ARRAY;
static
{
Object[] lockArray = new Object[LOCK_ARRAY_SIZE];
for (int i = 0; i < LOCK_ARR

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

: 请教一个多线程lock机制的问题
: 我有这样的一个method:
: public void methodA(int i) {
: Integer key = new Integer(i);
:
: synchronized (key) {
: .......... (codeXXX)
: }
: }
: methodA将会被多线程调用。

m*t2005-11-08 08:11

9 楼

Hmm... I guess I'm still missing some part of your idea, then.
When a thread is inserting a new value, how do you make sure other retrieving
threads still see a consistent tree, i.e., without being disturbed by
the ongoing insertion process?
I guess it's really the question of - what kind of data structure do you plan
to represent the tree with.
We don't really know, do we? It depends on which one is dominant - the

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

: The point of the tree is that locking can be avoided completely if the
: tree has the item already. Locks only happen during insertion. For
: HashSet, lock has to be placed no matter whether or not modification
: is performed.
: While traversing tree does have log(n) problem, usually it is significantly
: smaller than context switch/blocking/locking etc.
: Of course, I don't mean to say HashSet is that bad. It is for lazy people :)
:
: sound

c*t2005-11-08 08:11

10 楼

Here is a piece of pseudo-code that does reading + insertion:
public Integer search (Node currentNode, int i)
{
int v = currentNode.value.intValue ();
if (i == v)
return currentNode.value;
if (i < v)
{
if (currentNode.left == null)
{
synchronized (currentNode)
{

m*t2005-11-08 08:11

11 楼

Sounds interesting. Look forward to the pseudo code(if you have time).
Well, I guess that's our difference - you are a scientist, I'm an engineer,
and one that charges by the hour. 8-)

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

: Here is a piece of pseudo-code that does reading + insertion:
: public Integer search (Node currentNode, int i)
: {
: int v = currentNode.value.intValue ();
: if (i == v)
: return currentNode.value;
: if (i < v)
: {
: if (currentNode.left == null)
: {

r*l2005-11-08 08:11

12 楼

If java treats String as sun specifies, can do
synchronize (String.valueOf(i))

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

: You implementation is incorrect, since each method creates an Object
: and you lock on it. Since this object is created a local scope and
: never seen by other threads, there would be no synchronization at all.
: One way doing so if the range of i is small (say max 65536), what you can
: do is
: public class Foo
: {
: public final static int LOCK_ARRAY_SIZE = 65536;
: public final static Object[] LOCK_ARRAY;
: static

m*t2005-11-08 08:11

13 楼

The Sun JDK javadoc for Integer.valueOf does specify something to that effect.
I wouldn't be suprised if other JVM vendors followed the suit.
That's a good point, though.

t*52005-11-08 08:11

14 楼

is it worth it to make it so complicated than just using the damn '
synchronized'?
and the tactic won't help your tree.
a thread reading a volatile data structure must use some kind of sync,
otherwise it's perfectly legal for JVM to feed the thread with stale copy.
"some kind of sync", because there are many ways of synchronization.
unless one reads and understands the language spec, which only 12 and half
guys in the world did, just use the damn 'synchronized'.

other

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

: Here is a piece of pseudo-code that does reading + insertion:
: public Integer search (Node currentNode, int i)
: {
: int v = currentNode.value.intValue ();
: if (i == v)
: return currentNode.value;
: if (i < v)
: {
: if (currentNode.left == null)
: {

m*t2005-11-08 08:11

15 楼

IIRC, Integer.valueOf(i) always returns the same Integer instance for the same
i, but I'm not sure about String.valueOf.
Regardless of that, even String.valueOf(i) also always returns the same String
instance, I wouldn't use it for synchronization, because it is also globally
available to any other code, and somebody else might be thinking "hey, why don
't we just do String.valueOf(i) and synchronize on that?!". 8-) So, as far as
that goes, I think coconut's lock token objects are a better solu

【在 r*****l 的大作中提到】

: If java treats String as sun specifies, can do
: synchronize (String.valueOf(i))

c*t2005-11-08 08:11

16 楼

hehe, we were talking about the same thing, although I think that choosing
HashSet is a bad idea.
The reason is that any modification to the HashSet would require this
hash table to be locked. Making modification a time consuming task.
In constrast, a Tree is actually faster since this tree is only growing.
Insertion on the tree node only effect the child nodes. Thus, a tree can
simultaneously handle multiple requests. Comparing to the cost of
synchronization, even for an unbalanced tree, it

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

:
: IIRC, Integer.valueOf(i) always returns the same Integer instance for the same
: i, but I'm not sure about String.valueOf.
: Regardless of that, even String.valueOf(i) also always returns the same String
: instance, I wouldn't use it for synchronization, because it is also globally
: available to any other code, and somebody else might be thinking "hey, why don
: 't we just do String.valueOf(i) and synchronize on that?!". 8-) So, as far as
: that goes, I think coconut's lock token objects are a better solu

c*t2005-11-08 08:11

17 楼

I know this DCL problem :)
http://www.javaworld.com/javaworld/jw-11-2001/jw-1116-dcl.html

still

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

:
: IIRC, Integer.valueOf(i) always returns the same Integer instance for the same
: i, but I'm not sure about String.valueOf.
: Regardless of that, even String.valueOf(i) also always returns the same String
: instance, I wouldn't use it for synchronization, because it is also globally
: available to any other code, and somebody else might be thinking "hey, why don
: 't we just do String.valueOf(i) and synchronize on that?!". 8-) So, as far as
: that goes, I think coconut's lock token objects are a better solu

t*52005-11-08 08:11

18 楼

same
no way dude...
if it does, there has to be some sync/lookup inside the method.
so reaBull just transfered the problem to somewhere he can't see.
String
globally
don
as

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

:
: IIRC, Integer.valueOf(i) always returns the same Integer instance for the same
: i, but I'm not sure about String.valueOf.
: Regardless of that, even String.valueOf(i) also always returns the same String
: instance, I wouldn't use it for synchronization, because it is also globally
: available to any other code, and somebody else might be thinking "hey, why don
: 't we just do String.valueOf(i) and synchronize on that?!". 8-) So, as far as
: that goes, I think coconut's lock token objects are a better solu

c*t2005-11-08 08:11

19 楼

hmm, the professor mentioned that there wasn't a general solution to this
problem. He said to use hash table to map i to lock if maximum # of lock
objects are known.
My new idea was:
1. still use the tree for insertion.
2. each thread use a hash map to cache to known path to existing integers.
(that is, if the path is not found in the local cache, then follow the
global tree and insert path to local. At the same time, check if the
integer exists, if not insert the integer into the g

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

: I know this DCL problem :)
: http://www.javaworld.com/javaworld/jw-11-2001/jw-1116-dcl.html
:
: still

m*t2005-11-08 08:11

20 楼

I didn't catch this one. It's good to know. ThreadLocal in 1.4/5.0 indeed has
become a lot of faster. Although I'm still not sure whether it's worth the
hassle, the synchronization issue in your algorithm has been dealt with for
sure.
What about the other point related to the worst scenario performance of
unbalanced trees?

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

: I know this DCL problem :)
: http://www.javaworld.com/javaworld/jw-11-2001/jw-1116-dcl.html
:
: still

c*t2005-11-08 08:11

21 楼

I just mailed this problem to a professor on this subject. I am not sure
if he would reply though.
Meanwhile, I have an idea in the work that I think that will solve the
worst case scenario (in fact any distribution of integer).
I will wait for his reply first :)

has

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

:
: I didn't catch this one. It's good to know. ThreadLocal in 1.4/5.0 indeed has
: become a lot of faster. Although I'm still not sure whether it's worth the
: hassle, the synchronization issue in your algorithm has been dealt with for
: sure.
: What about the other point related to the worst scenario performance of
: unbalanced trees?

c*t2005-11-08 08:11

22 楼

As for this problem, I actually treated it in a more general sense,
since we don't know how many integers, how frequent the first step
gets locked on, how much work is done inside criticale block, and
the randomess of i.
For simple ones, HashSet is suffice, but it's limitation is fairly
obvious. Of course we always try it first to see if is enough.
One may have to play around with hash side, hash formula etc.
If these failed, I think the tree solution is necessary unless you
have better ideas.