Project 6

Submit: Turn in your entire xinu-hw6 directory source files using the turnin command on morbius.mscsnet.mu.edu or one of the other Systems Lab machines. Please run "make clean" in the compile/ subdirectory just before submission to reduce unnecessary space consumption.

Work should be completed in pairs. Be certain to include both names in the comment block at the top of all source code files, with a TA-BOT:MAILTO comment line including any addresses that should automatically receive results. It would be courteous to confirm with your partner when submitting the assignment.

Scheduling

Preparation

First, make a copy of your Project 5 directory:
cp -R xinu-hw5 xinu-hw6
Then, untar the new project files on top of it:
tar xvzf ~brylow/os/Projects/xinu-hw6.tgz

Be certain to make clean before compiling for the first time.

Proportional Share Scheduling

In prior Embedded Xinu projects, we have had a simple, FIFO-based cooperative scheduling algorithm. (See section 7.3 in our textbook.) For this project, we will improve upon this with a Proportional Share scheduling algorithm (See section 9 in our textbook,) also sometimes called a "Lottery" scheduler, or a "Fair Share" scheduler. The basic idea is that each ready process gets a number of "tickets". When rescheduling, the O/S generates a random number and picks a "winner" process to be context switched in next. Processes with more tickets will naturally win more often over time, and thus will run for more timeslots.

This proportional share scheduler can be implemented in three easy steps:

Add an unsigned integer field called "tickets" into the PCB structure defined in include/proc.h.
Add an unsigned integer priority parameter to create(), and properly initialize the tickets field in each new PCB created. (Make priority the third argument to create(), between ssize and name.)
Modify the resched() function to call a helper function that totals up the number of ready process tickets and calculates a random winner. (A basic implementation is in Figure 9.1 of the book.) See corresponding TODO comments in resched.c for details.

New test cases are in system/testcases.c, which should demonstrate Proportional Share execution once your new scheduler is operational. You will need to create others to fully test your implementation.

Preemption

The new files system/clk* will provide you with basic preemption, as discussed in class. Take time to familiarize yourself with the contents of these files, as you will be responsible for understanding how these components of the operating system work.

Activate preemption by changing the PREEMPT constant in include/kernel.h to TRUE. How can you test that preemption is working in your system? Create a test case that demonstrates preemptive scheduling. Put your preemption test case in testcases.c, and make it run when the input is 'P'.

dispatch.c

The following lines (specifically the else statement) will need to be added to your dispatch() function in the dispatch.c file to handle interrupts.

if((long)cause > 0) {
    cause = cause << 1;
    cause = cause >> 1;

    // ... Your dispatch code here ...
} else {
    cause = cause << 1;
    cause = cause >> 1;
    uint irq_num;

    volatile uint *int_sclaim = (volatile uint *)(PLIC_BASE + 0x201004);
    irq_num = *int_sclaim;

    if(cause == I_SUPERVISOR_EXTERNAL) {
        interrupt_handler_t handler = interruptVector[irq_num];

        *int_sclaim = irq_num;
        if (handler)
        {
            (*handler) ();
        } else {
            kprintf("ERROR: No handler registered for interrupt %u\r\n",
                    irq_num);

            while (1)
                ;
        }
    }
}

Notes