Lecture 5: CPU Scheduling PDF

Chapter 6: CPU Scheduling Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Previous Lecture Process Synchronization Background The Critical-Section Problem Peterson’s Solut...

Chapter 6: CPU Scheduling Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013  Previous Lecture Process Synchronization Background The Critical-Section Problem Peterson’s Solution Synchronization Hardware Mutex Locks Semaphores Classic Problems of Synchronization Monitors Synchronization Examples Alternative Approaches Operating System Concepts – 9th Edition 6.2 Silberschatz, Galvin and Gagne ©2013  Chapter 6: CPU Scheduling Basic Concepts Scheduling Criteria Scheduling Algorithms Thread Scheduling Multiple-Processor Scheduling Operating System Concepts – 9th Edition 6.3 Silberschatz, Galvin and Gagne ©2013  Process State Transition Diagram Operating System Concepts – 9th Edition 6.4 Silberschatz, Galvin and Gagne ©2013  Objectives To introduce CPU scheduling, which is the basis for multiprogrammed operating systems To describe various CPU-scheduling algorithms To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system To examine the scheduling algorithms of several operating systems Operating System Concepts – 9th Edition 6.5 Silberschatz, Galvin and Gagne ©2013  Basic Concepts Maximum CPU utilization obtained with multiprogramming CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait CPU burst followed by I/O burst CPU burst distribution is of main concern Operating System Concepts – 9th Edition 6.6 Silberschatz, Galvin and Gagne ©2013  Histogram of CPU-burst Times Operating System Concepts – 9th Edition 6.7 Silberschatz, Galvin and Gagne ©2013  CPU Scheduler Short-term scheduler selects from among the processes in ready queue, and allocates the CPU to one of them Queue may be ordered in various ways CPU scheduling decisions may take place when a process: 1. Switches from running to waiting state 2. Switches from running to ready state 3. Switches from waiting to ready 4. Terminates Scheduling under 1 and 4 is non-preemptive All other scheduling is preemptive Consider access to shared data Consider preemption while in kernel mode Consider interrupts occurring during crucial OS activities Operating System Concepts – 9th Edition 6.8 Silberschatz, Galvin and Gagne ©2013  Dispatcher Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: switching context switching to user mode jumping to the proper location in the user program to restart that program Dispatch latency – time it takes for the dispatcher to stop one process and start another running Operating System Concepts – 9th Edition 6.9 Silberschatz, Galvin and Gagne ©2013  Scheduling Criteria CPU utilization – keep the CPU as busy as possible Throughput – # of processes that complete their execution per time unit Turnaround time – amount of time to execute a process Waiting time – amount of time a process has been waiting in the ready queue Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment) Operating System Concepts – 9th Edition 6.10 Silberschatz, Galvin and Gagne ©2013  Scheduling Algorithm Optimization Criteria A CPU scheduling algorithm tries to maximize and minimize the following: Operating System Concepts – 9th Edition 6.11 Silberschatz, Galvin and Gagne ©2013  First- Come, First-Served (FCFS) Scheduling First come first serve (FCFS) scheduling algorithm simply schedules the jobs according to their arrival time. The job which comes first in the ready queue will get the CPU first. The lesser the arrival time of the job, the sooner will the job get the CPU. FCFS scheduling may cause the problem of starvation if the burst time of the first process is the longest among all the jobs. Operating System Concepts – 9th Edition 6.12 Silberschatz, Galvin and Gagne ©2013  FCFS Scheduling TAT = WT + BT Assign CPU to the process which comes first TAT = CT-AT WT = TAT - BT Non-preemptive Process Arrival Time Burst Time CT TAT WT RT (AT) (BT) P1 2 2 4 2 0 0 P2 0 1 1 1 0 0 P3 2 3 7 5 2 2 P4 3 5 12 9 4 4 P5 4 4 16 12 8 8 P2 P1 P3 P4 P5 0 1 2 4 7 12 16 Operating System Concepts – 9th Edition 6.13 Silberschatz, Galvin and Gagne ©2013  First- Come, First-Served (FCFS) Scheduling Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is: P1 P2 P3 0 24 27 30 Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 Operating System Concepts – 9th Edition 6.14 Silberschatz, Galvin and Gagne ©2013  FCFS Scheduling (Cont.) Suppose that the processes arrive in the order: P2 , P3 , P1 The Gantt chart for the schedule is: P2 P3 P1 0 3 6 30 Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect - short process behind long process Consider one CPU-bound and many I/O-bound processes Operating System Concepts – 9th Edition 6.15 Silberschatz, Galvin and Gagne ©2013  Convoy Effect Process AT BT TAT WT Process AT BT TAT WT P1 0 50 50 0 P1 1 50 52 2 P2 1 1 50 49 P2 0 1 1 0 P3 1 2 52 50 P3 0 2 3 1 Avg. Waiting Time = 99/3 = 33 Avg. Waiting Time = 3/3 = 1 P1 P2 P3 P2 P3 P1 0 50 51 53 0 1 3 53 Process having a very long burst time Starvation is the problem that occurs when has arrived before the small processes high priority processes keep executing and Therefore, small processes must low priority processes get blocked for wait for long time → Convoy Effect indefinite time. Operating System Concepts – 9th Edition 6.16 Silberschatz, Galvin and Gagne ©2013  Convey Effect Convoy Effect is phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to few slow processes. FCFS algorithm is non-preemptive in nature, that is, once CPU time has been allocated to a process, other processes can get CPU time only after the current process has finished. This property of FCFS scheduling leads to the situation called Convoy Effect. Operating System Concepts – 9th Edition 6.17 Silberschatz, Galvin and Gagne ©2013  FCFS Advantages and Disadvantages Advantages It is simple and easy to understand. Disadvantages The process with less execution time suffer i.e., waiting time is often quite long. Favors CPU Bound process then I/O bound process. Here, first process will get the CPU first, other processes can get CPU only after the current process has finished its execution. Now, suppose the first process has large burst time, and other processes have less burst time, then the processes will have to wait more unnecessarily, this will result in more average waiting time, i.e., Convey effect. This effect results in lower CPU and device utilization. FCFS algorithm is particularly troublesome for time-sharing systems, where it is important that each user get a share of the CPU at regular intervals. Operating System Concepts – 9th Edition 6.18 Silberschatz, Galvin and Gagne ©2013  Shortest-Job-First (SJF) Scheduling Shortest job first (SJF) or shortest job next, is a scheduling policy that selects the waiting process with the smallest execution time to execute next. SJN is a non-preemptive/preemptive algorithm. Algorithm: Sort all the process according to the arrival time. Then select that process which has minimum arrival time and minimum Burst time. After completion of process make a pool of process which after till the completion of previous process and select that process among the pool which is having minimum Burst time. Operating System Concepts – 9th Edition 6.19 Silberschatz, Galvin and Gagne ©2013  SJF Scheduling Shortest Job First/Shortest Job Next Out of all available (waiting) processes, it selects the process with the smallest burst time to execute next Non-preemption → Once CPU has been allocated to a process then that process cannot be forcefully removed from the CPU till its termination Pre-emption (Shortest Remaining Time First – SRTF/SRTN) → Forcefully remove the process from CPU If multiple processes with same burst time are ready to be scheduled, then FCFS technique shall be applied Operating System Concepts – 9th Edition 6.20 Silberschatz, Galvin and Gagne ©2013  SJF Scheduling TAT = WT + BT WT = TAT - BT Process Arrival Time Burst Time CT TAT WT RT (AT) (BT) P1 2 1 7 5 4 4 P2 1 5 16 15 10 10 P3 4 1 8 4 3 3 P4 0 6 6 6 0 0 P5 2 3 11 9 6 6 P4 P1 P3 P5 P2 0 6 7 8 11 16 In Ready Queue, we have all the other process, i.e., P1, P2, P3, P5 Operating System Concepts – 9th Edition 6.21 Silberschatz, Galvin and Gagne ©2013  Example of SJF ProcessArrival Time Burst Time P1 0.0 6 P2 2.0 8 P3 4.0 7 P4 5.0 3 SJF scheduling chart P4 P1 P3 P2 0 3 9 16 24 Average waiting time = (3 + 16 + 9 + 0) / 4 = 7 Operating System Concepts – 9th Edition 6.22 Silberschatz, Galvin and Gagne ©2013  Determining Length of Next CPU Burst Can only estimate the length – should be similar to the previous one Then pick process with shortest predicted next CPU burst Can be done by using the length of previous CPU bursts, using exponential averaging 1. t n = actual length of n th CPU burst 2.  n +1 = predicted value for the next CPU burst 3.  , 0    1 4. Define :  n =1 =  t n + (1 −  ) n. Commonly, α set to ½ Preemptive version called shortest-remaining-time-first Operating System Concepts – 9th Edition 6.23 Silberschatz, Galvin and Gagne ©2013  Prediction of the Length of the Next CPU Burst Calculate the exponential averaging with T1 = 10, α = 0.5 and the algorithm is SJF with previous runs as 8, 7, 4, 16. Explanation : Initially T1 = 10 and α = 0.5 and the run times given are 8, 7, 4, 16 as it is shortest job first, formula is:  n =1 =  t n + (1 −  ) n. So the possible order in which these processes would serve will be 4, 7, 8, 16 since SJF is a non-preemptive technique. So, using formula: T2 = α*t1 + (1-α)T1 so we have, T2 = 0.5*4 + 0.5*10 = 7, here t1 = 4 and T1 = 10 T3 = 0.5*7 + 0.5*7 = 7, here t2 = 7 and T2 = 7 T4 = 0.5*8 + 0.5*7 = 7.5, here t3 = 8 and T3 = 7 So the future prediction for 4th process will be T4 = 7.5 which is the option(c). Operating System Concepts – 9th Edition 6.24 Silberschatz, Galvin and Gagne ©2013  SJF with Preemption/SRTF Here, the burst time of P2 is 5 and the remaining time of P4 is 5, which one is smaller? As both are same so FCFS. Whenever new process arrives, there may be preemption of the running process If the newly arrived process has shorter burst time than the remaining burst time of the currently running process. Then the OS remove the currently running process and allocates the CPU to the newly arrived Is there any newly process arrived at 1? process. When all the processes Available Process are P4 and P2 arrived in the Ready Queue then In queue, we have 4 processes: the OS does Burst not need P4, P2, P1, and P5 Process Arrival Time Timeto monitor Which process has the smallest (AT)the scheduling (BT) after burst time? every unit of time. After Yes! That is P2 P1 2 that moment 0 1 the SRTF P1 will work as SJF At 3, do we have any other process P2 1 5 that arrived in the queue? P3 4 1 0 No The processes in the queue are: P4 0 6 5 4 P4, P2, and P5 P5 2 3 2 P5 has the smallest burst time Is there any other process came at unit time 4? P4 P4 P1 P5 P3 Is there any other process came at 1 2 3 4 5 unit time 4? 0 Operating System Concepts – 9th Edition 6.25 P4, P2, P5, and P3 Silberschatz, Galvin and Gagne ©2013  Whenever new process arrives, there may be preemption of the running process If the newly arrived process has shorter burst time than the remaining burst time of the currently running process. Then the OS remove the currently running process and allocates the CPU to the newly arrived process. 33/5 17/5 Optimal = 6.6 = 3.4 Solution Process Arrival Time Burst Time CT TAT WT RT (AT) (BT) P1 2 1 0 3 1 0 0 P2 1 5 0 16 15 10 10 P3 4 1 0 5 1 0 0 P4 0 654 0 11 11 5 0 P5 2 32 0 7 5 2 1 P4 P4 P1 P5 P3 P5 P4 P2 0 1 2 3 4 5 7 11 16 Operating System Concepts – 9th Edition 6.26 Silberschatz, Galvin and Gagne ©2013  Example of Shortest-remaining-time-first Now we add the concepts of varying arrival times and preemption to the analysis ProcessAarri Arrival TimeT Burst Time P1 0 8 P2 1 4 P3 2 9 P4 3 5 Preemptive SJF Gantt Chart P1 P2 P4 P1 P3 0 1 5 10 17 26 Average waiting time = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec Operating System Concepts – 9th Edition 6.27 Silberschatz, Galvin and Gagne ©2013  SJF Advantages and Disadvantages Advantages Shortest jobs are favored. It is provably optimal; in that it gives the minimum average waiting time for a given set of processes. Disadvantages SJF may cause starvation, if shorter processes keep coming. This problem is solved by aging. It cannot be implemented at the level of short-term CPU scheduling. Operating System Concepts – 9th Edition 6.28 Silberschatz, Galvin and Gagne ©2013  Priority Scheduling A priority number (integer) is associated with each process The CPU is allocated to the process with the highest priority (smallest integer  highest priority) Preemptive Nonpreemptive SJF is priority scheduling where priority is the inverse of predicted next CPU burst time Problem  Starvation – low priority processes may never execute Solution  Aging – as time progresses increase the priority of the process Operating System Concepts – 9th Edition 6.29 Silberschatz, Galvin and Gagne ©2013  Example of Priority Scheduling ProcessA arri Burst TimeT Priority P1 10 3 P2 1 1 P3 2 4 P4 1 5 P5 5 2 Priority scheduling Gantt Chart Average waiting time = 8.2 msec Operating System Concepts – 9th Edition 6.30 Silberschatz, Galvin and Gagne ©2013  Priority Scheduling Advantages and Disadvantages Advantages The priority of a process can be selected based on memory requirement, time requirement or user preference. Disadvantages: A second scheduling algorithm is required to schedule the processes which have same priority. In preemptive priority scheduling, a higher priority process can execute ahead of an already executing lower priority process. If lower priority process keeps waiting for higher priority processes, starvation occurs. Operating System Concepts – 9th Edition 6.31 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. Process Time = CPU Time + I/O Time OR Suppose Arrival Time of each process = 0 CPU Burst Time + I/O Burst Time 30% 50% 20% Process CPU I/O CPU Processes Time AT Time Time Time SJF: That process will get the CPU which has shortest Burst Time, However, make P1 20 0 6 10 4 = 20 sure that those processes need to be in the Ready queue. It means, you must P2 30 0 9 15 6 = 30 check the arrival time, if the process is in Ready Queue, then you must take into P3 10 0 3 5 2 = 10 account the burst time for SJF Now Time has been divided in accordance with the question Now divide the time as per the requirements 30% of 20 is 6. for each of the given processes 30% of 20 can be written as 30% × 20 = 30/100 × 20 =6 Operating System Concepts – 9th Edition 6.32 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. 30% 50% 20% Processes Process AT CPU I/O CPU Which Process is having a shortest Time ? Time Time Time Time P1 20 0 6 10 4 P2 30 0 9 15 6 P3 10 0 3 5 2 P1 P2 P3 New Ready Run Exit If Process P3 Needs some I/O Wait/ Block operations 0 3 Operating System Concepts – 9th Edition 6.33 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. 30% 50% 20% P3 will return after 5 units of time = 8 Process CPU I/O CPU Processes Time AT Time Time Time So, the OS needs to allocate the CPU to other processes P1 20 0 6 10 4 In ready queue, which processes are 15 6 there, and which process needs to be P2 30 0 9 dispatched to running state? P3 10 0 3 5 2 P1 P2 P3 Till what time? New Ready Run Exit 6 units of Time Because it also requires I/O after 6 units of time P3 P1 Wait/ 0 3 9 Block Operating System Concepts – 9th Edition 6.34 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Please Note That: Three processesThe P1,OS P2, must P3 withneed processto time consider 20, 30, 10, respectively. Each process uses the Wait/Blocked the first state 30% of its process time in CPU then 50% in I/O as well before allocating and last 20% in CPU. to CPU, May be some processes Find Avg. WT, TAT andrequire RT, if system to movefollows toSJF scheduling. Ready Queue 30% 50% 20% P3 will return after 5 units of time = 8 Process CPU I/O CPU Processes Time AT Time Time Time P1 will return after 10 units of time (9+10) = 19 P1 20 0 6 10 4 In Ready Queue, we have P2 and P3, So CPU will be allocated to which Process? P2 30 0 9 15 6 P3 10 0 3 5 2 P3 P2 New Ready Run Exit P3 P1 Wait/ P1 0 3 9 Block Operating System Concepts – 9th Edition 6.35 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. 30% 50% 20% P3 will return after 5 units of time = 8 Process CPU I/O CPU Processes Time AT Time Time Time P1 will return after 10 units of time (9+10) = 19 P1 20 0 6 10 4 Between P2 and P3, which Process will be allocated to CPU? P2 30 0 9 15 6 P2 Require 30 units of time and P3 requires how much unit of time? P3 10 0 3 5 2 P3 P2 New Ready Run Exit P3 P1 P3 Wait/ P1 0 3 9 11 Block Operating System Concepts – 9th Edition 6.36 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. 30% 50% 20% Process CPU I/O CPU Processes Time AT Time Time Time P1 will return after 10 units of time (9+10) = 19 P1 20 0 6 10 4 We have two processes now. As P1 is still in Blocked state so in the ready P2 will return after 15 units of time (20 + 15) = 35 P2 30 0 9 15 6 queue, we just have P2 P3 10 0 3 5 2 P2 P2 shall be in the running state for 9 units of time As it also requires I/O Processing New Ready Run Exit P3 P1 P3 P2 Wait/ P1 0 3 9 11 20 Block Operating System Concepts – 9th Edition 6.37 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process At unit time 24, uses There isthe no first 30% of its process time P2 will in CPU remain then in Blocked 50% in I/O state Process in20% the Ready queue, till 35 unit of time. and last in CPU. A process is in the Blocked state, So, CPU is now doing nothing But this is doing I/O processing At 35, it will be moved to Find Avg. WT, TAT and It will return at unit time 35 RT, if system follows SJF ready scheduling. queue and dispatched to running state. 30% 50% 20% Process CPU I/O CPU Processes AT Time Time Time Time P1 will return after 10 units of time (9+10) = 19 P1 20 0 6 10 4 P2 will return after 15 units of time (20 + 15) = 35 Now in Ready Queue, We have P1, which will be P2 30 0 9 15 6 moved to running state for 4 units of time. P3 10 0 3 5 2 P1 New Ready Run Exit P3 P1 P3 P2 P1 P2 Wait/ P2 0 3 9 11 20 24 35 41 Block Operating System Concepts – 9th Edition 6.38 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. TAT = CT – AT or BT + WT Process CPU I/O CPU TAT Processes AT Time Time Time Time P1 20 0 6 10 4 24 TAT for P2 = 41 - 0 P2 30 0 9 15 6 41 TAT for P3 = 11 - 0 P3 10 0 3 5 2 11 P1 completed its execution TAT = 24 – 0 = 24 Gantt Chart P3 P1 P3 P2 P1 P2 0 3 9 11 20 24 35 41 Operating System Concepts – 9th Edition 6.39 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and last 20% in CPU. Find Avg. WT, TAT and RT, if system follows SJF scheduling. TAT = CT – AT or WT = TAT - BT BT + WT Here BT means the Processes Process Time AT CPU Time I/O Time CPU Time TAT WT CPU Burst Time P1 20 0 6 10 4 24 14 WT for P1 = 24 - ? P2 30 0 9 15 6 41 WT for P1 = 24 – 10 = 14 3 5 2 11 OR P3 10 0 P1 waited for 3 units P1 waited for 11 So, 3 + 11 = 14 of time (20-9) units of time Gantt Chart P3 P1 P3 P2 P1 P2 0 3 9 11 20 24 35 41 Operating System Concepts – 9th Edition 6.40 Silberschatz, Galvin and Gagne ©2013  SJF with processes with CPU & I/O Time Three processes P1, P2, P3 with process time 20, 30, 10, respectively. Each process uses the first 30% of its process time in CPU then 50% in I/O and lastEfficiency 20% in CPU.of CPU or Find Avg. WT,Utilization CPU TAT and RT,=if system follows SJF scheduling. expected CPU Time/ActualTAT Time = Taken CT – AT or WT = TAT - BT = 10 + 15 + 5/41 = 30/41 = 73% BT + WT Processes Process AT CPU I/O CPU TAT WT RT RT = It is the time Time Time Time Time when the CPU was Idle P1 CPU 20 time 0 = (35 6 – 10 24)/41 4 = 11/41 24 14 3 allocated to the = 27% process for the very 9 15 6 41 26 11 P2 30 0 first time – the P3 10 0 3 5 2 11 6 0 Arrival Time or when the process came to running queue for WT for P2 = 41 – 15 = 26 the very first time – the Arrival Time WT for P3 = 11 – 5 = 6 RT for P1 = 3 – 0 = 3 Gantt Chart RT for P2 = 11 – 0 = 11 RT for P3 = 0 – 0 = 0 P3 P1 P3 P2 P1 P2 0 3 9 11 20 24 35 41 Operating System Concepts – 9th Edition 6.41 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) Each process gets a small unit of CPU time (time quantum q), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units. Timer interrupts every quantum to schedule next process Performance q large  FIFO q small  q must be large with respect to context switch, otherwise overhead is too high It is always pre-emptive scheduling algorithm Time quantum is a time in which a process is allowed to run uninterrupted in a preemptive multitasking operating system Here the criteria is Arrival Time + Time Quantum Operating System Concepts – 9th Edition 6.42 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) In this example, Used in Time Sharing Systems Just Consider CPU Bound Similar to FCFS with Time Quantum Processes with Preemptive mode Suppose Time Quantum → 3 units of time Processes AT BT P1 0 8 5 Try to maintain a Ready Queue along with the Gantt Chart for your ease P2 5 2 Criteria = AT + TQ P3 1 7 4 Now at unit time 3, the Process P1 would be P4 6 3 moved from the CPU and need to moved P5 8 5 into the ready queue. However, you need to check whether any Ready Queue other process came into the ready queue or not. Like here, at unit time 1 P3 came into P1 P3 P1 the ready queue At Unit time 3, P1 will be removed to running to the ready queue because of the P1 P3 criteria Now which process (es) is in the ready 0 3 6 queue ? P3 so move that to running Gantt Chart Operating System Concepts – 9th Edition 6.43 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) In this example, Used in Time Sharing Systems Just Consider CPU Bound Similar to FCFS with Time Quantum Processes with Preemptive mode Suppose Time Quantum → 3 units of time Processes AT BT P1 0 8 5 You don’t just need to move the process P2 5 2 from running to the ready queue, however, P3 1 7 4 before moving the process, just see for any new process. P4 6 3 At unit time 5, P2 came into the ready P5 8 5 queue Ready Queue Now, at unit time 6, a new process (P4) came and at unit time 6, P3 need to move to ready queue or P4? P1 P3 P1 P2 P4 P3 In such kind of situations, the newly arrived processes need to be in the ready queue P1 P3 0 3 6 Gantt Chart Operating System Concepts – 9th Edition 6.44 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) In this example, Used in Time Sharing Systems Just Consider CPU Bound Similar to FCFS with Time Quantum Processes with Preemptive mode Suppose Time Quantum → 3 units of time Processes AT BT P1 0 8 5 2 Now P1 will be removed from Ready Queue to running. P2 5 2 0 At unit time 9, P1 will move from running to P3 1 7 4 1 ready P4 6 3 0 However, you must for any newly arrived processes, like P5 in this case. P5 8 5 Now, P1 needs to be in the ready queue Ready Queue Now, here check the burst time P1 P3 P1 P2 P4 P3 P5 P1 P3 P1 P3 P1 P2 P4 P3 As P2 is in the terminate sate so no need to put the process in the ready queue. 0 3 6 9 11 14 17 P4 will not move to ready queue, as Gantt Chart It has completed the execution Operating System Concepts – 9th Edition 6.45 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) In this example, Used in Time Sharing Systems Just Consider CPU Bound Similar to FCFS with Time Quantum Processes with Preemptive mode Suppose Time Quantum → 3 units of time Processes AT BT P1 0 8 5 2 0 P3 needs to move to the ready queue P2 5 2 0 P3 1 7 4 1 0 P4 6 3 0 P5 8 5 2 Ready Queue P1 P3 P1 P2 P4 P3 P5 P1 P3 P5 P1 P3 P1 P2 P4 P3 P5 P1 P3 P5 0 3 6 9 11 14 17 20 22 23 25 Gantt Chart Operating System Concepts – 9th Edition 6.46 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) In this example, Used in Time Sharing Systems Just Consider CPU Bound Similar to FCFS with Time Quantum Processes with Preemptive mode Suppose Time Quantum → 3 units of time Processes AT BT CT TAT WT RT P1 0 8 5 2 0 22 22 14 0 P2 5 2 0 11 6 4 4 P3 1 7 4 1 0 23 22 15 2 P4 6 3 0 14 8 5 5 P5 8 5 2 25 17 12 9 Ready Queue P3 needs to move to the ready queue P1 P3 P1 P2 P4 P3 P5 P1 P3 P5 P1 P3 P1 P2 P4 P3 P5 P1 P3 P5 0 3 6 9 11 14 17 20 22 23 25 Gantt Chart Operating System Concepts – 9th Edition 6.47 Silberschatz, Galvin and Gagne ©2013  Example of RR with Time Quantum = 4 Process Burst Time P1 24 P2 3 P3 3 The Gantt chart is: P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 14 18 22 26 30 Typically, higher average turnaround than SJF, but better response q should be large compared to context switch time q usually 10ms to 100ms, context switch < 10 usec Operating System Concepts – 9th Edition 6.48 Silberschatz, Galvin and Gagne ©2013  Time Quantum and Context Switch Time Operating System Concepts – 9th Edition 6.49 Silberschatz, Galvin and Gagne ©2013  Turnaround Time Varies With The Time Quantum 80% of CPU bursts should be shorter than q Operating System Concepts – 9th Edition 6.50 Silberschatz, Galvin and Gagne ©2013  Round Robin (RR) Advantages: Each process is served by the CPU for a fixed time quantum, so all processes are given the same priority. Starvation doesn't occur because for each round robin cycle, every process is given a fixed time to execute. No process is left behind. Disadvantages: The throughput in RR largely depends on the choice of the length of the time quantum. If time quantum is longer than needed, it tends to exhibit the same behavior as FCFS. If time quantum is shorter than needed, the number of times that CPU switches from one process to another process, increases. This leads to decrease in CPU efficiency. Operating System Concepts – 9th Edition 6.51 Silberschatz, Galvin and Gagne ©2013 Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013