What is the difference between preemptive and nonpreemptive scheduling?
Answer:
Preemptive cpu scheduling algorithms may take the cpu away from a running process BEFORE it has finished its current cpu burst. A non-preemptive cpu scheduling algorithm will allow a running process to completely finish its current cpu burst.
Non-preemptive cpu scheduling would not be used in a computer center since it cannot provide reasonable response time to interactive users. It will unfairly allow some processes to keep the cpu for relatively long periods of time will other processes wait for a response.
Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:
| Process | burst Time | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 3 |
| P4 | 1 | 4 |
| P5 | 5 | 2 |
For each of the scheduling algorithms, FCFS, Shortest-Job-First (SJF, nonpreemptive), Priority (smaller priority number implies higher scheduling priority), and RR (quantum = 1) do the following.
Which of these scheduling algorithm gives the smallest average waiting time?
Answer: a. Gantt charts
(The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.) a. The four Gantt charts are _______________________________________________________ | P1 | P2| P3 |P4 | P5 | FCFS |_________________________|___|______|___|_____________| 0 10 11 13 14 19 _______________________________________________________ |P2| P4| P3 | P5 | P1 | SJF |__|___|______|_____________|__________________________| 0 1 2 4 9 19 There is a tie between the priorities of P1 and P3. If P1 is scheduled first: _______________________________________________________ |P2| P5 | P1 | P3 | P4| Priority13 |__|______________|_________________________|______|___| 0 1 6 16 18 19 or if for the tie between P1 and P3 priorities, P3 is scheduled first: _______________________________________________________ |P2| P5 | P3 | P1 | P4| Priority31 |__|______________|______|_________________________|___| 0 1 6 8 18 19 ____________________________________________________________________ |P1| P2| P3| P4| P5| P1| P3| P5| P1| P5| P1| P5| P1| P5| P1 |RR |__|___|___|___|___|___|___|___|___|___|___|___|___|___|____________| 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 19
Answer: b. Turnaround Times
b. The turnaround time of each process for each of the
scheduling algorithms in part a:
Turnaround_time = Finish_time - Arrival_time
FCFS SJF Priority1 Priority3 RR
P1 10 19 16 18 19
P2 11 1 1 1 2
P3 13 4 18 8 7
P4 14 2 19 19 4
P5 19 9 6 6 14
Answer: c. Waiting Times
c. The waiting time of each process for each of the scheduling
algorithms in part a:
Waiting time (turnaround time minus burst time) =
Finish_time - Arrival_time - Burst_time
FCFS SJF Priority13 Priority31 RR
P1 0 9 6 8 9
P2 10 0 0 0 1
P3 11 2 16 6 5
P4 13 1 18 18 3
P5 14 4 1 1 9
Answer: d. Smallest Average Waiting Time
d. The schedule in part that results in the minimal average waiting time (over all processes): FCFS SJF Priority1 Priority3 RR Ave. wait 9.6 3.2 8.2 6.6 5.4 So the answer is Shortest Job First.
Suppose the following three processes arrive for execution at the arrival times indicated.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0.0 | 8 |
| P2 | 0.4 | 4 |
| P3 | 1.0 | 1 |
Note! You cannot schedule a process to execute before it has arrived!
Answers:
Average wait times: a. FCFS 6.2 b. SJF 5.2 c. SRTF 2.0
Calculation Details: Gantt charts
a) First Come First Serve
____________________________________
| P1 | P2 | P3 |
____________________________________
8 12 13
b) Shortest Job First
____________________________________
| P1 | P3 | P2 |
____________________________________
8 9 13
c) Shortest Remaining Time First
_____________________________________________
| P1 | P2 | P3 | P2 | P1 |
_____________________________________________
0.4 1 2 5.4 13
Calculation Details: Wait times
___________________________________________________________________________ | | FCFS | SJF | SRTF | |Process | Finish-Arr-CPU=Wait | Finish-Arr-CPU=Wait | Finish-Arr-CPU=Wait | |________|_____________________|_____________________|_____________________| | P1 | 8 - 0.0 - 8.0 = 0.0 | 8 - 0.0 - 8.0 = 0.0 |13 - 0.0 - 8.0 = 5.0 | | P2 |12 - 0.4 - 4.0 = 7.6 |13 - 0.4 - 4.0 = 8.6 |5.4- 0.4 - 4.0 = 1.0 | | P3 |13 - 1.0 - 1 = 11.0 | 9 - 1.0 - 1.0 = 7.0 | 2 - 1.0 - 1.0 = 0.0 | ___________________________________________________________________________ Average 6.2 5.2 2.0
Answer
Round robin does not cause starvation. A process in the ready list will have to wait only N turns of length at most q each before being allocated the cpu where N is the number of processes in the ready queue ahead of the process and q is the quantum of cpu allocated to a process when it is scheduled.
SJF and SRTF can cause starvation of some process, P, if just before the running process finishes its cpu burst, a new process always arrives with a cpu burst smaller P's burst.
Priority scheduling algorithms can also cause starvation of some process, P, if just before the running process finishes its cpu burst, a new process always arrives with a priority smaller than P's priority. However, if priorities are adjusted during execution so that any process which has not received any recent cpu usage eventually has the highest priority (this is called aging), then starvation obviously cannot occur.
FCFS does not quite guarantee that starvation cannot occur. A process that has an infinite cpu burst (e.g., that executes code with an infinite loop) will starve all remaining processes. On the other hand if no process has an infinite cpu burst, then starvation will not occur. For in this case a process in the ready list will then have to wait for only N turns, each of finite length, before being allocated the cpu where N is the number of arrivals in the ready list before this process.