Transcription
CS 350 Operating SystemsSpring 20229 CPU Scheduling I
Question?How does an OS provide the illusion of many “CPUs”,thus to execute multiple programs?Via processesp1p3p2p4Operating SystemCPUp1p2p3p4p1Time sharing2
Process Lifecycle Ready Processis ready to execute, but not yet executing Its waiting in the scheduling queue for the CPU scheduler to pick it up. Running Process is executing on the CPU Blocked Process is waiting (sleeping) for some event to occur. Once the event occurs, process will be woken up, and placed on thescheduling queue. CPU scheduler makes the transitions between states.3
CPU scheduler The job of the CPU scheduler is to select the next process -- based onsome scheduling policies -- to run on the CPU from the processesthat are ready to execute CPU scheduler is a piece code of the kernel The in-kernel “ready queue” data structure stores processes whoare “ready”proc1proc2proc3proc4CPU Queue of ready processesWho’s Next?CPU Scheduler4
When? CPU scheduling decisions mainly take place during process statetransitions: Switches from running to blocked state E.g., the process runs on the CPU and issues a blocking I/Orequest; after this, the process cannot run anymore Switches from running to ready state (pre-emptive scheduling) E.g., the process runs too long; to avoid starve other processes, the CPU scheduler is invoked to stop running the currentprocess and picks up another one Switches from blocked to ready E.g., the I/O completes, and the process is ready again. Betterto check if the CPU scheduler will pick up this process. Terminates E.g., the process completes its execution; the CPU schedulerneeds to pick up another process, if any, to execute5
Scheduler & Dispatcher CPU scheduler only focuses on selecting the next processto execute.Afterwards, the dispatcher gives control of the CPU to theprocess selected by the scheduler via: Context switchCurrentprocCPUSchedulerproc1proc2Queue ofreadyprocessesproc3proc4Dispatcher Who’s Next?CPUproc16
Context Switch Context switch Save CPU register values for thecurrently-executing process (e.g.,onto its kernel stack) and restore theones for the soon-to-be-executingprocess (e.g., from its kernel stack).Due to context switch, once the CPUscheduler returns, the system willstart executing the newly selectedprocessAs aside, when the system transitsfrom the user mode to the kernelmode (i.e., system calls), it also doescontext switch (between user codeand kernel code within the sameprocess)Dispatch latency Time spent in context switchContext switch is a tersMemorykernel stackuser adregisterskernel stackuser stackHeap.bssSoon-to-beexecutingprocess.data.text7
Put it all How is the scheduler invoked? Scheduler is a piece of kernel code, hence whenever kernel is invoked, thereis a chance for the scheduler to runThree ways to invoke kernel code System calls Hardware Interrupts (timer interrupts and device interrupts) ExceptionsTimer is the most common way to invoke schedulerUser Mode System Call (Read())Interrupt (End of Read()Timer interruptKernel ModeSys read() Schedule() context switch()Handler ofinterruptProc1 Proc28
Scheduling PoliciesHow should we develop a basic frameworkfor thinking about scheduling policies?What are the key assumptions?What metrics are important?9
Scheduling CriterionOptimization Criteria CPU utilization – keep the CPU asbusy as possible Throughput – Number ofprocesses that complete theirexecution per time unit Turnaround time – amount oftime to execute a particularprocess, from submission totermination. Waiting time – amount of time aprocess has been waiting in theready queue Response time – amount of timeit takes from when a request wassubmitted until the first responseis produced. Max CPU utilization Max throughput Min turnaround time Min waiting time Min response time10
Scheduling Goals All systems Fairness – giving each process a fair share of the CPU Policy enforcement – seeing that stated policy iscarried out Balance – keeping all parts of the system busy Batch systems Throughput – maximize jobs per hour Turnaround time – minimize time betweensubmission and termination CPU utilization – keep the CPU busy all the time Interactive systems Response time – respond to requests quickly Proportionality – meet users’ expectations Real-time systems Meeting deadlines – avoid failing critical missions Predictability – avoid quality degradation inmultimedia systems11
Model Applications/Processes To design a CPU scheduler, we also needto model applications/processes Without loss of generality, a process canbe modeled in the way: It consists of a sequence of CPUburst and I/O burst tasks CPU tasks: consume CPU cycles I/O tasks: block the process until I/Ocompletions12
Model Applications/Processes CPU-bound processes: occupy the CPU in its most time (ifpossible), and rarely yield the CPU for I/O tasks I/O-bound processes: frequently issue I/O requests; foreach I/O, consume little CPU time A CPU-bound process An I/O-bound process13
Takeaways Before we design a CPU scheduling policy, we need tofigure out: What are the target systems? What are the goals of these target systems? What are the optimization criterion/metrics to achievethe goals? How do we model the workloads in these systems?14
CS 350 Operating SystemsSpring 202210. CPU Scheduling II
CPU Scheduling First come, first served (FCFS) Shortest job first (SJF) Round Robin (RR) Real-time scheduling Priority Scheduling Multi-level feedback queue (MLFQ)16
First-Come, First-Served (FCFS)ProcessBurst TimeP124P23P33 Suppose that the processes arrive in the order: P1 , P2 , P3 TheGantt Chart for the schedule is:P10P224P32730 Waiting time for P1, P2, P3 (assume they arrive almost at thesame time)? 0 for P1, 24 for P2, and 27 for P3 Average waiting time? (0 24 27)/3 1717
FCFS, cont.d Suppose that the processes arrive in the orderP2 , P 3 , P1 The Gantt chart for the schedule is:P20 P33P1630Waiting time for P1, P2, and P3? 6 for P1, 0 for P2, and 3 for P3Average waiting time？ (6 0 3)/3 3Much better than previous case In terms of smaller average waiting timeConvoy effect The whole system slows down due to shortprocesses behind long processes18
CPU Scheduling First come, first served (FCFS) Shortest job first (SJF) Round Robin (RR) Real-time scheduling Priority Scheduling Multi-level feedback queue (MLFQ)19
Shortest-Job-First (SJF) SJF runs the shortest job first, then the next shortest,and so on. Consider & compare the length of its next CPU burst foreach process.Schedule the process having the shortest next CPU burst.proc1proc2proc3proc4SJFproc5CPU burst length20
SJF Two schemes:Non-preemptive: The scheduler should wait till thecompletion of current process to select the next one Preemptive: The scheduler can pick up a better candidateanytime and replaces the current process with the newselectionPreemptive SJF is also called Shortest Remaining Time First(SRTF) proc6proc1CPUproc2proc3proc4SJFproc5CPU burst length21
Shortest-Job-First (SJF)Claim: SJF algorithm is optimal w.r.t. least average waiting time SJF gives a schedule with least average waiting time compared to anypossible scheduling algorithm.Proof (by contradiction) optional:Assume that there is an algorithm X that gives better average waitting timethan SJF for a set of N processes.Since X is not the same as SJF, it means that there must be at least twoprocesses P1 and P2 in the schedule generated by X such thati. P1 executes before P2 does andii. The CPU execution time of P1 is longer than that of P2 andiii. The average waiting time of X is smaller than SJF (X better than SJF)BUT, if you swap the positions of P1 and P2, you will get another scheduler Ywith the average waiting time less than X!So keep swapping all such process pairs that satisfy conditions i&ii above.Each swap will reduce the average waiting time -- a better schedule!Finally you will end up with a schedule which is exactly the same as SJF (acontradiction to iii). Hence SJF is Optimal.22
Example of Non-Preemptive SJFProcessArrival TimeP10.0P22.0P34.0P45.0 SJF (non-preemptive)p10123567 Average waiting time (0 6 3 7)/4 4p4p2p34Burst Time74148910111213141516
Example of Preemptive SJFProcessArrival TimeBurst TimeP10.07P22.04P34.01P45.04 SJF (preemptive) – shortest time-to-completion job first01p3p2p1234p4p256789p110 Average waiting time (9 1 0 2)/4 3 How about “turnaround” time?111213141516
DiscussionFCFSSJFAdvantagesSimple; easy toimplementDisadvantagesNot optimal; longwaiting timeOptimal; least averagewaiting timeNot realistic – hard toimplement in practice
Exponential Averaging:Predict Next CPU Burst Not easy to get the length of next CPU burst. Canonly guess. One approach: using the length of previous CPUbursts via exponential averaging Predict future from historytn actual length of the nth CPU burst (history)τn 1 predicted value of the (n 1)th CPU burstα, 0 α 1(smoothing parameter)Define:τn 1 α tn (1-α) * τn
Exponential Averaging:Predict Next CPU 8α 0.5time09Time
Exponential Averaging:Predict Next CPU Burstτn 1 α tn (1-α) * τn α 0τn 1 τnCPU burst history does not count α 1τn 1 tnOnly the actual last CPU burst counts If we expand the formula, we get:τn 1 α tn (1 - α)α tn-1 (1 - α )j α tn -j (1 - α )n 1 τ0 Since both α and (1 - α) are less than or equal to 1, eachsuccessive term has less weight than its predecessor
Responsiveness SJF is optimal in terms of least waiting time (or turnaroundtime given the fixed CPU burst) Desired goal for batch system Not responsive; it may cause “starvation” – a long jobmay wait forever if short jobs keep coming Modern computer systems more care about interactiveperformance How quickly the system responds to a new job Response time as the time from when the job arrives in asystem to the first time it is executed (with a response)Tresponse Tfirstrun Tarrival29
CPU Scheduling First come, first served (FCFS) Shortest job first (SJF) Round Robin (RR) Real-time scheduling Priority Scheduling Multi-level feedback queue (MLFQ)30
Round Robin (RR) Each process gets a fixed unit of CPU burst time (timequantum) usually, 10 to 100 milliseconds. After this time has elapsed, the process is preempted andadded to the end of the ready queue. If there are n processes in the ready queue and the timequantum is q, then each process gets 1/n of the CPU time inbursts of at most q time units at once. No process waits morethan (n-1)q time units.p1 p2 p3 p4 p1 p2 p3 p4 p1 p2 p3 p4 p1 p2 p3 p431
Performance Discussion q large FCFS, because processes rarely get pre-emptedq small Smaller response time, but too much context switchingoverhead. q must be larger compared to context switch time,otherwise overhead is too high32
Example of RR Assume the four processes arrive at the same time Time quantum 20ProcessBurst TimeP153P217P368P424 The Gantt chart is:0p3p2p12037 40p457 60p177 80p397100p4p1p3p3117120 121 134140 154 160 162 Typically, higher average turnaround/waiting time than SJF, but Better response time No Starvation33
CPU Scheduling First come, first served (FCFS) Shortest job first (SJF) Round Robin (RR) Real-time scheduling Priority Scheduling Multi-level feedback queue (MLFQ)34
Real-Time Scheduling Mission-critical tasks need to be completed before a given deadlineHard real-time systems Required to complete a critical task before its deadline For example, in a flight control system, or nuclear reactorSoft real-time systems Meeting deadlines desirable, but not essential For example, video or audioSchedulability criteria Given m periodic events, where event i occurs withinperiod Pi and requires Ci computation time each period Then the load can be handled only ifsumi (Ci/Pi) 1 The above condition is necessary but NOT sufficient.35
CPU Scheduling First come, first served (FCFS) Shortest job first (SJF) Round Robin (RR) Real-time scheduling Priority Scheduling Multi-level feedback queue (MLFQ)36
Priority Scheduling We may run a mixed group of tasks with different importance levelsA priority number (integer) is associated with each processScheduling: the CPU is allocated to the process with the highestpriority (e.g., smallest integer highest priority)Again, two types Preemptive Non-preemptiveExample with four priority classes SJF is a priority scheduling algorithm where priority is the (predicted)next CPU burst Problem: Starvation low priority processes may never executeSolution Aging as time progresses increase the priority of alower priority process that is not receiving CPU time. 37
DiscussionFCFSAdvantagesSimple; easy toimplementSJFOptimal; least averagewaiting timeRRResponsivenessPredictabilityDisadvantagesNot optimal; longwaiting timeLack of responsivenessNot realistic – hard toimplement in practicestarvationLong turnaround timePossible high overheadSimple; easy to iationLong turnaround time38
CPU Scheduling First come, first served (FCFS) Shortest job first (SJF) Round Robin (RR) Real-time scheduling Priority Scheduling Multi-level feedback queue (MLFQ)39
Multi-Level Feedback Queue(MLFQ)40
Multi-Level Feedback Queue (MLFQ) Developed by Turing Award winner FernandoCorbato. Adopted in many modern OSes. Problems to be addressed optimize turnaround/waiting time (by running shorter jobsfirst) minimize response time for interactive users Do we know anything (running time) about the jobs? How to schedule without perfect knowledge? Can the scheduler learn? How? Learn from history Learn from the past to predict the future E.g., exponential averaging How does MLFQ achieve this?41
MLFQ Basic setup The MLFQ has a number of distinct queues, each assigneda different priority level. At any given time, a ready-to-run job is in a single queue. MLFQ uses priorities to decide which job should run at agiven time: a job in a queue with the highest priority ischosen to run. For jobs in the same queue (same priority), RR is used. First two basic rules for MLFQ Rule 1: If Priority(A) Priority(B), A runs (B doesn’t) Rule 2: If Priority(A) Priority(B), A & B run in RR42
MLFQ example[High Priority]Q8ABQ7Q6Q5Q4CQ3Q2[Low Priority]Q1D43
MLFQ The key to MLFQ scheduling is to properly set priorities. MLFQ varies the priority of a job based on its observedbehavior(Assumption: CPU-bound jobs should have lower priority than I/O-bound jobs) Fob a job that uses the CPU intensively for long periods of time,what should MLFQ do with its priority? Should reduce its priority For a job that repeatedly relinquishes CPU and waits for I/O,what should MLFQ do with its priority? Should keep its priority high MLFQ uses history of a job to predict its future behavior44
Changing priority Priority changes over time. How? Workload - a mix of interactive jobs that are short-running (and may frequently relinquishCPU), and some longer-running “CPU-bound” jobs that need a lot of CPU timebut where response time isn’t important Rules on changing job priority Rule 3: When a job enters the system, it is placed at the highestpriority (the topmost queue) Rule 4a: If a job uses up an entire time slice while running, its priorityis reduced (i.e., it moves down one queue) Rule 4b: If a job gives up CPU before the time slice is up, it stays at thesame priority level45
Example One long-running jobTime slice length 10 ms46
Example Two jobs: A (long-running and CPUbound), and B (short-running andinteractive)B B arrives at T 100 ms and will run for 20ms.A How MLFQ approximate SJF for job B inthis case? A has run some time drops to theTime slice length 10 mslowest priority queue. When B comes in, the scheduler doesn’t know whether B is shortor long-running, it first assumes it is a short job by placing it in thehighest priority queue. If B actually is a short job, it will run quickly and complete (i.e.,SJF-like behavior); If B is not a short job, it will slowly move down the queues, andthus soon prove itself to be a long-running.47
How about I/O? Rule 4b: If a job gives up CPU before the time slice is up,it stays at the same priority level. If an interactive job, for example, is doing a lot of I/O, it willrelinquish the CPU before its time slice is complete; in suchcase, we don’t wish to penalize the job and thus simply keep itat the same level.BA48
MLFQ MLFQ rules thus far Rule 1: If Priority(A) Priority(B), A runs (B doesn’t). Rule 2: If Priority(A) Priority(B), A & B run in RR. Rule 3: When a job enters the system, it is placed at thehighest priority (the topmost queue). Rule 4: If a job uses up an entire time slice while running,its priority is reduced (i.e., it moves down one queue); If ajob gives up CPU before the time slice is up, it stays at thesame priority level.Any problems with the current version of MLFQ?49
Problems so far Problems with the current version of MLFQ Starvation Too many interactive jobs, and thus long-running jobswill never receive any CPU time Game the scheduler Doing something sneaky to trick the scheduler intogiving you more than your fair share of the resource. What if a CPU-bound job turns to I/O-bound There is no mechanism to move the job up to queueswith higher priorities!50
Boosting priority Rule 5: After some time period S, move all the jobs in thesystem to the topmost queue. What problems does this rule solve? Starvation When a CPU-bound job turns to I/O bound.AAHow to deal withthose gamerprocesses?51
CPU time accounting The scheduler keeps track of how much time a job hasexecuted; once the job has accumulatively used itstime allotment (e.g., one time slice), it is demoted tothe next priority queue.Rule 4: If a job uses up an entiretime slice while running, itspriority is reduced (i.e., it movesdown one queue); If a job givesup CPU before the time slice isup, it stays at the same prioritylevel.Rule 4: Once a job uses up itstime allotment at a given level(regardless of how many timesit has given up the CPU), itspriority is reduced (i.e., itmoves down one queue).52
CPU time accountingBBAAw/o time accountingw/ time accounting53
Tuning MLFQ How to parameterize MLFQ ? How many queues? How big should time slice be per queue? How often should priority be boosted? No easy answers and need experience with workloads Varying time-slice length across different queues (e.g., highpriority queues are usually given short time slices, and lowpriority queues are with long time slices) Some schedulers reserve the highest priority levels foroperating system work. Some systems also allow some user advice to help setpriorities (e.g., for example, by using the command-line utilitynice you can increase or decrease the priority of a job(somewhat) and thus increase or decrease its chances ofrunning at any given time).54
MLFQ summary Rule 1: If Priority(A) Priority(B), A runs (B doesn’t) Rule 2: If Priority(A) Priority(B), A & B run in RR Rule 3: When a job enters the system, it is placed at the highestpriority (the topmost queue) Rule 4: Once a job uses up its time allotment at a given level(regardless of how many times it has given up the CPU), its priority isreduced (i.e., it moves down one queue) Rule 5: After some time period S, move all the jobs in the system tothe topmost queue Instead of demanding a priori knowledge of a job, MLFQ insteadobserves the execution of a job and prioritizes it accordingly MLFQ manages to achieve the best of both worlds: it can deliverexcellent overall performance (similar to SJF/STCF) for interactiveshort-running jobs, and is fair and makes progress for long-running55CPU-intensive workloads
56
Fair scheduling Notion of “fairness” does not necessarily mean equalCPU share for all processes.Proportional share: Say you have N processes Each process Pi is assigned a weight wi Then the CPU time will be divided amongprocesses in proportion to their weights.𝑤𝑖𝐶𝑃𝑈𝑖 𝑁 𝐶𝑃𝑈σ𝑗 1 𝑤𝑗57
Fair-share scheduler Lottery scheduling: the scheduler holds a lottery todetermine which process should get to run next. Processes that should run more often should be givenmore chances to win the lottery. Foundational concept – tickets Example: two processes and a total 100 tickets in the system Fair share of Process A 25%, Process B 75% Process A has 25 tickets, process B has 75 tickets:assuming A holds tickets 0 24, B holds 25 99 While scheduling, the scheduler randomly generatesa ticket between 0 and 99; whoever holds the ticketwill take the CPU58
References Operating Systems: Three Easy Pieces – Chapter 7:http://pages.cs.wisc.edu/ remzi/OSTEP/cpusched.pdf -- to finish reading this chapter! Operating Systems: Three Easy Pieces – Chapter 8 & 9 https://pages.cs.wisc.edu/ remzi/OSTEP/cpu-schedmlfq.pdf; https://pages.cs.wisc.edu/ remzi/OSTEP/cpu-schedlottery.pdf Finish reading these two chapters!59
Its waiting in the scheduling queue for the CPU scheduler to pick it up. . scheduling queue. CPU scheduler makes the transitions between states. 3. CPU scheduler The job of the CPU scheduler is to select the next process -- based on some scheduling policies -- to run on the CPU from the processes . ESP pc FLAGS Memory user stack Heap.text .
