Considering current directions in PC hardware technologies, with the widespread availability of dual core processors and the imminent popularisation of processors with even more cores, programmers need to be familiar with techniques that allow these capabilities to be fully exploited. This article shows you the obvious way to go to use threads, which can both increase application efficiency and improve the overall user experience.

Considering current directions in PC hardware technologies, with the widespread availability of dual core processors and the imminent popularisation of processors with even more cores, programmers need to be familiar with techniques that allow these capabilities to be fully exploited.

The obvious way to go is to use threads, which can both increase application efficiency and improve the overall user experience.

Threading essentials

The vast majority of modern operating systems are multitasking, meaning they allow multiple processes to be executed simultaneously (concurrently). Of course, if the platform has fewer processors than processes, concurrency is implemented by a time sharing scheme for the processor(s). Processes are queued for processor access by the scheduler. Multithreading is an operating system feature that allows many threads to be executed concurrently within each process. As with multitasking, concurrent multithreading is implemented by sharing processor time.

Threads vs processes

The term process is usually used to refer to a program while it is being executed. A process is made up of the program code, instruction counter, process stack and data section. Each thread within a process shares the program code, data section and system resources with other threads, but has its own instruction counter, processor register set and stack. In some publications on concurrent programming, you will also see threads called lightweight processes (LWPs) and traditional processes called heavyweight processes.

Threading implementations

The operating system can implement threads in two basic ways. User-space threads are created using library functions and switching between them does not require system kernel calls. The advantage of this model is that thread switching is very fast, resulting in better process performance, even under a heavy load. However, the effectiveness of user-space threads is very much dependent on operating system capabilities, as it is possible for a multi-threaded process to be assigned the same processor time as a single-threaded one. If the system kernel is single-threaded, each system call by a user-space thread halts the execution of the entire process.

The other approach to threading is to have kernel-space threads, coordinated by the system kernel. Kernel-level threading ensures that processor time is properly allocated to all threads that request it, but the use of system calls incurs an additional overhead on thread switching. Some systems also support mixed threads, which basically combine the functionality of user-space and kernel-space threads.

Multithreading models

There are three basic multithreading models. In the many-to-one model, many user-space threads are mapped to one kernel-space thread - this is the model used by operating systems that don’t have kernel-level support for threading. In the one-to-one model, each user-space thread is mapped to a single kernel-space thread. Finally, in the many-to-many model, many user-space threads can be mapped to many kernel-space threads.

The pros and cons of multithreading

The most important advantage of threading is that the system resources assigned to a process are shared within it, which makes inter-thread communication much easier and faster than costly inter-process communication and allows resources to be used more efficiently. Moreover, on multiprocessor platforms threads are physically executed concurrently, significantly increasing performance.

Unfortunately, threading comes with its own pitfalls. An error in any one thread can threaten the execution of the entire process, and threads must be synchronised using operating system-specific mechanisms. Synchronisation incurs its own overhead, increases program size and significantly complicates the process of developing and testing software.

Thread synchronisation

As long as threads run independently and don’t need to write to shared resources, synchronisation problems don’t occur. All other sharing scenarios require mutually exclusive resource access, and synchronisation is the general term used to refer to the various ways of doing this. Existing literature on concurrent and distributed programming describes what are called the classic concurrency problems, which are formulated in terms of processes, but apply equally well to threads.

Core synchronisation mechanisms

A number mutual exclusion mechanisms can be used for synchronising processes/threads. Probably the simplest method are atomic instructions, which are guaranteed to always be executed in their entirety, without being interrupted by another thread. To appreciate the significance of this feature we need to realise that a single instruction in a high-level programming language can (and frequently does) translate into a block of multiple processor instructions. If a thread is interrupted while modifying such a block, another thread could for example read an incorrect value of a shared variable. Critical sections are a further development of the same mechanism, allowing uninterruptable blocks of code to be delimited.

Atomic instructions and critical sections can be classified as low-level thread synchronisation mechanisms. Semaphores are more abstract mechanisms. A semaphore is an integer that has an initial state and can be raised (incremented) or lowered (decremented). All changes to semaphore values must of course be atomic. For general semaphores, raising the semaphore causes one of the threads waiting on it to be resumed, and a thread can only leave the semaphore once its value is greater than zero. Binary semaphores are a specific version of general semaphores and can only have a value of 0 or 1.

Plenty of publications exist that deal with semaphores and other thread synchronisation methods in detail. One thing to remember when reading up on synchronisation is that the methods available in practice are strictly related to the operating system or threading library.

Deadlocks

Deadlocks are probably the most common problem with thread synchronisation. A group of threads is said to be in deadlock when each thread in the group is waiting for an event that can only be caused by another thread from the same group. The unpredictable nature of concurrent execution makes deadlock detection a difficult task, since a specific deadlock situation need not occur for each program execution.

The simplest deadlock scenario is called the Mexican standoff and involves two threads that require the same two resources, protected using critical sections or other mutual exclusion mechanisms. The first thread accesses the first resource and then tries to access the second resource, while the second thread accesses the second resource and tries to access the first resource. Neither thread can now access the critical section of a required resource, resulting in deadlock.

Systems than can potentially enter into deadlock are commonly analysed using resource allocation graphs. Threads {T1, T2, ..., Tn} and resources {R1, R2, ..., Rm} make up the graph’s vertices. The graph also contains two types of edges: request edges Ti® Rj, interpreted to mean that thread Ti has requested resource Rj, and allocation edges Tj® Ri, interpreted to mean that one copy of resource Rj has been allocated to thread Ti. Of course, the number of allocation edges cannot exceed the number of available Rj copies.

If the resource allocation graph contains no cycles, no deadlock is possible in the application under analysis. If a cycle exists, deadlock may occur, but is not guaranteed to occur, unless there is only one copy of each resource. Figure 1 presents a resource allocation graph for a Mexican standoff situation.

Figure 1. Resource allocation graph for a Mexican standoff deadlock

No universal method of preventing deadlocks exists. The most basic measure is to place restrictions on resource access so as to ensure that the required condition for deadlock cannot be satisfied. More expensive methods use real-time resource access analysis to detect cycles in the resource allocation graph. The banker’s algorithm can also be used to check the risk of a resource allocation operation before deciding whether to allow it. Another commonly used method is to allow deadlocks rather than prevent them, with the reaction typically involving killing one or all of the deadlocked threads.

Classic concurrency problems

The producer and consumer problem is one of the best-known concurrency problems. It involves the synchronisation of two threads: a producer that regularly produces a portion of data and a consumer that regularly retrieves and consumes data supplied by the producer. Synchronisation issues arise when the producer cannot supply the required data on time or the consumer cannot retrieve the producer’s waiting goods. In either case, one of the threads has to wait for the other.

Another classic concurrency problem is the readers and writers problem, involving the synchronisation of reader and writer processes competing for access to a shared resource. A reader thread periodically accesses the data to read it, and many readers can use the resource simultaneously. A writer thread modifies the data, so it needs to have exclusive access to it. A variant of the problem with a limited number of simultaneous read operations also exists.

The last classic problem mentioned here is the dining philosophers problem. Imagine you have five philosophers (threads) sitting at a round table and thinking. Every now and again, a philosopher gets hungry and has to eat. Each philosopher has a plate of spaghetti, and on the table there is one fork (or chopstick, if you prefer) between each pair of plates. Eating spaghetti requires two forks (or chopsticks), so when a philosopher starts to dine, he prevents his two neighbours from eating. The dining time is finite, but sufficient for a philosopher to eat his fill.

A d v e r t i s e m e n t

sum:

0 €

» Library of the Month
» Workshop
» Software Engineering
» Programming Tools
» Interview
» High quality and
secure programming
» Reverse Engineering
» Portable GUI
» Artificial intelligence