Trace

Shortest Remaining Time First scheduling

At every moment the process with the least time left runs, even if that means interrupting another. Press play and watch every decision.

Processes

Name Arrival Burst Priority Remove
Why this happened

P1 is the only process ready, so it runs.

Ready queue, next in line first
    Decision log

    Every moment something was decided. Choose a line to move the playhead there.

      Keyboard shortcuts
      Space
      Play or pause
      Left Right
      Step back or forward one unit
      Home End
      Jump to the start or the end
      R
      Reset
      [ ]
      Slower or faster
      T
      Switch light or dark theme

      Shortcuts are off while you type in a field.

      Results

      Process Arrival Burst Finished Turnaround Waiting Response
      Average

       

      Turnaround is finished - arrival. Waiting is turnaround - burst. Response is first run - arrival. CPU utilization is total burst / last finish.

      How Shortest Remaining Time First works

      Shortest Remaining Time First (SRTF) is the preemptive version of Shortest Job First. At every moment the CPU belongs to the process with the least work left. Since remaining times only change for the running process, the decision can only change at two kinds of moments: when the running process finishes, and when a new process arrives.

      The arrival check is where most of the action happens. The newcomer's burst is compared with the time the running process has left, not with its original burst. If the newcomer needs strictly less, it takes over and the interrupted process goes back to the ready queue with its remaining time intact, to resume later from where it stopped.

      In Trace, if a newcomer needs exactly as much time as the running process has left, the running process keeps the CPU, because switching would gain nothing. Other ties, between waiting processes, go to the earlier arrival and then to the lower process number.

      With known burst lengths and free switching, SRTF gives the lowest average waiting time of any schedule for the same processes. Real systems pay for each switch and cannot know remaining times exactly, and long jobs can starve when short ones keep arriving. Trace treats a switch as taking no time, so the numbers here are the textbook ideal.

      Worked example

      P1 arrives at 0 needing 8. At time 1, P2 arrives needing 4, less than the 7 that P1 has left, so P2 takes over. At times 2 and 3, P3 (9) and P4 (5) arrive, but neither needs less than P2's remaining time, so P2 keeps running until it finishes at 5.

      SRTF. Order of execution: P1 0 to 1, P2 1 to 5, P4 5 to 10, P1 10 to 17, P3 17 to 26.

      SRTF worked example results
      ProcessArrivalBurstFinishedTurnaroundWaitingResponse
      P108171790
      P2145400
      P32926241515
      P43510722
      Average136.50 (13/2)4.25 (17/4)

      Open this example in the simulator

      From time 5 on, the shortest remaining job is P4 (5), then P1 (7 left), then P3 (9). The average waiting time is (9 + 0 + 15 + 2) / 4 = 6.5. Look at P1: its response time is 0 because it started immediately, but it waited 9 units in total, from 1 to 10. Non-preemptive SJF on the same processes averages 7.75, because it cannot let P2 in early.

      Formulas

      • Turnaround time = finished - arrival
      • Waiting time = turnaround - burst
      • Response time = first run - arrival

      The waiting formula already counts every gap, which matters once processes are split. P1 finishes at 17 after arriving at 0, so its turnaround is 17, and 17 - 8 = 9 units of waiting: the stretch from 1 to 10 when it was ready but not running. Response time only measures the first wait, so for preempted processes it is often much smaller than the waiting time.

      Strengths and weaknesses

      Strengths

      • The lowest average waiting time when bursts are known and switching is free.
      • Short jobs that arrive late still get through quickly.
      • Reacts to every arrival instead of waiting for the CPU to free up.

      Weaknesses

      • Needs to know how much work each process has left.
      • Long jobs can be preempted again and again and may starve.
      • More context switches than SJF, each of which costs time in a real system.

      Common exam mistakes

      1. Comparing against the original burst. At time 1 in the example, P2's 4 is compared with P1's remaining 7, not with P1's burst of 8.
      2. Preempting on a tie. When the newcomer needs exactly what the running process has left, check the rule your course uses. Trace keeps the running process, and the page states it so you can match your textbook.
      3. Losing the waiting time after a preemption. A process that is interrupted keeps accumulating waiting time until it gets the CPU back. Use turnaround minus burst rather than adding gaps by hand.
      4. Mixing up response and waiting time. They are equal in FCFS and SJF, but not here: P1 above has a response time of 0 and a waiting time of 9.
      5. Checking only when a process finishes. That is non-preemptive SJF. SRTF must re-check at every arrival.

      Spotted a mistake?

      Preemptive schedules are easy to get subtly wrong, in textbooks and in tools. If you think this one is, send the processes or the copied link and the answer you expected.

      Email: abdul at abmans dot com