Kthreads is a relatively simple, non-preemptive threads library that we will be using to implement our operating system later in the labs. For our purposes, it has an advantage over pthreads because it works in the debugger and because it will not interfere with the simulator (making your development life easier). It’s also simple enough to understand, and therefore makes for a good teaching tool.
The kthreads library is at /cs/faculty/rich/cs170/lib/libkt.a, the source is at /cs/faculty/rich/cs170/src/libkt/, and the header is /cs/faculty/rich/cs170/include. You will also need to link to /cs/faculty/rich/cs170/lib/libfdr.a which provides some basic C functions like linked lists and red-black trees.
Using kthreads is pretty straightforward, so we will not go into it in much detail. You should all understand the basic thread primitives by now although you need to remember that (unlike in the case of pthreads) kthreads do not pre-empt each other. The kthreads calls are:
void *kt_fork(void *(*func)(void *), void *arg);
void kt_join(void *kt_id);
void kt_sleep(int sec);
Kthreads includes counting semaphores as its only synchronization primitive.
kt_sem make_kt_sem(int initval);
void kill_kt_sem(kt_sem ksem);
void P_kt_sem(kt_sem ksem);
void V_kt_sem(kt_sem ksem);
int kt_getval(kt_sem s);
The basic kt primitives (fork, exit, join) play the same role that pthread_create, pthread_exit, and pthread_join play for pthreads. Of the other functions,
kt_yield() interrupts the current thread and lets the scheduler run a new one. This primitive is nice in non-pre-emptive thread systems because it allows a kind of “polling” of the scheduler. A thread calling
kt_yield() blocks itself and allows other threads that can run to go ahead. When no more runnable threads are available, the yielding thread will be resumed at the point of the yield.
kt_sleep() sleeps the current thread for a specified time period. Again, because the thread is non-pre-emptive, the thread will be “awakened” and made runnable after the specified time, but it will not actually run until it is given the CPU.
kt_self() returns the thread id. No confusion here.
kt_joinall() is a useful function that causes the current thread to block until all other threads have either exited or blocked on a semaphore.
You will find that this function is particularly handy in designing your OS.
The semaphore primitives are exactly as we discussed.
make_kt_sem() creates a semaphore with a value greater than or equal to zero, and
kill_kt_sem() destroys (and frees) it.
P_kt_sem() decrements the semaphore’s value by 1, and if it is negative blocks it.
V_kt_sem() increments the value by one, and it if it is zero or less it unblocks one thread.
There is also a call to interrogate the current value of the semaphore –
kt_getval(). While not strictly part of the semaphore API, there are occasions where the ability to know how many threads are blocked on a semaphore is quite handy.
So far we have discussed mutexes and condition variables as the tools of synchronization and of managing critical sections of code. These are not the only tools that can be used for the job, and you are going to find yourselves very soon doing a lab where mutexes and condition variables are not available to you, but semaphores are. So we need to consider semaphores.
The concept of semaphores as used in computer synchronization is due to the Dutch computer scientist Edsgar Dijkstra. They have the advantages of being very simple, but sufficient to construct just about any other synchronization function you would care to have; we will cover a few of them here. There are several versions of the semaphore idea in common use, and you may run into variants from time to time. The end of these notes briefly describe two of the most common, binary semaphores and the SYSV IPC semaphores.
A semaphore is an integer with a difference. Well, actually a few differences.
There are various ways that these operations are named and described, more or less interchangeably. This can be confusing, but such things happen in computer science when we try to use metaphors, especially multiple metaphors, to describe what a program is doing. Here are some:
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.