CPU Scheduling Algorithms
Lecture-7
I/O event based numerical on Scheduling
algorithms
• Consider the following processes with AT and BT (CPU+IO):
Cont..
• Consider the following processes with AT and BT (CPU+IO):
• Calculate average TAT and WT using preemptive priority scheduling.
• Avg. TAT = (10+13+6)/3 = 9.67
• Avg. WT = (6+9+3)/3 = 6
Cont..
• Consider the following processes with AT and BT (CPU+IO):
• Calculate average TAT and WT using SRTF scheduling.
• Avg. TAT = (11+7+7+11)/4 = 9
• Avg. WT = (6+4+4+8)/4 = 5.5
Multilevel Queue (MLQ) CPU Scheduling
• It may happen that processes in the ready queue can be divided into
different classes where each class has its own scheduling needs.
• For example, a common division is a foreground (interactive) process and
a background (batch) process. These two classes have different
scheduling needs. For this kind of situation Multilevel Queue
Scheduling is used.
• Advantages of Multilevel Queue CPU Scheduling:
• The processes are permanently assigned to the queue, so it has advantage of
low scheduling overhead.
• Disadvantages of Multilevel Queue CPU Scheduling:
• Some processes may starve for CPU if some higher priority queues are
never becoming empty.
• It is inflexible in nature.
Cont..
• Ready Queue is divided into separate queues for each class of processes. For example, let us take three
different types of processes System processes, Interactive processes, and Batch Processes. All three
processes have their own queue. Now, look at the below figure.
• System Processes: The CPU itself has its own process to run which is generally termed as
System Process.
• Interactive Processes: An Interactive Process is a type of process in which there should be
same type of interaction.
• Batch Processes: Batch processing is generally a technique in the Operating system that
collects the programs and data together in the form of the batch before the processing starts.
•
Cont..
• All three different type of processes has their own queue. Each queue has
its own Scheduling algorithm. For example, queue 1 and queue 2
uses Round Robin while queue 3 can use FCFS to schedule their
processes.
• Scheduling among the queues: What will happen if all the queues have
some processes? Which process should get the CPU? To determine this
Scheduling among the queues is necessary. There are two ways to do so –
• Fixed priority preemptive scheduling method – Each queue has absolute
priority over the lower priority queue. Let us consider following priority
order queue 1 > queue 2 > queue [Link] to this algorithm, no
process in the batch queue(queue 3) can run unless queues 1 and 2 are
empty. If any batch process (queue 3) is running and any system (queue 1)
or Interactive process(queue 2) entered the ready queue the batch process is
preempted.
• Time slicing – In this method, each queue gets a certain portion of CPU
time and can use it to schedule its own processes. For instance, queue 1
takes 50 percent of CPU time queue 2 takes 30 percent and queue 3 gets 20
percent of CPU time.
Cont..
• Consider below table of four processes under Multilevel queue scheduling.
Queue number denotes the queue of the process. Priority of queue 1 is
greater than queue 2. queue 1 uses Round Robin (Time Quantum = 2) and
queue 2 uses FCFS.
Multilevel Feedback Queue Scheduling (MLFQ) CPU
Scheduling
• Multilevel Feedback Queue Scheduling (MLFQ) CPU Scheduling is
like Multilevel Queue(MLQ) Scheduling but in this processes can move
between the queues. And thus, much more efficient than multilevel queue
scheduling.
• Advantages of Multilevel Feedback Queue Scheduling:
• It is more flexible.
• It allows different processes to move between different queues.
• It prevents starvation by moving a process that waits too long for the lower
priority queue to the higher priority queue.
• Disadvantages of Multilevel Feedback Queue Scheduling:
• For the selection of the best scheduler, it requires some other means to
select the values.
• It produces more CPU overheads.
• It is the most complex algorithm.
Cont..
• Multilevel feedback queue scheduling, however, allows a process to
move between queues. Multilevel Feedback Queue Scheduling keeps
analyzing the behavior (time of execution) of processes and according to
which it changes its priority.
Cont..
• Example: Consider a system that has a CPU-bound process, which
requires a burst time of 40 seconds. The multilevel Feed Back
Queue scheduling algorithm is used and the queue time quantum
‘2’ seconds and in each level it is incremented by ‘5’ seconds.
Then how many times the process will be interrupted and in which
queue the process will terminate the execution?
• Solution:
• Process P needs 40 Seconds for total execution.
• At Queue 1 it is executed for 2 seconds and then interrupted and
shifted to queue 2.
• At Queue 2 it is executed for 7 seconds and then interrupted and
shifted to queue 3.
• At Queue 3 it is executed for 12 seconds and then interrupted and
shifted to queue 4.
• At Queue 4 it is executed for 17 seconds and then interrupted and
shifted to queue 5.
• At Queue 5 it executes for 2 seconds and then it completes.
• Hence the process is interrupted 4 times and completed on queue 5.
Performance Analysis of the CPU scheduling algorithms
• Performance of Round-Robin scheduling:
• Performance of Round-Robin scheduling depends on time quantum.
• When TQ is small, then there is more context switch overhead.
• Larger TQ makes the system less responsive.
• The value of TQ should neither be too large, wherein it degenerates to work
like FCFS, nor the TQ should be too small , where the efficiency of the
scheduler tends to become almost nearing to zero.
Cont..
Cont..