Linux SchedulerDescending to Reality…PhilosophiesProcessor SchedulingProcessor AffinityBasic Scheduling AlgorithmThe Run QueueThe Highest Priority ProcessCalculating TimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding Indefinite OvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The Traditional AlgorithmLinux is More EfficientLocking RunqueuesReal-Time SchedulingSleeping and WakingSleeping and WakingSleepingWaking Up a ProcessScheduler-Related System CallsMajor Kernel FunctionsFair Share SchedulingTimersWhy Does the Kernel Need Timers?Two Basic FunctionsTimer TypesTimer TicksJiffiesPotent and Evil MagicTime of DayKernel TimersDynamic TimersDelay FunctionsSystem CallsLinux SchedulerLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers1 / 40Descending to Reality. . .Linux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers2 / 40■ The Linux scheduler tries to be very efficient■ To do that, it uses some complex datastructures■ Some of what it does actually contradicts theschemes we’ve been discussing. . .PhilosophiesLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers3 / 40■ Use large quanta for important processes■ Modify quanta based on CPU use■ Bind processes to CPUs■ Do everything in O(1) timeProcessor SchedulingLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers4 / 40■ Have a separate run queue for each processor■ Each processor only selects processes from itsown queue to run■ Yes, it’s possible for one processor to be idlewhile others have jobs waiting in their runqueues■ Periodically, the queues are rebalanced: if oneprocessor’s run queue is too long, someprocesses are moved from it to anotherprocessor’s queueProcessor AffinityLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers5 / 40■ Each process has a bitmask saying what CPUsit can run on■ Normally, of course, all CPUs are listed■ Processes can change the mask■ The mask is inherited by child processes (andthreads), thus tending to keep them on thesame CPU■ Rebalancing does not override affinityBasic Scheduling AlgorithmLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers6 / 40■ Find the highest-priority queue with a runnableprocess■ Find the first process on that queue■ Calculate its quantum size■ Let it run■ When its time is up, put it on the expired list■ RepeatThe Run QueueLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers7 / 40■ 140 separate queues, one for each priority level■ Actually, that number can be changed at agiven site■ Actually, two sets, active and expired■ Priorities 0-99 for real-time processes■ Priorities 100-139 for normal processes; valueset via nice() system callThe Highest Priority ProcessLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and WakingTimers8 / 40■ There is a bit map indicating which queueshave processes that are ready to run■ Find the first bit that’s set:◆ 140 queues ⇒ 5 integers◆ Only a few compares to find the first thatis non-zero◆ Hardware instruction to find the first 1-bit◆ Time depends on the number of prioritylevels, not the number of processesCalculating TimeslicesLinux SchedulerDescending toReality. . .PhilosophiesProcessorSchedulingProcessor AffinityBasic SchedulingAlgorithmThe Run QueueThe Highest PriorityProcessCalculatingTimeslicesTypical QuantaDynamic PriorityInteractive ProcessesUsing QuantaAvoiding IndefiniteOvertakingThe Priority ArraysSwapping ArraysWhy Two Arrays?The TraditionalAlgorithmLinux is MoreEfficientLocking RunqueuesReal-TimeSchedulingSleeping and