Project 3: Preemptive Scheduling

Overview

Getting Started

We have provided the program: tasks which prepares tasks (test cases) for your OS to run. Its usage is ./tasks taskset. We have also provided five test sets:

• 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 26 threads and 1 process. The threads all sleep for a random period of time, and then barrier_wait on a common barrier. They repeat this process several times.
• tsk_test tests priorities, locks, condition variables, semaphores, barriers, etc. Its output is self-explanatory. Note: it does not test the deadlock detection extra credit.

For example, to test the barrier primitive on your OS, run ./tasks test_barrier and then make clean. This will update the symbolic links in your main project directory so that, upon recompiling the project, your OS will run those tasks.

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 suite your needs.

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

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 yield, else do nothing.
4. Decrement entry.S:disable_count in anticipation of 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 processes that take too long are preempted.

Blocking Sleep

You must modify the provided implementation 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

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.

Design Review

Hints

• We put -Wall -Wextra -Werror flags in the Makefile to enable all warnings and make them errors, so your code must be warning free. When you start developing, you may turn off those flags for convenience, but don't forget to re-enable them for the final test.
• Don't forget to link a test case using ./tasks taskset before compiling.
• We have provided a printf function, by which you can do some debugging.
• C functions are allowed to trash registers %eax, %ecx, and %edx. Keep this in mind when calling them from assembly.
• If interrupts are disabled, will the kernel clock num_ticks continue to increment?
• 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 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.
• We have provided a system call named write_serial, which writes a character to bochs' serial port. Additionally, we have configured bochs so that everything written to its serial port is in turn written to a file named serial.out on the real computer. This could be helpful for debugging. However, please ensure that the code you submit does not use write_serial, since we may use it for testing purposes.

Checklist

Submission

To ensure compatability with our tests, do the following:

1. ./tasks tsk_test
2. make clean; make
3. Fix any compilation errors without modifying files within tsk_test. Upon running, the screen should display which extra credits you have attempted. If the display is incorrect, then fix your #defines in common.h.
4. We encourage you to print out diagnostics as a way to inspect your code. However, please do so in a way that leaves the output of the supplied tasks intact.

When you are ready to submit, You will submit only these files along with a readme which should be no more than 500 words:

1. common.h
2. entry.S
3. helper.S
4. interrupt.h
5. interrupt.c
6. kernel.h
7. kernel.c
8. queue.h
9. queue.c
10. scheduler.h
11. scheduler.c
12. sync.h
13. sync.c
14. syslib.h
15. syslib.c
16. util.h
17. util.c

Extra Credit

Prioritized Task Scheduling

For an additional 1 point of extra credit, change the scheduler algorithm so that it allocates precessor time proportional to each task's priority. If you choose to do this, you should come up with your own priority scheduling algorithm and describe it 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. In the syslib.[ch] files we have provided a setpriority function for you to use. If you observe that two counters are growing in different rates and the priority numbers and entry counts of processes/threads are changing as you extected, probably your algorithm works. You do not need to submit these test cases.

If implemented, add #define EC_PRIORITIES to common.h and report it in your readme.

Automatic Deadlock Detection

Imagine a directed graph in which every process and every lock is a vertex. Draw an edge p_i → l_j if process p_i blocks while trying to acquire lock l_j. Draw an edge l_m → p_n if lock l_m is held by process p_n. Whenever this graph contains a cycle, a deadlock has occurred.

You don't need to implement this as a graph algorithm per se, but for extra credit you do need to implement something which is at least as sensitive as this this algorithm, and which has no false positives.

If a deadlock is detected, lock_acquire fails with return value 1. In all other situations, lock_acquire returns 0. Only one call to lock_acquire should fail for a single deadlock situation. A failed lock_acquire should not affect the state of the lock (it should remain locked). This enables one process to recover from failure, and all other processes to continue as normal. For instance, that process may choose to release all locks it holds and then retry.

This style of deadlock detection is only relevant to locks, and is not relevant to semaphores, condition variables or barriers. In fact, it's only relevant to a restricted use of locks, in which locks are only unlocked by the same process which locks them.

To test your implementation of deadlock detection, create a new test set containing processes which will necessarily deadlock. These processes should report if lock_acquire ever returns failure. You do not need to submit these new test cases.

If you implement this extra credit, you should add #define EC_DEADLOCK to common.h, and report it in your readme.