Unformatted text preview:

CPU SchedulingSchedulersProcess SchedulingWhen does scheduler run?Process ModelScheduling Evaluation Metrics“The perfect CPU scheduler”Problem CasesScheduling Algorithms FCFSConvoy EffectScheduling Algorithms LIFOProblemScheduling Algorithms: SJFScheduling Algorithms SRTFPowerPoint PresentationPriority SchedulingRound RobinRR with Time Quantum = 20Turnaround Time w/ Time QuantaRR: Choice of Time QuantumScheduling AlgorithmsMultilevel Queue SchedulingSlide 23Multilevel Feedback QueuesA Multi-level SystemThread SchedulingReal-time SchedulingPostscriptSlide 29CPU SchedulingSchedulers•Process migrates among several queues–Device queue, job queue, ready queue•Scheduler selects a process to run from these queues•Long-term scheduler: –load a job in memory–Runs infrequently•Short-term scheduler:–Select ready process to run on CPU–Should be fast•Middle-term scheduler–Reduce multiprogramming or memory consumptionProcess Scheduling•“process” and “thread” used interchangeably•Many processes in “ready” state•Which ready process to pick to run on the CPU?–0 ready processes: run idle loop–1 ready process: easy!–> 1 ready process: what to do?New Ready Running ExitWaitingWhen does scheduler run?•Non-preemptive minimum–Process runs until voluntarily relinquish CPU•process blocks on an event (e.g., I/O or synchronization)•process terminates•Preemptive minimum –All of the above, plus:•Event completes: process moves from blocked to ready•Timer interrupts•Implementation: process can be interrupted in favor of anotherNewReadyRunningExitWaitingProcess Model•Process alternates between CPU and I/O bursts–CPU-bound jobs: Long CPU bursts–I/O-bound: Short CPU bursts–I/O burst = process idle, switch to another “for free”–Problem: don’t know job’s type before runningMatrix multiplyemacsemacsScheduling Evaluation Metrics•Many quantitative criteria for evaluating scheduler algorithm:–CPU utilization: percentage of time the CPU is not idle–Throughput: completed processes per time unit–Turnaround time: submission to completion–Waiting time: time spent on the ready queue–Response time: response latency–Predictability: variance in any of these measures•The right metric depends on the context• An underlying assumption:–“response time” most important for interactive jobs (I/O bound)“The perfect CPU scheduler”•Minimize latency: response or job completion time •Maximize throughput: Maximize jobs / time. •Maximize utilization: keep I/O devices busy. –Recurring theme with OS scheduling•Fairness: everyone makes progress, no one starvesProblem Cases•Blindness about job types–I/O goes idle•Optimization involves favoring jobs of type “A” over “B”.–Lots of A’s? B’s starve•Interactive process trapped behind others. –Response time sucks for no reason•Priorities: A depends on B. A’s priority > B’s. –B never runsScheduling Algorithms FCFS•First-come First-served (FCFS) (FIFO)–Jobs are scheduled in order of arrival–Non-preemptive•Problem:–Average waiting time depends on arrival order•Advantage: really simple!timeP1P2P30 16 20 24P1P2P30 4 8 24Convoy Effect•A CPU bound job will hold CPU until done, –or it causes an I/O burst •rare occurrence, since the thread is CPU-bound long periods where no I/O requests issued, and CPU held–Result: poor I/O device utilization•Example: one CPU bound job, many I/O bound•CPU bound runs (I/O devices idle)•CPU bound blocks•I/O bound job(s) run, quickly block on I/O•CPU bound runs again•I/O completes•CPU bound still runs while I/O devices idle (continues…)–Simple hack: run process whose I/O completed?•What is a potential problem?Scheduling Algorithms LIFO•Last-In First-out (LIFO)–Newly arrived jobs are placed at head of ready queue–Improves response time for newly created threads•Problem:–May lead to starvation – early processes may never get CPUProblem•You work as a short-order cook–Customers come in and specify which dish they want–Each dish takes a different amount of time to prepare•Your goal: –minimize average time the customers wait for their food•What strategy would you use ?–Note: most restaurants use FCFS.Scheduling Algorithms: SJF•Shortest Job First (SJF)–Choose the job with the shortest next CPU burst–Provably optimal for minimizing average waiting time •Problem:–Impossible to know the length of the next CPU burstP1P2P30 15 21 24P1P2P30 3 9 24P2P3Scheduling Algorithms SRTF•SJF can be either preemptive or non-preemptive–New, short job arrives; current process has long time to execute•Preemptive SJF is called shortest remaining time firstP1P2P3062110P1P3P1P2062410 13•Approximate next CPU-burst duration–from the durations of the previous bursts•The past can be a good predictor of the future•No need to remember entire past history•Use exponential average:tn duration of the nth CPU burstn+1 predicted duration of the (n+1)st CPU burst n+1 =  tn + (1- ) nwhere 0    1 determines the weight placed on past behaviorShortest Job First PredictionPriority Scheduling•Priority Scheduling–Choose next job based on priority–For SJF, priority = expected CPU burst–Can be either preemptive or non-preemptive•Problem:–Starvation: jobs can wait indefinitely•Solution to starvation–Age processes: increase priority as a function of waiting timeRound Robin•Round Robin (RR)–Often used for timesharing–Ready queue is treated as a circular queue (FIFO)–Each process is given a time slice called a quantum–It is run for the quantum or until it blocks–RR allocates the CPU uniformly (fairly) across participants. –If average queue length is n, each participant gets 1/nRR with Time Quantum = 20Process Burst TimeP153 P2 17 P368 P4 24•The Gantt chart is: •Higher average turnaround than SJF, •But better response timeP1P2P3P4P1P3P4P1P3P30 20 37 57 77 97 117 121 134 154 162Turnaround Time w/ Time QuantaRR: Choice of Time Quantum•Performance depends on length of the timeslice–Context switching isn’t a free operation.–If timeslice time is set too high •attempting to amortize context switch cost, you get FCFS. •i.e. processes will finish or block before their slice is up anyway–If it’s set too low •you’re spending all of your time context switching between threads.–Timeslice frequently set to


View Full Document

CORNELL CS 4410 - CPU Scheduling

Download CPU Scheduling
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view CPU Scheduling and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view CPU Scheduling 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?