After covering the basic concepts of non-preemptive scheduling algorithms, will see the preemptive scheduling algorithms later in the post.
Formulas of Preemptive scheduling Algorithms are
- Completion Time = Total Time in-between the Process arrival to termination
- Turnaround Time = Completion time- Arrival time OR waiting time+ Burst Time
- Waiting Time = Turnaround time – Burst Time
- Response Time = In Non-Preemptive Response Time= Waiting 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 the every example 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’s
1. Shortest Remaining Time First
In non-preemptive this algorithm also called SJF.
Note: shortest remaining time or Job is depending on Burst time. Highest Remaing time First (HRJF) can also be used where Highest Burst time process are 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 of Queue’s
In Round robin, after completion of each Quantum Period in Running Queue
- All incoming processes in that specific Quantum period are appended in Ready Queue
- If the running process has still its remaining Burst time then it also appended just after point 1 appended processes.
Repeat the same procedure for next quantum period.
- At time Zero only process P1 came and it execute for 2 unit of time. At this execution time, P2 and P3 arrived which are appended in Ready Queue. As P1 still remaining Burst time of 3 unit. So, it also appended just after P3.
- As P1 is completed its quantum so P2 is Picked up from Ready Queue and brings it in Running Queue.
- P2 execute for 2-4 unit of time in Running Queue. At this execution time P4 is arrived which is appended in Ready Queue. As P2 still remaining Burst time of 2 unit. So, it also appended just after P4.
- Now the next number in ready queue after P1,P2 is P3. As P3 executed in 4-6 unit of time and no new process came in this time and P3 is also completed in his first turn so, nothing append in Ready Queue.
- Now the next number in ready queue after P1,P2 ,P3 is P1. As P1 reaming it’s 3 units of Burst time. 2 units are executed from 6-8 unit in running queue. Still No new process is arrived and remaining Burst Time =1 Unit of P1 is appended in ready queue just after P2.
- Now the next number in ready queue after P1,P2 ,P3, P1 is P4. It’s Burst time is only 1.it is completed in 8-9 unit of time in running queue. no new process came in this time and P4 is also completed in his first turn so, nothing append in Ready Queue.
- Now the next number in ready queue after P1,P2 ,P3, P1 ,P4 is P2. It’s reaming Burst time is 2 and it is completed in 9-11 unit of time in running queue. no new process came in this time and P2 is also completed. So, nothing append in Ready Queue.
- In ready queue only the P1 remaining with Burst time =1. it will execute in running queue from 11-12 unit of time.
Note: 6 times context switching takes place.
3. Priority Based (Higher No Higher Priority)
- priority is also given in question.
Note: Questions may be according to (Lower Number have higher the priority)
4. Multilevel Queue
Processes are categorized and given to different ready queue and each ready queue use it’s CPU scheduling algorithm
If the process is system process then it will enter into system queue and it will remain there until it termination. So any coming process to particular queue cannot migrate to other queue. It permanent resides there and terminated.
No lower priority process can execute until all higher priority process 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 will be preempted.
Scheduling in Queues:
If there are multiple processes in Queue then we have to 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 lower priority queue. Let us consider 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) entered then interactive process is preempted to ready Queue and system process gets CPU.
2. Time slicing: In this method each queue executed by CPU for 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.
Consider below table of five processes under multilevel queue scheduling.
- First Queue (Q3) Follows Round Robin (Quantum=4)
- Second Queue (Q2) Follows SRJF
- Third Queue (Q1) Follows FCFS
One big problem with multilevel queue is
when low priority process is request for CPU and at the same time medium or highest priority process came then highest priority process executed first and low priority process have to wait for a long until there will be no high priority process there then low priority process are executed. It will cause the starvation
This problem has been solved through Multi-level feedback
5. Multi-level feedback
Increasing the priority of lower queue process by one each time when it request for CPU and CPU is executing the higher priority processes at that time (called aging). In this way, that lower priority process becomes higher priority process after requesting sometimes. Therefore, starvation can be minimized which was occurring in multilevel queue.
In multilevel feedback, any process can entered in any queue according to their type (system, interactive, batch).
Explain With Example
- There are number of queues having different priority levels,
- Process will enter in the queue according to his priority
- There is a scheduling algorithm for each queue
Multilevel Feedback Queue Methods
- When to upgrade a process to higher-priority queue from lower priority queue
If any Batch process arrive, having Brust Time Less than the Quantum of his Queue. Then it will terminate in his queue otherwise it’s priority will Updated. And it will go to Higher priority Queue which is Intractive process Queue.
Note: If any process is not completed in his quantum period (Round Robin), then it will shifted to lower queue.
1. When to demote a process to lower priority queue from higher priority queue.
If any System process arrive, having Brust Time Less than the Quantum of his Queue then it will terminated in his queue. Otherwise it’s priority will demoted and it will go to lower priority Queue which is Intractive process Queue
Method 2 Example (demote a process to lower priority)
- Queue1 having highest priority and Queue3 having lowest priority
- Queue1 following Round Robin (quantum= 5)
- Queue2 following Round Robin (quantum= 8)
- Queue3 following FCFS
- P3 arrive at zero time when no other process was there it execute for just 2 unit of time then higher priority process P4 of Queue 1 arrive. Preemption occurs.
- CPU execute the P4 (Queue 1 using quantum=5). As 5 unit of time completed the P4 move to lower priority in Queue 2. At this time P2 in Q3 arrive (at point 6) but it’s priority is less than Q 1 and Q2.
- As P4 arrive 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 unit of time then it will demoted to Q3 for it’s remaining (3 unit) execution.
- P4 which is present in Queue 2.And It has remaining only 4 unit of time for execution. Now It will be executed and terminated.
- At this point Queue 1 and Queue 2 are empty.
- And Queue 3 is containing process P1, P2 and demoted P3. As P2 arrive at time 6, P1 arrive at time 8 and P3 arrive in Q3 at time 15. As Q3 follow the algorithm FCFS. So P2 executed first and after that P1 and P3 are executed.
What is the difference between multilevel queue and multilevel feedback queue?
Multilevel queue: Processes are permanently assigned to one queue based on their process priority, memory size, or any other reason.
Multilevel Feedback queue: it allows a process to move between the queues, according to the characteristics i.e. CPU burst.