It is possible to use locks (pthread_mutex_lock in pthreads) to implement different forms of synchronization, but often it is cumbersome to do so. In particular, there are cases when it is necessary to have one thread wait for something to be computed by another and then only to make progress when that computation has been completed. In the examples we have studied so far, the thread that logically waits is created by the thread that is logically producing the computation upon which that thread is waiting.
That is, if thread 1 produces a variable value that will be used by thread 2 (as in the average example in the IntroThreads lecture), thread 1 performs the computation, stores the value, and spawns the threads that then use this computation.
This form of parallelism is often called “producer-consumer” parallelism and it occurs in operating systems frequently. In this example, thread 1 “produces” a value that thread 2 consumes (presumably to compute something else).
Perhaps more germane to the class at hand, this problem is also called the bounded buffer problem since the buffer used to speed-match the producers and consumers has a fixed length. In an operating systems context, these types of synchronization problems occur frequently. There are cases where threads and/or devices need to communicate, their speeds differ or vary, and the OS must allocate a fixed memory footprint to enable efficient producer-consumer parallelism.
While it is logically possible to spawn a new thread that runs every time a new value is produced and to have that thread terminate after it has consumed the value, the overhead of all of the create and join calls would be large. Instead, pthreads includes a way for one thread to wait for a signal from another before proceeding. It is called a condition variable and it is used to implement producer-consumer style parallelism without the constant need to spawn and join threads.
Condition variables are a feature of a syncronization primitive called a monitor which is similar to the way in which operating systems kernels work. We won’t discuss them formally at this juncture but their use will become clear as the class progresses. For pthreads, however, condition variables are used to
which as we will see are more or less equivalent usages.
Okay – we are ready for our second operating systems concept. Operating systems must be able to protect shared state from race conditions. Rather than giving you a formal definition for a race condition (which I will provide later), we will start with a very simple example.
The first thing to understand is that it is possible to run more than one thread on each CPU. Try running the avg-manythread.c on 50 threads or so. The machines you can access have at most 8 processors. How could they run 50 threads?
The answer is that the OS and threading system to arrange to multiplex the threads on the CPUs. Each thread is given a turn on some CPU. When it goes to do I/O, or a fixed amount of time has expired, the OS pauses the thread (saving off all of its machine state), and selects another thread to run. It then loads the saved machine state from the new thread onto the CPU and starts that thread at the spot where it last left off (or at the beginning if it was just created).
The process of pausing one thread to run another is called pre-emption and the second thread is said to pre-empt the first. The process of switching to a new thread (as a result of a pre-emption event) is called context switching and the saved machine state that is necessary to get a thread running again after a pause is often called a context.
We’ll spend quite a bit of time in this class discussing the concept of “concurrency” – the notion that independent sets of operations can be occurring at the same time inside the machine when it is executing a program. For example, when a program does I/O (say to a disk), the CPU may be switched that it is able to work on some other task while the I/O is taking place. Operating systems both allow the user to manage concurrency and also (in many cases) exploit concurrency on behalf of the user to improve performance. As a result, concurrency and concurrency management/control will be themes that recur throughout this course.
Threads are a programming abstraction that is designed to allow a programmer to control concurrency and asynchrony within a program. In some programming languages, like Java, threads are “first class citizens” in that they are part of the language definition itself. For others, like C and C++, threads are implemented as a library that can be called from a program but otherwise are not considered part of the language specification.
Some of the differences between having threads “in the language” and threads “as a library” are often subtle. For example, a C compiler need not take into account thread control while a Java compiler must. However one obvious difference is that in the library case, it is possible to use different thread libraries with the same language. In this class, we’ll be programming in C, and we’ll use both POSIX Threads and a thread library specifically designed for the OS project called Kthreads. Kthreads and POSIX threads are similar in that they are both thread abstractions and they are both implemented as libraries that can be called from a C program. They are different in that POSIX threads requires operating system support to work properly and, thus, can’t be used directly to implement the operating system. In contrast, Kthreads can be implemented without the OS using only the C language compiler and a little bit of the C runtime. For this reason, we can use Kthreads as an abstraction with which to build an operating system (i.e. there is no circular dependence).
We’ll study both before the end of the class but we’ll start with POSIX threads since they a standard.