James Jarman's Devblog

Synchronisation and Locks

Posted in The IOs of Game Netcode on

We’ve already established you need to run your netcode framework on a different thread to your main game’s update/render loop, something which all netcode developers will agree is a requirement for writing good netcode. This means you’re already in danger of the threading and concurrency issues mentioned in the last post. So how do you ensure that you don’t run into these issues? Well, you have a few weapons in your arsenal to tackle the problem. The first one I’m going to discuss is locks.

Locks

Think of locks as your most basic weaponry against threading issues. The pistol with infinite ammo you switch back to after your power-up wears off. Locking is a synchronisation mechanism that ensures that only one thread can execute a piece of code at any given time. It does by forcing other threads to wait until the currently active thread is finished with the locked code.

Locks are such a common mechanism that I’m pretty sure all modern languages that support multi-threading also support locking. It’d be pretty disastrous if they didn’t. The main differences are the types of locks, the terminology and how they’re used. You usually have a couple of types available to you, such as object-level locks and method-level locks. Object-level locks are the bread and butter here and more complex locking mechanisms can be built upon them. In C# an object-level lock looks like this:

lock (this) {
  // Your synchronised code
}

In Java you achieve object-level locks using synchronized blocks, which are essentially the same thing:

synchronized (this) {
  // Your synchronised code
}

Unfortunately, in C++ you do not have a simple statement for object-level locking (although I’m sure you can create a template to do it). Instead, you need to instantiate a mutex (mutually exclusive) object (part of the C++ standard library) and perform the lock operation on that.

std::mutex mtx; // Declared in the class constructor
 
mtx.lock();
// Your synchronised code
mtx.unlock();

These code snippets will all do the same thing when multiple threads hit it at the same time. The first thread to request the lock will get it and be allowed to proceed to execute the code within the lock. All other threads will request the lock, but will be forced to wait (block) until the thread with the lock leaves the synchronised code, after which another thread will receive rights to the lock and proceed.

There are also method-level locks, which work similarly to the object-level locks, except work at the method level, synchronising everything inside a particular method. In C# this is achieved with the following:

[MethodImpl(MethodImplOptions.Synchronized)]
public void SynchronisedMethod() {
  // Your synchronised code
}

In Java, you use the same synchronized keyword as in object-level locking:

public synchronized void synchronisedMethod() {
  // Your synchronised code
}

C++ does not have a mechanism for method-level locking, but this can be easily achieved with a simple object-level lock. The method-level locking is just a convenience mechanism for object-level locking everything in a method.

Now, method-level locking and the examples I’ve shown for object-level locking have a pretty serious issue to take into consideration. A thread can achieve a lock on a method or an object while another thread has the same lock on a different object of the same class. This is because these types of locks are handled at the object level (locking against it’s own instance or a member object). For the most part this is exactly what is required, but sometimes there are situations in which you need to synchronise all instances of a particular class. This is called class-level locking and can be achieved in a couple of ways. You can perform an object-lock on a static object shared by all instances of a specific class, or you can do method-level locking on static methods.

Of course, with most coding concepts, there is a down-side to very up. With locking mechanisms, that is deadlocks.

Deadlocks

A deadlock is when a thread is indefinitely blocked by a lock and they usually occur when multiple threads are executing code that results in nested locks on. For example, let’s take the classic bank transfer scenario.

public class Account {
 
  private double balance;

  public Account(double balance) {
    this.balance = balance;
  }

  public void withdraw(double amount) {
    balance -= amount;
  }

  public void deposit(double amount) {
    balance += amount;
  }
 
}
 
public class Bank {
 
  public void transfer(Account from, Account to, double amount) {
    synchronized (from) {
      synchronized (to) {
        from.withdraw(amount);
        to.deposit(to);
      }
    }
  }
 
}

Both accounts are synchronized so that exclusive access is obtained and the program is assured that it can perform all operations required of the transfer without blocking. The deadlock arises when a Bank executes two opposing transfers between the same two accounts at the same time (separate threads).

final Account account1 = new Account(1000);
final Account account2 = new Account(1000);
final Bank bank = new Bank();
 
new Thread(new Runnable() {
  public void run() {
    bank.transfer(account1, account2, 500);
  }
}).start();
 
new Thread(new Runnable() {
  public void run() {
    bank.transfer(account2, account1, 500);
  }
}).start();

The result can vary depending on execution order, but if both threads manage to obtain their first lock, then a deadlock will occur. This is because both threads cannot obtain their second lock until the other thread releases it, resulting in both thread blocking indefinitely.

The primary reason behind deadlocks is bad software design. Deadlocks can easily be avoided if the developer takes a step back and designs the inter-thread communication first. If the program/system makes use of multiple threads, then a deadlock scenario should be at the forefront of the developer’s mind. I’ve seen a number of poorly written programs where the deadlock scenario isn’t even considered and, for the most part, the program runs fine, but occasionally a deadlock will occur. This is because the developer will just throw in a lock here or there to ensure they don’t run into concurrent modification exceptions and suddenly have methods with locks calling other methods with locks, resulting a nested deadlock. Of course, the way they solve this is to ensure the proper execution order by adding more locks, which as you can guess, just makes things worse.

In my experience, the best implementation of multi-threaded operation consists of very few locks, but in the right places. DESIGN YOUR MULTITHREADING FIRST! 🙂

Thread-safe and Concurrent Data Structures

So now you should understand how to synchronise your multithreaded code, while avoiding potential deadlocks. It will help you avoid the concurrency issues when writing good threaded netcode. Now, I’m going to briefly touch on a set of special data structures that are designed to further help you avoid concurrency issues and deadlocks.

Thread-safe and concurrent data structures are a set of data structures that follow a certain set of rules to ensure that race conditions do not happen. This is done through a variety of different methods, such as locking and atomic operations.

They take care of all of the concurrency issues without any of the potential deadlocks, making your life a lot easier. Java, C# and C++ all have a decent set of thread-safe data structures in their standard libraries, too many to go through here, but it’s definitely worth searching their respective documentations and read up on the specifics.

One thing you need to keep in mind though, even though the add and remove operations are thread-safe, any iterators or enumerations generated from these data structures may not be. Meaning, if you loop over all the elements in a thread-safe data structure, the resulting collection may not be thread-safe. So if another thread adds or removes an element to the data structure while the loop is being processed, you’ll end up with concurrent modification and a race condition causing unpredictable behaviour. Fortunately, these thread-safe data structures usually offer up some kind of fail-fast iterator or enumerator which will throw a concurrent modification exception when it detects that the underlying structure has been modified after it has been created, which can then be handled properly by the developer.

You can usually avoid the concurrent modification exception by using the correct concurrent data structure for the job and in the right place. I like to use a concurrent queue for inter-thread communication as it allows me to iterate through the queue in a thread-safe way using peek and pop operations (no need for iterators or enumerators), which I will show an example of in a later post.

This pretty much wraps up this post. It’s a bit longer than the previous ones but I wanted to finish with the multithreading so that I can actually get into some nitty-gritty netcode stuff next post 🙂 Hopefully you can take something away from this that will aid you in your game development, and as always, if you want to chat or pick my brains about anything you can either comment below, catch me on IRC (click Chat above) or fire me a tweet to @Jargon64.

Thanks for reading! 🙂