Project 3: Preemptive Scheduler

Project TA: Marcela Melara (melara@cs.princeton.edu)

Overview

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

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:

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 start code is available on Blackboard as project 3 - preemptive scheduler start code under Course Materials or on the lab machines at /u/318/code/project3/p3_start_code.tar.gz


Steps

  1. Review project specs and download the start code.
  2. Write your design review (due Mon Oct 21, 2013)
  3. Complete entry.S, scheduler.c with blocking sleep and sync.[ch]
  4. Compile and create the OS image.
  5. Test
    • Choose the appropriate test and run the Bochs emulator with your OS image.
    • Write the image to a USB disk, then boot off that device.
  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 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
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.

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

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 do 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) : If the semaphore is not positive, then block. Decrement the semaphore once it is positive.
semaphore_up(sem) : Increments the semaphore.

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:


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.

Each group must schedule a 10-minute design review slot. The Review will take place on Monday, Oct 21 between 10:00am and 7:00pm. Additional flexibility will be provided for extreme circumstances.

Some tips:

To sign up for a design review, use our signup page. We provide 30 time slots on Oct 21.


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.


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 Dropbox; only one person per group should submit. When submitting the assignment, please turn in the files specified in the Dropbox, along with your readme (less than 500 words in text format).