Suzan Cioc
Reputation: 30097
I there a way to lock 2 or more locks or monitors atomically?
I there a way to lock 2 or more locks or monitors atomically? I mean, suppose my thread wishes to lock 2 locks and waits until both of them are free, i.e. never lock one then wait for another?
Upvotes: 4
Views: 227
Answers (3)
andreas
Reputation: 7415
You could use an additional lock.
Let's say you want to acquire the locks l_0, l_1, ..., l_n. To acquire all the locks atomically, introduce an additional lock l_extra:
synchronized (l_extra) {
synchronized (l_0) {
synchronized (l_1) {
// ...
}
}
}
Upvotes: 0
electroCutie
Reputation: 194
There is no way to acquire multiple monitors atomically.
A lock system could be designed to do something similar, albeit inefficiently.
Without more information about your use case it is difficult to prescribe any potential solution, but there is a pattern which would allow the safe acquisition of multiple locks with no potential for deadlock.
I know that isn't what you asked for, and I'd be glad to point you in a better direction with more details, but if your only desire was to avoid deadlock do this:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class LockSort{
private int ptr = 0;
private final Object[] locks;
private final Runnable toRun;
private LockSort(Runnable r, Object[] l){
locks = l;
Arrays.sort(locks, identCompare);
toRun = r;
}
private static final Comparator<Object> identCompare = new Comparator<Object>(){
@Override
public int compare(Object a, Object b){
return System.identityHashCode(a) - System.identityHashCode(b);
}
};
private void lockSingle(){
synchronized(locks[ptr++]){
dispatch();
}
}
private static final Map<Integer, MutableInteger> breakers = new HashMap<>();
private static MutableInteger getTieBreaker(Integer hash){
synchronized(breakers){
MutableInteger b = breakers.get(hash);
if(null != b){
b.val++;
return b;
}
breakers.put(hash, b = new MutableInteger(1));
return b;
}
}
private static void releaseTieBreaker(Integer hash){
synchronized(breakers){
MutableInteger b = breakers.get(hash);
if(0 == --b.val)
breakers.remove(hash);
}
}
private void breakTie(){
final Integer hash = System.identityHashCode(locks[ptr]);
try{
synchronized(getTieBreaker(hash)){
synchronized(locks[ptr++]){
dispatch();
}
}
}finally{
releaseTieBreaker(hash);
}
}
private void dispatch(){
if(ptr == locks.length)
toRun.run();
else if(ptr + 1 == locks.length || System.identityHashCode(locks[ptr]) != System.identityHashCode(locks[ptr + 1]))
lockSingle();
else
breakTie();
} import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class LockSort{
private int ptr = 0;
private final Object[] locks;
private final Runnable toRun;
private LockSort(Runnable r, Object[] l){
locks = l;
Arrays.sort(locks, identCompare);
toRun = r;
}
private static final Comparator<Object> identCompare = new Comparator<Object>(){
@Override import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class LockSort{
private int ptr = 0;
private final Object[] locks;
private final Runnable toRun;
private LockSort(Runnable r, Object[] l){
locks = l;
Arrays.sort(locks, identCompare);
toRun = r;
}
private static final Comparator<Object> identCompare = new Comparator<Object>(){
@Override
public int compare(Object a, Object b){
return System.identityHashCode(a) - System.identityHashCode(b);
}
};
private void lockSingle(){
synchronized(locks[ptr++]){
dispatch();
}
}
private static final Map<Integer, MutableInteger> breakers = new HashMap<>();
private static MutableInteger getTieBreaker(Integer hash){
synchronized(breakers){
MutableInteger b = breakers.get(hash);
if(null != b){
b.val++;
return b;
}
breakers.put(hash, b = new MutableInteger(1));
return b;
}
}
private static void releaseTieBreaker(Integer hash){
synchronized(breakers){
MutableInteger b = breakers.get(hash);
if(0 == --b.val)
breakers.remove(hash);
}
}
private void breakTie(){
final Integer hash = System.identityHashCode(locks[ptr]);
try{
synchronized(getTieBreaker(hash)){
synchronized(locks[ptr++]){
dispatch();
}
}
}finally{
releaseTieBreaker(hash);
}
}
private void dispatch(){
if(ptr == locks.length)
toRun.run();
else if(ptr + 1 == locks.length || System.identityHashCode(locks[ptr]) != System.identityHashCode(locks[ptr + 1]))
lockSingle();
else
breakTie();
}
public static void lockMultipleAndRun(Runnable toRun, Object... toLock){
new LockSort(toRun, toLock).dispatch();
}
public static void lockMultipleAndRun(Runnable toRun, Collection<Object> toLock){
new LockSort(toRun, toLock.toArray()).dispatch();
}
private static class MutableInteger{
int val;
MutableInteger(int i){
val = i;
}
}
public static void main(String args[]){
final int THREADS = 0 == args.length ? Runtime.getRuntime().availableProcessors() : Integer.valueOf(args[0]);
for(int j = 0; j < 1000; j++){
final int RUNID = j;
final Object locks[] = new Object[300];
for(int i = 0; i < 300; i++){
locks[i] = new Object(){
};
}
List<Thread> threads = new ArrayList<>(50);
for(int i = 0; i < THREADS; i++){
final int ID = i;
Thread t = new Thread(new Runnable(){
@Override
public void run(){
for(int i = 0; i < 1000; i++){
int a = (int) Math.floor(Math.random() * 300.0);
int b = (int) Math.floor(Math.random() * 300.0);
final int l = Math.min(a, b);
final int h = Math.max(a, b);
final int CT = i;
lockMultipleAndRun(new Runnable(){
@Override
public void run(){
System.out.println(RUNID + ":" + ID + " @ " + CT + " w/ " + l + "-" + h);
}
}, Arrays.copyOfRange(locks, l, h));
}
}
});
t.start();
threads.add(t);
}
for(Thread t : threads){
try{
t.join();
}catch(InterruptedException e){
throw new RuntimeException(e);
}
}
}
}
}
public int compare(Object a, Object b){
return System.identityHashCode(a) - System.identityHashCode(b);
}
};
private void lockSingle(){
synchronized(locks[ptr++]){
dispatch();
}
}
private static final Map<Integer, MutableInteger> breakers = new HashMap<>();
private static MutableInteger getTieBreaker(Integer hash){
synchronized(breakers){
MutableInteger b = breakers.get(hash);
if(null != b){
b.val++;
return b;
}
breakers.put(hash, b = new MutableInteger(1));
return b;
}
}
private static void releaseTieBreaker(Integer hash){
synchronized(breakers){
MutableInteger b = breakers.get(hash);
if(0 == --b.val)
breakers.remove(hash);
}
}
private void breakTie(){
final Integer hash = System.identityHashCode(locks[ptr]);
try{
synchronized(getTieBreaker(hash)){
synchronized(locks[ptr++]){
dispatch();
}
}
}finally{
releaseTieBreaker(hash);
}
}
private void dispatch(){
if(ptr == locks.length)
toRun.run();
else if(ptr + 1 == locks.length || System.identityHashCode(locks[ptr]) != System.identityHashCode(locks[ptr + 1]))
lockSingle();
else
breakTie();
}
public static void lockMultipleAndRun(Runnable toRun, Object... toLock){
new LockSort(toRun, toLock).dispatch();
}
public static void lockMultipleAndRun(Runnable toRun, Collection<Object> toLock){
new LockSort(toRun, toLock.toArray()).dispatch();
}
private static class MutableInteger{
int val;
MutableInteger(int i){
val = i;
}
}
public static void main(String args[]){
final int THREADS = 0 == args.length ? Runtime.getRuntime().availableProcessors() : Integer.valueOf(args[0]);
for(int j = 0; j < 1000; j++){
final int RUNID = j;
final Object locks[] = new Object[300];
for(int i = 0; i < 300; i++){
locks[i] = new Object(){
};
}
List<Thread> threads = new ArrayList<>(50);
for(int i = 0; i < THREADS; i++){
final int ID = i;
Thread t = new Thread(new Runnable(){
@Override
public void run(){
for(int i = 0; i < 1000; i++){
int a = (int) Math.floor(Math.random() * 300.0);
int b = (int) Math.floor(Math.random() * 300.0);
final int l = Math.min(a, b);
final int h = Math.max(a, b);
final int CT = i;
lockMultipleAndRun(new Runnable(){
@Override
public void run(){
System.out.println(RUNID + ":" + ID + " @ " + CT + " w/ " + l + "-" + h);
}
}, Arrays.copyOfRange(locks, l, h));
}
}
});
t.start();
threads.add(t);
}
for(Thread t : threads){
try{
t.join();
}catch(InterruptedException e){
throw new RuntimeException(e);
}
}
}
}
}
public static void lockMultipleAndRun(Runnable toRun, Object... toLock){
new LockSort(toRun, toLock).dispatch();
}
public static void lockMultipleAndRun(Runnable toRun, Collection<Object> toLock){
new LockSort(toRun, toLock.toArray()).dispatch();
}
private static class MutableInteger{
int val;
MutableInteger(int i){
val = i;
}
}
public static void main(String args[]){
final int THREADS = 0 == args.length ? Runtime.getRuntime().availableProcessors() : Integer.valueOf(args[0]);
for(int j = 0; j < 1000; j++){
final int RUNID = j;
final Object locks[] = new Object[300];
for(int i = 0; i < 300; i++){
locks[i] = new Object(){
};
}
List<Thread> threads = new ArrayList<>(50);
for(int i = 0; i < THREADS; i++){
// Shuffle the locks per-thread to see more highly chaotic and difficult to deal with locking behavior
final Object[] myLocks = new Object[300];
System.arraycopy(locks, 0, myLocks, 0, 300);
for(int k = 0; k < 300; k++){
int a = (int) Math.floor(Math.random() * 300.0);
int b = (int) Math.floor(Math.random() * 300.0);
Object o = myLocks[a];
myLocks[a] = myLocks[b];
myLocks[b] = o;
}
final int ID = i;
Thread t = new Thread(new Runnable(){
@Override
public void run(){
for(int i = 0; i < 1000; i++){
int a = (int) Math.floor(Math.random() * 300.0);
int b = (int) Math.floor(Math.random() * 300.0);
final int l = Math.min(a, b);
final int h = Math.max(a, b);
final int CT = i;
lockMultipleAndRun(new Runnable(){
@Override
public void run(){
System.out.println(RUNID + ":" + ID + " @ " + CT + " w/ " + l + "-" + h);
}
}, Arrays.copyOfRange(locks, l, h));
}
}
});
t.start();
threads.add(t);
}
for(Thread t : threads){
try{
t.join();
}catch(InterruptedException e){
throw new RuntimeException(e);
}
}
}
}
}
It looks like a lot of recursive calls, but let the JIT worry about that. So long as all your code that needs to acquire multiple locks does this then you won't ever deadlock. I included the test main method so you can test it yourself.
Locks are always acquired in the same order except when two or more identity hashes in a lock chain are the same (a vanishingly rare event) in which case a tie breaker unique to that hash is acquired first to ensure that only one thread trying to lock more than one object with that particular hash code can proceed.
It should be obvious how this could be extended to any other lock type but be wary of duplicate non-reentrant locks as that will cause deadlocks. Synchronized blocks are reentrant so there is no risk of that here. It could also easily be made to work trivially with Callable types.
Upvotes: 1
Anders R. Bystrup
Reputation: 16060
I think that is equivalent to the Dining Philosophers problem - visiting the Wikipedia entry can give you pointers to several possible solutions.
Cheers,
Upvotes: 0
Related Questions
- Is there a way to set a lock on AtomicReference
- Is it possible to use Java intrinsic locks explicitly?
- Atomically grab multiple locks
- java synchronizing access to different critical sections
- Multiple lock single unlock in Java?
- Multiple locks - Behind the scene
- Java locking other critical sections
- Managing multiple locks
- Can several threads hold a lock on the same monitor in Java?
- Release multiple locks atomically in Java