ud702 ยป



Hello and welcome. In this module you will implement a user level threads package with mutual exclusion. The API for your package will be very close to the standard POSIX threads library. And indeed part of the goal is to help you understand what is going on behind the scenes in threaded programs that you may work on. Though we assume that you have an understanding of the relationship between threads in a process. Why we need mutual exclusion, and the perils of deadlock. We also provide a few warmup exercises to help you get started. The videos that follow will provide some hints to help you. For this and all projects in the course, you should not expect that the videos will explain everything you need to know to complete the projects. One of the most important skills for a developer, and indeed in many professions, is the ability to comb through various sources to find the information you need. Part of the exercise is to practice this skill. Not all of the OS interfaces that we will be using to implement our thread's package are standard. So I highly suggest that you set up a virtual environment on your machine that mimics our testing platform. A link to the instructions for doing this can be found in the instructor notes. You also find a link to the written instructions. Pay close attention to the requirements specified in the written document. Writing my own user level threads package was a fun and satisfying experience for me. I hope it will be for you too. Let's get started.

Mutex Initializer

To help you familiarize yourself with the pthreads library, we're going to examine this toy program that embodies the producer/consumer model. We have one producer thread and two consumer ones. You can find the code in the course repository or in the link in the instructor notes. Your first task is to fix a few bugs. While we're scanning the code, we notice that our mutex lock variables don't seem to be initialized. And this then becomes your first task. Fill in the text box with code that will initialize the g_num_prod_lock variable properly. You may consult the man pages on your system, or the guide suggested in the instructor notes.

Mutex Intitializer

And the answer is Pthread_Mutex_initializer. An alternative solution is to use the Pthread_mutex_init method in our main thread in order to initialize these locks. Both these solutions are equally valid.

Locking a Global Counter

Notice we continue to scan through this program, the next thing we notice is the decrement of a global variable. This may look innocent enough, but in fact it can be the source of an insidious bug in your program; that could be difficult to replicate when testing. You see a decrement like this, may look like a single CPU instruction that can't be interrupted, but in fact it is not. Let's say that our global variable is stored over here in memory. If we increment it, we first have to load it into a CPU register, decrement it, and then write it back. This all seems fine, but we could run into a problem if another thread also tries to decrement it at the same time. Let's say that the value five is currently in memory. Then there's two decrements, it should go down to three. But if one thread meets the value, five, stores it in memory, and then decrements it down to four. And as it's doing that, another thread also reads it from memory as five and then decrements it down to four. And then these threads go to write back the answer, they'll write four into main memory. When of course because we have two decrements we should end up with three. The solution of course is to use a mutex lock on this global variable and that is what I want you to do in this question in order to fix the bug.

Locking a Global Counter

And the answer is that we use the pthread_mutex_lock and the pthread_mutex_unlock functions like so.

Debugging Producer Consumer

Now there are at least three remaining bugs in our toy program. Find and correct them so that your version passes the test.

Debugging Producer Consumer

One problem, is that we try to join here the producer thread which we had already detached, hopefully when you ran the programme, I gave you a helpful message to this effect. We can actually choose either to leave it as detached or to join it but just can't do both. Another problem has to do with our handling of the return value. From the consumer thread. Notice that we're calling free on it here. But actually, it was never mount. The consumer thread wants to return an integer, and plays a trick by casting this integer to a pointer, effectively returning by a value. The thread that return, just needs to be cast as an Int to get the value it wants. The last bug has to do with the mutual exclusion used in this loop. As thing stands. They're only locked for the first iteration. Here we lock them, and then here we unlock them. But as we loop around, the next time they won't be locked. There are several ways to address this problem. Perhaps the easiest is simply to re-lock the variables at the bottom of the loop down here.

Dining Philosophers

A good exercise for understanding the perils of deadlock Its the famous Dining Philosophers Problem originally posed by Dijkstra. There are five philosophers setting around the table. Plato, Aristotle, Rousseau, Nietzsche, and Allen Bloom would be my choice. And being philosophers, they like to think. But they also have to eat every now and again. Each philosopher gets his own rice bowl. But there are only five chopsticks. One made between each pair of neighboring philosophers. For permission to eat, a philosopher has to pick up the chopsticks on either side of him. For permission to think, he places the chopsticks back in their place for his neighbors to use. The main loop for a thread representing a philosopher therefore, looks like this. Your task is going to be to implement the pickup chopsticks and put down chopsticks method by filling the code in where indicated in the template that I'll give you. The output should read like the directions for a play where the action involves philosophers thinking, picking up chopsticks, eating, and putting them down. The directions for the play must be valid. That is, a philospher can only pick up a chopstick that's next to him and he can only put one down if he already has it. So equally important is that no philosopher should be starved. A particularly bad situation is deadlock, where all five philosophers pick up the chopsticks to the left. So Rousseau might grab this one, Nietzsche this one, Allen Bloom this one, Plato this one, and Aristotle this one. And then, they would wait for the one to their right to be set down, so that they could pick it up. Of course this chopsticks will never be put down because another philosopher is holding it waiting for the one to his right to be picked up. In this deadlock situation the philosophers starve. Take care that your program avoids this problem.

Kernel level vs User level

Before we implement our threats library, I want to clarify some important distinctions between kernel level threads, such as p-threads or Posix threads, and the user level threads that will implement as part of this project. In both cases let's say we have multiple processes each with multiple threads inside them. And of course we have a process level scheduler inside of the kernel. The key difference is where the thread level scheduler lies. For kernel level threads the thread scheduler is inside of the kernel, and hence it can schedule multiple threads from the same process on different cores. Just as importantly when one thread blocks, a kernel level library can schedule another thread from the same process. In the user-level thread set up, the kernel doesn't even know that a process has multiple threads, and hence can't schedule them on different course. When one thread blocks, the OS won't know that there's another thread from the frame pro, same process that it could schedule. So the whole process necessarily blocks. Remember that for user-level threads, the schedule is actually part of the process itself. Which is not the case for kernel-level threads. Okay so lets review the comparison here. In kernel-level threads, we have thread concurrency within a process. That's not possible for user-level threads. Remember that the kernel didn't even know that the process had multiple threads. Another difference was that at the kernel level, only an individual thread blocked on a blocking call. For a user-level thread library, however, the whole process necessarily bocks. And because of these advantages, kernel-level thread libraries have become the standard. User-level libraries on the other hand, are easier to implement. Which is lucky for us.


We're now ready to move on to the implementation of our library. I'll offer some advice and provide a few resources that will be helpful as you do your implementation. But to larger degree, you need to research and figure things out on your own. This ability is one of the most important skills for a programmer to have. To help save you some time however, I'll give you a few points. As you program your threads library, it is important to remember that from the operating system's point of view, our mur, our multithreaded programs will just be a single threaded user process, plus they will have one segment of memory for the code, another for global variables and constants and so forth literals, space for a heap. And then growing in the other direction stack. Not all of this is supposed to be shared among the threads in a process, except for the stack. Each thread is supposed to have its own. Where do we get the memory for these stacks? Well, from the heap of course. We also need to remember other information about what values are in the registers and so forth while a thread is not actively running. For all this, we'll use a UContext type, which I'll illustrate through an example program. It will keep all of the relevant information about a stack pointer, a program counter for the thread, and any registered values inside the CPU that we're using in our code. So to illustrate how to switch context, we'll examine this little test program. It simulates what a rather unimaginative announcer might say while working a tennis match. So, looking at the code, we see that we have one function that simulates Federer's play and another one that simulates Nadal's. For those of you who don't know, these are famous tennis players who had a great rivalry in the early part of the 21st Century. Each of these functions runs in it's own thread. After Federer returns the ball, we swap context to give Nadal's thread control again. Nadal can then return, and we swap context back to Federer. All the information about what's stored on a stack, what's in the registers, where the program counter is, etcetera, are stored in these ucontext variables. One for Federer and one for Nadal. We have set these up in main. First, by calling getcontext to fill them in with some essential information about the process. Then we allocate memory for the stacks and set the stack sizes. Then we use the makecontext method to specify where these contacts should start. The federer one starts with the federer function; the nadal one starts with the nadal function. And to actually start the threads, we use the swap context method to switch from the current context of the main thread, to the one that we made to begin with the federer function. That was a pretty fast explantaion. So don't worry if you don't feel like you understand it all right away. In fact, one of the goals of the project is to give you practice reading example code and documentation on your own. You may find some good resources on the Internet the demand pages will probably be the most helpful for understanding the Ucontext calls.

Moving On

We're now ready to move on to the implementation of our library. I'll offer some advice and I'll provide a few resources that will help as you do your implementation. But to a large degree, you will need to research and figure things out on your own, this ability is one of the most important skills for a programmer to have.

Scheduling and Locks

So your scheduling policy should be round-robin. So a simple queue data structure will suffice. Once a thread has finished, he should go to the back of the line, like so. To actually switch to another thread in the program, you should use the swapcontext method alluded to earlier. Implementing mutex locks can be equally simple. Each lock should keep a FIFO queue of threads waiting on it. And the waiting thread should not allow it to be, to execute. A generic steque data structure that has all the capability of a FIFO queue is provided along with the project.


So deciding which thread has the next turn is therefore relatively easy, and the abstractions involved are all very standard. Making a thread give up his turn on time, however, is a little more unusual. Technically, we would say that this is making our package preemptive. For this, you're to use system signals. Remember that a process doesn't just execute a single line of control. It also has to be able to handle signals from the kernel, which can interrupt their normal program flow. These signals might be the result of an exception by the segfault, or dividing by zero. They might come from a user who wants to, kill, sends the kill signal to the process, or as we will use in this project, they might come from an alarm that the process asks the kernel to set for it. Now, three things can happen to a signal. It can be handled by the default handler provided by the operating system. This is probably what's happened in most of the programs that you've written. You can register your own handler to respond to the signal. You will do this as part of the project. Or, you can block the signal entirely, so that your program doesn't respond to it at all. As you write code with signal handlers, it's important to remember that the signal could arrive at any point during the execution of your program. Therefore, if the signal handler relies on some data structure in your program, you may want to block the signal as you nim, manipulate the data structure, to make sure the signal handler always finds it in a consistent state. Say, for instance, that your main control manipulates a queue data structure In this section here. And also that your signal handler also manipulates this same queue data structure. Well, you wouldn't want the signal handler to run in the middle of your main control's updated queue structure. It may find it in an inconsistent state. So we will want to block the signal before we manipulate the queue, and then unblock the signal afterwards, in order to be able to handle future signals afterwards. As a programmer, you have to worry about not just your own data structures, but system data structures too. A signal might arrive in the middle of system call. If the handler also makes a system call, it might interact with the interrupted system call in an unfriendly way. This concern gives the rise to the notion of signal safe system calls, which don't have this problem. To illustrate the alarm signal, we'll examine this test program that I've named DEFCON. The premise is that you can do periodic missile tests, set off whenever the alarm goes off, but you have to stop the test if there's some nuclear crisis which might start a war. So usually, tests are okay, but when there's a nuclear crisis, we halt them. And when the crisis is past, we want to start them up again. Okay, the first part of the code here creates a mask for the signals, allowing us to block and unblock the sigvtalarm. Then we set up a timer for the alarm using the setitimer function. And then we register a handler for our method. Using the function pointer which points to the alarm handler, which is up here at the top of the code, right there. Just says missile test. In the first part of the code, the signal is unblocked, so we have missile tests interspersed with the passing of time. As in will be indicated by the printing of these dots. Then we block the signal. For the critical part of the nuclear crisis, and then unblock it afterwards. Now for your user level threads library, they're going to be critical sections too. For instance, if you're modifying the schedule, the queue, or a new text box, you probably don't want that thread to be interrupted. Otherwise, we control switches to another thread, it might find a key data structure in some corrupted or intermediate state. So you'll want to employ the same strategy of blocking and unblocking signals.

Good Luck!

I've talked about the major challenges for this project. Now it's up to you. Consult the documentation provided. And if you find anything else useful, please let others know about it in the forums. Good luck.