Assignment 2 Deterministic Modeling of CPU Scheduling Algorithms Example
What is deterministic modeling? See p. 245, section 5.8.1 “Deterministic Modeling”.
Assignment 2 Deterministic Modeling of CPU Scheduling Algorithms Example
Diagram of process state
preemption /
Assignment 2 Deterministic Modeling of CPU Scheduling Algorithms Example
3 processes P1, P2 , P3 : Arrival_Time(P1)=0, Arrival_Time(P2)=0, Arrival_Time(P3)=2; Process_Priority(P1)=3, Process_Priority(P2)=4, Process_Priority(P3)=1
Sequence of CPU Computation Time and I/O Time Requirements:
P1: (1) CPU_time(P1)=4; (2) I/O_time(P1, 0)=3; (3) CPU_time(P1)=2;
P2: (1) CPU_time(P2)=1; (2) I/O_time(P2, 0)=2; (3) CPU_time(P2)=2;
P3: (1) CPU_time(P3)=2; (2) I/O_time(P3, 0)=1; (3) CPU_time(P3)=1; (4) I/O_time(P3, 1)=2; (5) CPU_time(P3)=1;
(6) I/O_time(P3, 0)=1; (7) CPU_time(P3)=2;
Scheduling Algorithm used by the CPU scheduler: C5 Preemptive Priority Scheduling
Scheduling Algorithm used by the I/O device schedulers: C1 Nonpreemptive First-Come-First-Served (FCFS) Scheduling
P1
P3
P1
P3
P1
P2
P3
P1
P2
P3
P2
CPU schedule:
I/O device 0
schedule:
I/O device 1 schedule:
0 2
4 5 6 7 8 9 10
12 13
12 13
15 16
16
16
P3
P1
P2
P3
0 45 7 10
068
P3
Assignment 2 Deterministic Modeling of CPU Scheduling Algorithms Example
Waiting time for each process Pi is the sum of periods spent by Pi in the ready queue waiting to be scheduled by the CPU
scheduler in order for Pi to be able to execute on the CPU (it does not include time in the I/O device queue or doing I/O).
P1: waiting_time(P1)= 0 + (4 – 2) + (6 – 5) + 0 = 0 + 2 + 1 + 0 = 3;
P2: waiting_time(P2)= (7 – 0) + 0 + (15 – 13) = 7 + 0 + 2 = 9; P3: waiting_time(P3)= 0 + 0 + 0 + 0 = 0 ;
Average Waiting Time = (3 + 9 + 0)/3 = 12/3 = 4;
Turnaround time for each process Pi is the time from the arrival/submission of Pi to the completion time of Pi .
Average Turnaround Time = (turnaround_time (P1) + turnaround_time (P2) + turnaround_time (P3)) / 3 = ((12 – 0)
+ (16 – 0) + (15 – 2) ) / 3 = (12 +16 + 13) / 3 = 41/3 CPU schedule:
P1
P3
P1
P3
P1
P2
P3
P1
P2
P3
P2
I/O device 0 schedule:
I/O device 1 schedule:
0 45 7 10
0 2
4 5 6 7 8 9 10
12 13
12 13
15 16
16
P3
P1
P2
P3
P3
068
16
Assignment 2 Deterministic Modeling of CPU Scheduling Algorithms Example
In the definition of Deterministic Modeling in Section 5.8.1, it is stated that:
“Deterministic modeling is one type of analytic evaluation. This method takes a particular predetermined workload and defines the performance of each algorithm for that workload.”
So what is the particular predetermined workload in this example?
All of the following data in this example can be considered as one particular predetermined workload, thus one should be able to provide all the following data as input parameters to a System for Deterministic Modeling of CPU Scheduling Algorithms:
Number of Processes; Process Arrival Times; Process Priorities:
3 processes P1, P2 , P3 ; Arrival_Time(P1)=0, Arrival_Time(P2)=0, Arrival_Time(P3)=2; Process_Priority(P1)=3, Process_Priority(P2)=4, Process_Priority(P3)=1
Sequence of CPU Computation Time and I/O Time Requirements for Each Process:
P1: (1) CPU_time(P1)=4; (2) I/O_time(P1, 0)=3; (3) CPU_time(P1)=2;
P2: (1) CPU_time(P2)=1; (2) I/O_time(P2, 0)=2; (3) CPU_time(P2)=2;
P3: (1) CPU_time(P3)=2; (2) I/O_time(P3, 0)=1; (3) CPU_time(P3)=1; (4) I/O_time(P3, 1)=2; (5) CPU_time(P3)=1; (6) I/O_time(P3, 0)=1; (7) CPU_time(P3)=2;
Assignment 2 Deterministic Modeling of CPU Scheduling Algorithms Example
In the definition of Deterministic Modeling in Section 5.8.1, it is stated that:
“Deterministic modeling is one type of analytic evaluation. This method takes a particular predetermined workload and defines the performance of each algorithm for that workload.”
So what is the performance of each algorithm for that workload in this example?
The following results of the computation in this example defines the performance of one particular scheduling algorithm used by the CPU scheduler, C5 Preemptive Priority Scheduling, on one particular predetermined workload (the workload as defined earlier) in a System for Deterministic Modeling of CPU Scheduling Algorithms:
AverageWaitingTime = (3 + 9 + 0)/3 = 12/3 = 4;
Average Turnaround Time = ((12 – 0) + (16 – 0) + (15 – 2) ) / 3 = (12 +16 + 13) / 3 = 41/3
Additional Assumptions:
You may assume that each process always starts by submitting a request for CPU execution; then submits a request for performing I/O on a particular I/O device; then submits a request for CPU execution again; etc, and the last request is always a a request for CPU execution before terminating.
If two processes have a same priority, then a scheduler breaks the tie by selecting the process with the smaller process index.