Project 3: Preemptive Scheduler

Overview

Unlike project 2, the tasks in this project can be preempted by another task via a time interrupt. You need to deal with the time interrupt and handle the critical section issues so that a task can be preempted safely. Additionally, you will implement three kinds of synchronization primitives: condition variables, semaphores, and barriers. To fulfill the requirements of this project, you must determine:

• when interrupts are on, and when they are off
• how round-robin scheduling works
• how tasks are put to sleep and woken up
• the properties of synchronization primitives

We have provided starter code which contains 24 files:

• entry.S: Contains the entry points to several kernel facilities
• scheduler.[ch]: The kernel's process scheduler
• sync.[ch]: The kernel's synchronization facility
• interrupt.[ch]: The kernel's interrupt facility
• syslib.[ch]: The kernel's system call facility
• kernel.[ch]: A 264-sector kernel
• queue.[ch]: The library and implementation for a queue
• util.[ch]: Useful helper functions
• printf.[ch]: Printing functions for debugging
• common.h: Library for common type definitions
• createimage: The executable for creating a bootable image
• bootblock: The executable for the bootloader
• helper.S: Helper function for some of the provided test programs
• settest: Script to set up a specific test for the preemptive scheduler
• Makefile: Used to compile and create your files
• bochsrc: The configuration file for the Bochs emulator

Steps

Preemptive Scheduling

The start code includes handlers for the system call interrupt, irq0 interrupt, and the various exceptions (in particular, IRQ 7 used in the test programs). The first part of implementing preemptive scheduling is to complete irq0_entry and the TEST_NESTED_COUNT macro in entry.S. We recommend you use the other handlers as guides. At the same time, the second part of implementing preemptive scheduling is to complete the put_current_running() function in scheduler.c.

You will want to consult scheduler.h and queue.[ch] to familiarize yourself with the queue data structure we provide, and since the definition of the PCB structure has moved to scheduler.h.

The processor takes the following actions on an interrupt:

1. Disable interrupts
2. Push the flags register, CS, and return IP (in that order)
3. Jump to the interrupt handler

IRQ 0 is a hardware interrupt, so you must acknowledge it quickly using the macro entry.S:SEND_EOI -- otherwise the hardware won't deliver any more timer interrupts. The tasks entry.S:irq0_entry must perform are

Blocking Sleep

For this part of the project, it is your job to implement the do_sleep() and check_sleeping() functions in scheduler.c so that the currently running process can be put to sleep and the next one in line woken up. check_sleeping() takes care of checking when it is time to awaken all sleeping processes whose deadlines have been reached. The passing of the deadline is determined in part by looking at time_elapsed.

Unfortunately, the current implementation of do_sleep() has a loop that does not allow it to be preempted. As a result, if one task sleeps, all tasks sleep. You must modify the provided implementation of do_sleep() so that calls to sleep will block the current process (i.e. take it out of the ready queue until some appropriate time in the future).

Synchronization Primitives

The files you will edit here are sync.c and sync.h. You will need to consult queue.[ch]. In particular, in sync.h, you must define the properties of each of the sync primitives, where knowing how to use queues will be very useful.

We've given you an implementation of locks as a reference. These primitives must operate correctly in the face of preemption by turning interrupts on and off with the functions enter_critical and leave_critical.

In the descriptions below, if an operation is performed on an uninitialized structure, the results are up to you. All unblocks should place the unblocked thread at the end of the ready queue. For each of the primitives, you must implement the following functions.

Testing

In order to clean up your directory after running a test you may run make cleantest, which cleans and removes all the testing files. If you just want to reset your kernel, scheduler etc. you should run make clean.

These are the five provided tests:

• test_regs observes the value of all registers both before and after a loop. Presuming that the process is preempted at some time during the loop, it will compare the values before and after, to see if any registers were improperly clobbered by preemption. Although this will test all registers (and flags), note that some classes of errors may manifest themselves rarely, and so passing this test does not mean that your code is perfect.
• test_preempt creates two processes which spin as quickly as possible, but never yield or sleep. If you see that both counters are incrementing, then preemption is working (at least a little bit). Notice that for some reason, the counter growing speeds of two processes may be different, but the numbers of entry counts must be roughly the same if you are doing the round robin scheduling.
• test_blocksleep creates two threads, and one goes to sleep. It tests four things: (i) that the scheduler survives when all processes are sleeping, (ii) that a process is not re-entered during sleep, (iii) that sleep lasts about the right amount of time, and (iv) the non-sleeping process is scheduled during the sleep.
• test_barrier creates 3 threads. The threads sleep for a random period of time, and then barrier_wait on a common barrier. They repeat this process several times.
• test_all is the final test for your project 3 solution. It tests priorities, locks, condition variables, semaphores, barriers, etc.

Note:

• The outputs of all the tests are self-explanatory, and tell you if something has gone wrong.
• If you implement the extra credit, you will have to uncomment some portions of some of the tests in order to test your solution.
• All tests need all the files in the test directories in order to function properly, even if some of these files don't contain any code. Don't waste time trying to change this format. It has to do with how the kernel is built by createimage.

Lastly, here is an example for how to test your code. Suppose you want to test the barrier primitive on your OS, run ./settest test_barrier and then bochs

If you wanted to create your own test set, or to create a test set with no processes, you could copy one of these test sets to a new directory, and then modify it to suit your needs.

Use this to test your kernel. We will use similiar test cases when grading.

Design Review

Hints

• The counter time_elapsed in scheduler.c counts the number of clock ticks.
• The variable nested_count is not very clear, so here's a rephrasing of what it's trying to say. nested_count indicates whether we are in kernel mode (e.g. when the kernel is currently performing a system call, or a kernel thread is being executed), or not. If we are in kernel mode, nested_count = 1, otherwise nested_count = 0.
• Let's rephrase what "If nested_count is zero, enter the kernel the way a system call would yield, else do nothing." is trying to say. If nested_count is zero, we know we are not in a system call. So we need to enter the kernel. We want to use the fact that a timer interrupt was invoked in order to preempt tasks. In particular, what part of the kernel do we need to enter? The scheduler. This is where the actual switching between tasks happens. But what if nested_count is not zero? The specs tell us to "do nothing". So we just return? Well, what got us here is the fact that the currently running task was performing a system call (or is a kernel thread), and the processor timer went off in the middle of it (If you look at system_call_helper() in interrupt.c you'll see that it is possible for this to happen.) Since we're in the middle of a system call, we want to let that system call finish. So in irq0_entry, the comment that says do system call actually goes right above the return label, because do we want to switch tasks if we're in the middle of a system call? This should help you determine the workflow of irq0_entry.
• If interrupts are disabled, will the kernel clock time_elapsed continue to increment?
• What does the incrementing of disable_count imply, what does the decrementing of disable_count imply? Recall that we do this to indicate that interrupts are on/off. When does this happen?
• Use the provided macros in entry.S whenever you need to save a context, restore a stack etc. They are there to save you some work, and to make your code more readable and uniform.
• For completing the semaphores, a notion that should help you avoid the mistakes in the warm-up exercise is the idea that for every semaphore_up invocation, there should be a corresponding semaphore_down invocation. What this means is that, if there is an unbalance because there are more processes calling one or the other, your code should not allow race conditions to arise. Calling semaphore_init(sem, value) counts as value ups.
• C functions are allowed to trash registers %eax, %ecx, and %edx. Keep this in mind when calling them from assembly.

Checklist

Extra Credit

Prioritized Task Scheduling

For an additional 1 point of extra credit, change the scheduler algorithm so that it allocates processor time proportionally to each task's priority. If you choose to do this, you should come up with your own priority scheduling algorithm. We provide the functions do_getpriority and do_setpriority in scheduler.[ch] to help you with this. Describe your algorithm in your README_EXTRA.

One way to test your implementation of priority scheduling would be to modify test_preempt, so that each task has a different priority. If you observe that two counters are growing at different rates and the priority numbers and entry counts of processes/threads are changing as you expect, your algorithm probably works. You do not need to submit these test cases.

Program Submission