Project 3: Preemptive Scheduling

Overview

Design Review

Getting Started

Preemptive Scheduling

The support code installs handlers for IRQ 0, IRQ 7, the system call interrupt, and the various exceptions. Your job for this part is to complete the handler for IRQ 0, entry.S:irq0_entry; the others are given to you as examples. The main file you will be working with is entry.S, but you may need to consult other files, especially interrupt.[ch] and scheduler.[ch]. In particular, 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

As with entry.S:syscall_entry, it may be some time before entry.S:irq0_entry actually performs the iret, since other tasks may execute in the middle. IRQ 0 is a hardware interrupt, so you should acknowledge it quickly using the macro entry.S:SEND_EOI -- otherwise the hardware won't deliver any more timer interrupts. The other tasks entry.S:irq0_entry must perform are

1. Increment the 64-bit counter, num_ticks
2. Increment entry.S:disable_count to reflect the fact that interrupts are off
3. If nested_count is zero, enter the kernel the way a system call would
4. Yield. Take note of the hint about calling C functions below
5. If nested_count was zero, leave the kernel the way a system call would
6. Decrement entry.S:disable_count in anticipation of
7. iret

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:

• Safety: To avoid race conditions, interrupts should be off whenever your code is accessing kernel data structures, primarily the PCBs and task queues.
• Liveness: Interrupts should be on most of the time so that threads, processes, and system calls that take too long are preempted.

Synchronization Primitives

In the descriptions below, if an operation is performed on a uninitialized structure, the results are up to you. All unblocks should place the unblocked thread at the end of the ready queue.

Checklist

Grading

• Preemptively scheduled threads and processes
• Condition Variables
• Semaphores
• Barriers
• Writeup, style, and submission mechanics

The writeup should include:

• A statement regarding the correctness of your project. Are there any parts that you have not completed, that do not follow the specification, or otherwise don't work? In what way? If a shortcoming you discuss cascades into a disproportionate number of failures against test cases, we may restore some credit. State if you believe your implementation to be correct in all ways.
• An overview of your design, modulo aspects that we discessed in the design review.

We don't have strict rules concerning style; strive for clear code with meaningful comments.

Submission

Hints

• We have provided a printf function.
• C functions are allowed to trash registers %eax, %ecx, and %edx. Keep this in mind when calling them from assembly.
• This example suffers from a race condition:

  void condition_wait(lock_t *lock, condition_t *cond) { lock_release(lock); /* 1 */ enter_critical(); block(&cond->wait_queue); leave_critical(); lock_acquire(lock); }

  At location 1, we may be preempted, then another thread can acquire the lock and signal, resulting in a lost wakeup.
• As does this:

  void semaphore_up(semaphore_t *sem) { enter_critical(); ++sem->value; unblock_one(&sem->wait_queue); leave_critical(); } void semaphore_down(semaphore_t *sem) { enter_critical(); if(sem->value <= 0) { block(&sem->wait_queue); } --sem->value; leave_critical(); }

  Consider this trace: thread 1 calls down, but the value is 0, so it blocks; thread 2 calls up, unblocking thread 1; before thread 1 can run, however, thread 3 calls down; thread 1 now decrements the value to -1. Consider how to satisfy the fairness condition before applying the obvious fix.
• And this:

  void barrier_wait(barrier_t *bar) { enter_critical(); if(--bar->value > 0) { block(&bar->wait_queue); ++bar->value; } else { unblock_all(&bar->wait_queue); ++bar->value; } leave_critical(); }

  Suppose bar->value is initially 4, and thread 4 is the last of four threads to call barrier_wait(bar). Thread 4 will unblock the other threads and increment bar->value to 1. Now, if thread 4 immediately calls barrier_wait(bar) again, it will return immediately, contrary to the specification.

Extra Credit

Blocking Sleeps

If you implement blocking sleep, add #define EC_BLOCKING_SLEEP to scheduler.h.

Prioritized Task Scheduling