What is multithreading?
Multithreading allows a single process to execute multiple parts of a program simultaneously.
Concurrency and Parallelism
Concurrency is the ability to handle multiple tasks at the same time. A computer can run tasks concurrently even if it only has a single CPU. The operating system will schedule the execution of concurrent tasks by time-slicing. When one task has finished its allotted number of CPU cycles, another task will be selected to run.
Concurrency is useful for creating responsive applications and reacting quickly to requests or events. An good example would be a web server. A web server needs to respond quickly to many concurrent requests. It is not always predictable how long each request will take to handle. Handling web requests in a synchronous manner would be very inefficient. Multithreading allows these requests to be handled asynchronously.
Parallelism is the technique of splitting a computationally intensive job into smaller tasks which can be run independently. On a multiprocessor system, these independent tasks can be shared between the processing units to make the maximum use of the system’s resources.
What are the types of multithreading architecture?
A well known classification of multithreading architectures is Flynn’s Taxonomy. Architectures can be characterised in one of the following ways:
- SISD – single instruction, single data
- SIMD – single instruction, multiple data
- MISD – multiple instruction, single data
- MIMD – multiple instruction, multiple data
MIMD is the most flexible architecture. For most developers, this is the only environment they will need to be familiar with.
What common problems are associated with multithreading?
- Data race
- Race condition
- Deadlock
- Livelock
- Starvation
- Priority inversion
A data race occurs when one thread modifies an object in memory whilst another thread is reading it.
A race condition occurs when the ordering of interleaved operations is unpredictable leading to undesired results. An example would be two people working in parallel to make a sandwich. One person is responsible for adding the bread layers and another responsible for adding the filling. If they fail to synchronise, the order of the layers will be wrong and the sandwich will be rather disappointing.
A deadlock occurs when two threads are holding a resource and each thread is trying to access a resource that the other is holding. An example is a hostage handover situation. The kidnappers are holding the hostage and won’t release them until they get the money. The police have the money but won’t relinquish it until the hostage is handed over.
In multithreaded programming, deadlocks arise when two threads attempt to access the same resources but acquire them in a different order.
A livelock differs from a deadlock in that states are continuously changing but the system is stuck in an endless cycle. Imagine two chess players repeatedly making the same moves. As soon as one player tries to gain an advantage, the other counters it and the first player has to respond by moving their piece back. The position repeats until the game is abandoned.
Starvation occurs when a thread is not able to access a resource because other threads keep getting access to it first. For example, this can happen when using the Win32 function WaitForMultipleObjects(). This function allows you to specify an array of events to wait for. If multiple events are triggered while the listening thread is busy (e.g. responding to a previous event), the next call to the function returns only the first signalled event in the array. In a busy environment, events which come first in the list will be handled properly but events at the end of the array will repeatedly be overlooked.
Priority inversion occurs when a high priority task and a low priority task need to access the same resource. If the low priority task acquires the resource first, the high priority will have to wait for the low priority task to complete.
What synchronisation mechanisms can be used in multithreading programming?
- Mutex – A mutex allows a resource to be protected such that only one thread can have access to it at any given time.
- Condition variable – A condition variable can be used to send notifications from one thread to another. For example, one thread might wish to enter a sleep state and be awoken when another thread has completed a certain task.
- Semaphore – A semaphore can be thought of as a generalisation of a mutex. A semaphore allows a fixed number of threads (N say) to access the same resource simultaneously. Once N threads are accessing the resource, no further threads will be allowed access until another thread relinquishes access.
- Latch – A latch is a counter that counts down to zero. A waiting thread can be notified when the counter reaches zero. For example, in the thread pool pattern, a latch could be used to notify a waiting thread when all the tasks have been completed.
- Recursive lock – A recursive lock allows the same thread to acquire a lock that it already has. If the lock is acquired twice within the same thread, the resource remains locked until both locks are released.