Module 3 Lesson 4 - Multilevel Scheduling Algorithms PDF

Module 3: Lesson 4 Multilevel Queue Scheduling Lesson Outline: Multiple-Processor Scheduling Multilevel Queue Algorithms Multilevel Feedback Queue Algorithms Operating System – CPU Scheduling Examples  Multiple-Processor Scheduling CPU scheduling more complex when multiple C...

Module 3: Lesson 4 Multilevel Queue Scheduling Lesson Outline: Multiple-Processor Scheduling Multilevel Queue Algorithms Multilevel Feedback Queue Algorithms Operating System – CPU Scheduling Examples  Multiple-Processor Scheduling CPU scheduling more complex when multiple CPUs are available Homogeneous processors within a multiprocessor Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing Symmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes Currently, most common Processor affinity – process has affinity for processor on which it is currently running soft affinity hard affinity Variations including processor sets  Multiple-Processor Scheduling – Load Balancing If SMP, need to keep all CPUs loaded for efficiency Load balancing attempts to keep workload evenly distributed Push migration – periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPUs Pull migration – idle processors pulls waiting task from busy processor  Multilevel Queue Ready queue is partitioned into separate queues, eg: foreground (interactive) background (batch) Process permanently in a given queue Each queue has its own scheduling algorithm: foreground – RR background – FCFS Scheduling must be done between the queues: Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation. Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR 20% to background in FCFS Multilevel Queue Scheduling  Multilevel Queue (MLQ) According to the priority of process, processes are places in different queues. Generally high priority processes are placed in the top level queue. Online after completion of processes from top level queue, lower level queued processes are scheduled.  Multilevel Queue (MLQ) Example: Consider the given table: As you can see, the Queue No column is added to the table. That column is connected to this table below in which each level is assigned to a single algorithm and a priority. Since Queue No. 0 has the highest level queue, all jobs under the said queue will be executed first, then followed by the queue number with the next to the highest level queue and so on.  Multilevel Queue (MLQ) Following the algorithm on the Queue No. 0, J3 was executed first followed by J5. Since, there no jobs left for Queue No. 1, the next queue number will be executed then. Hence, having J4 to be executed first followed by J2, following the algorithm on the Queue No. 1. Note that Average Wt and Average TAt will be computed the same the other algorithms.  Multi-Level Feedback Queue (MLFQ) It allows the process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it is moved to a lower-priority queue. This is similar to MLQ however, this process can move between the queues. MLFQ keep analyzing the behavior (time of execution) of processes and according to which it changes its priority.  Multilevel Feedback Queue A process can move between the various queues; aging can be implemented this way Multilevel-feedback-queue scheduler defined by the following parameters: number of queues scheduling algorithms for each queue method used to determine when to upgrade a process method used to determine when to demote a process method used to determine which queue a process will enter when that process needs service  Example of Multilevel Feedback Queue Three queues: Q0 – RR with time quantum 8 milliseconds Q1 – RR time quantum 16 milliseconds Q2 – FCFS Scheduling A new job enters queue Q0 which is served FCFS When it gains CPU, job receives 8 milliseconds If it does not finish in 8 milliseconds, job is moved to queue Q1 At Q1 job is again served FCFS and receives 16 additional milliseconds If it still does not complete, it is preempted and moved to queue Q2  Multi-Level Feedback Queue (MLFQ) The diagram and the explanation below will make you understand how MLFQ works.  MLFQ Example: Let us suppose that Queue 1 and 2 follow Round Robin with a time slice of 4 and 8, respectively, and Queue 3 follows FCFS. The implementation of MLFQ will be: 1. When a process starts executing then it enters Queue 1. 2. In Queue 1, process executes for 4 unit and if it completes its Burst time, then the CPU will be ready for the next process. 3. If a process completes the 4 unit and still has remaining burst time, then its priority gets reduced and will be shifted to Queue 2. 4. Above steps 2 and 3 are true for Queue 2, however, must use a time slice of 8 instead of 4. If a process has still remaining burst time after executing for 8 unit, it will be shifted to Queue 3. 5. In the last queue, processes are scheduled in FCFS. 6. A process in lower priority can be only executed when higher priority queues are empty. 7. A process running in the lower priority queue is interrupted by a process arriving in the higher priority queue. MLFQ Example:  MLFQ Example: First level will be using RR algorithm with tq= 2. When there are remaining burst time (BT) left, job will be executed using second level algorithm, which is RR tq=3. Again, when there are remaining BT left for the given jobs, third level algorithm will be used which is FCFS. Operating System – CPU Scheduling Examples Linux scheduling Windows scheduling  Linux Scheduling Through Version 2.5 Prior to kernel version 2.5, ran variation of standard UNIX scheduling algorithm Version 2.5 moved to constant order O(1) scheduling time Preemptive, priority based Two priority ranges: time-sharing and real-time Real-time range from 0 to 99 and nice value from 100 to 140 Higher priority gets larger q Task run-able as long as time left in time slice (active) If no time left (expired), not run-able until all other tasks use their slices All run-able tasks tracked in per-CPU run queue data structure Two priority arrays (active, expired), tasks indexed by priority When no more active, arrays are exchanged Worked well, but poor response times for interactive processes  Windows Scheduling Windows uses priority-based preemptive scheduling Highest-priority thread runs next Dispatcher is scheduler Thread runs until (1) blocks, (2) uses time slice, (3) preempted by higher-priority thread Real-time threads can preempt non-real-time 32-level priority scheme Variable class is 1-15, real-time class is 16-31 Priority 0 is memory-management thread Queue for each priority If no run-able thread, runs idle thread  Windows Priority Classes (Cont.) If wait occurs, priority boosted depending on what was waited for Foreground window given 3x priority boost Windows 7 added user-mode scheduling (UMS) Applications create and manage threads independent of kernel For large number of threads, much more efficient UMS schedulers come from programming language libraries like C++ Concurrent Runtime (ConcRT) framework  End of Module 3 -Lesson 4 If you have questions regarding this lesson, kindly message me at my messenger account or on our GC. Thank you!  Reading Assignment: https://www.tutorialspoint.com/operating_system/os_process_schedulin g_algorithms.ht m https://www.guru99.com/cpu-scheduling-algorithms.html https://www.studytonight.com/operating-system/cpu-scheduling https://www.geeksforgeeks.org/cpu-scheduling-in-operating-systems/ https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/5_CPU_Sc heduling.html https://www.javatpoint.com/os-scheduling-algorithms https://afteracademy.com/blog/process-scheduling-algorithms-in-the- operating-system