CPU SchedulingAnnouncementsReview: ThreadsReview ThreadsGoals for TodaySchedulersProcess SchedulingWhen does scheduler run?Process ModelPresidential debates in 2 weeksScheduling Evaluation Metrics“The perfect CPU scheduler”Problem CasesScheduling Algorithms FCFSConvoy EffectScheduling Algorithms LIFOProblemScheduling Algorithms: SJFScheduling Algorithms SRTFSlide 20Prediction of the Length of the Next CPU BurstExamples of Exponential AveragingPriority SchedulingRound RobinRR with Time Quantum = 20Turnaround Time w/ Time QuantaRR: Choice of Time QuantumScheduling AlgorithmsMultilevel Queue SchedulingSlide 30Multilevel Feedback QueuesA Multi-level SystemMultiple-Processor SchedulingNUMA and CPU SchedulingMulticore ProcessorsMultithreaded Multicore SystemThread SchedulingReal-time SchedulingOperating System ExamplesSolaris Dispatch TableSolaris SchedulingWindows XP PrioritiesLinux SchedulingPriorities and Time-slice lengthList of Tasks Indexed According to PrioritiesSummaryCPU SchedulingAnnouncements•CS 4410 was due two days ago!•CS 4411 projects due next Wednesday, September 17th•Everyone should have access to CMS (http://cms3.csuglab.cornell.edu)–Check and contact me ([email protected]) or Bill Hogan ([email protected]) today if you do not have access to CMS•Also, everyone should have CSUGLab account–Contact Bill or I if you do notReview: Threads•Each thread has its own PC, registers, and stack pointer•But shares code, data, accounting info (address space)•Pthreads (POSIX - “Portable Operating System Interface for uniX)–A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization–API specifies behavior of the thread library, implementation is up to development of the library–Common in UNIX operating systems (Solaris, Linux, Mac OS X)•Windows XP Threads–Implements the one-to-one mapping–Each thread contains•A thread id•Register set•Separate user and kernel stacks•Private data storage area–The register set, stacks, and private storage area are known as the context of the threadsReview Threads•Linux Threads–Linux refers to them as tasks rather than threads–Thread creation is done through clone() system call–clone() allows a child task to share the address space of the parent task (process)•Java Threads–Java threads are managed by the JVM–Java threads may be created by:•Extending Thread class•Implementing the Runnable interfaceGoals for Today•CPU Schedulers•Scheduling Algorithms•Algorithm Evaluation Metrics•Algorithm details•Thread Scheduling–Multiple-Processor Scheduling–Real-Time 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 (aka swapper)–Reduce multiprogramming or memory consumptionProcess Scheduling•“process” and “thread” used interchangeably•Which process to run next•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•process yields•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 multiplyemacsemacsPresidential debates in 2 weeks•Why watch?–Want to see what hype is about–Very entertaining–See either first woman elected VP or first African-american elected president•What does the presidential debates have to do with scheduling?!–Also, want to watch Football, 24 reruns, Law & Order, etc–But, have to finish Project and Homework!–What criteria to use to schedule events?Scheduling Evaluation Metrics•Many quantitative criteria for evaluating sched 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•Priority Inversion: 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