I am supposed to create a Windows-NT scheduler but am not sure how to go about it. We have a version of DLXOS written specifically for this project.

The basic DLXOS scheduler is round-robin with preemption. This project asks you to implement a Windows-NT multilevel feedback queue scheduler described in this document (more accurately, something that very much resembles a WinNT scheduler).

Processes in the WinNT scheduler are assigned priorities ranging between 0 to 31. Real-time processes use base priorities 16-31, variable levels are 1-15, and 0 is reserved for system level. Processes that are ready for execution reside in one of 32 runqueues, each associated with a specific priority level. Processes within each runqueue are not ordered. A process has two priority values associated with it, base and current. The current priority for processes in the variable levels is often higher than the base priority. Processes in the real-time range never change priority (we will not have any processes in this range anyway). Processes reside in a priority queue that matches their current priority.

A quantum is the amount of time a process gets to run before the scheduler checks whether another thread at the same priority will get a chance to run. If there are no other processes at the same priority, the running process is rescheduled. Each process has a quantum value that represents how long the process can run until its quantum expires; the value is an integer value. By default all processes start with a quantum value of 6. Each time the clock interrupt occurs, a fixed value (3) is deducted from the process quantum. If this results in the process quantum becoming 0 or less, another process may be selected to run. The length of the clock interval varies according to hardware platform. Well make ours 10ms.

A process quantum may additionally be doubled when process priority priority is boosted to avoid priority inversion. Additionally, when a thread comes out of a wait state, its quantum is decremented by 1 (if this adjustment results in a 0 quantum, then the quantum is reset to the process default value). When a process enters the wait state, the quantum value is unchanged.

At the end of a quantum (the value reaches 0 or less), the scheduler determines whether the priority of the process should be decremented. If priority is reduced, the scheduler looks for a more appropriate process to schedule (remember: highest priority ready processes run first). If priority is not reduced, then the process is placed at the tail of the queue in the same priority level. The scheduler scans the run queues starting with the highest priority one and runs the process at the head of the first non-empty queue it finds. (Dont forget to reset the quantum value of a process reaching 0 or less back to its default: 6)

A process does not have to finish its quantum for another process to run. At each clock interrupt, if a higher priority process is available, the currently executing process will be preempted. A preempted process stays at the head of its priority run queue. When it is eventually scheduled again, the process finishes executing the remainder of its time.

On completion of I/O events, the priority of a waiting process is boosted by 2 (in Windows NT, the amount of the boost depends on the type of device responsible for the I/O event, with higher boost values being associated with slower devices). At the end of each quantum, a boosted process decays by one priority level until it reaches its base priority.

To avoid starvation, all queues are scanned once a second. If a process is found to have been in the ready state for longer than 300 clock interrupts, that process priority is boosted to 15 and given double the normal quantum. Once these quantums are up, the process priority immediately decays back to base priority.

Implement the described WinNT scheduling in DLXOS by modifying process.c and process.h, and any other files necessary. At the very least, test the implementation with the userprog provided inside project3.tgz. Youll likely need to modify at least these functions: ProcessSchedule(), ProcessSuspend(), ProcessWakeup(), and ProcessFork(), in addition to whatever utility functions are necessary.

Let every process start at the default Normal priority (8) for this part.