Assignment 1: CPU Scheduling
In this assignment you’ll try your hand at (manually) simulating a number of scheduling algorithms discussed in lecture. Please type up your submissions and show all your work for full credit — handwritten work will not be accepted! (Diagrams may be neatly hand drawn with a ruler, if you’re not comfortable doing those on a computer).
Submissions are due 6/24/09 at the beginning of lecture. Internet/TV students please have your work submitted via the blackboard digital dropbox by then.
Exercise 1
Consider the following set of processes with the given CPU-burst lengths and arrival times:
| Process | CPU Burst | Arrival Time |
|---|---|---|
| P0 | 2 | 0 |
| P1 | 10 | 1 |
| P2 | 6 | 5 |
| P3 | 3 | 7 |
- Draw four Gantt charts illustrating the execution of these processes using the FCFS, non-preemptive SJF, preemptive SJF, and RR (quantum=2) scheduling algorithms.
- What is the average turnaround time for each of the scheduling algorithms in part (1)? Show how you compute your answer.
- What is the average waiting time for each of the scheduling algorithms in part (1)? Show how you compute your answer.
- Which of the scheduling algorithms results in the minimum average waiting time in part (1)?
The Process Scheduling Simulator
Consider the following run setup for the scheduling simulator:
seed 5000
numprocs 10
firstarrival 0.0
interarrival constant 0.0
duration constant 50
cpuburst exponential 5
ioburst exponential 10
The following experiment configures the above run with the SJF, preemptive-SJF, and SJFA 0.5 (CPU burst duration predicted using an EMA with a configured alpha of 0.5) algorithms:
run alpharun algorithm SJF key "SJF"
run alpharun algorithm PSJF key "PSJF"
run alpharun algorithm SJFA 0.5 key "SJFA"
Create the necessary configuration files — you may need to add some of your own lines — and run the simulator with the given settings. Refer to the output for exercise 2. Exercises 3 and 4 asks you to make some modifications to the run settings.
Exercise 2
Which of the scheduling algorithms completes all 10 processes in the least amount of time (and consequently achieves the best CPU utilization)? Referring to the Gantt charts for the three algorithms, explain in general terms why this happens. It may help in particular to examine how processes 2 and 10 are scheduled.
Exercise 3
For our setup we specified an exponential distribution for CPU burst durations. You can read about exponential distributions at Wikipedia — they are particularly useful when modeling/simulating the inter-arrival times or durations (as in our case) of events in certain systems where the mean inter-arrival time or duration is known.
First, change the duration of the processes in the simulated run to 1000 (so that the simulation is somewhat lengthier). Via either prediction or experimentation, can you determine an optimal value (to one decimal place) for alpha for the SJFA algorithm? Explain your reasoning for why it is optimal.
Exercise 4
Modify the (original) run above by adding context switch times to the experiment. You can do this by inserting the following lines in the run file after the seed setting:
cstin 0.5
cstout 0.5
Run the experiment again. Are there any changes in the overall (and relative) performance of the algorithms? Explain your observed changes.
Leave a comment
You must be logged in to post a comment.