Project 3: Preemptive Scheduler


Overview

In this third project, you will add support for preemptive scheduling and synchronization in the kernel. Specifically, it will be your job to modify entry.S, scheduler.c, sync.h and sync.c.

WARNING: Do not view the starter code for this project before completing the previous one. Doing so is a violation of the honor code.

Unlike the second project, the tasks in this project can be preempted by another task via a timer interrupt. You need to deal with the timer 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:

We have provided starter code which contains 24 files:

We also provide five test programs for you to test your code at various stages. See
Testing for instructions on how to use these tests.

The starter code is available at /u/318/code/project3 on courselab.


Steps

  1. Review project specs and download the start code
  2. Attend Design Review
  3. Complete entry.S, scheduler.c with Blocking Sleep and sync.[ch]
  4. Compile and create the OS image
  5. Testing
    • Choose the appropriate test and run the Bochs emulator with your OS image
  6. Complete the general project requirements
  7. Submit

Preemptive Scheduling

Processes and threads in x86 are preempted using a timer interrupt. In x86, interrupts can be triggered in several different ways: hardware, software, exceptions. For this project, the relevant interrupt, the timer interrupt IRQ 0, is a hardware interrupt.

The starter 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. 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. 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
Once the interrupt handler has run, it returns control to the interrupted task with the iret instruction, which pops the instruction pointer and the flags register, then reenables interrupts.

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

  1. Increment the 64-bit counter, time_elapsed
  2. Increment entry.S:disable_count to reflect the fact that interrupts are off
  3. Check whether nested_count is zero. If it is, enter the kernel the way a system call would yield, otherwise do nothing
  4. Check whether there are tasks ready to be awakened (Note: You'll need to implement Blocking Sleep to finish this part!)
  5. Decrement entry.S:disable_count in anticipation of iret
nested_count is a field in the PCB. For processes, it is 1 during a system call and 0 otherwise. For threads, it is always 1. You should study how interrupt.c changes this field during a system call. This will help you implement the macro TEST_NESTED_COUNT in entry.S.

This may not look very hard, but the tricky part is managing when interrupts are on, and when they are off. Your solution should satisfy the following two properties:

Once you have the timer interrupt handler, you will want to implement put_current_running() function in scheduler.c. This function saves the currently running task in anticipation of a preemption.


Blocking Sleep

The other major aspect to preemptive scheduling is blocking sleep. This is supposed to suspend the currently running task, and allow the next task in line to execute for some time period, until the next task is woken up and run for some time.

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.

A non-conforming implemention of do_sleep() has been provided. You must modify the implementation of do_sleep() so that calls to sleep block the current process (i.e. take it out of the ready queue until some appropriate time in the future) instead of busy waiting.


Synchronization Primitives

An important part of preemptive scheduling is to handle synchronization. Thus, you will implement three synchronization primitives in this project: condition variables, semaphores, and barriers.

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.

Condition Variables

condition_init(cond) : Initializes the specified memory to hold a condition variable
condition_wait(lock, cond) : Releases lock, blocks until signalled, then reacquires lock. The calling thread is responsible for acquiring lock before calling this function
condition_signal(cond) : Unblocks the first thread to have blocked on condition_wait(lock,cond). If no thread is blocked on cond, then does nothing
condition_broadcast(cond) : Unblocks all threads that have blocked on condition_wait(lock,cond). The order in which threads are unblocked is not important

Semaphores

semaphore_init(sem, value) : Initializes the specified memory to hold a semaphore whose starting value is value; a non-negative integer
semaphore_down(sem) : Decrement the semaphore, and block the current process if the value is now negative
semaphore_up(sem) : Increment the semaphore, and unblock one waiting process if the value was negative

Barriers

barrier_init(bar, n) : Initializes a barrier for use by n threads
barrier_wait(bar) : Blocks until a total of n threads have called barrier_wait(bar). The order in which threads are unblocked is unimportant. Immediately after the last call to barrier_wait(bar) returns, and possibly before the other calls have returned, the barrier is available for another round of waits

Testing

After you complete each phase of the preemptive scheduler, you should test it with one of our provided test programs. The script: settest prepares a specified test for your OS to run. Its usage is ./settest test_name_here. Then simply run bochs to see the test in action.

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:

Note:

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.

When you have finished the project, the test_all test should look similar to this:

Regular credit screenshot

Design Review

As always, please take a look at
what we expect from you in general.

For this project, at your design review, we want you to be able to describe the workflow of all the preemptive scheduling components you will be implementing.
You should be able to describe:

You need to convince the TA that you understand the workflow of the timer interrupt and the synchronization primitives. It would be helpful to write the pseudo code down to show to the TA.

Though not required for the design review, we strongly suggest you to study the new system call mechanism of this project, familiarize yourself with the mechanics of round-robin scheduling, and devise the steps the scheduler needs to take in order to complete one cycle of scheduling. Knowing this is key to understanding what each component of the scheduler must take care of.

Some tips:

Use the signup sheet to schedule a time to see the TA.


Hints


Checklist

Here is a rough checklist to help you complete the three phases of the project:

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.

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.

If you do attempt the extra credit, insert the line #define EC_PRIORITIES near the top of common.h. You may ignore any mentions of deadlock extra credit in this assignment.

When you have finished the extra credit, the test_all test should look something like this:

Extra credit screenshot

Program Submission

Don't forget to complete the general requirements for each project! In particular, you need to submit a README file, which concisely describes your design and implementation, and what parts work and what parts you didn't get to work. You don't have to repeat anything you presented in the design review. If you implement the extra credit, describe your priority scheduling algorithm.

Submit via Canvas.