COT 4600 Operating Systems Fall 2009Lecture 25SchedulingExample: an overloaded transaction processing systemScheduling objectivesCPU burstScheduling policiesFirst-Come, First-Served (FCFS)FCFS Scheduling (Cont’d.)Shortest-Job-First (SJF)Example of non-preemptive SJFExample of Shortest-Remaining-Time-First (SRTF) (Preemptive SJF)Round Robin (RR)RR with time slice q = 20Time slice (quantum) and context switch timeTurnaround time function of time quantumSlide Number 17Slide Number 18Priority schedulingPriority inversionEstimating the length of next CPU burstExponential averagingPredicting the length of the next CPU burstMultilevel queueMultilevel Queue SchedulingMultilevel feedback queueExample of a multilevel feedback queue examMultilevel Feedback QueuesUnix schedulerCOT 4600 Operating Systems Fall 2009Dan C. MarinescuOffice: HEC 439 BOffice hours: Tu-Th 3:00-4:00 PM222222Lecture 25 Attention: project phase 4 and HW 6 – due Tuesday November 24 Final exam – Thursday December 10 4-6:50 PM Last time:  Multi-level memories Memory characterization Multilevel memories management using virtual memory Adding multi-level memory management to virtual memory Today: Scheduling Next Time: Network properties (Chapter 7) - available online from the publisher of the textbookScheduling The process of allocating resource e.g., CPU cycles, to threads/processes. Distinguish Policies Mechanisms to implement policies Scheduling problems have evolved in time: Early on: emphasis on CPU scheduling  Now: more interest in transaction processing and I/O optimization Scheduling decisions are made at different levels of abstraction and it is not always easy to mediate.Example: an overloaded transaction processing system Incoming transaction are queued in a buffer which may fill up; The interrupt handler is constantly invoked as dropped requests are re-issued;  The transaction processing thread has no chance to empty the buffer; Solution: when the buffer is full disable the interrupts caused by incoming transactions and allow the transaction processing thread to run.Scheduling objectives Performance metrics: CPU Utilization Î Fraction of time CPU does useful work over total time Throughput Î Number of jobs finished per unit of time Turnaround time Î Time spent by a job in the system Response time Î Time to get the results Waiting time Î Time waiting to start processing All these are random variables Î we are interested in averages!! The objectives - system managers (M) and users (U): Maximize CPU utilization ÎM Maximize throughput Î M Minimize turnaround time Î U Minimize waiting time Î U Minimize response time Î UCPU burst CPU burst Æ the time required by the thread/process to executeScheduling policies First-Come First-Serve (FCFS) Shortest Job First (SJF) Round Robin (RR) Preemptive/non-preemptive schedulingFirst-Come, First-Served (FCFS)Thread Burst TimeP124P23P33 Processes arrive in the order: P1Î P2Î P3 Gantt Chart for the schedule: Waiting time for P1= 0; P2= 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 Convoy effect Îshort process behind long processP1P2P324 27 300FCFS Scheduling (Cont’d.) Now threads arrive in the order: P2Î P3Î P1 Gantt chart: Waiting time for P1 = 6;P2= 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better!!P1P3P263 300Shortest-Job-First (SJF) Use the length of the next CPU burst to schedule the thread/process with the shortest time. SJF is optimal Îminimum average waiting time for a given set of threads/processes Two schemes:  Non-preemptive Î the thread/process cannot be preempted until completes its CPU burst Preemptive Î if a new thread/process arrives with CPU burst length less than remaining time of current executing process, preempt. known as Shortest-Remaining-Time-First (SRTF)Example of non-preemptive SJFThread Arrival Time Burst TimeP10.0 7P22.0 4P34.0 1P45.0 4 SJF (non-preemptive) Average waiting time = (0 + 6 + 3 + 7)/4 = 4P1P3P273 160P48 12Example of Shortest-Remaining-Time-First (SRTF) (Preemptive SJF)Thread Arrival Time Burst TimeP10.0 7P22.0 4P34.0 1P45.0 4 Shortest-Remaining-Time-First Average waiting time = (9 + 1 + 0 +2)/4 = 3P1P3P242110P45 7P2P116Round Robin (RR) Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the thread/process is preempted and added to the end of the ready queue. If there are n threads/processes in the ready queue and the time quantum is q, then each thread/process gets 1/n of the CPU time in chunks of at most q time units at once. No thread/process waits more than (n-1)q time units. Performance q large ⇒ FIFO q small ⇒ q must be large with respect to context switch, otherwise overhead is too highRR with time slice q = 20Thread Burst TimeP153P217P368P424 Typically, higher average turnaround than SJF, but better responseP1P2P3P4P1P3P4P1P3P30 20 37 57 77 97 117 121 134 154 162Time slice (quantum) and context switch timeTurnaround time function of time quantumJob Arrival time Work Start time Finish time Wait timetill startTime in systemA0 3 0 3 0 3B 1 5 3 3 + 5 = 8 3 – 1 = 2 8 – 1 = 7C 3 2 8 8 + 2 = 10 8 – 3 = 5 10 – 3 = 7A0 3 0 3 0 3B 1 5 5 5 + 5 = 10 4 10 – 1 = 9C 3 2 3 3 + 2 = 5 0 5 – 3 = 2A0 3 0 6 0 6 –0 = 6B 1 5 1 10 1 – 1 = 0 10 – 1 = 9C 3 2 5 8 5 –3 = 2 8 –3 = 5Scheduling policyAverage waiting time till the job startedAverage time in systemFCFS 7/3 17/3SJF 4/3 14/3RR 3/3 20/3Priority scheduling Each thread/process has a priority and the one with the highest priority (smallest integer ≡ highest priority) is scheduled next. Preemptive Non-preemptive SJF is a priority scheduling where priority is the predicted next CPU burst time Problem Î Starvation – low priority threads/processes may never execute Solution to starvation Î Aging – as time progresses increase the priority of the thread/process Priority my be computed dynamicallyPriority inversion A lower priority thread/process prevents a higher priority one from running. T3 has the highest priority, T1 has the lowest priority; T1and T3 share a lock. T1acquires the lock, then it is suspended when T3starts. Eventually T3requests the lock and it is suspended waiting for T1to release the lock. T2 has higher