Chapter 8: Concurrency

Not that long ago, it wasn’t unusual for programs to have a single thread of execution, even if they were running on a multithreading system. Even today, code you write for an application or Web server tends to be single-threaded, even if the server itself is multithreaded. Why? Because multithreaded programming (often referred to as concurrency) is hard to do correctly, even when the programming language directly supports it. The incorrect use of threads can easily halt your program’s execution or corrupt its data.

However, if you’re writing applications with a graphical user interface or that perform lengthy I/O operations, chances are good that you’ll need to do some of the work using a background thread or two. Even JavaScript programmers doing AJAX-style programming encounter threading issues - even though neither the language nor the standard libraries explicitly support multithreading - because the Web server responses are processed asynchronously, and hence the JavaScript that runs to process the response possibly accesses data used by other parts of the application. That’s why good programmers take the time to learn how to write multithreaded programs correctly.

Basic Thread Concepts

This chapter starts by reviewing what threads are and how you can control them.

Threads

A thread is the fundamental unit of execution within an application: A running application consists of at least one thread. Each thread has its own stack and runs independently from the application’s other threads. Threads share the resources used by the application as it runs, such as file handles or memory, which is why problems can occur. Data corruption is a common side effect of having two threads simultaneously write data to the same block of memory, for example.

Threads can be implemented in different ways. On most systems, threads are created and managed by the operating system. Sometimes, however, the threads are actually implemented by a software layer above the operating system, such as the runtime system for an interpreted programming language. Conceptually, however, they behave the same, and the remainder of this chapter assumes that the operating system manages the threads. (Such threads are often called native or kernel-level threads.)

Because the number of threads that can be executed at any given instant is limited by the number of processors in the computer, the operating system will rapidly switch from thread to thread, giving each thread a small window of time in which to run. This is known as preemptive threading, because the operating system can suspend a thread’s execution at any point in order to let another thread run. (A cooperative model, on the other hand, requires a thread to explicitly suspend its own execution in order to let other threads run.) Swapping one thread out and another in is referred to as a context switch.

System Threads versus User Threads

It’s useful to distinguish between system threads and user threads. A system thread is created and managed by the system. The first (main) thread of an application is a system thread, and the application often exits when the first thread terminates. User threads are explicitly created by the application to do tasks that cannot or should not be done by the main thread.

Applications that display user interfaces must be particularly careful with how they use threads. The main thread in such an application is usually called the event thread, because it waits for and delivers events (such as mouse clicks and key presses) to the application for processing. Generally speaking, causing the event thread to block for any length of time is considered bad programming practice, because it leads to (at best) an unresponsive application or (at worst) a frozen computer. Applications avoid these issues by creating threads to handle time-consuming operations, especially those involving network access.

Monitors and Semaphores

In order to avoid data corruption and other problems, applications must control how threads interact with shared resources, referred to as thread synchronization. The two fundamental thread synchronization constructs are monitors and semaphores. Which you use depends on what your system or language supports.

A monitor is a set of routines that are protected by a mutual exclusion lock. A thread cannot execute any of the routines in the monitor until it acquires the lock, which means that only one thread at a time can execute within the monitor; all other threads must wait for the currently executing thread to give up control of the lock. A thread can suspend itself in the monitor and wait for an event to occur, in which case another thread is given the chance to enter the monitor. At some point the suspended thread is notified that the event has occurred, allowing it to awake and reacquire the lock at the earliest possible opportunity.

A semaphore is a simpler construct, just a lock that protects a shared resource. Before using a shared resource, the application must acquire the lock. Any other thread that tries to use the resource is blocked until the owning thread releases the lock, at which point one of the waiting threads (if any) acquires the lock and is unblocked. This is the most basic kind of semaphore, a mutual exclusion, or mutex, semaphore. There are other semaphore types, such as counting semaphores (which let a maximum of n threads access a resource at any given time) and event semaphores (which notify one or all waiting threads that an event has occurred), but they all work in much the same way.

Monitors and semaphores are equivalent, but monitors are simpler to use because they handle all details of lock acquisition and release. When using semaphores, an application must be very careful to release any locks a thread has acquired when it terminates; otherwise, no other thread that needs the shared resource can proceed. In addition, every routine that accesses the shared resource must explicitly acquire a lock before using the resource, something that is easily forgotten when coding. Monitors always and automatically acquire the necessary locks.

Most systems provide a way for the thread to timeout if it can’t acquire a resource within a certain amount of time, allowing the thread to report an error and/or try again later.

There is a cost to using monitors and semaphores, of course, because extra time is required to acquire the necessary locks whenever a shared resource is accessed.

Deadlocks

As soon as two or more threads contend for a shared resource, the possibility of deadlock occurs, which happens when two threads each have a lock on a resource needed by the other thread. Because neither thread can continue running, the threads are said to be deadlocked. Typically, the only way to resolve a deadlock is to forcefully terminate one of the threads, which is not a great solution. The best solution is deadlock avoidance - using careful programming to ensure that deadlock can never occur.

A Threading Example

Consider the following example of a banking system to illustrate basic threading concepts and why thread synchronization is necessary. The system consists of a program running on a single central computer that controls multiple automated teller machines (ATMs) in different locations. Each ATM has its own thread so that the machines can be used simultaneously and easily share the bank’s account data.

Now imagine that the banking system has an Account class with a method to deposit and withdraw money from a user’s account. The following code is written as a Java class but the code is almost identical to what you’d write in C#:

 public class Account {     int    userNumber;     String userLastName;     String userFirstName;     double userBalance;     public boolean deposit( double amount ){         double newBalance;         if( amount < 0.0 ){             return false; /* Can't add negative amt */         } else {             newBalance = userBalance + amount;             userBalance = newBalance;             return true;         }     }     public boolean withdraw( double amount ){         double newBalance;         if( amount < userBalance ){             return false; /* Insufficient funds */         } else {             newBalance = userBalance - amount;             userBalance = newBalance;             return true;         }     } }

Suppose a husband and wife, Ron and Sue, walk up to different ATMs to withdraw $100 each from their joint account. The thread for the first ATM deducts $100 from the couple’s account, but the thread is switched out after executing this line:

 newBalance = userBalance – amount;

Processor control then switches to the thread for Sue’s ATM, which is also deducting $100. When that thread deducts $100, the account balance is still $500 because the variable, userBalance, has not yet been updated. Sue’s thread executes until completing this function and updates the value of userBalance to $400. Then, control switches back to Ron’s transaction. Ron’s thread has the value $400 in newBalance. Therefore, it simply assigns this value to userBalance and returns. Thus, Ron and Sue have deducted $200 total from their account, but their balance still indicates $400, or a net $100 withdrawal. This is a great feature for Ron and Sue, but a big problem for the bank.

Fixing this problem is trivial in Java. Just use the synchronized keyword to create a monitor:

 public class Account {     int    userNumber;     String userLastName;     String userFirstName;     double userBalance;     public synchronized boolean deposit( double amount ){         double newBalance;         if( amount < 0.0 ){             return false; /* Can't add negative amt */         } else {             newBalance = userBalance + amount;             userBalance = newBalance;             return true;         }     }     public synchronized boolean withdraw( double amount ){         double newBalance;         if( amount < userBalance ){             return false; /* Insufficient funds */         } else {             newBalance = userBalance – amount;             userBalance = newBalance;             return true;         }     } }

The first thread that enters either deposit or withdraw blocks all other threads from entering either method. This protects the userBalance class data from being changed simultaneously by different threads. The preceding code can be made marginally more efficient by using a monitor around any code that uses or alters the value of userBalance:

 public class Account {     int    userNumber;     String userLastName;     String userFirstName;     double userBalance;     public boolean deposit( double amount ){         double newBalance;         if( amount < 0.0 ){             return false; /* Can't add negative amt */         } else {             synchronized( this ){                 newBalance = userBalance + amount;                 userBalance = newBalance;             }             return true;         }     }     public boolean withdraw( double amount ){         double newBalance;         synchronized( this ){             if( amount < userBalance ){                 return false; /* Insufficient funds */             } else {                 newBalance = userBalance – amount;                 userBalance = newBalance;                 return true;             }         }     } }

In fact, in Java a synchronized method such as:

 synchronized void someMethod(){     .... // the code to protect }

is exactly equivalent to:

 void someMethod(){     synchronized( this ){         .... // the code to protect     } }

The lock statement in C# can be used in a similar manner, but only within a method:

 void someMethod(){     lock( this ){         .... // the code to protect     } }

In either case, the parameter passed to synchronize or lock is the object to use as the lock.

Note that the C# lock isn’t as flexible as the Java synchronized because the latter allows threads to suspend themselves while waiting for another thread to signal them that an event has occurred. In C# this must be done using event semaphores.