Preemptive Scheduling 

After covering the basic concepts of non-preemptive scheduling algorithms, we will see the preemptive scheduling algorithms later in the post.

Formulas of Preemptive scheduling Algorithms are

    • Completion Time = Time at which Process terminates (see Gantt chart)
    • Turnaround Time = Completion time- Arrival time    OR    waiting time+ Burst Time
    • Waiting Time = Turnaround time – Burst Time
    • Response Time (In Preemptive)  =  When Process Get the CPU first Time (from Gantt chart) – Arrival time
    • Response Ratio = (Waiting_time + Service_Time) / service_time
    • Avg. Turnaround Time = Sum of turnaround time of all processes/ total processes

All examples of preemptive scheduling algorithms are explained under,

In every example, the Given Fields are

  • Process No
  • Arrival Time
  • Burst Time

We have to find the following fields:

  • Completion Time
  • Turnaround Time
  • Waiting Time
  • Response Time
  • Average Turnaround Time

 Types of Preemptive Scheduling 

1. Shortest Remaining Time First

In non-preemptive, this algorithm is also called SJF.

Shortest remaining time first FCFS preemptive

 Note: The shortest remaining Time or job depends on Burst time. The highest Remaining Time First (HRJF) can also be used where the Highest Burst time process is executed first.

2. Round Robin

Running Queue, also known as Gantt chart. So, To understand Round Robin, we draw two Queues.

  • Ready Queue
  • Running Queue (Gantt chart)

Working on queues

In Round robin, after completion of each Quantum Period in the Running Queue

  • All incoming processes in that specific Quantum period are appended in the Ready Queue.
  • If the running process still has its remaining Burst time, it is also appended just after point 1 appended processes.

Repeat the same procedure for the next quantum period.

 Round Robin

Steps:

  • At Time Zero, only process P1 came, and it executed for 2 units of Time. At this Time of execution, P2 and P3 have arrived and are appended in the Ready Queue. As P1 still has a Burst time of 3 units. So, it is also appended just after P3.
  • As P1 has completed its quantum, P2 is Picked up from the Ready Queue and brought to the Running Queue.
  • P2 executes for 2-4 units of Time in the Running Queue. At this Time of execution, P4 has arrived, which is appended in the Ready Queue. As P2 still has a Burst time of 2 units. So, it is also appended just after P4.
  • The next number in the ready Queue after P1 and P2 is P3. As P3 was executed in 4-6 units of Time, no new process came in this Time, and P3 was also completed in his first turn, so nothing was appended in the Ready Queue.
  • The next number in the ready Queue after P1, P2, and P3 is P1. As P1 reaming, it’s 3 units of Burst time. 2 units are executed from 6-8 units in the running queue. Still, No new process arrives, and the remaining Burst Time =1 Unit of P1 is appended in the ready Queue just after P2.
  • The next number in the ready Queue after P1, P2, P3, and P1 is P4. Its Burst time is only 1. It is completed in 8-9 units of Time in the running Queue. No new process came in this Time, and P4 was also completed in his first turn, so nothing was appended in the Ready Queue.
  • After P1, P2, P3, and P4, the next number in the ready Queue is P2. Its remaining burst time is 2, and it will complete in 9-11 units of Time in the running queue.no. No new process came in this Time, and P2 was also completed. So, nothing is in the Ready Queue.
  • In the ready QQueue, only the P1 remains with burst time =1. it will execute in running Queue from 11-12 units of Time.

Note: 6 times, context switching takes place.

3. Priority Based (Higher No Higher Priority)

  • priority is also given in question.

Priority Based preemptive

Note: Questions may be according to (Lower Number have higher priority)

4. Multilevel Queue

Processes are categorized and given to different ready Queues, and each ready Queue uses its CPU scheduling algorithm.

Multilevel Queue

If the Process is a system process, it will enter into the system queue and remain there until its termination. So, any coming process to a particular queue cannot migrate to another. It permanently resides there and is terminated.

No lower-priority process can be executed until all higher-priority processes are executed. And all higher-priority queues are empty.

If an interactive process entered the ready Queue while a batch process was running, the batch process would be preempted.

Scheduling in Queues: 

If multiple processes exist in the Queue, we must decide which Process should get the CPU first. That’s why Scheduling among the queues is necessary.

1. Fixed priority preemptive scheduling method: Each Queue has priority over a lower priority queue. Consider the following priority order: queue 1 > queue 2 > queue 3… Qn. According to this algorithm, no process in the batch queue (queue 3) can run unless queue 1(System Process and Queue 2(Interactive process) are empty. If any Interactive process (queue 2) is running and any system (queue 1) is entered, then the interactive Process is preempted to ready the Queue, and the system process gets CPU.

2. Time slicing: In this method, each Queue is executed by the CPU for a certain amount of Time. For example, queue 1 takes 60 percent of CPU time, queue 2 takes 40 percent, and queue 3 gets 10 percent of CPU time.

Example Problem:
Consider the below table of five processes under multilevel queue scheduling.

  • First Queue (Q3) Follows Round Robin (Quantum=4)
  • Second Queue (Q2) Follows SRJF
  • The third Queue (Q1) Follows FCFS

Multilevel Queue question

One big problem with multilevel queues is

when a priority process is requested for CPU, and at the same Time, the medium or highest-priority process comes. The highest-priority Process is executed first, and the priority process has to wait a long time until there is no high-priority process; then, the low-priority process is executed. It will cause starvation

This problem has been solved through Multilevel feedback

5. Multilevel feedback

Increasing the priority of the lower queue process by one each Time it requests for CPU and CPU is executing the higher priority processes at that Time (called aging). In this way, that lower priority process becomes a higher priority after requesting sometimes. Therefore, starvation, which occurs in multilevel queues, can be minimized.

In multilevel feedback, any process can entered in any queue according to their type (system, interactive, batch).

Explain With Example

  • Several queues are having different priority levels,
  • The Process will enter the Queue according to his priority
  • There is a scheduling algorithm for each Queue

Multilevel Feedback Queue Methods

  1. When to upgrade a process to a higher-priority queue from a priority queue

multilevel feedback example

If any batch process arrives, it will have a Brust Time Less than the Quantum of his Queue. Then, it will terminate in his Queue; otherwise, its priority will Updated. It will go to the Higher priority Queue, which is the Interactive Process Queue.

Example

Multilevel feedback Question

Note: If any process is not completed in his quantum period (Round Robin), it will shift to a lower queue.

1. When to demote a process to a lower priority queue from a higher priority queue.

If any System process arrives having Brust Time Less than the Quantum of his Queue, it will terminate in his Queue. Otherwise, its priority will be demoted, and it will go to the lower priority Queue, the Interactive Process Queue.

Method 2 Example (demote a process to lower priority)

  • Queue1 has the highest priority, and Queue3 has the lowest priority
  • Queue1 following Round Robin (quantum= 5)
  • Queue2 following Round Robin (quantum= 8)
  • Queue3 following FCFS

Multilevel Feed Back Preemptive

Steps:

  • P3 arrived at zero Time when no other process was there. It executes for just 2 units of Time than the higher priority process P4 of Queue 1 arrives. Preemption occurs.
  • CPU executes the P4 (Queue 1 using quantum=5). As 5 time units were completed, the P4 moved to lower priority in Queue 2. At this Time, P2 in Q3 arrives (at point 6), but its priority is less than Q1 and Q2.
  • As P4 arrives in Q2 at time 7 and P3 is also there in Queue 2, which will execute first for his quantum period =8

  • When P3 is executed for 8 units of Time, then it will demoted to Q3 for its remaining (3 unit) execution.
  • P4, which is present in Queue 2. And It has remained only 4 units of Time for execution. Now, It will be executed and terminated.

  • At this point, Queue 1 and Queue 2 are empty.
  • And Queue 3 contains processes P1, P2, and demoted P3. P2 arrives at time 6, P1 arrives at time 8, and P3 arrives in Q3 at time 15. Q3 follows the algorithm FCFS. So, P2 is executed first, and after that, P1 and P3 are executed.

What is the difference between a multilevel queue and a multilevel feedback queue?

Multilevel Queue:  Processes are permanently assigned to one Queue based on their process priority, memory size, or other reasons.

Multilevel Feedback queue:  it allows a process to move between the queues according to the characteristics, i.e., CPU burst.