CPU SCHEDULING “WY ———— ee The scheduling done by CPU is the basis of multiprogrammed operating systems. Scheduling refers to a set of policies and mechanisms built into the operating system that govern the order in which the work to be done by a computer system. A scheduler is an operating system module that selects the next jobs to be admitted into the system and the next process to run. The primary objective of scheduling is to optimize system performance in accordance with the criteria deemed most important by the system designers. In this section we examine that what is scheduling, when to schedule and how do we perform scheduling ? We begin by describing the roles of these different types of schedulers encountered in an operating system. Then we describe the objectives and criteria of scheduling. Finally we describe various scheduling disciplines. 4.1| TYPES OF SCHEDULERS Generally, there are three types of schedulers, which may coexist in a complex operating system: 2 Long term scheduler > Medium term scheduler > Short term scheduler. Fig. 4.1 shows the possible traversal paths of jobs and programs through the components and queues, in a computer system. As shown in figure 4.1 a submitted batch job joins the hatch queue while waiting tot ‘processed by the long term scheduler. Once, scheduled for execution, processes spawned by the batch job, enter the ready queue to await the processor allocation bY the short term scheduler. After becoming suspended in waiting queue, the runnits process may be removed fram memory and swapped out to secondary storage. ‘Such processes are subsequently admitted to main memory by the medium term scheduler” order to be consider ion by the termj Modiantorm schodulor Walling & Long torm ‘swapped out}, schedulor quouo Ud Short torn Batch ‘Schadulor jobs_[ Batch ou it A.) ay Interactive asl Watting ams progr quouo Fig. 4.1 Scheduler opJECTIVES OF SCHEDULING 4 are many objectives that must be considered in the design of scheduling discipline qhere uch as: i) Fairness: Fairness can be reflected by treating all the processes same and no (a process should suffer indefinite postponement. (i Throughput: It must attempt to service the largest possible number of processes per unit time. (ii) Predictable: A given job should run in about the same amount of time and at the same cost irrespective of the load on the system. (i Overhead: A certain portion of system resources invested as overhead can greatly improve overall performance of the system. (4 Resources: Scheduling mechanism should keep the resources of the system busy. (0) Indefinite Postponement: Avoiding indefinite postponement of any process so that each and every process is executed in a certain amount of time. (vi) Priorities: Scheduling mechanism should favour the high priority processes. SCHEDULING CRITERIA taty criteria have FF Cleristics used © best algorith; 'C ss, ?U Utilization eh en it gh KeeP the CPU as busy as possible. It may range from 0 to 100%. In a real, ‘ould range from 40 — 90% for lightly loaded and heavily loaded systems. been suggested for comparison of CPU scheduling algorithms. The for comparison can make a substantial difference in the determination m. The criteria includes the following: Wovehput sti te'gk lng prone R°ASUre of work in terms of number of processes completed per unit time. For "be 19 Se this rate may be_1 process per hour; for short transactions, throughput ~ Process per second.SS a. t i 58 nt in wot to ge ound TIME iods SPC Vi fle, of time ae nd eer pletion of job ol into memory, Waiting in y, o i = e of submission of jo} tis the sum oe, executing 7 ‘urn around ate quew time nite trae Ating fect the @ hi i s not aft articular system. It affert ®t: ret el ing 2 ort ne are ones Oe a queue. Waiting times 8 jo because they iting in : or Ss f time that @ ae in ready queue: ds the amount o ting i jods gum of time-perno ; . ; : not the time ‘aken to out; rut « Response Time ponding, mil It is the amoun! response. 4| TYPES OF SCHEDULING ptive scheduling schemes: ; : take place under the following four circumstances; g state to the waiting state (for exam S| tof time, it takes to start res Nonpreemptive and preemy ‘CPU scheduling decisions may f () When a process switches from the runnin, input/output wait). (i) When a process switches from the running state to the ready state (for exampk when an interrupt occurs). (i) When a process switches from the waiting state to the ready state (for exampk completion of input/output). (iy) When a process terminates. Inci i i — Place only under (9 and (iv) Gein selected for execution. When scheduling tak However, in circumstances (i) and aa ‘ay the scheduling scheme is Nonpreemptire au i i il ae, . Process may or may not be selected, f i) there is a choice in terms of scheduling ie! Preemptive. for its execution, this type of scheduling is alld Under nonpreempti tive scheduli Process keeps ey eouling, once thi ‘ i¢ Waiting ae i = ay antl it releases the ae has been allocated to a ‘process, then is ecaton ee APOE start gehe” Y terminating or by switche! oe ny interruption ao ted until the Process j ‘on under nonpreemptive schedulit oF timer” needed for wrcemption, ‘Asa Gg dene keeution completes its burst we aan i ‘Mptive ; not : ; wi completion of baPtive sched, ae Scheduling, require any special hard\ in Whose priority ie oo time of fe, execution her than riage 88 and any a Process is preempted before w West arrive Process 1 Process may starts its execu” in th e system, it ibe in thy. * Jor Ls, . i aes : ; ed to the Nee term med; ection is teat 'y any of the above des ee _ typ cri o 4 e of Short temanng sath59 —__CPU Scheduling CPU scheduling deals with the eve is lo be allocated the algorithm that exist: freblem of decicing which of the process in arene CPU. Now we describe neveral of the many CPU scheduling 4.5.1 First-Come, First-Served (ECF: ‘S) Scheduling Algorithm FCFS is the simplest of all sche (ting algorithms. ‘The key concept of this algorithm is ou Culing, aly ! Y pt of this raltocated the CPU in the order in whch ae Processes arrive.” That is the process that requests the CPU first is allocated the cry first. The implementation of FCFS policy is managed with a FIFO (First-in-firat out qe its PCB is linked onto the tail of the process at the head of the que The code for FCFS scheduling When a process enters the ready queue, queue, When the © We. The running proc is simple FCFS Scheduling Algorithm is Non. Once the CPU has been given toa the CPU cither by terminating or by re for Batch operating system. The aver, especially if requests of short CPU b for time-sharing systems where it j PU is free, it is allocated to the s is then removed from the queue. to write and understand. Preemptive keeps the CPU until it releases ‘The FCFS algorithm is suitable tems * important that each user should get the CPU for an equal amount of arrival time, > fe Pe —! oy Ready Queen Fig. 4.2 FCFS Scheduling EXAI MPLE 4.1 Consider the fol TRE Set of processes having their burst time mentioned in milliseconds. CPU-burst time indicates that for hew muck time, the process needs the CPU. Process Burst Time (ms) Pp 20 P, 7 P, 5 Calculate the average waiting time if the processes arrive in the order of; () Py, Py, Py (i) Py, Py, Py (tt) P,, P,P, (iv) Pay Poy Py Solution: ( If processes arrive in order P,, P,, P; let us assume at 0 ms, 1 ms and 2 ms Tespectively, wait Process Burst time Arrival time Py 20 0 P, 7 1 Py 5 2 Since, FCFS is a non-preemptive algorithm; so when a process execution is started it is not preempted until its execution is completed, The Gantt chart will be: a Py Pa 160 Operating Systems Waiting time for process Py = 0 ms Waiting time for process 2,” 20 ms ~1ims = 19 ms Waiting time for process P,* 27 ms = 2 ms © 25 ms 0419425 Average waiting time = 4 ma © 14.67 ms. Consider a case, if the processes P,, 2, and Py arrives at the same time say at 0 ms in the system, in the order of P,, P,, Py then: Waiting time for process P, = 0 ms Waiting time for process P, = 20 ms Waiting time for process P, = 27 ms 0+20427 47 3 ms = —> ms = 15.67 ms. (i Ifthe processes P,, P,, P, arrives at the same time say at 0 ms in the system and in the order of P,, P,, P, then the Gantt chart will be ». Average waiting time = Pe Py Py oO 7 12 32 Waiting time for process P, = 0 ms Waiting time for process P, = 7 ms Waiting time for process P, = 12 ms O+7412 19 —j ms = J ms = 6.33 ms. (ii) If the three processes P,, P, and P, arrives at the same time say 2 ms in the order of P,, P,, P, then the Gantt chart will be Average waiting time = Ps Py i 2 7 27 32 Waiting time for process P, = (7-2) ms = 5 ms Waiting time for process P, = (27 - 2) ms = 25 ms Waiting time for process P, = 0 ms 5+25+0 320 ge 10 SS -—T ms = > ms = 10 ms, ime (iv) If the processes arrive in the order of P,, P,, P, at the same time say 0 ms then the Gantt chart will be ate ©. Average waiting time = Py Py P, Waiting time for process P, = 12 ms Waiting time for process P, = 5 msCPU Scheduling Wailing time for process Py = 0 ing ‘ 124540 17 +. Average waiting time : ma = Fins = 5.67 ms. Hence, from the example it in clear that if Processes of short burst time arrives firstly then the average waiting time is minimum. So, in FOFS scheduling order of proceagen plays am: average waiting time, ajor role in the measurement of 4.5.2 Shortest-Job-First (SJFI Scheduling Algorithm sim ancorate SIF) scheduling isa different approach to Cpu scheduling. This algorithm associates with each proceas the length of the latter's next CPU burst. When the CPU is available, it is assigned to the process that hae din smallest next CPU burst. If the two proces: have the same length of CPU burst then FCF: scheduling algorithms is followed. As scheduling is done by examin, st of The key concept of this algorithm is burst time”. This algorithm is considered fhe process with least CPU — minimum average waiting time as a result. to be an optimal algorithm, as it gives the controls the relative weight of rece then a formula called exponent: ; and t, stores the past history in prediction => recent history has no effect (current conditions are assumed to be transient) ifa= 0, then t,,, = 1, fa~ 1, then t,,,=t,=9 in this case only the most recent CPU burst matters. Ha 1/2 then recent and past history are equally weighted. The SJF algorithm. may be either preemptive or non-preemptive The choice arises when a new process arrives in the ready queue while a previous Process is executing, i i i the execution A preemptive 8JF will preempt this currently executing process and starts i of newly entered Process while non-preemptive SJF will allow the currently executing Process to complete its burst time without any interruption in its execution. Preemptive SJF scheduling is sometimes called Shortest-Remaining-Time-First (SRTF) Scheduling,a Operating Systems IS 2a Process Arrival time Burst time Pr, 7 . Py a 7 ’ : - 3 8 Py hedulit ti) Non Calculate Average waiting time in (i) preemptive SJF scheduling and (ii) Non. Preemptive SUF scheduling. Solution: (i) Preemptive SUF: IP} Pe Pa Py Ps o123 5 10 17 26 PP, At t= 0 ms only one process P, is in the system, whose burst time is 8 ms; starts jt execution. After I ms, ie, at t= 1, new process P, (burst time = 4 ms) arrives in the ready queue. =: Its burst time (4 ms) is less than the remaining burst time of P, (7 ms) so p, ig preempted and execution of P, is started. Again after one ms ie., at t= 2, a new process p. arrive in ready queue but its burst time-(9 ms) is larger then the remaining burst time of currently executing process (3 ms). So P, is not preempted and it continuous its execution, Again after one ms at f= 3, new process P, (burst time = 5 ms) is arrived but again for the same reason P, is not preempted until its execution is completed. At t~ 5 all the processes have arrive in the system. Now the processes are executed in SJF scheduling manner resulting as following: Waiting time for process P, = 0 ms + (10 - 1} ms = 9 ms Waiting time for process P, = 1 ms ~ 1 ms = 0 ms Waiting time for process P, = 17 ms - 2 ms = 15 ms Waiting time for process P, = 5 ms ~ 3 ms = 2 ms +0+15+2 =. Average waiting time aerst2 ms 8 65 A = 7 765ms. Ans. (i) Non-Preemptive SUF: , Pa Pe Ps 0 P, P,P, 8 12 7 26 At t= 0 ms only one process is in the ready queue P, (burst time = 8 ms). Since in non- preemptive scheme when a process starts its execution then it is not preempted unless its burst time is completed. So, even P,, P, and P, are arrived one after the another in the: duration of one ms P, continues its execution upto 8 ms, After this processes are executed in the accordance of SJF scheduling resulting as following: Persone Waiting time for process P, = 0 ms eS Waiting time for process P, = (8-1) ms = 7 ms Waiting time for process P, = (17 - 2) ms = 15 ms § a Waiting time for process P, = (12-3) ms = 9 ms2 _CPU Scheduling 68 Average wai 4.5.3 Priority Scheduling Apriority is associated with each the highest priority, Equat-priority p, An SJF is simply a priority algorit next CPU burst. The larger the CPU b, Priorities are generally some fixed ers such as 0 to 7. However. no general agreement on whether O is the hi low numbers to represent low priori ty; others use low numbers to represent higher Priority. This difference can lead to confusion, i In our text we use low numbers to Tepresent high priority. EXAMPLE 4.3 Consider the following set of processes, 0 » assumed to have arrived at time 0, in the order P,, Pay... Ps » with the length of the CPU-burst thne given in milliseconds: Process Burst time Priority Pp 10 3 P, a 1 P, 2 4 P, 1 5 Ps 5 2 Using priority scheduling calculate average waiting time. toe ae, Using Priority scheduling, we would schedule the given processes according to the following Gantt chart: Py Py | Py 16° (18 19 o4 6 Waiting time for process P, = 6 ms Waiting time for process P, = 0 ms Waiting time for process P, = 16 ms Waiting time for process P, = 18 ms Waiting time for process P, = 1 ms 6+0+16+18+1 Avg. waiting time = S ms = 8.2 ms, Priority Schedulin, When a proces: Tuning process. th A Preemptive priority scheduling algorithm will preempt the CPU if the priority of new : yack eH tly running in ® atived process is higher than the priority of the process current he system. a nan preeniaage ¢ priority scheduling algorithm will simply put the new € is Either Preemptive or Non-preemptive S$ arrives at ready queue, its priority is compared with the currently SnOperating Systems 64 __ Operating Sy i sseoetiaumree _— y queue locs not preempt the execution of of the ready queue d ; cure, Pree at head of Wht ention even when the priority of newly arrived process is higher Pha priority inthe process currently running in the system, than priority of EXAMPLE 4.4 Preemptive Priority Scheduling Process Burst time Priority Arrival time P, 10 3 o Pr, 5 Es 1 P, 2 1 2 tution: Initially we have a process P; (burst time = 10 ms) in the system, Ton thems. at {= Lnew process P. (5 ms) and priority 2 arrives in the systems. Since ite prionty is higher than the priority of P,(3), So Pi is preempted and P, started its execution” Aeun at 2, Py (priority ~ 1) arrives So P, is preempt for the same reason and Pris Again ot (nil Hs execution is completed, Since P, has got highest priority among the ses. After the completion of P;, remaining part of process P, starts its executio; riority then P,. So, the Gantt chart is as: n three proce: as it is got higher p Py} Pe| Ps Pe Py o12 4 8 “ Waiting time for process P, = 0 ms + (8~ 1) ms = 7 ms Waiting time for process P, = (4-2) ms = 2 ms Waiting time for process P, = (2-2) ms = 0 ms T+24+0 2 Average w. a ae ms = 3 ms. Priorities may be assigned by the user or by the operating system, depending upon the importance of the process. A natural question that arrises here is: What will happen if the two processes having same priorities ? The tie will be broken by comparing their CPU burst time. i rter burst time is firsth executed and if there may be a situation that two processes having same burst time then they are executed on the basis of FCFS scheduling. ‘The problem with priority scheduling algorithm arises when it becomes the biggest cause of starvation of a process. If a process is in ready state but its execution is almost always preempted, due to the arrival of higher priority processes, it will starve for its execution. Therefore, a mechanism called “ageing” has to be built into the system so that alinost every process should get the CPU in a fixed interval of time. This can be done by increasing the priority of a low-priority process after a fixed interval of time, so that one moment of time it becomes a high-priority job as compared to others and thus, finally gets CPU for its execution. 4.5.4 Round-Robin Scheduling Algorithm ‘The Round-Robin (RR) scheduling algorithm is desi ime-sharing oun igned especially for time-sharing 5} It is similar to FCFS scheduling algorithm, but preemption is added to switch'b processes. A small unit of time called a time quantu: ime-slice) is, define range is kept between 10 to 100 ms. in. (or time-slice) ieageny stCPU Scheduling 65 port-term) goes around the ready queue, (rerval of upto 1 time quantum. Toimplement RR scheduling, we keep the reatly queue as a FIFO Queue of the processes. New processes are added to the tail ofthe ready queue The crn scheduler picks the first process from the ready qucue, sets a timer to int, Trupt after 1 time quantum, and dispatches the process. One of the two things may happen. The process time quantum. In this case, the en Ready Queue Fig. 4.3. RR scheduling If there are N processes in the ready Process gets 1/N of CPU time in hunks of at most ‘t’ times units. Each process must wait no longer than (N quantum. queue and the time quantum is ‘t, then each ~ 1) * t time units until its next time EXAMPLE 4.5 Consider the following set of processes that arrives at time O ms. Process Burst Time P, 20 P, 3 Ps; 4 Iie use time quantum of 4 ms then calculate the average waiting time using R-R scheduling. eva [er [eevee | eae [iene] cee 4 7 W 15 19 23 27 o- Solution: According to R-R scheduling processes are executed in FCFS order. So, firstly Fi (burst time = 20 ms) is executed but after 4 ms it is preempted and new process Py ‘urst time = 3 ms) starts its execution whose execution is commpleted can Ee ‘time uantum then next process P, (burst time = 4 ms) starts its execution and finally remaining Part of P, gets executed with time quantum of 4 ms. Waiting time of process P, = 0 ms + (11 - 4) ms = 7ms Waiting time for process P, = 4 ms aiting time for process P, = 7 ms T+447 Average waiting time = —3-— ms = 6 ms.66 Operating Systems 4.5.5 Multilevel Queue Scheduling Algorithm ‘The other types of scheduling algorithims has been created for situations in which processes are easily classified into different groups. ; : ‘A Multilevel Queuc Scheduling (MQS) algorith 1m partitions the ready queue into severa] separate qui he processes are permanently assigned to one queue, generally based dn Some property of the process, such as memory size, process priority or process type, Bach queue has its own scheduling algorithm. For example, different queues can be used for foreground and b: und processes. The foreground queue might be schedule ‘an RR scheduling algorithm, whereas background queues are scheduled by FCFS ‘scheduling algorithm. ein addition, there must be scheduling among the queues, and is generally implemented as fixed priority preemptive scheduling. For example, the foreground queue may have absolute priority over the background queue. Let us consider an example of a multiliver queue scheduling algorithm with 5 queues : ()) System processes (ii) Interactive processes (iii) Interactive editing processes (iv) Batch processes (v) Student processes Highest Priority ‘System Processes [_- eee Interactive Processes |__. | interactive Exiting Processes = -——~ —| Batch Processes — fae Student Processes }—~ Highest Priority Fig. 4.4 MQS algorithm Each queue has absolute priority over lower priority queues. No process in the. batch queue, say, could run unless the queues for system processes, interactive processes; interactive editing processes were all empty. If an interactive editing process ente! eae the ready queue which a batch process is running then the batch process would be preempted. 4.5.6 Multilevel Feedback Queue Scheduling ete A scheduling mechanism is expected to fre O favour short jobsCPU Beheduling, u favour lnpat/outpat bound Job1 10 net yood input/output device utilization. u Determine the natite of job quickly and achedule it ac ordingly. U MEQH provides and atructuey.hat agpomplishen thege.goals, Anew pricenn entora the quicuing networleat the brick of the top queue. It moves through the FIFO Queue untiLit gets the CPU. u Ifthe Job completen or relinquiahen the completion of Kome event, tHe CVU to wat for input/output completion or Job leaven the queuing network, the process voluntarily relinquishes the CPU, the 1eof next lower level queue, ‘d when it reaches the OI the quanti expiren before procenn in placed at the bn ‘The process in next nerviee head of the queue of the first queue in empty, © An tong an the procens uses the full move to the back of the next lower quewc, ‘Bn many multilevel feedback queue g {t moven to cach lower-level queue be een in the queuing networ the CPU, G Mululevel feedback queues are i al for separating processes into categories based on their need for the CPU, In a time sharing system, cach time a process leaves the queuing, network, it can be “stamped” with the identity of the lowest level queue in which it resides. When the process reenters the queuing network, it can be sent directly to the queue in which it last completed operation Here, the ucheduler is using the heuristic that the recent past behaviour of a process is & good indientor of its near future behaviour. So, a CPU bound process returning to the aucuing network is not put into the higher level queues, where it would interne with service to high priority short processes OR input/output bound processes. duantum provided at cach level, it continues to hieo) Py Py Py P, —+ [cru]. Proomption P,P, P, —~ [cru] —- Proomption Proomption al a Lovoln ——s PF, Py Pp P, —+ [cru] —- A Fig. 4.5 Multiple Feedback Queue.Operating Systems 68 eee eee EXAMPLE 4.6 Consider the set of processes given in the table and the following scheduling algorithm: {i) Shortest Job First (SUF) (ii) Shortest Remaining Job First (SRIF) . | Process id ‘Arrival time | Executive time } A ° 7 B 1 5 c 2 3 D 6 2 E 12 3 irthere is a tie within the processes, the tie is broken in the favowe of the oldest process. Draw the Gantt chart and find the average waiting time and fur, around time for the two Rigorithms. Comment on your result which one is better and why? Solution: (i) For SUF the Gantt chart will be: A. pic E B | o BoD 7 9 1215 20 Waiting time for process id A= 0 Waiting time for process id B= (15-1) = 14 Waiting time for process id C= (9-2) =7 Waiting time for process id D= (7-6) = 1 Waiting time for process id B= (12 - 12)=0 Average waiting time = ore telse =44 unit. Ans. Turn around time for process id A=7-O=7 ~ Turn around time for process id B= 20-1 = 19 Tum around time for process id C= 12-2 = 10 Turn around time for process id D= 9-6 = 3 Tum around time for process id B= 15-12 =3 74194104343 Average turn around time = 5 = =8.4 unit. Ans.