In the first project, your task is to write a non-preemptive, user-level threads package. Many operating systems provide an implementation of threads at user-level because they allow concurrency with a very low overhead, without requiring a call to the kernel to switch between threads. Windows NT does not provide a user-level threads package, only kernel threads.
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 environment in the same way that NT builds its abstractions on top of the hardware.
Special announcement! There is an incompatibility between the
version of machineprimitives_x86.c
and the new C compiler
included with Visual Studio .NET.
This manifests itself when you do the following: context switch
from thread A to B, and then context switch back to
A, and will cause minithreads to crash (return address is
outside the program). This problem only occurs if you're using Visual
Studio .NET; earlier versions of Visual Studio will not have this
problem. To fix it, download machineprimitives_x86_dotnet.c
and rename it to "machineprimitives_x86.c
", replacing the
old version. Everything will now work.
Special announcement! Some special steps are required to get minithreads to work on the machines in Rhodes Hall 453, since they run a different version of Visual Studio (the .NET version).
If you have tried compiling minithreads using Visual Studio .NET, you'll probably have discovered that the instructions we've given you don't work. The problem is that Visual Studio .NET puts its libraries in a different place from the earlier version, which breaks the linking stage of building minithreads. Here's some revised instructions:
n.b. The original instructions will work fine if you're using an earlier version of Visual Studio.
minithread_create
and
minithread_yield
, and go on to implement the
scheduler. Once you have those two working, you can come back to
implement the rest of the functionality. minithread_yield()
.
Finally, you need to demonstrate your threads package by implementing a solution to the "food services" problem. This is actually an instance of the better-known multiple-producer, multiple-consumer problem. There are N cooks (each a separate minithread) who constantly produce burgers. We'll assume for debugging purposes that each burger has a unique id assigned to it at the time it is created. The cooks place their burgers on a stack (at the front of the queue you built earlier in this assignment). There are M hungry students (each a separate minithread) who constantly grab burgers from the stack and eat them. Each time a student eats a burger, she prints a message containing the id of the burger she just ate. Ensure, for health and sanity reasons, that a given burger is consumed at most once by at most one student.
minithreads1.zip
minithreads.zip
file in the directory for
your project.
.c
files. Do the same in
the "Header Files" folder, and add all the .h
files.
VISUALSTUDIO = c:\Program Files\Microsoft Visual Studio
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
make
to compile the project incrementally (will detect which
files have been modified and recompile them).
Three small test programs, test1.c
, test2.c
,
and test3.c
, are included in the
minithreads1.zip
file. They test spawning a thread,
spawning multiple threads, and ping-ponging between threads. They
should be useful when you are implementing minithreads. Two larger
test programs, buffer.c
, a bounded buffer, and
sieve.c
, a sieve for finding primes, are more
complicated. Ideally, you should test your Minithreads implementation
against these.
If you have problems with the project or questions, please send mail to the instructors or come to office hours.
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 importantly, 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.
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()
calls inserted at
random locations throughout the application code (note that we don't
expect the system code in minithread.c
or
synch.c
to be yield-safe for this project -- just the
applications).
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.
For this project you have to submit the source of all the files you
modify (at least minithread.c
, queue.c
,
synch.c
) and the NT executable for the multi-producer,
multi-consumer problem. Also submit the Makefile with the
MAIN
symbol set to the name of your producer-consumer
program.