Your task in this project is to write a non-preemptive user-level threads package. Most operating systems, e.g. Linux, Solaris, Mach, etc, provide such a lightweight thread abstraction because, as you might recall from the lectures and the reading, user-level threads provide concurrency with very low-overhead. NT does not have a user-level threads library. Your task is to write one.
We have provided you with some skeletal code that creates an environment on top of NT that closely resembles the environment on top of raw hardware shortly after booting. We use NT to provide us with a virtual processor and memory. NT also bootstraps our kernel; that is, it loads it into memory and starts executing it at its entry point. Your task is to build high-level abstractions on top of this runtime environment in the same manner NT builds its abstractions on top of the hardware.
There are a few distinct components to this project.
First, read through the entire assignment, figure out how you'll do it, and write up a design document. Submit it via CMS, and come discuss with us. Tell us about data structure choices. What structs do you need, and what are the members? How will you test? What invariants should hold for the functions you write? This should be a few pages, but don't go overboard.
You should discuss your design with the course staff by Friday, February 2. Earlier is better.
Think before you code. It's a good habit to get into, even if for this first project you can come up with something reasonable without it.
Next, you will have to write a generic FIFO (first-in, first-out)
queue with enqueue and dequeue operations. We will be relying on this
queue implementation throughout the rest of the semester, so it's
important that the implementation be efficient and robust. Specifically, enqueue and dequeue operations should both work in O(1) time. Watch out for corner cases, be sure to check function arguments, and above all, test thoroughly.
One common bug in C programs is a memory leak, where memory is malloced but never freed. If your program has a memory leak, it will use more and more heap space and eventually crash. Check for memory leaks by writing a program that exercises your queues heavily, and then use the windows task manager to make sure that your program's memory usage remains bounded.
Third, you need to define and implement thread control blocks, and the functions that operate on them. We suggest you start with minithread_create and minithread_yield before implementing the rest of the functionality.
Fourth, you need to implement a scheduler. For this assignment, all you need is a first-come, first-served scheduler. You can assume that your threads will voluntarily give up the CPU, which means that your test programs should make occasional calls to minithread_yield().
Fifth, you need to implement semaphores in order to be able to synchronize multiple threads. Semaphores are discussed in the textbook,and we'll be getting to them in the 414 lectures in a little bit.
Last, be sure to test everything. Describe your test scheme and include it and any test programs you wrote, in your final submission.
If you decide not to use the integrated development environment (visual studio), you can use any other editor you like and compile the code from the command line. To compile the code from the command line, go to the directory where you unpacked the project and type nmake to compile the project incrementally (will detect which files have been modified and recompile them) or nmake clean to delete all of the intermediate files. Note that you still need to install Visual Studio to get the nnmake command and the compilers proper.
If you have problems with the project or questions, please send mail to the course mailing list or come to office hours for one of the TAs.
It's crucial that systems code be correct and robust. You must test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly. Note that you should maintain some separation between the minithread package and minithread applications. Most notably, your minithread applications should not contain any dependencies on the scheduling algorithm or on the lack of preemption.
To facilitate testing, we provided you with some test programs. It's a good idea to start with these, and develop your own tests as you need them. The simplest test cases are test1.c, test2.c and test3.c, which test single thread creation, multiple thread creation, and ping-pong between two threads. buffer.c provides a bounded buffer implementation. A producer and consumer keep producing values and consuming them across a buffer of finite length. sieve.c is a Sieve of Eratosthenes for concurrently searching for primes. It has a single thread on one end, injecting the numbers 1, 2, 3, 4, 5, 6, 7, 8, ... into a pipe. For each prime p, there is a thread in the middle of the pipe that consumes a number from the pipe if that number is divisible by p. Otherwise, it passes the value on to the next thread in the pipe. At the very end, there is a thread that prints the values that emerge from the pipe. Note that this assembly will only print out prime numbers, because the threads in the pipe will consume all non-primes. You will make extensive use of your queues in later projects; we strongly recommend creating several tests for your queues to make sure that they operate properly. Be sure to test every function, and watch out for corner cases.
Since we will soon make the threads package preemptive, all code you write should be properly synchronized. That is, everything should work no matter where in the application thread you place a minithread_yield. Consequently, it's a good idea to test your code with minithread_yield's inserted at random locations throughout the application code.
Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of threads are created and destroyed.
Everything should be in a single ZIP file that unpacks into a single minithreads[projectnumber] directory, with no subdirectories. Do a clean before submissions; we don't want a lot of binary files in your submission.
Add preemption and implement a multilevel feedback queue with four
levels, with round-robin at each level, and where the time quanta
doubles at every level. Demonstrate that it works as intended.
Final Word
Frequently asked questions will be posted as we hear them.
If you need help with any part of the assignment, we are
here to help. If you start
early, this should be a fun and easy project.