Preemptive Precedence CPU Scheduling Algortithm

Prerequisite – https://www.geeksforgeeks.org/cpu-scheduling-in-operating-systems/

Introduction:

It is a pre-emptive methodology of scheduling processes that works primarily based on the precedence of a course of. On this algorithm, the scheduler schedules the duties to work as per the precedence. The next precedence course of ought to be executed first. After we are having 2 processes with equal priorities then we select to pick out the method primarily based on FCFS (First Come First Serve). When it reaches to last course of then we are going to execute the remaining processes primarily based on precedence.

Word: Lesser the Quantity, Extra Precedence 

For instance: 1 is excessive precedence, 10 – low precedence

Process:

• Step-1: Choose the primary course of whose arrival time can be 0, we have to choose that course of as a result of that course of is simply be executing at time t=0.
• Step-2: Examine the precedence of the following out there course of.

                         Right here we have to verify for 3 circumstances.

                         (i) if precedence_{(current_process)} > precedence_{(prior_process)} then execute the present course of.

                         (ii) if precedence_{(current_process)} > precedence_{(prior_process)} then execute the prior course of.

                         (iii) if precedence_{(current_process)} > precedence_{(prior_process)} then execute the method which arrives first i.e., arrival time 

                               ought to be first.

• Step-3: Repeat Step-2 till it reaches the ultimate course of.
• Step-4: When it reaches the ultimate course of, select the method which is having the very best precedence & execute it. Repeat the identical step till all processes completes their execution.

Word: A Course of is accomplished when its burst time turns into 0.

Instance-1: Take into account the next desk of arrival time, Precedence and burst time for 5 processes P1, P2, P3, P4 and P5. 

Working: (for input-1):

Step-1:  At Arrival time t = 0, course of P1 is executed for 1ms as its arrival time is from 0ms to 1ms, as it’s the first course of within the prepared queue. Remaining Burst time (B.T) for P1 = 3-1 = 2 ms.

Step-2: At time t = 1, course of P2 is having greater precedence than P1, so we have to execute Course of P2, for 1ms.
             Remaining B.T for P2 = 4-1 = 3 ms.

Step-3: At time t = 2, Course of P2 is having greater precedence than P3, So once more P2 can be executed for 1 ms.
             Remaining B.T for P2 = 3-1 = 2 ms.

Step-4: At time t = 3, Course of P2 is having greater precedence than P4, So P2 now will execute for two ms because the arrival time of P4 is from 3 ms to five ms. Remaining B.T for P2 = 2-2 = 0 ms.

             -> Right here Course of P2 is accomplished with its execution because the burst time for P2 is 0.
             -> Right here the Arrival time for Processes is now 5 so it has reached to all of the Processes.

Step-5: Now we have to schedule the method with the very best precedence, Right here we’re having P1 as the very best precedence, So P1 is executed fully and the remaining B.T of P1 = 2-2 = 0 ms.

Step-6: Equally repeat Step-5 for all of the remaining processes primarily based on precedence till all processes full their execution.

Gantt chart:

 

Now we have to calculate the completion time (C.T) & First Arrival Time (F.A.T) of every course of by Gantt chart.

C.T -> P1-7 ms, P2-5 ms, P3-13 ms, P4-17 ms, P5-19 ms.
F.A.T -> P1-0 ms, P2-1 ms, P3-7 ms, P4-13 ms, P5-17 ms.

Flip Round Time (T.A.T) = (Completion Time) – (Arrival Time)

Ready Time (W.T) = (Flip Round Time) – (Burst Time)

Response Time (R.T) = (First Arrival Time) – (Arrival Time)

After calculating the above fields, the ultimate desk appears like

 

Right here, H – Increased Precedence L – Least Precedence

Output :

Complete Flip Round Time = 7 + 4 + 11 + 14 + 14 = 50 ms
Common Flip Round Time = (Complete Flip Round Time)/(no. of processes) = 50/5 = 10.00 ms

Complete Ready Time = 4 + 0 + 15 + 10 + 12 = 41 ms
Common Ready Time = (Complete Ready Time)/(no. of processes) = 41/5 = 8.20 ms

Complete Response Time = 0 + 0 + 5 + 10 + 12 = 27 ms
Common Ready Time = (Complete Ready Time)/(no. of processes) = 27/5 = 5.40 ms

Instance 2: 

Take into account the next desk of arrival time, Precedence and burst time for seven processes P1, P2, P3, P4, P5, P6 and P7

Working: (for input-2)

Step-1: At time t = 0, Course of P1 is accessible within the prepared queue, executing P1 for 1 ms. 
             Remaining B.T for P1 = 8-1 = 7 ms.

Step-2: At time t = 1, the precedence of P1 is larger than P2, so we execute P1 for two ms, because the arrival time of P2 is from 1 ms to three ms.                  Remaining B.T for P1 = 7-2 = 5 ms.

Step-3: At time t = 3, the precedence of P1 is larger than P3, so we execute P1 for 1 ms.
             Remaining B.T for P1 = 5-1 = 4 ms.

Step-4: At time t = 4, the precedence of P1 is larger than P4, so we execute P1 for 1 ms.
             Remaining B.T for P1 = 4-1 = 3 ms.

Step-5: At time t = 5, the precedence of P5 is larger than P1, so we execute P5 for 1 ms.
             Remaining B.T for P5 = 6-1 = 5 ms.

Step-6: At time t = 6, the precedence of P5 is larger than P6, so we execute P5 for 4 ms.
             Remaining B.T for P5 = 5-4 = 1 ms.

Step-7: At time t = 7, the precedence of P7 is larger than P5, so we execute P7 for 1 ms.
             Remaining B.T for P7 = 1-1 = 0 ms.
             -> Right here Course of P7 completes its execution.

Step-8: Now we take the method which is having the very best precedence. Right here we discover P5 is having the very best precedence & execute P5 fully and the remaining B.T of P5 = 1-1 = 0 ms.

Step-9: Equally repeat Step-8 for all of the remaining processes primarily based on precedence till all processes completes their execution.

Gantt chart:

 

Now we have to calculate the completion time (C.T) & First Arrival Time (F.A.T) of every course of by Gantt chart.

C.T -> P1-15 ms, P2-17 ms, P3-21 ms, P4-22 ms, P5-12 ms, P6-27 ms, P7- 11 ms.

F.A.T -> P1-0 ms, P2-15 ms, P3-17 ms, P4-21 ms, P5-5 ms, P6-22 ms, P7-10 ms.

Flip Round Time (T.A.T) = (Completion Time) – (Arrival Time)

Ready Time (W.T) = (Flip Round Time) – (Burst Time)

Response Time (R.T) = (First Arrival Time) – (Arrival Time)

After calculating the above fields, the ultimate desk appears like

 

Right here, H – Increased Precedence, L – Least Precedence

Output:

Complete Flip Round Time = 15 + 16 + 18 + 18 + 7 + 21 + 1 = 96 ms
Common Flip Round Time = (Complete Flip Round Time)/(no. of processes) = 96/7 = 13.71 ms

Complete Ready Time = 7 + 14 + 14 + 17 + 1 + 16 + 0 = 69 ms
Common Ready Time = (Complete Ready Time)/(no. of processes) = 69/7 = 9.85 ms

Complete Response Time = 0 + 14 + 14 + 17 + 0 + 16 + 0 = 61 ms
Common Ready Time = (Complete Ready Time)/(no. of processes) = 61/7 = 8.71 ms

Drawbacks of Pre-emptive Precedence Scheduling Algorithm:

Hunger Drawback: That is the issue by which a course of has to attend for an extended period of time to get scheduled into the     CPU. This situation is known as the hunger downside.

Instance: In Instance 2, we will see that course of P1 is having Precedence 3 and we have now pre-empted the method P1 and allotted the CPU to P5. Right here we’re solely having 7 processes.

Now, if suppose we have now many processes whose precedence is greater than P1, then P1 wants to attend for an extended time for the opposite course of to be pre-empted and scheduled by the CPU. This situation is known as as hunger downside.

Resolution: The answer for this Hunger downside is Ageing.

Getting older: This may be achieved by decrementing the precedence quantity by a sure variety of a selected course of which is ready for an extended time frame after a sure interval.

Instance: After each 3 models of time, all of the processes that are in ready state, the precedence of these processes can be decreased by 2, So, if there’s a course of P1 which is having precedence 5, after ready for 3 models of time its precedence can be decreased from 5 to three in order that if there’s any course of P2 which is having precedence as 4 then that course of P2 will wait and P1 can be scheduled and executed.

The implementation of this scheduling course of is supplied on this article.