synchronized block - lock more than one object

Question

I'm modelling a game where multiple players (threads) move at the same time. The information of where a player is located at the moment is stored twice: the player has a variable "hostField" that references to a field on the board and every field has an ArrayList storing the players that are currently located at this field.

I'm not very happy with the fact that I have redundant information, but I found no way avoiding that without looping through a big dataset.

However, when a player moves from one field to another, I'd like to make sure (1) the redundant information stays linked (2) nobody else is manipulating the field at the moment.

Therefore I need to do something like

synchronized(player, field) {
    // code
}

Which is not possible, right?

What should I do? :)

Solution 1

In fact, synchronization is for code, not objects or data. The object reference used as a parameter in synchronized block represent the lock.

So if you have code like:

class Player {

  // Same instance shared for all players... Don't show how we get it now.
  // Use one dimensional board to simplify, doesn't matter here.
  private List<Player>[] fields = Board.getBoard(); 

  // Current position
  private int x; 

  public synchronized int getX() {
    return x;
  }

  public void setX(int x) {
    synchronized(this) { // Same as synchronized method
      fields[x].remove(this);
      this.x = x;
      field[y].add(this);
    }
  }
}

Then Despite being in the synchronized block the access to field is not protected because the lock is not the same (it being on different instances). So your List of Players for your board can become inconsistent and cause runtime exceptions.

Instead if you write the following code, it will work because we have only one shared lock for all players:

class Player {

  // Same instance shared for all players... Don't show how we get it now.
  // Use one dimensional board to simplify, doesn't matter here.
  private List<Player>[] fields; 

  // Current position
  private int x;

  private static Object sharedLock = new Object(); // Any object's instance can be used as a lock.

  public int getX() {
    synchronized(sharedLock) {
      return x;
    }
  }

  public void setX(int x) {
    synchronized(sharedLock) {
      // Because of using a single shared lock,
      // several players can't access fields at the same time
      // and so can't create inconsistencies on fields.
      fields[x].remove(this); 
      this.x = x;
      field[y].add(this);
    }
  }
}

Be sure to use only a single lock to access all the players or your board's state will be inconsistent.

Solution 2

A trivial solution would be

synchronized(player) {
    synchronized(field) {
        // code
    }
}

However, make sure that you always lock the resources in the same order to avoid deadlocks.

Note that in practice, the bottleneck is the field, so a single lock on the field (or on a dedicated, common lock object, as @ripper234 rightly pointed out) may suffice (unless you are concurrently manipulating players in other, conflicting ways).

Solution 3

When using concurrency, it is always difficult to give good responses. It highly depends of what your are really doing and what really matter.

From my understanding, a player move involve :

1 Updading player position.

2 Removing the player from previous field.

3 Adding player to new field.

Imagine you use several locks at the same time but aquire only one at a time : - Another player can perfectly look at the wrong moment, basically between 1&2 or 2&3. Some player can appear to have disapeared from the board for exemple.

Imagine your do imbricked locking like this :

synchronized(player) {
  synchronized(previousField) {
    synchronized(nextField) {
      ...
    }
  }
}

The problem is... It don't work, see this order of execution for 2 threads :

Thread1 :
Lock player1
Lock previousField
Thread2 :
Lock nextField and see that player1 is not in nextField.
Try to lock previousField and so way for Thread1 to release it.
Thread1 :
Lock nextField
Remove player1 from previous field and add it to next field.
Release all locks
Thread 2 : 
Aquire Lock on previous field and read it : 

Thread 2 think that player1 as disapeared from the whole board. If this is a problem for your application, you can't use this solution.

Additionnal problem for imbriqued locking : threads can become stuck. Imagine 2 players : they exchange their position at exactly the same time :

player1 aquire it's own position at the same time
player2 aquire it's own position at the same time
player1 try to acquire player2 position : wait for lock on player2 position.
player2 try to acquire player1 position : wait for lock on player1 position.

=> Both players are blocked.

Best solution in my opinion is to use only one lock, for the whole state of the game.

When a player want to read the state, it lock the whole game state (players & board), and make a copy for its own usage. It can then process without any lock.

When a player want to write the state, it lock the whole game state, write the new state and then release the lock.

=> Lock is limited to read/write operations of the game state. Player can perform "long" examination of the board state on their own copy.

This prevent any inconsistant state, like a player in several field or none, but don't prevent that player can use "old" state.

It can appear weird, but it is the typical case of a chess game. When you are waiting for the other player to move, you see the board as before the move. You don't know what move the other player will make and until he has finally moved, you work on an "old" state.

Solution 4

You should not feel bad about your modelling - this is only a two way navigable association.

If you take care (as in the other answers told) to manipulate atomic, e.g. in the Field methods, thats fine.

public class Field {

  private Object lock = new Object();

  public removePlayer(Player p) {
    synchronized ( lock) {
      players.remove(p);
      p.setField(null);
    }
  }

  public addPlayer(Player p) {
    synchronized ( lock) {
      players.add(p);
      p.setField(this);
    }
  }
}

It would be fine if "Player.setField" were protected.

If you need further atomicity for "move" semantics, go one level up for board.

View more solutions

Comments

[Vishy]

Since the operations are very short lived, you may find that using just one global lock performs well enough that you cannot tell the difference. Using one lock might limit yourself to 200K moves per second (is that enough?) but may simplify your code and you won't get a deadlock.

[ripper234]

I just wanted to write this, and add that you should use dedicated lock objects and not lock on the business objects themselves, when two guys from work popped in and needed my help :) There goes the reputation boost.

[Rekin]

+1: straight to the point. As a side note: One could build a class with both field in it and use it as a player position model. With this, there could only one lock, but it may not fit the existing programming model at all.

[Péter Török]

@ripper234, oh those coworkers - always bothering with trivia and robbing our valuable time which we could otherwise spend peacefully on SO ;-)

[Péter Török]

@Rekin, this could be a very nice solution if it allowed us to limit the scope of changes to a single (reference) change, which can then be performed atomically using an AtomicReference. This would allow us to try a nonblocking (compare-and-swap) algorithm, which probably performed better in this case. However, the problem is that in this case we still have two references to the position object, so we still need to do two updates atomically - thus locking can't be avoided :-(

[speendo]

Thanks Péter Török! I was thinking on that solution too, but I don't know if this solution is really rockstable. Couldn't there be a situation where player and field get out of sync, if a manipulation (e.g. from another player) just happens after PLAYER is locked but before FIELD is locked?

[speendo]

I didn't completely understand the "private Object lock = new Object();" pattern. I read it before, but didn't really understand it... but if I got you right, you just make sure, that both changes happen at the same time, right? Why don't you lock Field but "lock"?

[mtraut]

@Marcel as @ripper234 already stated - this is good practice as it hides the monitor used for locking from public access. Anyone can lock on a field instance, only field on its private "lock". In your example this doesn't make a difference. Just use it as good style. This pattern will later on for example allow for increasing concurrency in more complicated scenarios by using more lock objects etc.

[ripper234]

Actually, I admit that 9 out of 10 I'm asking questions on SO and not answering them. I was just annoyed that this one time I was really going to write a good answer and got rudely diverted :)

[ripper234]

@Marcel - if you're consistent (always locking, always in the same order), then yes, this is rock solid.

[Péter Török]

@Marcel, since any changes are done only after acquiring both locks, I think this solution is safe. If the field has been locked by another thread, this thread will block upon entering the inner sync block. Once the other thread has finished its changes and releases the lock, this thread can proceed. Due to using locks, all changes made by the other thread is guaranteed to be visible to this thread. OTOH if the other thread manipulates this player, it must have already acquired the player lock, so this thread can't.

[speendo]

does this also hold if one player wants to manipulate another thread? let's think on the following situation: Player 1 is a ghost (field A), player 2 is pacman (field B). Pacman starts its move: "synchronized(pacman)". In the meantime ghost starts its move "synchronized(ghost), synchronized(field A) - move to field B, see pacman, ask pacman to die -> not possible due to lock -> wait" now pacman goes on "synchronized(field B) - move to field A -> not possible due to lock -> wait. Isn't this a deadlock?

[Péter Török]

@Marcel, yes, because here the lock order is not consistent between all cases. Your thread P acquires the lock on pacman, then blocks on field, while thread G has the lock on field, and after that tries to acquire the lock on pacman. This is why lock order consistency is so important! As a side note, here pacman can't move since the ghost still holds the lock on field. But another problem with your scheme is that evaluation of the current situation should only happen after all players have made their move in the current turn.

[speendo]

hm, I get your point, but it seems not to be applicable for my problem then... my programm is not round based, so I'll have a problem here :)

[Péter Török]

@Marcel, maybe my last comment doesn't apply then - I am not a game developer. I just don't see how you avoid the pacman getting caught by the ghost before it had the chance to make its actual move (or the other way around: evading the ghost before it had the chance to catch it).

[speendo]

it should be avoided by first come, first serve: if pacman is the first to move field B and pacman itself should be locked in one step, so ghost wouldn't have the chance to move to field B (as it is locked). If ghost is the first to move he should lock field B just before he looks for pacman on field B. If pacman is still on Field B he would not have the chance to move away, is he would have to wait until field B is unlocked again. In my opinion a problem arises due to the fact that locking happens in two steps - I get a problem if another thread "grabs away" the fields lock.

[speendo]

yes, using one lock would probably work (aswell as locking the whole field or locking Player.class). I'm afraid I can't go this way, because the specification of my exercise says I mustn't use too big locks... I even tried small locks vs. big locks, but found out that my program really runs way faster with small locks. Thank you once more for your long answer! I'd love to support you gaining points! :)

[AMDG]

about the player1 and player2 deadlock due to acquisition of own coordinates, don't use synchronized and make coordinates volatile, should prevent deadlock so that the following can happen safely: >player1 try to acquire player2 position; >player2 try to acquire player1 position; In a sort of way, volatile creates an imaginary "shared lock" in which multiple threads can "lock" onto the coordinates because the value is always updated in the respective thread's stack.

[Gordon]

I know this is an old q/a, but your model looks like nonsense. Thread1 has locked previousField. Thread2 has locked nextFIeld and is waiting for on a lock for previousField currently held by Thread1. There's no way Thread1 gets past "Lock nextField" to "remove player1". What you have here is two deadlocked threads, not a "missing Player1 from the board" as you suggest. Player1 can't be removed at all, because the deadlock happens before the removal does.