AdministriviaCPU SchedulingCPU SchedulingScheduling criteriaScheduling criteriaExample: FCFS SchedulingFCFS continuedView CPU and I/O devices the sameBursts of computation & I/OHistogram of CPU-burst timesFCFS Convoy effectSJF SchedulingSJF SchedulingExamplesSJF limitationsExp. weighted average exampleRound robin (RR)schedulingRR disadvantagesContext switch costsContext switch costsTime quantumTurnaround time vs. quantumTwo-level schedulingPriority schedulingPriority schedulingMultilevel feeedback queues (BSD)Process prioritySleeping process increases priorityhref {http://www.scs.stanford.edu/10wi-cs140/pintos/pintos_7.html#SEC131}{Pintos} notesLimitations of BSD schedulerReal-time schedulingMultiprocessor scheduling issuesMultiprocessor scheduling (cont)Thread schedulingThread dependenciesPriority donationFair Queuing (FQ)Packet schedulingPacket schedulingFQ AlgorithmFQ Algorithm (cont)Administrivia• Remember send email for any course staff to:[email protected] cs140-staff gets priority than my personal mailbox• Assignment 1 due one week from now• Please, please, please turn in your own work- Most of you would never think of cheating, and I apologizethat I even have to bring this up- 50% of honor-code violations are in CS, numbers up this year- If you are in trouble, ask for extensions, ask for help- But if you copy code, we have to turn it over to Judicial Affairs- If you copy code, re-format, re-name variables, etc., you willstill be caught. SeeMOSS for some of theory behind this.1/36CPU Scheduling• The scheduling problem:- Have K jobs ready to run- Have N ≥ 1 CPUs- Which jobs to assign to which CPU(s)• When do we make decision?2/36CPU Scheduling• Scheduling decisions may take place when a process:1. Switches from running to waiting state2. Switches from running to ready state3. Switches from waiting to ready4. Exits• Non-preemptive schedules use 1 & 4 only• Preemptive schedulers run at all four points3/36Scheduling criteria• Why do we care?- What goals should we have for a scheduling algorithm?4/36Scheduling criteria• Why do we care?- What goals should we have for a scheduling algorithm?• Throughput – # of procs that complete per unit time- Higher is better• Turnaround time – time for each proc to complete- Lower is better• Response time – time from request to first response(e.g., key press to character echo, not launch to exit)- Lower is better• Above criteria are affected by secondary criteria- CPU utilization – keep the CPU as busy as possible- Waiting time – time each proc waits in ready queue4/36Example: FCFS Scheduling• Run jobs in order that they arrive- Called “First-come first-served” (FCFS)- E.g.., Say P1needs 24 sec, while P2and P3need 3.- Say P2, P3arrived immediately after P1, get:• Dirt simple to implement—how good is it?• Throughput: 3 jobs / 30 sec = 0.1 jobs/sec• Turnaround Time: P1: 24, P2: 27, P3: 30- Average TT: (24 + 27 + 30)/3 = 27• Can we do better?5/36FCFS continued• Suppose we scheduled P2, P3, then P1- Would get:• Throughput: 3 jobs / 30 sec = 0.1 jobs/sec• Turnaround time: P1: 30, P2: 3, P3: 6- Average TT: (30 + 3 + 6)/3 = 13 – much less than 27• Lesson: scheduling algorithm can reduce TT- Minimizing waiting time can improve RT and TT• What about throughput?6/36View CPU and I/O devic es the same• CPU is one of several devices needed by users’ jobs- CPU runs compute jobs, Disk drive runs disk jobs, etc.- With network, part of job may run on remote CPU• Scheduling 1-CPU system with n I/O devices likescheduling asymmetric n + 1-CPU multiprocessor- Result: all I/O devices + CPU busy =⇒ n+1 fold speedup!- Overlap them just right? throughput will be almost doubled7/36Bursts of computation & I/O• Jobs contain I/O and computation- Bursts of computation- Then must wait for I/O• To Maximize throughput- Must maximize CPU u tilization- Also maximize I/O device utilization• How to do?- Overlap I/O & computation frommultiple jobs-Means response time very important forI/O-intensive jobs:I/O device will beidle until job gets small amount ofCPU to issue next I/O request8/36Histogram of CPU-burst times• What does this mean for FCFS?9/36FCFS Convoy effec t• CPU bound jobs will hold CPU until exit or I/O(but I/O rare for CPU-bound thread)- 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 job continues while I/O devices idle• Simple hack: run process whose I/O completed?- What is a potential problem?10/36SJF Scheduling• Shortest-job first (SJF) attempts to minimize TT- Schedule the job whose next CPU burst is the shortest• Two schemes:- Non-preemptive – once CPU given to the process it cannot bepreempted until completes its CPU burst- Preemptive – if a new process arrives with CPU burst length lessthan remaining time of current executing process, preempt(Know as the Shortest-Remaining-Time-First or SRTF )• What does SJF optimize?11/36SJF Scheduling• Shortest-job first (SJF) attempts to minimize TT- Schedule the job whose next CPU burst is the shortest• Two schemes:- Non-preemptive – once CPU given to the process it cannot bepreempted until completes its CPU burst- Preemptive – if a new process arrives with CPU burst length lessthan remaining time of current executing process, preempt(Know as the Shortest-Remaining-Time-First or SRTF )• What does SJF optimize?- Gives minimum average waiting time for a given set ofprocesses11/36ExamplesProcess Arrival Time Burst TimeP10.0 7P22.0 4P34.0 1P45.0 4• Non-preemptive• Preemptive• Drawbacks?12/36SJF limitations• Doesn’t always minimize average turnaround time- Only minimizes waiting time, which minimizes response time- Example where turnaround time might be suboptimal?• Can lead to unfairness or starvation• In practice, can’t a c tually predict the future• But can estimate CPU burst length based on past- Exponentially weighted average a good idea- tnactual length of proc’s nthCPU burst- τn+1estimated length of proc’s n + 1st- Choose parameter α where 0 < α ≤ 1- Let τn+1= αtn+ (1 − α)τn13/36Exp. weighted averag e example14/36Round robin (RR) scheduling• Solution to fairness and starvation- Preempt job after some time slice or qu antum- When
View Full Document
Unlocking...