Linux Scheduling AlgorithmIntroductionHistory and BackgroundScheduling in LinuxLinux ApproachSlide 6Process SchedulingSlide 8Priorities: Linux 2.4 SchedulingLinux SchedulingSlide 11Goodness Function in Scheduling AlgorithmSelecting the next ProcessTwo Level ImplementationSlide 15Linux Vs Two LevelLimitationsAdvantagesConclusionReferencesLinux Scheduling Algorithm-Ashish SinghIntroductionHistory and BackgroundLinux SchedulingModification in Linux SchedulingResultsConclusionReferencesQuestionsHistory and BackgroundIn 1991 Linus Torvalds took a college computer science course that used the Minix operating systemMinix is a “toy” UNIX-like OS written by Andrew Tanenbaum as a learning workbenchLinus went in his own direction and began working on LinuxIn October 1991 he announced Linux v0.02In March 1994 he released Linux v1.0Scheduling in LinuxTime Sharing System-magical effect by switching from one process to the other in short time frame.Question – when to switch and what process?Linux ApproachProcess run concurrently – CPU time divided into slices, one for each process.If current process is not terminated when its time quantum expires – switch process.Linux ApproachGeneral Systems – algorithms to derive priority of process, end result – process assigned a valueLinux – process priority is dynamic. Scheduler increases/decreases the priority.Process SchedulingLinux uses two process-scheduling algorithms:A time-sharing algorithm for fair preemptive scheduling between multiple processesA real-time algorithm for tasks where absolute priorities are more important than fairnessA process’s scheduling class defines which algorithm to applyFor time-sharing processes, Linux uses a prioritized, credit based algorithmThe crediting rulefactors in both the process’s history and its prioritypriority2credits : credits Process SchedulingLinux implements the FIFO and round-robin real-time scheduling classes; in both cases, each process has a priority in addition to its scheduling classThe scheduler runs the process with the highest priority; for equal-priority processes, it runs the process waiting the longest FIFO processes continue to run until they either exit or blockPriorities: Linux 2.4 Scheduling• Static priorityThe maximum size of the time slice a process should be allowedbefore being forced to allow other processes to compete for theCPU.• Dynamic priorityThe amount of time remaining in this time slice; declines withtime as long as the process has the CPU.When its dynamic priority falls to 0, the process is marked forrescheduling.• Real-time priorityOnly real-time processes have the real-time priority.Higher real-time values always beat lower valuesLinux SchedulingProcess Selectionmost deserving process is selected by the schedulerreal time processes are given higher priority than ordinary processeswhen several processes have the same priority, the one nearest the front of the run queue is chosenwhen a new process is created the number of ticks left to the parent is split in two halves, one for the parent and one for the childpriority and counter fields are used both to implement time-sharing and to compute the process dynamic priorityLinux SchedulingActions performed by schedule( )Before actually scheduling a process, the schedule( ) function starts by running the functions left by other kernel control paths in various queuesThe function then executes all active unmasked bottom halvesSchedulingvalue of current is saved in the prev local variable and the need_resched field of prev is set to 0a check is made to determine whether prev is a Round Robin real-time process. If so, schedule( ) assigns a new quantum to prev and puts it at the bottom of the runqueue listif state is TASK_INTERRUPTIBLE, the function wakes up the processschedule( ) repeatedly invokes the goodness( ) function on the runnable processes to determine the best candidatewhen counter field becomes zero, schedule( ) assigns to all existing processes a fresh quantum, whose duration is the sum of the priority value plus half the counter valueGoodness Function in Scheduling Algorithm goodness( ) functionidentify the best candidate among all processes in the runqueue list. It receives as input parameters prev (the descriptor pointer of the previously running process) and p (the descriptor pointer of the process to evaluate)The integer value c returned by goodness( ) measures the "goodness" of p and has the following meanings:c = -1000, p must never be selected; this value is returned when the runqueue list contains only init_taskc =0, p has exhausted its quantum. Unless p is the first process in the runqueue list and all runnable processes have also exhausted their quantum, it will not be selected for execution.0 < c < 1000, p is a conventional process that has not exhausted its quantum; a higher value of c denotes a higher level of goodness.c >= 1000, p is a real-time process; a higher value of c denotes a higher level of goodness.Selecting the next ProcessTwo Level ImplementationThe first level scheduler selects a set of processes, a batch, to be scheduled for a specified amount of time. Rather than selecting a constant number of processes for each batch, the processes selected are based on the system load to avoid any subsystem (PE or I/O) to be idle. The first level scheduler keeps processes in two lists: a ready queue and an expired queue. These queues are used to guarantee fairness. All new processes are placed on the ready queue and processes to be scheduled are selected from this queue. When a process has been scheduled for a defined period of time, Crq, the process is removed from the run queue, in the second level scheduler, and placed on the expired queue.Two Level ImplementationWhen the ready queue becomes empty, all processes from the expired queue are moved to the ready queue. This is repeated indefinitely. While processes are executed, the system keeps track of time spent in the running state and blocked state for each process. UPE += Trunning(p)/Tblocked(p) and UIO += 1 - (Trunning(p)/Tblocked(p))Linux Vs Two LevelLimitationsIt has not been possible to improve the Linux scheduler through modifications like this, while maintaining all of the advantages in the existing Linux scheduler. It is hypothesized that if knowledge of
View Full Document