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


Grading consisted of two parts - 1) testing with custom test programs (alarms, preemption, minimsg-test), and 2) code look-through, where most groups lost points for not protecting critical sections such as access to alarm queues etc.


Your task in this project is to extend your non-preemptive user-level threads package with preemption and networking.

In general, your applications will not be well-behaved, cooperating processes that routinely yield the processor on their own. You need to guard against processes that want to occupy the CPU by forcibly preempting them and switching to another process. You will also need to enable your applications to send information to each other by adding minimessages to your minithreads package.

We have provided you with some code that emulates clock and network interrupts. The interrupts arrive on the stack of the currently executing thread, just like they do on native hardware. You get to write a network handler that is supposed to do the right thing in response to the interrupt.

There are a few distinct components to this project.

First, you will need to make your threads package preemptive. Clock.c provides the interfaces you will need for this purpose. Soon after you initialize the clock module (clock_initialize) and enable interrupts (set_interrupt_level), you will start getting clock interrupts. You may initially want to set the clock period to a few seconds and print something from the clock interrupt handler to ensure that it is working (but disable such printfs because you cannot afford to spend time inside an interrupt handler printing things to the screen. You also need to reduce your quanta to ~100 ms.). Note that interrupts can arrive at any time, at any location in the code. They stop the currently running process and force it to jump to an interrupt handler. Your code can take control at this point and can force the interrupted process to yield. Note that there may be places in your code where you really do not want to take clock interrupts, e.g. when some system invariant is momentarily violated. It is ok to briefly disable interrupts at critical moments, as long as this happens in your system code and interrupts are reenabled shortly thereafter. However, you should never execute any application code with interrupts disabled.

Second, add an alarm facility by which processes can request an arbitrary procedure to be called N microseconds in the future. You will have to keep track of how many clock ticks have passed by in your clock interrupt handler in order to be able to decide when the alarms ought to expire. It's ok if the user specifies a clocktick value that is below the precision of your time quantum. Do the best you can with such requests instead of ignoring them.

Third, use this alarm facility to implement an interface, minithread_sleep_with_timeout(int timeout), by which threads can give up the CPU, go to sleep (i.e. relinquish the processor entirely) and wake up after a given number of microseconds have elapsed.

Fourth, you need to implement a simple, unreliable transport layer. We have provided you with network.c, which allows you to send a network packet and alerts you with a network interrupt whenever you receive a packet. You need to initialize the network device by calling network_initialize shortly after clock_initialize and before enabling interrupts. Since you may have multiple threads that want to communicate over multiple channels, you will need to create a port abstraction, through which minithreads will be able to send and receive packets. A port is a connection endpoint. When you send a packet, you need to attach sufficient header information such that the packet can be decoded on the receiving end. Once you receive the packet, you get to demultiplex it based on the contents of the header. Note that packets can be lost, reordered, and duplicated in transit, and you don't need to implement reliable ordered delivery or duplicate supression for this assignment (though you need to make your best effort at getting the packets to their intended recipients without undue reordering and duplication). If a packet arrives and no threads are waiting to consume it, it should get queued in the port until a thread performs a receive. If multiple threads are waiting to receive from the same port, packets should be delivered to threads on a first-come first-served basis. Note also that you need to control the port space - you need to track which ports are in use and clean up unused or finished (destroyed) ports. You can initially run two separate instances of the minithreads system on the same host to test your networking code. Once that works, you should be able to run one of the instances on a remote host.

How to Get Started

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

If you have problems or questions, please send mail to cs414@cs.cornell.edu or come to office hours for one of the TAs.


The usual criteria apply: correctness, robustness, and elegance. Unnecessarily disabling interrupts will be penalized. Incorrect thread cleanup, and an idle thread that takes up non-idle time will also be penalized. Ports should be cleaned up completely after use, packets should not leak, and the port space should be managed properly.

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.

You first need to demonstrate that your preemption code works by making pokemon work under preemption.

To facilitate testing of minimessages, 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 tests appear in network[1-6].c, and they are example uses of the minimsg interface.

Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of ports 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 proj2-yourgroupnumber. So if your group number is, say, 10, then you would create proj2-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.
    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 proj2-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 proj2-yourgroupnumber folder you created above, and choose copy.
    3. Go to the folder   \Courses\cs415-sp01\Project2-submit  on goose, right click on this folder, and choose paste.
    4. Do not drag and drop the proj2-yourgroupnumber folder into the  \Courses\cs415-sp01\Project2-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. If you absolutely need to submit a second time, create a proj2-resubmit-n-yourgroupnumber (where n is higher than your earlier submissions) and repeat the above steps with it instead of proj2-yourgroupnumber. So, if your group number is 10, your first resubmission would be proj2-resubmit-2-10, your second resubmission would be proj2-resubmit-3-10 ...
  7. We will evaluate only your last submission (or resubmission) turned in before 1 pm (sharp) on Mar 12th.
  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.

Add reliable message delivery to minimessages. Each packet sent should be resent until the receiver acknowledges its receipt, or until timeout. Each receive should block until either a packet arrives or a receive timeout value is exceeded. You do not need to have more than one packet outstanding on any one connection. If you add reliable communication to your system, you will be able to undertake more exciting projects in the second half of the course.

Extend your scheduling algorithm from RR to a multilevel feedback queue. Your scheduler should have four levels. Processes should be scheduled round-robin at each level, and the time quanta should double at every level. Pick whichever policy you like in allocating the CPU between the multiple queues. Demonstrate that your scheduler works as intended.


Please download a new version of minithread_md.c, and replace the old version you are using. Or you can download a new version of minithreads2.zip.

This fix changes minithread_switch to unconditionally enable interrupts. This allows you to make all actions up to and including the final switch to another thread atomic with respect to each other. If you did not do this and instead wrote code like this:

	saved_interrupt_level = set_interrupt_level(DISABLED);
	/* manipulate the run queue */
	/* oops, an interrupt can occur now */

You would have problems if an interrupt occurred between the restoring of the interrupt level and the minithread_switch (actually, all the way halfway through the minithread_switch, as long as you are on the stack of the thread you are context switching out of). The new minithread_switch changes interrupts to ENABLED unconditionally (no saved_interrupt_level) in context_switch, the assembly language routine to change the stack pointers, which minithread_switch calls. Interrupts are enabled once the hardware stack pointer points to the new thread's stack: that is, all the dangerous work has been done.

Now your minithread_yield can look like:

 	/* manipulate the run queue */
	/* interrupts are now ENABLED */

You may have to use the same technique in minithread_stop, and in semaphore_P, since those have the same potential race conditions.

A new version of minithreads2.zip is available, incorporating some bug fixes and clarifications. Make sure you don't overwrite your own modified files when you extract the contents of this zip file!

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.