Distributed systems comprise multiple independent pieces of code executing in parallel, or concurrently, on many processing nodes across multiple locations. Any distributed system is hence by definition a concurrent system.
This chapter, however, is concerned with concurrent behavior in our systems on a single node. By explicitly writing our software to perform multiple actions concurrently, we can optimize the processing and resource utilization on a single node, and hence increase our processing capacity both locally and system-wide.
While one program is waiting for an I/O event, the operating system schedules another program to execute. By explicitly structuring our software to have multiple activities that can be executed in parallel, the operating system can schedule tasks that have work to do while others wait for I/O.
The primary way to structure a software system as concurrent activities is to use threads.
Every software process has a single thread of execution by default. This is the thread that the operating system manages when it schedules the process for execution. In Java, for example, the main() function you specify as the entry point to your code defines the behavior of this thread. This single thread has access to the program’s environment and resources such as open file handles and network connections. As the program calls methods in objects instantiated in the code, the program’s runtime stack is used to pass parameters and manage variable scopes.
In your systems, you can use programming language features to create and execute additional threads. Each thread is an independent sequence of execution and has its own runtime stack to manage local object creation and method calls. Each thread also has access to the process’ global data and environment.
A comparison between a single-threaded and multithreaded process is as shown below.
The system scheduler (in Java, this lives in the Java virtual machine [JVM]) controls the order of thread execution. From the programmer’s perspective, the order of execution is nondeterministic.
Once the scheduler has given a thread an execution time slot on a CPU, it can interrupt the thread after a specified time period and schedule another one to run. This interruption is known as preemption. Preemption ensures each thread is given an opportunity to make progress. Hence the threads run independently and asynchronously until completion, and the scheduler decides which thread runs when based on a scheduling algorithm.
The basic problem in concurrent programming is coordinating the execution of multiple threads so that whatever order they are executed in, they produce the correct answer. Given that threads can be started and preempted nondeterministically, any moderately complex program will have essentially an infinite number of possible orders of execution. These systems aren’t easy to test.
There are two fundamental problems that all concurrent programs need to avoid.
Nondeterministic execution of threads implies that the code statements that comprise the threads:
- Will execute sequentially as defined within each thread.
- Can be overlapped in any order across threads.
Unfortunately, totally independent threads are not how most multithreaded systems behave. If you refer back to figure above, you will see that multiple threads share the global data within a process.
Threads can use shared data structures to coordinate their work and communicate status across threads. For example, we may have threads handling requests from web clients, one thread per request. We also want to keep a running total of how many requests we process each day. When a thread completes a request, it increments a global RequestCounter object that all threads share and update after each request. At the end of the day, we know how many requests were processed.
In Java, to perform an increment of a counter, the CPU must:
- Load the current value into a register.
- Increment the register value.
- Write the results back to the original memory location.
This simple increment is actually a sequence of three machine-level operations.
As the increment operation is not atomic at the machine level, one thread can load the counter value into a CPU register from memory, but before it writes the incremented value back, the scheduler preempts the thread and allows another thread to start. This thread loads the old value of the counter from memory and writes back the incremented value. Eventually the original thread executes again and writes back its incremented value, which just happens to be the same as what is already in memory.
When we lose updates in this manner, it is called a race condition. Race conditions can occur whenever multiple threads make changes to some shared state, in this case a simple counter. Essentially, different interleavings of the threads can produce different results.
Race conditions are evil! Luckily, eradicating them is straightforward if you take a few precautions.
The key is to identify and protect critical sections. A critical section is a section of code that updates shared data structures and hence must be executed atomically if accessed by multiple threads. The example of incrementing a shared counter is an example of a critical section.
As a rule of thumb, you should keep critical sections as small as possible so that the serialized code is minimized. This can have positive impacts on performance and hence scalability.
Deadlocks in multithreading occur when two or more threads are unable to proceed with execution because each is waiting for the other to release resources.
To solve multithreading deadlocks, consider the following strategies:
-
Resource Ordering: Assign a unique identifier to each resource. Ensure that threads always request resources in increasing order of their identifiers.
-
Timeout: Set a maximum time for which a thread can hold a resource. If the thread doesn't finish in this time, it releases the resource.
-
Deadlock Detection: Regularly check for deadlocks, and when detected, stop and restart one of the threads to break the deadlock.
-
Nested Locks: Ensure that if a thread needs multiple locks, it must obtain them in a nested manner and release them in the reverse order.
-
Lock Timeout: Introduce a maximum wait time for a thread to obtain a lock. If it doesn't get the lock in that time, it backs off and retries later.
-
Single Threaded Acquisition: Design a system where a single thread is responsible for acquiring all the resources, which it then distributes among other threads.
In Java, threads in multithreaded systems are managed by a preemptive, priority-based scheduler. Every thread has a priority, typically defaulting to 5, ranging from 0 to 10. Threads get their priority from their parent thread. The scheduler cycles threads through four states:
- Created: Thread objects have been initialized but haven't run the
start()method. - Runnable: Threads ready to execute. The scheduler uses a FIFO approach and threads can be in this state until they're blocked or preempted.
- Blocked: Threads waiting for events, locks, or other conditions. Once conditions are met, they return to the runnable state.
- Terminated: Threads that have finished execution or have been stopped.
Threads are preempted either by higher-priority threads or when a system-defined time slice expires. This mechanism ensures CPU fairness across threads. Higher-priority threads generally handle quick, event-driven tasks, while lower-priority ones handle background tasks, maximizing CPU usage.
There are many problems that require threads with different roles to coordinate their activities, e.g., the classic producer-consumer problem. Producers generate and send messages via a shared FIFO buffer to consumers. Consumers retrieve these messages, process them, and then ask for more work from the buffer.
The buffer, however, has limited space. When it's full, producers must wait until there's room, and if consumers are faster than producers, they wait for new items.
One solution is polling, where producers or consumers repeatedly check the buffer's status. But this approach, also known as busy waiting, can be resource-intensive.
A more efficient method has producers and consumers block until they can proceed. In this way, no resources are wasted. For signaling when to proceed:
- A producer, after adding to the buffer, signals any waiting consumers that an item is available.
- A consumer, after retrieving an item, signals any waiting producers that there's space in the buffer.
Many multithreaded systems need to create and manage a collection of threads that perform similar tasks. For example, in the producer-consumer problem, we can have a collection of producer threads and a collection of consumer threads, all simultaneously adding and removing items, with coordinated access to the shared buffer.
Barrier synchronization is a concept in multithreaded systems where threads are required to wait at a certain point in their execution until all other threads reach that same point. This concept can be likened to a family dinner scenario, where no member starts eating until everyone is seated at the table. For instance, in a multithreaded image-processing application, different segments of an image might be handed over to separate threads for processing. The final image isn't considered fully processed until every thread completes its task. To ensure all threads synchronize at a particular point, barrier synchronization is employed. Visually, when individual threads reach this synchronization point, they pause. Once all threads arrive at this barrier, they simultaneously continue their respective processes.
This chapter emphasized the fundamental importance of understanding threads and concurrency in the realm of scalable distributed systems. Even if you aren't directly writing multithreaded code, it's crucial to understand how your code operates in a multithreaded environment, particularly concerning thread safety. Additionally, to optimize system performance, one must grasp the impact of adjusting threading configurations.
While the programming constructs might differ across languages, the core challenges, like avoiding race conditions and deadlocks, remain consistent.
Foundations of Scalable Systems By Ian Gorton