Concurrency and Deadlocks in Java: A Brief Introduction

In attempting to understand how concurrency works with java it is important to lay the foundation by discussing process management in operating systems before moving on to specific concurrency issues in java.

Process Management in Operating Systems

A process is an instance of a computer program that performs some action. A process can have multiple threads and can be controlled by a user, other programs or by the operating system that its running on. The operating system will execute processes sequentially and can be running multiple processes at any one time, this is called concurrency.

To further explain, a single computer processor runs instructions one at a time, so that a user can run several programs at once, time-sharing is performed. Time-sharing allows for programs to be in either “executed” or “waiting to be executed” state, this gives the illusion to the user that multiple processes are running at the same time but in reality the operating system is switching between them rapidly. An operating system run on a computer with multiple processors can execute instructions simultaneously for different processes.

Mutexes and Threads

A mutex or mutual exclusion is used in parallel programming to “lock” a shared resources so that only one thread can access it at a time whilst at the same time giving waiting tasks a place to wait for their turn. A popular way to remember this is to think of an airplane bathroom. Only one person can access the bathroom at one time, in this case the lock is the mutex so when the door is locked the bathroom is unavailable to the people waiting in queue.

In java every object has one monitor and mutex associated with it. A monitor is a piece of code which is guarded by a mutex. Whenever a thread accesses a synchronized method, the mutex is locked, conversely when the method is finished, the mutex is unlocked. This ensures that only one synchronized method is called at a time on a given object.

Deadlocks and Prevention

A deadlock occurs when two or more threads are waiting for each other to finish and so therefore cannot.

Lock Ordering

One way to prevent a deadlock is to assign an order to the locks and require that they are accessed in that order. This can only work if you know about all locks ahed of time so is not always practical.

Lock Timeout

You can also prevent deadlocks by having a timeout function on lock attempts. This means a thread will only try for so long to acquire the necessary locks before quitting (backing up), thus freeing all locks taken. It will then try again after a random amount of time during which other threads can try to access the necessary threads.

One of the drawbacks if you have lots of threads trying to acquire the same lock they might end up waiting the same amount of time and therefore trying to obtain a lock at the same time over and over.

Deadlock Detected

What do you do if you have a deadlock? You can release all the locks and wait a random amount of time before retrying. But this is can have the same problems as described by a lock timeout above. A better way to do this would be to assigned a priority to the threads so that only the highest priority thread/s backup.