ASSIGNMENT
Exercise I
There are three processes in the scheduling queue and assume that all three of them are ready to run. Assume that P1 arrived a little before P2; and P2 arrived a little before P3. Scheduling starts at time t = 0. The CPU and I/O burst patterns of the three processes are as shown below:
Given the following processes that arrived in the order shown
|
|
CPU Burst Time
|
IO Burst Time
|
CPU Burst Time
|
IO Burst Time
|
CPU Burst Time
|
|
P1
|
4
|
2
|
4
|
2
|
4
|
|
P2
|
5
|
2
|
5
|
|
|
|
P3
|
2
|
2
|
2
|
2
|
2
|
Each process exits the system once its CPU and I/O bursts as shown above are complete.
Show the activity in the processor and the I/O area using the FCFS, SJF, and Round Robin (time quantum = 2) algorithms
For each algorithm, compute the average waiting time, the average response time, and the throughput.
Exercise II
Recall that Shortest Remaining Job First (SRJF) is a variant of Shortest Job First (SJF) with preemption added in. Consider the following three processes vying for the CPU. The scheduler uses SRJF. The scheduler re-evaluates which process to run only upon the arrival of a new process into the scheduling queue, or the completion of a process. The table shows the arrival time of each process.
|
Process
|
Arrival Time
|
Execution Time
|
|
P1
|
To
|
5 ms
|
|
P2
|
To + 2 ms
|
4 ms
|
|
P3
|
To + 3 ms
|
1 ms
|
The scheduling starts at time To.
Fill in the table below with the process that is executing on the processor during each time slot. Be sure to show your work as to how you arrived at schedule.
|
To+
|
0
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|
Running
|
|
|
|
|
|
|
|
|
|
|
|
|
|
SIMULATION ASSIGNMENT: Process Scheduling Simulator
Text Book- Operating Systems: Internals and Design Principles by William Stallings, Sixth Edition, ISBN-10: 0-13-600632-9 ISBN-13: 978-0-13-600632-9.
I. Overview
The Process Scheduling Simulator will execute a collection of processes that demonstrate a scheduling algorithm of either First-Come/First-Served (FCFS), Shortest Job First (SJF), Preemptive Shortest Job First (PSJF), Shortest Job First Approximation (SJFA), or Round Robin (RR) and will then generate visual aids along with statistics to explain the results.
II. Setup
i. Windows XP/Vista
1. Right click on the downloaded zip file containing the simulator and choose extract all.
2. Choose Next till the wizard has finished.
3. Navigate to the directory named 'ps' which contains the unzipped simulator.
4. Edit 'psconfig' so that following the word 'user' is your first and last name. Note: WordPad is a sufficient editor for editing our files.
5. Double click 'runps.bat' to start the simulator.
6. Avoid closing the DOS prompt as this will also close the simulator.
ii. Linux/Solaris
1. Execute the command 'unzip ps.zip -d ps' to unzip the simulator.
2. Navigate to the directory named 'ps' which contains the unzipped simulator.
3. Edit 'psconfig' so that following the word 'user' is your first and last name.
4. Now execute the shell script 'runps'. Note: You must have C Shell installed.
5. Avoid closing the terminal as this will also close the simulator.
III. Exercises
i. Introduction
1. The simulator operates by executing the same runs under one or more predefined algorithms. Those algorithms are FCFS, SJF, and RR #, where # is the quantum, which is defined as the number of units to execute for a process before it is removed from the processor.
2. First, execute the Process Scheduling Simulator and push the Run Experiment button. The default experiment should begin and display the current run being simulated in Event Log pane, which is located in the upper right of the simulator window.
3. The runs are located in a file named 'myexp.exp'. Notice that in the experiment file the runs are identified by the word 'run' with the following named run, keyword 'algorithm' preceding the respective predefined algorithm, and keyword 'key' preceding an identifier for that experiment.
4. Next, observe that all the runs are the same with the exception of differing algorithms. Returning to the simulator window we can view the statistics associated with each run by pushing Show All Table Data. In addition, we can view Gantt charts showing how each process in a run executed by pushing Draw Gantt Chart and selecting the run we wish to view or graphs demonstrating one statistic that pertains to all the runs by cycling through the statistics by pushing Graph Type then viewing that graph by pushing Draw.
5. The last feature of importance to us is the simulator's logging capability. Push Open Log to activate logging. Now, push Log All Table Data as this will log the same data that can be viewed when pushing Show All Table Data.
6. Next, draw a Gantt Chart for FCFS and in the new window push the button labeled Log in the lower right corner. Once finished, push Hide in the lower left corner of the window and this will return you to the simulator. Lastly, cycle thorough the graph types till you reach Turnaround, then push Draw. This will show the Turnaround Times for each run. Similar to logging the Gantt Chart, push Log and then Hide.
7. Finally, back at the simulator window push Show Local Log and verify that what you logged shows up in the log exactly in the order in which it was added. Now, close the simulator by pushing Quit in the lower right corner of the simulator window.
8. Notice a 'logfile.html' shows up in the working directory of the simulator. Open it to verify that this file is the same as the local log file that you viewed earlier. There will also be gif images in the same directory as the log file. These images contain the graph data that you logged. If the log file is ever moved you have to make sure to move these images as well so that the graph data shows in the new log location.
ii. Activity
1. Modify the 'myexp.exp' file to have 5 run lines that will use the following algorithms: FCFS, SJF, RR 1, RR 5, and RR 10. On each run line, make sure that both the algorithm and key are correctly identify each other.
2. Now modify the 'myrun.run' file so that there will be a total of 20 processes with the following properties:
• All processes arrive at time 0.0
• All processes have a constant duration of 100
• All have constant I/O bursts of 10
• All have basepriority 1.0
• The first set of 10 processes have CPU bursts uniformly distributed between 2 and 8
• The last set of 10 processes have CPU bursts uniformly distributed between 30 and 40
• Do not change the seed line of the run file as this will change the sample space.
3. Run the simulator and open a log file and add the tabular data and the 5 Gantt charts, one for each run.
4. Now let us analyze the results. SJF will have the best average waiting time. This is easily identifiable by graphing the Waiting. Why is this behavior evident with our chosen example?
5. Next, compare the trend in the Round Robin experiments as the quantum increases. For large values of the quantum which algorithm will Round Robin mimic and how large does the quantum need to be for our example?
6. Let us try to prove our conjecture by adding a 6th run to 'myexp.exp'. So to do this we must first Close Log and Quit our current session with the simulator. Now open the 'myexp.exp' and add an additional line defining a RR algorithm with your chosen quantum. Again, make sure the key correctly identifies the algorithm.
7. Run the simulator again and this time log the tabular data again but this time only log the 6th Gantt chart which should simulate the RR algorithm with a large quantum. So now, let us have the simulator Show Local Log which should correspond with our previous conjecture.
8. Finally, Close Log and Quit the simulator. Recall that the generated log can be viewed as an HTML file in the working directory of the simulator, and if the log file is moved so must the gif images be moved as well to the same destination directory.
IV. Assignments
1. (Activity 4)
2. (Activity 5)
V. Acknowledgments
The activities were adapted for Dr. William Stallings with permission from Dr. Steven Robbins. The original activities were written for the Operating Systems course taught at The University of Texas at San Antonio. These simulation exercises were developed by Adam Critchley (University of Texas at San Antonio).