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.
If you have problems or questions, please send mail to cs414@cs.cornell.edu 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.
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.
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.
Announcements
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 */ set_interrupt_level(saved_interrupt_level); /* oops, an interrupt can occur now */ minithread_switch(...);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:
set_interrupt_level(DISABLED); /* manipulate the run queue */ minithread_switch(...); /* 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!