Project 3: Preemptive Scheduling

Due: Midnight 10 November 2009

This project is managed by Nick Johnson.

The design review is worth a total of 5 points.

• System Calls: 1pt. Study the new system call mechanism and explain how it works. You should look at entry.S, interrupt.c, and syslib.c.
• irq0_entry: 1pt. Using what you know of system calls, explain in even greater detail what this does and how to use it.
• Blocking Sleep: 1pt. You should be able to explain how to implement blocking sleep, as well as its relationship with the ready queue.
• Condition Variables: 1pt.
• Semaphores 1/2pt.
• Barriers 1/2pt.

1. the fields of the structures that you will use, and
2. the pseudo-code for each operation.

For example, this is an acceptable explanation for the previous system call mechanism:

_start() writes the address of kernel_entry() to address 0xf00. When a process makes a system call, it looks up the address of kernel_entry() at 0xf00 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 previous 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.

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.

We have provided the program, tasks which prepares tasks 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).
• 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 prepare a set of tasks for 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. Over the course of the project, we may release additional task-sets to aid your testing.

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. Take note of the hint about calling C functions.
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.

Condition Variables

Semaphores

Barriers

• 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

Your writeup does not need to cover build procedures; an unmodified copy of the Makefile will suffice.

Regarding code style: We don't have strict rules concerning style; strive for clear code with meaningful comments. We think simple is better than complicated, but leave that choice up to you. However, code which does not compile---or only does so with warnings---is unacceptable.

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:

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

Please restrict your changes to these files. Submit via dropbox; only one person per group should submit.

• 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.
• If every process and every thread is sleeping, then the ready queue is empty. How can you handle this case? 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 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.
• 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.
• Remember that you can attach GDB to the programs running within bochs. The provided files include a properly configured .gdbinit file. To enable debugging, uncomment the gdbstub line at the top of bochsrc, then run bochs as usual. After bochs has started, and in a separate terminal, start gdb with the command gdb kernel, then issue the command target remote localhost:1234. Type c (for continue) to run; at any time, you can press CTRL-C in gdb to pause the simulator, and then use commands such as bt (for backtrace), b (for set breakpoint), etc.