Dynamic Priority Scheduling Example

Question: In a real time system four processes A, B, C and D are in a ready queue with the requirements shown in the table below. If a process will not complete within its maximum permitted period the priority changes to 1 where it will execute until finished. Processes should remain at priority level 2 for as long as possible. The clock tick period is 100ms and the context switch period is 1ms. Determine, through the use of a time-slice diagram, if the priority of any of the processes needs to be changed at any time for all of the time slices, for each of the processes determine the total run time and identify whether it meets the timing requirements. Compare results when round-robin scheduling is used.

	A	B	C	D
Total time(ms)	155	160	120	250
Initial priority	2	2	2	2
Max period(ms)	170	550	300	900

Solution:

N(process) = Number of time slots required
R(process) = Number of time slots remaining

Process A: N(A) = 155/100 = 1.6
                 R(A) = 170/101 = 1.7 R(A) ≤ N(A) + 1
Process B: N(B) = 160/100 = 1.6
                 R(B) = 550/101 = 5.5 R(B) ≥ N(B) + 1
Process C:  N(C) = 120/100 = 1.2
                 R(C) = 300/101 = 3.0 R(C) ≥ N(C) + 1
Process D:  N(D) = 250/100 = 2.5
                  R(D) = 900/101 = 9.0 R(D) ≥  N(D) + 1

Process A goes first because is priority is changed to 1

Time Slice 1

Process A: N(A) = 55/100 = 0.6
                 R(A) = 69/101 = 0.7 R(A) ≤ N(A) + 1
Process B: N(B) = 160/100 = 1.6
                 R(B) = 449/101 = 4.4 R(B) ≥ N(B) + 1
Process C:  N(C) = 120/100 = 1.2
                 R(C) = 199/101 = 2.0 R(C) ≤ N(C) + 1
Process D: N(D) = 250/100 = 2.5
                 R(D) = 799/101 = 7.9 R(D) ≥  N(D) + 1

Process A and Process C have their priority changed to 1, since process A was given the previous time slot, process C goes next as the two processes now execute in Round-Robin Scheduling.

Time Slice 2

Process A: N(A) = 55/100 = 0.6
                        R(A) = 69/101 = 0.7 R(A) ≤ N(A) + 1
Process B: N(B) = 160/100 = 1.6
                        R(B) = 348/101 = 3.4 R(B) ≥ N(B) + 1
Process C:         N(C) = 20/100 = 0.2
                        R(C) = 98/101 = 1.0 R(C) ≤ N(C) + 1
Process D:         N(D) = 250/100 = 2.5
                        R(D) = 698/101 = 6.9 R(D) ≥  N(D) + 1

Process A goes next for the next time slice since process A and C have equal priority and process C executed in the previous time slice.

Time Slice 3

Process A:         N(A) = 0/100 = 0

                        R(A) = 13/101 = 0.1 Finished

Process B: N(B) = 160/100 = 1.6

                        R(B) = 292/101 = 2.9 R(B) ≥ N(B) + 1

Process C:         N(C) = 20/100 = 0.2

                        R(C) = 42/101 = 0.4 R(C) ≤ N(C) + 1

Process D:         N(D) = 250/100 = 2.5

                        R(D) = 642/101 = 6.4 R(D) ≥  N(D) + 1

Process A has finished and therefore is removed from the list. Process C now becomes the only task with the highest priority and therefore goes next.

Time Slice 4

Process B: N(B) = 160/100 = 1.6

                        R(B) = 271/101 = 2.7 R(B) ≥ N(B) + 1

Process C:         N(C) = 0/100 = 0

                        R(C) = 21/101 = 0.2 Finished

Process D:         N(D) = 250/100 = 2.5

                        R(D) = 621/101 = 6.1 R(D) ≥  N(D) + 1

Process C has finished and therefore is removed from the list. Process B and D are now left, with the same priority of 2 and will be taken in round robin sequence starting with process B. 

Time Slice 5

Process B: N(B) = 60/100 = 0.6
                        R(B) = 170/101 = 1.7 R(B) ≥ N(B) + 1
Process D:        N(D) = 250/100 = 2.5
                        R(D) = 520/101 = 5.2 R(D) ≥  N(D) + 1

Process D goes next as both processes are taken in round robin scheduling with process B executing in the previous time slice.

Time Slice 6

Process B: N(B) = 60/100 = 0.6

                        R(B) = 69/101 = 0.7 R(B) ≤ N(B) + 1

Process D:        N(D) = 150/100 = 1.5

                        R(D) = 419/101 = 4.2 R(D) ≥  N(D) + 1

Process B becomes a priority and therefore goes next.

Time Slice 7

Process B: N(B) = 0/100 = 0

                       R(B) = 8/101 = 0.1 Finished

Process D:       N(D) = 150/100 = 1.5

                        R(D) = 358/101 = 3.5 R(D) ≥  N(D) + 1

Process B is completed and removed from the list. Only Process D is left and executes until completion in the next time slice.

Time Slice 8 and 9

Therefore, the full time slice diagram is given by:

Total time required for Process A:

100 + 1 + 100 + 1+ 55 = 257ms

Total time required for Process B:

100 + 1 + 100 + 1 + 55 + 1 + 20 + 1 + 100 + 1 + 100 + 1 + 60 = 541ms

Total time required for Process C:

100 + 1 + 100 + 1 + 55 + 1 + 20 = 278ms

Total time required for Process D:

100 + 1 + 100 + 1 + 55 + 1 + 20 + 1 + 100 + 1 + 100 + 1 + 60 + 1 + 100 + 1 + 50 = 693ms

Process B, C and D met their timing requirements while Process A failed to meet its maximum permitted time of 170ms.

Using round robin scheduling, the time slices are as shown

Total time required for Process A:

100 + 1 + 100 + 1+ 100 + 1 + 100 + 1 + 55 = 459ms

Total time required for Process B:

100 + 1 + 100 + 1+ 100 + 1 + 100 + 1 + 55 + 1 + 60 = 520ms

Total time required for Process C:

100 + 1 + 100 + 1+ 100 + 1 + 100 + 1 + 55 + 1 + 60 + 1+ 20 = 541ms

Total time required for Process D:

100 + 1 + 100 + 1+ 100 + 1 + 100 + 1 + 55 + 1 + 60 + 1+ 20 + 1 + 100 + 1 + 50 = 693ms

In round robin scheduling, Process B and D met their maximum permitted time while Process A and C failed to meet their timing requirements.