The O scheduler is the scheduler

Scheduling (computing)

In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...

 used in the Linux kernel

Linux kernel

The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....

 between versions 2.4 and 2.6. Since version 2.6, it has been replaced by the O(1) scheduler

O(1) scheduler

An O scheduler is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system. One of the major goals of operating system designers is to minimize overhead and jitter of OS services, so that...

 and later by the Completely Fair Scheduler

Completely Fair Scheduler

The Completely Fair Scheduler is the name of a task scheduler which was merged into the 2.6.23 release of the Linux kernel. It handles CPU resource allocation for executing processes, and aims to maximize overall CPU utilization while also maximizing interactive performance.Con Kolivas's work with...

 (CFS).

Algorithm

This scheduler divides processor time into epochs. Within each epoch, every task

Process (computing)

In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...

 can execute up to its time slice. If a task does not use all of its time slice, then the scheduler adds half of the remaining time slice to allow it to execute longer in the next epoch.

Advantages

This scheduler was an advantage in comparison to the previously used very simple scheduler based on a circular queue.

Disadvantages

If the number of processes is big, the scheduler may use a notable amount of the processor time itself. Picking the next task to run requires iteration through all currently planned tasks, so the scheduler runs in O(n) time

Big O notation

In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...

, where n is the number of the planned processes.