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.

Lottery 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.
• 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 timer-based preemption. The onboard clock hardware will be set to raise a clock interrupt every millisecond. The clock interrupt passes through the Xinu trap handler, xtrap(), and is routed to the interrupt dispatch function, dispatch(). From there, the specific clock handler is called, and the O/S updates its clock time variables, decrements its quantum counter, and calls resched() if the quantum has ended.

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'.

Interrupts On!

With the inclusion of clock timer interrupts, it is now important that each new process starts with hardware interrupts masked on. While we provide helper functions in intutils.S to enable(), disable(), and restore() the global interrupt mask, we do not wish to force each user process to explicitly call enable() for normal functioning. Moreover, if a process "forgets" to turn on interrupts, regular clock-driven preemption does not function properly.

Setting up user processes to run with interrupts on by default can be accomplished in three easy steps:

• Add an additional processor state value to the initial process context record setup in create.c,
• Move that state value into the CPSR register during the bottom half of ctxsw(), and
• Store the outgoing CPSR value into the mirror image context record for the outgoing process in the top half of ctxsw().

As you can see in the disable() function in system/intutils.S, the ARM opcode

mrs r0, cpsr

moves the current value of the CPSR (Current Program Status Register) into register r0 so that it can be returned back to the calling C function. The specific bits of CPSR are defined in ARM processor documentation, but the most relevant bits for this assignment are the rightmost eight "control" bits, which select the processor protection mode and mask on or off various interrupt sources.

Similarly, the code in the restore() function in system/intutils.S,

msr cpsr_c, r0

reloads the control bits stored in the r0 argument back into the processor CPSR register.

For the second two bullets listed above, you must incorporate these opcodes into your existing ctxsw() to store and restore the CPSR register. Take special care not to stomp on important values in the existing registers or context stack -- there are many correct ways to implement this, but many more incorrect ways are available. Because your team has created your own versions of ctxsw() and create(), the project tarball does not contain new versions of these files, so there are no new TODOs in those files. Instead, this spec serves as the instructions.

Finally, there is the matter of initializing a brand new process starting CPSR value over in create(). This is very similar to the way in which you built the initial funcaddr and userret values into the new process context record. For now, we want the initial CPSR to put the process in ARM_MODE_SYS "System" privilege mode, and to mask off the "Fast IRQs" bit, ARM_F_BIT. Construct your initial CPSR value by ORing these together.

In contrast, the ARM_I_BIT bit, which masks off hardware interrupts, should be left clear. You will know this is working when you can reschedule to a new user process and that process displays interrupt-driven preemption automatically.

Notes

• To submit your project, please run "make clean" in your compile directory, change directory back two levels, and submit the entire system with the command turnin xinu-hw6. You can verify what you have submitted using turnin -v.
• To complete this assignment, you will have made changes to several header files in the include/ directory, and many .c files in the system/ directory.