15-410, S’04- 1 -SchedulingMar. 15, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL20a_Scheduling15-410“...Everything old is new again...”15-410, S’04- 2 -SynchronizationCheckpoint 2Checkpoint 2Monday, March 22Watch for detailsFinal Exam list postedFinal Exam list postedYou must notify us of conflicts in a timely fashionToday would be good15-410, S’04- 3 -OutlineChapter 6: SchedulingChapter 6: Scheduling15-410, S’04- 4 -CPU-I/O CycleProcessProcess view: 2 states view: 2 statesRunningWaiting for I/OLife CycleI/O (loading executable), CPU, I/O, CPU, .., CPU (exit())SystemSystem view viewRunning, WaitingRunnable – not enough processors for you right nowRunning Running ⇒⇒ waiting is mostly voluntary waiting is mostly voluntaryHow long do processes choose to run before waiting?15-410, S’04- 5 -CPU Burst LengthsOverallOverallExponential fall-off in CPU burst length0 5 10 15 20 25 30010203040506070809010015-410, S’04- 6 -CPU Burst Lengths“CPU-bound” program“CPU-bound” programBatch jobLong CPU bursts0 5 10 15 20 25 30010203040506070809010015-410, S’04- 7 -CPU Burst Lengths“ I/O-bound” program“ I/O-bound” programCopy, Data acquisition, ...Tiny CPU bursts between system calls0 5 10 15 20 25 30010203040506070809010015-410, S’04- 8 -Preemptive?Four opportunities to scheduleFour opportunities to scheduleA running process waits (I/O, child, ...)A running process exitsA waiting process becomes runnable (I/O done)Other interrupt (clock, page fault)Multitasking typesMultitasking typesFully Preemptive: All four cause scheduling“ Cooperative” : only first two15-410, S’04- 9 -Preemptive kernel?Preemptive multitaskingPreemptive multitaskingAll four cases cause context switchPreemptive Preemptive kernelkernelAll four cases cause context switch in kernel modeThis is a goal of Project 3System calls: interrupt disabling only when really necessaryClock interrupts should suspend system call execution15-410, S’04- 10 -CPU SchedulerInvoked when CPU becomes idleInvoked when CPU becomes idleCurrent task blocksClock interruptSelect next taskSelect next taskQuicklyPCB's in: FIFO, priority queue, tree, ...Switch (using “ dispatcher” )Switch (using “ dispatcher” )Your term may vary15-410, S’04- 11 -DispatcherSet down running taskSet down running taskSave register stateUpdate CPU usage informationStore PCB in “run queue”Pick up designated taskPick up designated taskActivate new task's memory Protection, mappingRestore register stateTransfer to user mode15-410, S’04- 12 -Scheduling CriteriaSystem administrator viewSystem administrator viewMaximize/trade off CPU utilization (“ busy-ness” ) Throughput (“ jobs per second” )Process viewProcess viewMinimize Turnaround time (everything) Waiting time (runnable but not running)User view (interactive processes)User view (interactive processes)Minimize response time (input/output latency)15-410, S’04- 13 -AlgorithmsDon't try these at homeDon't try these at homeFCFSSJFPriorityReasonableReasonableRound-RobinMulti-level (plus feedback)Multiprocessor, real-timeMultiprocessor, real-time15-410, S’04- 14 -FCFS- First Come, First ServedBasic ideaBasic ideaRun task until it relinquishes CPUWhen runnable, place at end of FIFO queueWaiting time Waiting time veryvery dependent on mix dependent on mix“ Convoy effect”“ Convoy effect”N tasks each make 1 I/O request, stall1 task executes very long CPU burstLather, rinse, repeatN “ I/O-bound tasks” can't keep I/O device busy!15-410, S’04- 15 -SJF- Shortest Job FirstBasic ideaBasic ideaChoose task with shortest next CPU burstWill give up CPU soonest, be “ nicest” to other tasksProvably “ optimal” Minimizes average waiting time across tasksPractically impossible (oh, well) Could predict next burst length...»Text presents exponential average»Does not present evaluation (Why not? Hmm...)15-410, S’04- 16 -PriorityBasic ideaBasic ideaChoose “most important” waiting task (Nomenclature: does “ high priority” mean p=0 or p=255?)Priority assignmentPriority assignmentStatic: fixed property (engineered?)Dynamic: function of task behaviorBig problem: Big problem: StarvationStarvation“ Most important” task gets to run often“ Least important “ task may never runPossible hack: priority “aging”15-410, S’04- 17 -Round-RobinBasic ideaBasic ideaRun each task for a fixed “ time quantum”When quantum expires, append to FIFO queue“ Fair”“ Fair”But not “provably optimal”Choosing quantum lengthChoosing quantum lengthInfinite (until process does I/O) = FCFSInfinitesimal (1 instruction) = “Processor sharing”Balance “fairness” vs. context-switch costs15-410, S’04- 18 -True “ Processor Sharing”CDC Peripheral ProcessorsCDC Peripheral ProcessorsMemory latencyMemory latencyLong, fixed constantEvery instructionSolution: round robinSolution: round robinQuantum = 1 instructionMemoryProcessor CoreRegister SetRegister SetRegister SetRegister SetRegister Set15-410, S’04- 19 -True “ Processor Sharing”CDC Peripheral ProcessorsCDC Peripheral ProcessorsMemory latencyMemory latencyLong, fixed constantEvery instructionSolution: round robinSolution: round robinQuantum = 1 instructionOne “ process” runningN-1 “ processes” waitingMemoryProcessor CoreRegister SetRegister SetRegister SetRegister SetRegister Set15-410, S’04- 20 -True “ Processor Sharing”Each instructionEach instruction“ Brief” computationOne load xor one storeSleeps process N cyclesSteady stateSteady stateRun when readyReady when it's your turnMemoryProcessor CoreRegister SetRegister SetRegister SetRegister SetRegister Set15-410, S’04- 21 -Everything Old Is New AgainIntel “ hyperthreading”Intel “ hyperthreading”N register setsM functional unitsSwitch on long-running operationsSharing less regularSharing illusion more lumpyGood for some application mixesMemoryProcessor CoreRegister SetRegister SetRegister SetRegister SetRegister Set15-410, S’04- 22 -Multi-level QueueN independent process queuesN independent process queuesOne per priorityAlgorithm per-queuePriority 0P1 P7Priority 1P2 P9 P3BatchP0 P4R. RobinR. RobinFCFS15-410, S’04- 23 -Multi-level
View Full Document
Unlocking...