Priority Scheduling

Operating System presentation on priority Scheduling, Queue Scheduling and multi level feedback scheduling with examples.

1. Operating system Presentation Group 3rd

2. Jawad Haider (20011519-055) Sana Khalid (20011519-019) Faiza Ijaz (20011519-047)

3. Topics Priority Scheduling Multilevel Queue Scheduling Multilevel Feedback Queue Scheduling

4. Jawad Haider 20011519-055 01 Priority Scheduling

5. Priority Scheduling 01 Introduction What is priority Scheduling 02 Preemptive priority Scheduling 03 Non- preemptive Priority Scheduling 04 Example Gantt chart, Process waiting time and average waiting time 05 Problem Solution of this problem 06 Question Using preemptive scheduling

6. Priority Scheduling( Basic Concept ) A priority is associated with each process, and the CPU is allocated to the process with the highest priority.  Equal-priority processes  are scheduled in  FCFS order. Types of Priority Scheduling Preemptive Priority Scheduling Non-preemptive Priority Scheduling

7. Preemptive priority Scheduling A  Preemptive Priority scheduling algorithm will pre-empt the CPU if the priority of the newly arrived process is higher than the priority of the currently running process.

8. N o n-Preemptive priority Scheduling A  Non-preemptive Priority scheduling algorithm will put the new process at the head of the ready queue. Here, the currently running process will not be pre-empted by the new process.

9. The priority of the process is determined in terms of  high priority  and  low priority.   Some fixed range of numbers generally indicates priorities. However, there is no general agreement on whether 0 is the highest or lowest priority. Some systems use low numbers to represent low priority; others use low numbers for high priority. This difference can lead to confusion. Here, we will assume that  low numbers represent high priority. Deciding the priority of a process

10. Example Consider the following set of processes, assumed to have arrived at time 0, in the order P1, P2, P3, P4, P5, with the length of the CPU burst given in milliseconds: Process ID Brust Time Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2

11. Gantt chart: P2 P5 P1 P3 P4 4 0 1 6 16 18 19 Waiting Time for P1 =  6 milliseconds. Waiting Time for P2 =  0 milliseconds. Waiting Time for P3 =  16 milliseconds. Waiting Time for P4 =  18 milliseconds. Waiting Time for P5 =  1 milliseconds. So, the  Average Waiting Time  = (6+0+16+18+1)/5 =  8.2 milliseconds.

12. Problem with Priority Scheduling A major problem with priority scheduling algorithms is  indefinite blocking   or  starvation. A process that is ready to run but waiting for the CPU can be considered blocked. If a low priority process is waiting in the queue for CPU and new high priority processes keep entering the queue, the higher priority processes will keep executing. In such a case, the process with low priority will be delayed, or it may never get the CPU in the worst case. A priority scheduling algorithm can leave some low priority processes waiting indefinitely. In a heavily loaded computer system, a steady stream of higher-priority processes can prevent a low-priority process from ever getting the CPU.

13. Solution A solution to the problem of indefinite blockage of low-priority processes is  aging. Aging  is a technique of gradually increasing the priority of processes that wait in the system for a long time. For Example: If priorities range from 127 (low) to 0 (high), we could increase the priority of a waiting process by 1 every 15 minutes. Eventually, even a process with an initial priority of 127 would have the highest priority in the system and would be executed. Thus, we have discussed how priority scheduling works, the problem of starvation the low priority processes face, and its solution in the form of aging.

14. Solve Example Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes has I/O burst time. Process ID Arrival Time Brust Time Priority P1 11 2 P2 5 28 P3 12 2 3 P4 2 10 1 P5 9 16 4 The average waiting time (in milliseconds) of all the processing using preemptive priority scheduling algorithm is _________________. (A) 29 (B) 30 (C)31 (D)32

15. Gantt Chart 0 2 5 33 40 49 51 67 P1 P4 P2 P4 P1 P3 P5 Waiting Time = Total Waiting Time – No. of milliseconds Process executed – Arrival Time Waiting Time for P1 = (40 -2-0) =  38 milliseconds. Waiting Time for P2 = (5-0-5) =  0 milliseconds. Waiting Time for P3 = (49-0-12) =  37 milliseconds. Waiting Time for P4 = (33-3-2) =  28 milliseconds. Waiting Time for P5 = (51-0-9) =  42 milliseconds. Average Waiting time  = (38+0+37+28+42)/ 5 = 145/5 =  29 milliseconds

16. Sana Khalid 20011519-019 02 Multilevel Queue Scheduling

17. Basic concept Multilevel queue scheduling is  used when processes in the ready queue can be divided into different classes where each class has its own scheduling needs . For instance, foreground or interactive processes and background or batch processes are commonly divided.

18. Cont.… Each queue is assigned a priority and can use its own scheduling algorithm which makes it convenient to use many scheduling algorithms at the same time .  Generally, topmost level of queue has highest priority which decreases as we move to lower levels.

19. Advantage The major advantage of this algorithm is that we can use various algorithms such as FCFS, SJF, LJF, etc. At the same time in different queues. Disadvantage The lowest level processes suffer from  starvation problem .

20. Priority queue scheduling. It executes processes based upon their priorities . It is both preemptive and non preemptive in nature. There is no idea of average waiting time and response time. MLQ. Processes are executed depending on priority of that particular level of queue to which process belongs. It can be both non-preemptive and preemptive in nature depending upon conditions. Average waiting time and average response time depends upon algorithms used in various levels of multi level queue for scheduling. Difference between MLQ and priority queue scheduling

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

22. Ready Queue 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.

23. The Description of the processes are as follows: 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.

24. 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. All three different type of processes has their own queue. Each queue has its own Scheduling algorithm. 

25. Solve Example Consider the below table of four processe s under Multilevel Queue scheduling. Queue number denoted the queue of the process. Priority of queue 1 is greater then queue 2. Queue one has Round Robin and queue 2 uses FCFS. Process Queue AT BT CT TAT WT P1 1 4 P2 1 3 P3 2 8 P4 1 10 5

26. Faiza Ijaz 20011519-047 03 Multilevel Feedback Queue Scheduling

27. Difference between (MLQ)and(MLFQ) CPU scheduling algorithms: MLQ: The priority is fixed in this algorithm. When all processes in one queue get executed completely then only processes in other queue are executed. MLFQ: The priority for process is dynamic as process is allowed to move between queue. A process taking longer time in lower priority queue can be shifted to higher priority queue and vice versa.  Since, processes do not move between queues, it has low scheduling overhead and is inflexible.  Since, processes are allowed to move between queues, it has high scheduling overhead and is flexible.

28. Multilevel Feedback Queue Scheduling In this processes can move between the queues. And thus, much more efficient than multilevel queue scheduling. Multilevel Feedback Queue Scheduling:

29. Multilevel feedback queue scheduling, however, allows a process to move between queues. The idea is to separate processes with different CPU-burst characteristics. If a process uses too much CPU time, it will be moved to a lower-priority queue. Similarly, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue. Working of MLFQS:

30. Multilevel feedback queue scheduling , however, allows a process to move between queues. Multilevel Feedback Queue   Scheduling  (MLFQ)  keeps analyzing the behavior (time of execution) of processes and according to which it changes its priority.  Cont.…

31. In general, a multilevel feedback queue scheduler is defined by the following parameters: The number of queues. The scheduling algorithm for each queue. The method used to determine when to upgrade a process to a higher-priority queue. The method used to determine when to demote a process to a lower-priority queue. The method used to determine which queue a process will enter when that process needs service.

32. Exercise Question:  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? 

33. Solutio n: 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. 

34. Advantage 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. Disadvantage It produces more CPU overheads. It is the most complex algorithm.