Project 3: Preemptive Scheduling
Due: 11:59pm 5 November 2012
Overview
You will extend the provided kernel (which are available on both
Blackboard and the fishbowl machines at the directory /u/318/codes/project3/start_code_3.tar.gz) with
preemptive multitasking and implement several synchronization primitives.
Unlike the 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.
Besides, you will implement three kinds of synchronization primitives: condition variable, semaphore and barrier by yourself.
Getting Started
Refer to previous projects for information on building and testing your
project. Some versions of
gcc may not support the
-fno-stack-protector flag; it is safe to remove
this flag from
Makefile if you are using one
of those versions. If you are using fishbowl machines or the provided image on VirtualBox,
it should be fine to directly use the provided
Makefile.
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 x86 interrupt mechanism is quite complicated, so we will present
only the details relevant to this project. Interrupts can be triggered
in several different ways: hardware, software, exceptions. The timer
interrupt, IRQ 0, is a hardware interrupt, as is IRQ 7. The system call
mechanism, which uses the
int instruction, is
a software interrupt. Exceptions are generated for a variety of invalid
actions: dividing by zero, for example, will cause an exception.
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:
- Disable interrupts
-
Push the flags register, CS, and return IP (in that order)
- 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.
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
-
Increment the 64-bit counter,
num_ticks
-
Increment entry.S:disable_count to reflect the fact that interrupts
are off.
-
If nested_count is zero, enter the kernel the
way a system call would yield, else do nothing.
-
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 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
In the provided code, function
sleep
and
do_sleep work by spinning on
num_ticks.
Unfortunately, this loop runs within the kernel, and so it cannot be preempted.
As a result, if one task sleeps, all tasks 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
The main file you will edit here is
sync.[ch], but you will need to consult
queue.[ch] and
scheduler.[ch]. You have to implement condition
variables, semaphores, and barriers. 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.
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.
Please see the hints section.
|
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.
Please see the hints section.
|
semaphore_up(sem) |
Increments the semaphore.
Please see the hints section.
|
Fairness requirement: in a trace with exactly
n
ups, the downs that complete successfully are the first
n invocations. Calling
semaphore_init(sem, value) counts as
value
ups.
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.
Please see the hints section.
|
Design Review
First, take a look at
what we
expect from you in general.
The design review is worth a total of 5 points.
-
irq0_entry: 1 pt.
Comparing to what you know of system calls (although irq0 is a hardware interrupt while system calls are software interrupts, they share with similar workflows), explain what this does and how to use it.
-
Blocking Sleep: 1 pt.
You should be able to explain how to implement blocking
sleep (how to make a task sleep and how to wake it up), as well as its relationship with the ready queue.
If every process and every thread is sleeping,
then the ready queue is empty, how can you handle this case?
-
Condition Variable, Semaphore, Barrier: 3 pts.
For the above three synchronization primitives, specify 1)the data structure that you will use, and
2) the pseudo-code for each operation. The pseudo-codes provided in the hints are
almost right, you can start from there to fix the issues they have. Specially, try to satisfy the fairness requirement
for all primitives.
For example, this is an acceptable explanation for the
project 2's
system call mechanism:
When a process makes a system call, it
looks up the kernel_entry() and calls it with the ID number of the
system call. kernel_entry() saves the user
context in the PCB, restores the kernel stack, then calls
kernel_entry_helper().
kernel_entry_helper() multiplexes
(switch) its argument and invokes the "do_"
version of the system call. When kernel_entry_helper()
returns, kernel_entry() saves the kernel
stack, restores the user context, then returns to the process.
This is an example of an acceptable explanation of the
project 2's
implementation of lock:
The lock structure contains a bit indicating whether the lock is held or
not and a queue of threads waiting for the lock.
lock_init() sets the lock to not held and sets up an empty queue.
lock_acquire() enters a critical section and
tests if the lock is held. If it is, then it adds itself to the lock queue
and blocks. Otherwise, it sets the held bit. Finally, it leaves the
critical section. lock_release() also enters a
critical section and tests if there are any threads waiting on the lock.
If there are, it removes the next thread from the front of the queue and
unblocks it; otherwise, it clears the held bit. Finally, it leaves the
critical section.
You answer may not be so complete,
but at least you need to convince the TA that you understand the workflow of system calls and locks.
For the synchronization primitives, it would be nice if you write the pseudo-codes down to show to the TA.
Besides, as part of the previous year's design review requirement, we strongly suggest you to study
the new system call mechanism of this project and explain how it works. You should
look at at least
entry.S,
interrupt.c, and
syslib.c.
To siun up for a design review, use our
signup page.
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
Note: this is not intended to be a thorough list; just a quick
reference.
-
Preemptive Scheduling
- implement irq0_entry
- yields the current process
- edit: entry.S
-
Blocking Sleep
- Implement do_sleep
- Compute some future time at which the process should unblock.
- Remove the current process from the ready queue, save it somewhere else
- Periodically check if these blocked processes can be added to the ready queue
- edit: scheduler.c
-
Synchronization Primitives
-
Operations on uninitialized structures are undefined; you may
handle such cases as you like.
-
Unblocks place the current process at the end of the ready queue
- Must work with preemption
- Condition Variables
- Semaphores
- Barriers
- edit: sync.c
Submission
To ensure compatability with our tests, do the following:
- ./tasks tsk_test
- make clean; make
-
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.
-
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:
- common.h
- entry.S
- helper.S
- interrupt.h
- interrupt.c
- kernel.h
- kernel.c
- queue.h
- queue.c
- scheduler.h
- scheduler.c
- sync.h
- sync.c
- syslib.h
- syslib.c
- util.h
- util.c
Please restrict your changes to these files.
Submit via dropbox; only
one person per group should submit.
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
For another additional 1 point of extra credit, write an algorithm which automatically
tests for a particular class of deadlock. This algorithm
is conceptually simple, but may be difficult to implement:
Imagine a directed graph in which every process and every
lock is a vertex.
Draw an edge pi → lj
if process pi blocks while trying to acquire lock lj.
Draw an edge lm → pn if lock lm is held by process pn.
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.