CS 414/415 Programming Project 1
Emin Gün Sirer


Your task in this project is to write a non-preemptive user-level threads package. Most operating systems, e.g. Solaris, Mach and DEC OSF, 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 skelatal 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 entrypoint. Your task is to build high-level abstractions on top of this environment in the same manner NT builds its abstractions on top of the hardware.

There are a few distinct components to this project.

First, you will have to write some generic FIFO (first-in, first-out) 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. Specifically, enqueue and dequeue operations should both work in O(1) time.

Second, 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, and go on to implement the scheduler. Once you have those two working, you can come back to implement the rest of the functionality.

Third, 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 occassional calls to minithread_yield().

Fourth, you need to implement semaphores in order to be able to synchronize multiple threads.

Finally, you need to demonstrate your threads package by implementing a solution to the storefront (single-producer, multiple-consumer) problem. The problem is that there is one really busy toy store owner (producer thread), a storefront with N locations, and a bunch of independent pokemon addicts (consumer threads) who want to buy pokemon merchandise. The owner creates pokemon merchandise, numbered sequentially from 1 on up, out of the thin air and places each on one of the N locations in the storefront. The consumers snatch these items as soon as they are placed on the shelf (but no sooner) and announce to the world the serial number of the item they purchased. Your solution will be evaluated for correctness and concurrency.

How to Get Started

To unpack and set up minithreads in Visual Studio under Windows NT, do the following:

Three small test programs, test1.c, test2.c, and test3.c, are included in the minithreads.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 cs414@cs.cornell.edu or come to office hours for one of the TAs.

How to Test Your Code

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 divisable 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's 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.


Follow the following steps to submit. 

  1. Log into CSUGLAB using the login id given to you in class. This login id should be a member of the cs415 group.
  2. Create your submission:
    1. Get your group numbers from the Group Assignments link on the web-page. Create a folder named as proj1-yourgroupnumber. So if your group number is, say, 10, then you would create proj1-10. 
    2. Create two subfolders within this folder - one named Code and another named Executable.
    3. Put all your .c files and project files into the Code folder. We should be able to go to this folder and just click on your project file to open up all your working code. Note: we should be able to import our own test case .c files into this project and test your code.
    4. Compile your Pokemon code (of course with the rest) and put the executable in the folder Executable.
    5. Put a  README file, maximum length one page, into the proj1-yourgroupnumber folder. It should contain:
  3.  Check your submission:
    1. Check: that you are able to open your project by double-clicking on it (in the Code folder). 
    2. Check: that you are able to run your Pokemon application by double-clicking on the executable file in the Executable folder. 
    3. Check: that Executable and Code folders, and README is actually within the main folder you created (i.e., with your netid).
  4. Submit:
    1. Log into goose using the same id as in step 1. 
    2. Right click on the proj1-yourgroupnumber folder you created above, and choose copy.
    3. Go to the folder   \Courses\cs415-sp01\Project1-submit  on goose, right click on this folder, and choose paste.
    4. Do not drag and drop the proj1-yourgroupnumber folder into the  \Courses\cs415-sp01\Project1-submit folder. We will not be able to access it.


  5. Your project will have been submitted ! You won't get any confirmation, or be able to view anyone' submissions (including your own).
  6. Try to submit at most once. If you absolutely need to submit a second time, create a proj1-resubmit-n-yourgroupnumber (where n is higher than your earlier submissions) and repeat the above steps with it instead of proj1-yourgroupnumber. So, if your group number is 10, your first resubmission would be proj1-resubmit-2-10, your second resubmission would be proj1-resubmit-3-10 ...
  7. We will evaluate only your last submission (or resubmission) turned in before 1 pm (sharp) on Feb 21st.
  8. Do not mail your submissions to us ! They will not be evaluated.

For the Adventurous

Note: These suggestions for an extra challenge will be examined but not graded. They will have no impact on the class grades. They are here to provide some direction to those who finish their assignments early and are looking for a way to impress friends and family.

There is a bug in the original version of clock.c which causes the system to sometimes freeze if you enable debugging. A new version of clock.c is available. The minithreads1.zip file has also been updated to include the bug fix.

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.

Add a facility to the clock routine such that threads can schedule functions to be called N seconds in the future. Add a minithread_sleep_with_timeout(int timeout) routine that enables threads to go to sleep and wake up after a given number of microseconds have elapsed.

Final Word

If you need help with any part of the assignment, we are here to help. If you start early, this should be an incredibly fun project.