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..
