Your task in this project is to make your user-level threads package preemptive.
In the previous project, you built a non-preemptive thread package and assumed that applications will cooperate with each other and voluntarily yield the CPU frequently. 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 monopolize the CPU by forcibly preempting them and switching to another process.
We have provided you with some code that emulates clock interrupts. When an interrupt occurs, the provided code begins executing the interrupt handling function, using the stack of the currently executing thread (this is similar to what a hardware interrupt controller does). Your task is to write an interrupt handling function that correctly handles clock interrupts.
You will also allow threads to interact with the clock by sleeping, and will implement a more sophisticated multi-level scheduler.
There are two versions of the release code on CMS. The first is a zip file containing skeleton code for the entire project. The second is a patch file that contains only the differences between the p1 release and the p2 release.
The easiest way to merge in the project 2 changes is to apply the patch file. To do this, make sure you have checked in your existing code. Then execute the following command in the directory containing your files:
patch -p1 < p1_p2.patch
This will attempt to merge the changes for p2 into your existing code base. If there are conflicts, the patch tool will report them, and you will have to fix them manually.
Review your merged code to ensure that the merge has not introduced any bugs.
There are a few distinct components to this project.
You will need to make your threads package preemptive. interrupts.h provides the interfaces you will need for this purpose. Soon after you initialize the clock module (using minithread_clock_init) and enable interrupts (set_interrupt_level), the system will begin calling your interrupt handler periodically. You should install a handler that causes the currently executing thread to yield. To check that your clock handler is being called, you can also put in print statements.
To check that you did this correctly, you should first set the clock period to a few seconds and print something from the clock handler to ensure it is working. You can do this by setting PERIOD in interrupts.h.
Afterwards, make sure that you disable all print statements since you cannot spend time printing to the screen in your interrupt handler if you want reasonable performance. After your interrupt handler works, set your clock period to 100 ms.
Interrupts can arrive at any time, including within the interrupt handler, so you must ensure that your code is interrupt safe. That is, your code should function correctly even if the interrupt service routine is called in the middle of execution.
Your semaphore implementation from project 1 is not interrupt safe. Modify your implementation so that the critical sections mentioned in the synchronization lecture here are protected by disabling interrupts.
An important requirement is that you can V a semaphore from within the interrupt handler.
In order to ensure interrupt safety, you may briefly disable interrupts by calling set_interrupt_level(DISABLE). Any interrupts that arrive while interrupts are disabled will be dropped, so your code cannot be interrupted while interrupts are disabled. This allows you to protect critical sections of your system code.
Disabling interrupts is dangerous, because the longer they are disabled, the more likely you are to lose interrupts. Therefore you should work hard to ensure that critical sections that are protected by disabling interrupts are as short and infrequent as possible. In particular, you must absolutely avoid running application code with interrupts disabled, or writing tight loops that disable interrupts.
Interrupts can be reenabled in two ways. The first is by calling set_interrupt_level. You will typically want to restore the interrupt level to its previous value rather than setting it directly to ENABLED. A typical critical section will look like this:
interrupt_level_t old_level = set_interrupt_level(DISABLED); execute_critical_section(); set_interrupt_level(old_level);This ensures that executing a critical section within a function will not accidentally reenable interrupts.
The second way to reenable interrupts is by calling minithread_switch, which always enables interrupts just after switching to the new thread.
Implement the interface in alarm.h, which allows you to schedule functions to be executed after a given delay. The alarm facility is intended to be used in the system implementation, and not by applications. This means that alarm functions may be run within the interrupt handling routine, and they may be run with interrupts disabled.
You should take care that any alarms that you schedule execute quickly. They should not perform I/O, and they absolutely must not block. For testing purposes, you might want to have the alarm print to the screen. However, make sure to remove them after you have correct code.
Using the system clock is too expensive for the interrupt service routine. Instead, you should keep track of the current time by counting clock interrupts. If an alarm is scheduled to execute between clock interrupts, it is fine to wait until the next clock interrupt to execute it.
The interrupt handler should be able to execute quickly even if there are a very large number of pending alarms. An interrupt handler that runs in linear time in the number of pending alarms will not receive full credit.
Use your alarm facility to implement the minithread_sleep_with_timeout(int timeout) function, which allows threads to block for a given duration.
External libraries such as the C standard library are not thread safe. For example, if a call to malloc is interrupted, it may leave the heap in an inconsistent state, causing future calls to malloc to fail.
To avoid this problem, the interrupt system we are providing automatically drops interrupts if they arrive while external library code is executing. In other words, while you are executing non-minithreads code, interrupts will be disabled.
This can cause many interrupts to be dropped if an application spends a lot of time in library code. For example, a thread that just does:
while(1)
printf("hello world\n");
will spend most of its time in the printf function, and will
effectively block all interrupts. This is considered acceptable (the alternative
is implementing minithread-safe versions of the entire C library!), but may
surprise you while testing.
1. Unnecessarily disabling interrupts.
2. Allowing user threads to run with interrupts disabled. (This frequently happens when returning from an interrupt handler without a context switch).
3. Incorrectly synchronized code (especially the portion of OS code that runs just after a context switch).
It's crucial that systems code be correct and robust. You must write your own test programs and test your code with reasonable and unreasonable test cases, and ensure that it behaves correctly.
Do not forget to check for memory leaks. Your threads package should not run out of memory when large numbers of threads or alarms are created and destroyed.
Make sure to test that preemption works with CPU-bound threads, and that your multilevel feedback scheduler is appropriately lowering thread priorities.
Use CMS to submit your project. You should include a README file with your name, your partner's name, and anything you think we should know. This includes documenting any broken functionality (although you will have trouble later on if you do not complete this project now, so you should not be submitting a broken project).
The files you should upload to CMS are:
Any of the following issues will prevent you from receiving full credit. Make sure your code doesn't:
Start early.