Project 2: Non-Preemptive Scheduling

Overview

Important Dates

Design Review

Design Review is graded as follows:
Data structures diagram
1 point. Draw the contents of the data structures for PCBs, locks, and any other structures you need.
Scheduling
1 point. Given that the threads below are listed in order, explain how the execution unfolds and why.
Kernel threads and scheduling design
1 point. Describe at a medium level how you will implement this part, with particular emphasis on how you are using your data structures.
Processes and system calls design
1 point. Similar to the above.
Mutual exclusion design
1 point. Similar to the above.

The threads:

Thread 1

lock_init(&lock);
lock_acquire(&lock);
do_yield();
lock_release(&lock);
do_exit();

Thread 2

while(TRUE) {
    do_yield();
}

Thread 3

do_yield();
lock_acquire(&lock);
lock_release(&lock);
do_exit();

Thread 4

lock_acquire(&lock);
lock_release(&lock);
do_exit();

Glossary

For 1 point extra credit: using util.c:get_timer(), implement a scheduler that allocates CPU time fairly, together with some tests that prove to us that it's working. The grading criteria will be similar to that of the main assignment.

Hints

• The boot loader provided to you for this project does more than the one you wrote last project. Specifically, it enables address line 20 and enters protected mode.
• One of the first things you will need to do is to implement a queue data structure. gdb is a much nicer environment than bochs in which to debug, so we strongly recommend you that you test your data structure code in user-space first.
• We've placed examples of how to call C from assembly and vice versa in hello1.c and hello2.S. Build the executable by typing make hello.
• The dependencies of the parts of this project look like this:

                     Processes --> Timing a process context switch
  Kernel threads --> Mutual exclusion
                     Timing a thread context switch
  

• We have tried to specify the scheduler in such a way that at any point in the execution, there is exactly one correct choice for which task to schedule next. If you have even the slightest doubt about what this choice is in some situation, please contact us for clarification--some of our test code will assume that your scheduler is doing what we think it should.
• Saving and restoring the general purpose registers (eax, ecx, edx, ebx, esp, ebp, esi, edi) is reasonably straightforward, but the flags register (eflags) is tricky. The only way to save eflags is the instruction pushf, which pushes the contents of eflags onto the stack--eflags is not a valid operand for mov. Similarly, the only way to restore eflags is popf, which pops the top of the stack into eflags. Worse, you must take care not to alter any register before it is saved or after it is restored, and many instructions set and clear flags. Instructions that don't alter eflags include mov, pop, push, pushf, and ret, while arithmetic operations typically do. Consult the x86 manuals for more information.
• To allocate space for the PCBs, declare an array of PCB structures, for example,
  static pcb_t pcbs[NUM_TASKS];
  and then link them together as necessary.
• Several people have asked why we declared ready_queue as a PCB structure as opposed to a pointer to one. The answer is that our queue uses this structure as a sentinel node--you should feel free to change the type of this declaration or even delete it.
• I inadvertently left the declaration
  pcb_t ready_queue;
  in the provided source code. Please feel free to change or delete this declaration--it is an internal implementation detail.
• If you have an address as a uint32_t and want to write to it from C, you have to cast it to a pointer:
  *(uint32_t)address_as_an_integer = value;
• The popf and pushf instructions do not take any operands. They always pop/push eflags from/onto the stack (i.e., the current value of esp, which may not correspond to any of the stacks you allocate to tasks).

Grading Criteria