Linux Scheduler - Columbia University

1 Linux SchedulerLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers1 / 40 Descending to Reality.. Linux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers2 / 40nThe Linux Scheduler tries to be very efficientnTo do that, it uses some complex datastructuresnSome of what it does actually contradicts theschemes we ve been discussing.

2 PhilosophiesLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers3 / 40nUse large quanta for important processesnModify quanta based on CPU usenBind processes to CPUsnDo everything in O(1) timeProcessor SchedulingLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?

3 The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers4 / 40nHave a separate run queue for each processornEach processor only selects processes from itsown queue to runnYes, it s possible for one processor to be idlewhile others have jobs waiting in their runqueuesnPeriodically, the queues are rebalanced: if oneprocessor s run queue is too long, someprocesses are moved from it to anotherprocessor s queueProcessor AffinityLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers5 / 40nEach process has a bitmask saying what CPUsit can run onnNormally, of course, all CPUs are listednProcesses can change the masknThe mask is inherited by child processes (andthreads), thus tending to keep them on thesame CPUnRebalancing does not override affinityBasic Scheduling AlgorithmLinux SchedulerDescending toReality.

4 PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers6 / 40nFind the highest-priority queue with a runnableprocessnFind the first process on that queuenCalculate its quantum sizenLet it runnWhen its time is up, put it on theexpiredlistnRepeatThe Run QueueLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?

5 The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers7 / 40n140 separate queues, one for each priority levelnActually, that number can be changed at agiven sitenActually, two sets,activeandexpirednPriorities 0-99 for real-time processesnPriorities 100-139 for normal processes; valueset vianice()system callThe Highest Priority ProcessLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers8 / 40nThere is a bit map indicating which queueshave processes that are ready to runnFind the first bit that s set:u140 queues 5 integersuOnly a few compares to find the first thatis non-zerouHardware instruction to find the first 1-bituTime depends on the number of prioritylevels,notthe number of processesCalculating TimeslicesLinux SchedulerDescending toReality.

6 PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers9 / 40nCalculateQuantum= (140 SP) 20if SP<120(140 SP) 5if SP 120where SP is thestatic prioritynHigher priority process getlongerquantanBasic idea: important processes should runlongernOther mechanisms used for quick interactiveresponseTypical QuantaLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?

7 The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers10 / 40 StaticPri Niceness QuantumHighest Static Pri 10020800 msHigh Static Pri110-10600 msNormal1200100 msLow Static Pri130+1050 msLowest Static Pri139+205 msDynamic PriorityLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers11 / 40nDynamic priority is calculated from staticpriority andaverage sleep timenWhen process wakes up, record how long itwas sleeping, up to some maximum valuenWhen the process is running, decrease thatvalue each timer ticknRoughly speaking, the bonus is a number in[0,10]that measures what percentage of thetime the process was sleeping recently; 5 isneutral, 10 helps priority by 5, 0 hurts priorityby 5DP=max(100, min(SP bonus+ 5,139))Interactive ProcessesLinux SchedulerDescending toReality.

8 PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers12 / 40nA process isinteractiveifbonus 5 S/4 28nLow-priority processes have a hard timebecoming interactivenA default priority process becomes interactivewhen its sleep time is greater than 700 msUsing QuantaLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?

9 The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers13 / 40nAt every time tick, decrease the quantum ofthe current running processnIf the time goes to zero, the process is donenIf the process is non-interactive, put it aside ontheexpiredlistnIf the process is interactive, put it at the endof thecurrent priority queuenIf there s nothing else at that priority, it willrun again immediatelynOf course, by running so much is bonus will godown, and so will its priority and its interativestatusAvoiding Indefinite OvertakingLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?

10 The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers14 / 40nThere are two sets of 140 queues,activeandexpirednThe system only runs processes fromactivequeues, and puts them onexpiredqueueswhen they use up their quantanWhen a priority level of theactivequeue isempty, the Scheduler looks for the next-highestpriority queuenAfter running all of theactivequeues, theactiveandexpiredqueues are swappednThere are pointers to the current arrays; at theend of a cycle, the pointers are switchedThe Priority ArraysLinux SchedulerDescending toReality..PhilosophiesProcessorScheduli ngProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypi cal QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?