Operating Systems Project
1 Overview
DLXOS has been changed to fit the requirements for this lab. You will have to copy this new version of DLXOS (/home/cs314/project3.tgz) to see the changes.
Setup Instructions
As before:
mkdir ~/cs314/project3
cp /home/cs314/project3.tgz ~/cs314/project3/ cd ~/cs314/project3/
tar xvfz project3.tgz
Make sure you have /home/cs314/dlxtools/bin/ in your PATH. Compile as before : type make in ~/csc314/project3/src directory. Run in ~/csc314/project3/execs directory
DLXOS Modifications
DLXOS has been modified as follows:
The prototype of create process has been changed to facilitate passing in additional parame- ters: p nice and p info. The new prototype is:
void process_create(int p_nice, int p_info, char * args...);
See userprog.c for examples.
The function to return the time elapsed in seconds since the simulator start is my timer get(). There is a known bug with timerget(), so use this function instead to find out the elapsed time since simulator start:
uint32 my_timer_get(){
uint32 temp = total_num_quanta * 100 + total_num_quanta * 1; return temp;
}
Windows NT-style Multilevel Feedback Queue Scheduler
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. We'll 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. (Don't 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.
Assignment
Describe in detail how DLXOS schedules processes using the round-robin preemp- tive scheduler and the preliminary design of your WinNT scheduler. Do this before you begin coding. Update the document with a description of your actual implementation, explaining how it is different from what you had envisioned at the start.
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. You'll 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.
Compare round-robin and WinNT scheduling by showing the effect that priority setting in WinNT scheduling has on the process' time on the CPU over time. Do this by profiling both the round-robin and WinNT schedulers: keep track of which process is chosen for execution and compute the time taken to complete the execution of a process (from the time the process is created until it exits). Do this by creating sets of tasks and specifying different priorities for them at creation time.
Consider using p nice to set the process base priority and p info to control collection of CPU timings (it's not used for anything, so you can use it to pass data to the forked process).
3 What to Turn In
Turn in the following as a group:
A .tgz of your project directory, as before. (Any additional information that would be useful for grading: testing, configuration, compiling, etc should go into a README file.) The following should be included in your tgz, in addition to your code:
- group.txt containing information about your group.
- design.txt containing your detailed description of existing round-robin scheduling and preliminary and final design of your WinNT scheduler.
- profiles.txt containing a description and results of your timing experiments.
Individually:
Each group member should individually turn in a text file containing a brief account of your group activity. Keeping in mind your group's dynamic, answer at least the following questions: What worked? What did not work? What were you responsible for in the project? What could be done differently next time?
Attachment:- Project-3.tgz