Interactive SchedulingRound-RobinQuantum LengthPriority SchedulingPriority AdjustmentsDynamic Priority AdjustmentRun QueuesVarying QuantaHelping Interactive ProcessesGaming the SystemProcess PrioritiesUnix PrioritiesSome Linux PrioritiesShortest Process NextWhose History?Guaranteed SchedulingLottery SchedulingFair-Share SchedulingReal-Time SchedulingReal-Time SystemsPeriodic EventsAperiodic EventsMixing Real-Time and Non-Realtime ProcessesMultiple Real-Time ProcessesDiagramOther IssuesRate Monotonic SchedulingAlgorithmRMSEarliest Deadline FirstEDFRMS Doesn't Always WorkRMS FailureWhy Did it Fail?EDF SucceedsGantt ChartsOther IssuesHow Do We Measure CPU Time?Statistical TimeI/O and MemoryScheduler AlgorithmsSummaryInteractive Scheduling 1 / 39Round-Robin■ Take turns■ Give each process a time quantum■ When the time is up, move the current process to the end of the queue1 / 39Quantum Length■ The shorter the quantum, the more responsive the system■ However, process switching is expensive (saving and reloading registers,switching virtual memory maps, flushing the cache, bookkeeping, etc.)■ Suppose the compute quantum is 4 msec and process switches take 1 msec.That’s 20% overhead — too much■ Suppose we have 100 msec quanta■ If the run queue ever gets long, even cheap requests will take too long■ Need a reasonable compromise: 20-50 msec?2 / 391Priority Scheduling■ Not all processes are equally important■ Assign them priority levels■ Simplest version: always run the highest-priority process■ Not a good idea — what if it’s CPU bound?3 / 39Priority Adjustments■ Periodically reduce the priority of the running process■ Eventually, it falls below the priority of the next process■ Alternative: increase the priority of non-running processes■ Called process aging■ Or do both4 / 392Dynamic Priority Adjustment■ Adjust process priority according to its recent history■ Example: increase priority of non-running processes; decrease priority ofrunning processes, as above■ Boost priority of I/O-bound processes:◆ If process used 1/f of its last quantum, boost its priority proportional to f■ Use priority classes: have separate queues for each priority level, and run eachqueue round-robin; switch to lower-priority queue when this one is empty5 / 39Run Queues■ Each run queue is a linked list■ To raise or lower a process’ priority, move it to a different list■ Two schemes for priority aging:◆ Not many processes: have a fine-grained counter for each processincremented at a clock interrupt; at some limit, increase priority◆ Lots of processes and queues: periodically, move each list to the next levelup6 / 393Varying Quanta■ Many processes need just a little bit of CPU time■ Since process switches can be expensive, don’t do them too often■ Solution to both problems: give lower priority queues longer quanta■ Top priority queue: one quantum■ Second queue: two quanta CPU allocation■ Third queue: four quanta, etc.■ Alternate solution: “short” (initial) quantum at high priority and “long”quanta at low priority thereafter7 / 39Helping Interactive Processes■ Look for signs of user input■ When they occur, give the process a very high priority■ Example: on CTSS, when a user typed a carriage return, the process got toppriority■ Harder to do today — what’s “interactive” on a networked process? For amouse movement, which process is credited?8 / 394Gaming the System■ On time-sharing systems, watch for attempts to fake out the scheduler■ CTSS example: typing spurious carriage returns■ XDS 940 example: do really quick I/O operation◆ Solution: save remaining CPU quantum; when process restarts, useremainder instead of full allocation■ Not applicable on single-user machines — you’re only hurting yourself■ Instead, watch for inadvertent influences on the wrong process9 / 39Process Priorities■ What processes should have higher priorities?■ Administrative issues■ System performance◆ Kernel processes (up to a point)◆ Interactive services processes (i.e., X server)■ Users can lower priority of their own processes, sometimes to avoid competingwith themselves10 / 395Unix Priorities■ Tradition: lower numbers indicate higher priorities■ “Nice” value is a user-specified modifier■ A nice value of +20 specifies a very low priority process■ Only root can set negative niceness■ Default is 0■ Note: this is an API; internal metric can be different11 / 39Some Linux PrioritiesUID PRI NI SZ CMDroot 76 0 606 initroot 94 19 0 [ksoftirqd/0]root 75 0 0 [khubd]root 83 0 0 [scsi_eh_1]root 79 0 6285 ypbindroot 75 0 1242 /usr/sbin/sshdsmb 76 0 1007 psThe PRI value factors in the niceness and the process’ dynamic priority12 / 396Shortest Process Next■ Can we emulate batch systems’ shortest first algorithm?■ It’s hard, because we don’t have good estimates■ Instead, use historical data for a moving, decaying, average■ Let first time = T0; second is T1T2= αT0+ (1 − α)T1T3= α2T0+ α(1 − α)T1+ (1 − α)T2T4= α3T0+ α2(1 − α)T1+ α(1 − α)T2+(1 − α)T3. . .13 / 39Whose History?■ Do we measure command history?■ Hard; requires a lot of kernel state■ Besides, command time can vary a lot depending on input data■ Better to measure user (or terminal) behavior14 / 397Guaranteed Scheduling■ For n users or process on a system, give each 1/n of the CPU■ Measure actual CPU usage■ Calculate process’ CPU time entitlement■ Look at the ratio of the two: 0.5 means it’s had only half the CPU it’s entitledto, so it gets priority over a process with a ratio of 2.015 / 39Lottery Scheduling■ Give each process lottery tickets■ Higher priority processes get more tickets; lower priority process get fewer■ At scheduling time, pick a random ticket■ The process holding that ticket gets to run■ Note: tickets can be exchanged between processes, such as between client andserver16 / 398Fair-Share Scheduling■ In some systems, processes don’t compete, users do■ We don’t want to encourage forking just to get a larger share of the CPU■ Solution: make decisions based on user CPU consumption instead of processCPU consumption■ Priorities, etc., can still apply17 / 39Real-Time Scheduling 18 / 39Real-Time Systems■ Must respond to actual clock-on-the-wall time■ A late process may be a useless process■ Two types, hard and soft■ Hard real time systems have deadlines that