Scheduling algorithm

From Free net encyclopedia

In computer science, a scheduling algorithm is the method by which threads or processes are given access to system resources, usually processor time. This is usually done to effectively load balance a system. The need for a scheduling algorithm arises from the requirement for most modern system to perform multitasking, or execute more than one process at a time. Scheduling algorithms are generally only used in a time slice multiplexing kernel. The reason is that in order to effectively load balance a system the kernel must be able to forcibly suspend execution of threads in order to begin execution of the next thread.

The algorithm used may be as simple as round robin in which each process is given equal time (for instance 1 ms, usually between 1 ms and 100 ms) in a cycling list. So, process A executes for 1 ms, then process B, then process C, then back to process A.

More advanced algorithms take into account process priority, or the importance of the process. This allows some processes to use more time than other processes. It should be noted that the kernel always uses whatever resources it needs to ensure proper functioning of the system, and so can be said to have infinite priority. In SMP systems, processor affinity is considered to increase overall system performance, even if it may cause a process itself to run slower. This generally improves performance by reducing cache thrashing.

The notion of a scheduling algorithm is also used in wireless communication when the air must be shared among many stations. The simplest algorithms are Round Robin, Proportionally Fair and Maximum C/I (carrier-to-interference ratio) also known as maximum throughput. Proportionally Fair algorithm schedules the channel for the station that has the maximum of the priority function <math>P=\frac{T^\alpha}{R^\beta}</math>, where T denotes the data rate potentially achievable for the station at the present moment (in the present time slot), R is the average data rate of this station. The time and station indexes are omitted for convenience. Parameters <math>\alpha</math> and <math>\beta</math> tune the fairness of the scheduler, that is, is it fair to all stations giving them equal bandwidth or is the scheduler maximizing the throughput of the channel. If <math>\alpha=0</math> and <math>\beta=1</math>, then the scheduler becomes a round-robin scheduler that is very fair to all stations. If <math>\alpha=1</math> and <math>\beta=0</math> then the scheduler is called Maximum C/I scheduler, that maximizes the throughput of the channel while stations with low T (that are far away, probably) are disadvantaged.