Description
-
Consider the following set of processes, with the length of the CPU burst given in milliseconds:
Process Burst Time Priority
P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2
The processes are assumed to have arrived in the order P1, P2, P3, P4, and P5 at time 0.
-
Draw four Gantt charts that illustrate the exclusion of these processes using the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1).
FCFS
|
P1 |
P2 |
P3 |
P4 |
P5 |
0 10 11 13 14 19
SJF
|
P2 |
P4 |
P3 |
P5 |
P1 |
0 1 2 4 9 19
non-preemptive priority
|
P1 |
P2 |
P3 |
P4 |
P5 |
0 1 6 16 18 19
RR q=1
|
P1 |
P2 |
P3 |
P4 |
P5 |
P1 |
P3 |
P5 |
P1 |
P5 |
P1 |
P5 |
P1 |
P5 |
P1 |
P1 |
P1 |
P1 |
P1 |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
-
What is the turnaround time of each process for each of the scheduling algorithms in part a?
|
Turn around Time |
FCFS |
SJF |
NP priority |
RR q=1 |
|
P1 |
10-0 = 10 |
19-0 = 19 |
16-0 = 16 |
19-0 = 19 |
|
P2 |
11-0 = 11 |
1-0 = 1 |
1-0 = 1 |
2-0 = 2 |
|
P3 |
13-0 = 13 |
4-0 = 4 |
18-0 = 18 |
7-0 = 7 |
|
P4 |
14-0 = 14 |
2-0 = 2 |
19-0 = 19 |
4-0=4 |
|
P5 |
19-0 = 19 |
9-0 = 9 |
6-0 = 6 |
14-0 |
-
What is the waiting time of each process for each of the scheduling algorithms in part a?
|
Waiting Time |
FCFS |
SJF |
NP priority |
RR q=1 |
|
P1 |
10-10 = 0 |
19-10 = 9 |
16-10 = 6 |
19-10 = 9 |
|
P2 |
11-1 = 10 |
1-1 = 0 |
1-1 = 0 |
2-1 = 1 |
|
P3 |
13-2 = 11 |
4-2 = 2 |
18-2 = 16 |
7-2 = 5 |
|
P4 |
14-1 = 13 |
2-1 = 1 |
19-1 = 18 |
4-1 = 3 |
|
P5 |
19-5 = 14 |
9-5 = 4 |
6-5 = 1 |
14-5 = 9 |
|
Avg WT |
9.6ms |
3.2ms |
8.2ms |
5.4ms |
-
Which of the schedules in part a results in the minimal average waiting time (over all processes)?
20 points
SJF → 3.2ms
2. Suppose that the following processes arrive for execution at the times indicated. Each process will run the listed amount of time. In answering questions, use non-preemptive scheduling and base all decisions on the information you have at the time the decision must be made.
Process Arrival Time Burst Time
P1 0.0 8
P2 0.4 4
P3 1.0 1
a. What is the average turnaround time for these processes with the FCFS scheduling algorithm?
|
P1 |
P2 |
P3 |
0 8 12 13
[ (8 – 0.0) + (12 – 0.4) + (13-1) ] / 3
= 10.53ms
b. What is the average turnaround time for these processes with the SJF scheduling algorithm?
|
P1 |
P3 |
P2 |
0 8 9 13
[ (8 – 0.0) + (13 – 0.4) + (9-1) ] / 3
= 9.53ms
c. The SJF algorithm is supposed to improve performance, but notice that we chose to run process P1 at time 0 because we did not know that two shorter processes would arrive soon. Compute what the average turnaround time will be if the CPU is left idle for the first 1 unit of time and then SJF scheduling is used. Remember that processes P1 and P2 are waiting during this idle time, so their waiting time may increase. This algorithm could be known as future-knowledge scheduling. Also keep in mind that the turnaround time is the finishing time minus the arrival time.
|
IDLE |
P3 |
P2 |
P1 |
0 1 2 6 13
[ (14 – 0.0) + (6 – 0.4) + (2-1) ] / 3
= 6.86ms
Note: For parts a, b, c it is required that you show the Gantt charts before computing the average turnaround times. Also show your computation. 15 points
3. Suppose that a scheduling algorithm (at the level of short term CPU scheduler) favors those processes that have used the least processing time in the past. Why will this algorithm favor I/O bound processes and yet not permanently starve CPU bound processes?
5 points
Since short term CPU schedulers are invoked infrequently, this algorithm will naturally favor I/O bound processes because they have short CPU bursts. However, even if our algorithm favors short term processes, the CPU bound processes will not starve because I/O bound processes will finish quickly (short CPU bursts) which will allow the CPU bound processes to use the CPU often
Additionally, I/O bound processes only require a thread as opposed to an entire process. So, I/O operations, can work concurrently with CPU computations within a single process.
