11CSE 380Computer Operating SystemsInstructor: Insup Lee & Dianna XuUniversity of Pennsylvania, Fall 2003Lecture Note 3: CPU Scheduling2CPU SCHEDULINGq How can OS schedule the allocation of CPU cycles toprocesses/threads to achieve “good performance”?q Overview of topicsß Issues in schedulingß Basic scheduling algorithms• First-come First-served• Round Robin• Shortest Job First• Priority basedß Scheduling in Unixß Real-time scheduling (Priority Inheritance)23Scheduling Issuesq Application Profile:ß A program alternates between CPU usage and I/Oß Relevant question for scheduling: is a program compute-bound (mostly CPU usage) or I/O-bound (mostly I/O wait)q Multi-level scheduling (e.g., 2-level in Unix)ß Swapper decides which processes should reside in memoryß Scheduler decides which ready process gets the CPU nextq When to scheduleß When a process is createdß When a process terminatesß When a process issues a blocking call (I/O, semaphores)ß On a clock interruptß On I/O interrupt (e.g., disk transfer finished, mouse click)ß System calls for IPC (e.g., up on semaphore, signal, etc.)4Scheduling Issuesq Is preemption allowed?ß Nonpreemptive scheduler does not use clock interrupts to stop aprocessq What should be optimized?ß CPU utilization: Fraction of time CPU is in useß Throughput: Average number of jobs completed per time unitß Turnaround Time: Average time between job submission andcompletionß Waiting Time: Average amount of time a process is ready butwaitingß Response Time: in interactive systems, time until the systemresponds to a commandß Response Ratio: (Turnaround Time)/(Execution Time) -- longjobs should wait longer35Scheduling Issuesq Different applications require different optimization criteriaß Batch systems (throughput, turnaround time)ß Interactive system (response time, fairness, user expectation)ß Real-time systems (meeting deadlines)q Overhead of schedulingß Context switching is expensive (minimize context switches)ß Data structures and book-keeping used by schedulerq What’s being scheduled?ß Processes in Unix, but Threads in Linux or Solaris6Basic Scheduling Algorithm: FCFSq FCFS - First-Come, First-Servedß Non-preemptiveß Ready queue is a FIFO queueß Jobs arriving are placed at the end of queueß Dispatcher selects first job in queue and this job runs tocompletion of CPU burstq Advantages: simple, low overheadq Disadvantages: inappropriate for interactive systems,large fluctuations in average turnaround time arepossible.47Example of FCFSq Workload (Batch system)Job 1: 24 units, Job 2: 3 units, Job 3: 3 unitsq FCFS schedule: | Job 1 | Job 2 | Job 3 | 0 24 27 30q Total waiting time: 0 + 24 + 27 = 51q Average waiting time: 51/3 = 17q Total turnaround time: 24 + 27 + 30 = 81q Average turnaround time: 81/3 = 278SJF - Shortest Job FirstqNon-preemptiveqReady queue treated as a priority queue based onsmallest CPU-time requirementß arriving jobs inserted at proper position in queueß dispatcher selects shortest job (1st in queue) and runs to completionqAdvantages: provably optimal w.r.t. average turnaroundtimeqDisadvantages: in general, cannot be implemented. Also,starvation possible !qCan do it approximately: use exponential averaging topredict length of next CPU burst==> pick shortest predicted burst next!59Example of SJFq Workload (Batch system)Job 1: 24 units, Job 2: 3 units, Job 3: 3 unitsq SJF schedule: | Job 2 | Job 3 | Job 1 | 0 3 6 30q Total waiting time: 6 + 0 + 3 = 9q Average waiting time: 3q Total turnaround time: 30 + 3 + 6 = 39q Average turnaround time: 39/3 = 13q SJF always gives minimum waiting time and turnaroundtime10Exponential Averagingt n+1 = a tn + (1 - a) ) tnqtn+1 : predicted length of next CPU burstqtn : actual length of last CPU burstqtn : previous predictionqa = 0 implies make no use of recent history(tn+1 = tn)qa = 1 implies tn+1 = tn (past prediction not used).qa = 1/2 implies weighted (older bursts get less andless weight).611 RR - Round Robinq Preemptive version of FCFSq Treat ready queue as circularß arriving jobs are placed at endß dispatcher selects first job in queue and runs untilcompletion of CPU burst, or until time quantum expiresß if quantum expires, job is again placed at end12Example of RRq Workload (Batch system)Job 1: 24 units, Job 2: 3 units, Job 3: 3 unitsq RR schedule with time quantum=3: | Job 1 | Job 2 | Job 3 | Job 1 | 0 3 6 9 30q Total waiting time: 6 + 3 + 6 = 15q Average waiting time: 5q Total turnaround time: 30 + 6 + 9 = 45q Average turnaround time: 15q RR gives intermediate wait and turnaround time(compared to SJF and FCFS)713Properties of RRq Advantages: simple, low overhead, works for interactivesystemsq Disadvantages: if quantum is too small, too much timewasted in context switching; if too large (i.e. longer thanmean CPU burst), approaches FCFS.q Typical value: 20 – 40 msecq Rule of thumb: Choose quantum so that large majority(80 – 90%) of jobs finish CPU burst in one quantumq RR makes the assumption that all processes are equallyimportant14 HPF - Highest Priority Firstq General class of algorithms ==> priority schedulingq Each job assigned a priority which may changedynamicallyq May be preemptive or non-preemptiveq Key Design Issue: how to compute priorities?815Multi-Level Feedback (FB)q Each priority level has a ready queue, and a time quantumq process enters highest priority queue initially, and (next) lower queue witheach timer interrupt (penalized for long CPU usage)q bottom queue is standard Round Robinq process in a given queue are not scheduled until all higher queues areempty16FB Discussionq I/O-bound processes tend to congregate in higher-levelqueues. (Why?)q This implies greater device utilizationq CPU-bound processes will sink deeper(lower) into thequeues.q large quantum occasionally versus small quanta oftenq Quantum in top queue should be large enough to satisfymajority of I/O-bound processesq can assign a process a lower priority by starting it at a lower-level queueq can raise priority by moving process to a higher queue, thuscan use in conjunction with agingq to adjust priority of a process changing from CPU-bound toI/O-bound, can move process to a higher queue each time itvoluntarily relinquishes CPU.917UNIX Scheduler18Process Scheduling in Unixq Based on multi-level feedback queuesq Priorities range from -64 to 63 (lower number