Consider a preemptive priority based scheduling algorithm based on dynamically…

Concept

A preemptive priority scheduler with ageing makes a fresh decision at the end of every time quantum and gives the CPU to whichever ready process holds the numerically largest priority. Priority here is a function of state, not a fixed attribute of the process: it grows at the waiting rate a while a process sits in the ready queue, at the running rate b while it holds the CPU, and it is reset to 0 every time a process enters the ready queue — on arrival, and again on every re-entry after its quantum expires.

When a is greater than b, waiting earns priority faster than running. A process whose quantum has just expired therefore re-enters at 0 and has to age before it can win the CPU back, while everything left waiting keeps climbing. That is the anti-starvation ageing mechanism, and it is why the completion order need not follow the arrival order.

Applying it to this schedule

Here a = 2, b = 1 and q = 1. The service demands are P1 = 4, P2 = 1, P3 = 2 and P4 = 1, a total of 8 units, so there are exactly eight one-unit slices to allocate. Track each priority at the end of every slice:

1. t = 0: P1 is alone in the ready queue at priority 0 and runs slice 0–1. Running at rate b = 1 leaves it at priority 1.

2. t = 1: P1’s quantum expires at the same instant P2 arrives, so both enter the ready queue together and both are set to 0. The stated tie-break — the process that has not executed recently goes first — places P2 ahead of P1, so P2 runs slice 1–2.

3. t = 2: P2 has now received its full 1 unit of service and leaves the system at time 2. P3 arrives at priority 0, while P1 has aged one unit at rate a = 2 and stands at 2, so P1 runs slice 2–3 and ends it at priority 3.

4. t = 3: P1’s quantum expires and resets it to 0 at the same instant P4 arrives at 0, so the same tie-break places P4 ahead of P1. P3 has aged to 2 and is the highest of the three, so P3 runs slice 3–4.

5. t = 4: P3’s quantum expires and resets it to 0. P4 and P1 have each waited one unit and both stand at 2, and P4 already sits ahead of P1 from the time-3 tie-break, so P4 runs slice 4–5.

6. t = 5: P4 has received its full 1 unit and leaves the system at time 5. P1 has aged two units to 4 and P3 one unit to 2, so P1 runs slice 5–6.

7. t = 6: P1’s quantum expires and resets it to 0 while P3 has aged to 4, so P3 runs slice 6–7. That is P3’s second unit, after slice 3–4, completing its 2 units of service, so P3 leaves the system at time 7.

8. t = 7: only P1 remains, having been served in slices 0–1, 2–3 and 5–6. It runs slice 7–8 for its fourth unit and leaves the system at time 8.

Finish times: P1 = 8, P2 = 2, P3 = 7 and P4 = 5.

Cross-check

The tally closes: P1 gets 4 slices, P2 gets 1, P3 gets 2 and P4 gets 1, exactly matching their service times, and the CPU is never idle across [0, 8], so the final departure has to fall at time 8. The completion order P2, P4, P3, P1 is the direct consequence of a > b — P1 arrives first and needs the most CPU, yet it is knocked back to priority 0 after every quantum and therefore leaves last.