O(1) scheduler


O(1) scheduler

An O(1) 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 application programmers who use them endure less of a performance impact. In Linux, it has replaced the previously used O(n) scheduler. An O(1) scheduler provides "constant time" scheduling services, thus reducing the amount of jitter normally incurred by the invocation of the scheduler. In the realm of real-time operating systems, deterministic execution is key, and an O(1) scheduler is able to provide scheduling services with a fixed upper-bound on execution times.

In versions of Linux kernel 2.6 prior to 2.6.23, the scheduler used is an O(1) scheduler by Ingo Molnár. The scheduler used thereafter is the Completely Fair Scheduler, also by Ingo Molnár, which runs in O(log N) time.

Meaning of O(1)

O(1) does not mean the scheduler is necessarily extremely fast. Big O notation does not make any statements about speed or execution time. As stated above, O(1) simply means that no matter how many tasks there are in the system, scheduling them takes at most some constant amount of time, however many tasks there might be. This constant amount of time (potentially) needed may be considered "slow" or "fast" when compared to other schedulers under a typical load.

See also

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Scheduler activations — is a threading mechanism that, when implemented in an operating system s process scheduler, provides kernel level thread functionality with user level thread flexibility and performance. This mechanism uses a so called N:M strategy that maps some …   Wikipedia

  • Scheduler — (englisch für: „Planer, Disponent“) steht für: Scheduler (Datenbank), verwaltet Schreib und Lesezugriffe Prozess Scheduler, regelt die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen Festplatten Scheduler, regelt die Abfolge von Lese… …   Deutsch Wikipedia

  • scheduler — UK US /ˈʃedjuːlər/ US  /ˈskedʒuːlər/ noun [C] PRODUCTION, COMMERCE, TRANSPORT ► someone whose job is to create or work with schedules …   Financial and business terms

  • Scheduler (Datenbank) — Ein (Datenbank )Scheduler dient der Verwaltung von Schreib und Lesezugriffen (sog. Operationen) auf Datenbankobjekten. Er sorgt dafür, dass keine Konflikte während der parallelen Ausführung nebenläufiger Transaktionen auftreten. (Transaktionen… …   Deutsch Wikipedia

  • Scheduler (Informatik) — Ein Prozess Scheduler (Scheduler = Steuerprogramm) ist eine Arbitrationslogik, der die zeitliche Ausführung mehrerer Prozesse in Betriebssystemen regelt. Prozess Scheduler kann man grob in unterbrechende (preemptive) und nicht unterbrechende (non …   Deutsch Wikipedia

  • Scheduler — Шаблон проектирования Планировщик Scheduler Описан в Design Patterns Нет Планировщик (англ. Scheduler)  шаблон проектирования, обеспечивающий механизм реализации политики планирования, но при этом не зависящий ни от одной… …   Википедия

  • Scheduler pattern — In computer programming, the scheduler pattern is a software design pattern. It is a concurrency pattern used to explicitly control when threads may execute single threaded code.The scheduler pattern uses an object that explicitly sequences… …   Wikipedia

  • Scheduler — I Scheduler   [dt. Zeitplaner], Betriebssysteme: Teil eines Betriebssystems; werden mehrere Programme gleichzeitig gestartet, die parallel ablaufen sollen, teilt der Scheduler den einzelnen Prozessen Zeitscheiben zu, in denen die CPU abwechselnd… …   Universal-Lexikon

  • scheduler — planuoklė statusas T sritis informatika apibrėžtis Kompiuterio programų paketo komponentas – programa, skirta to paketo programų paleidimo, atliekamų veiksmų ir užduočių tvarkaraščiui (sąrašui) sudaryti ir įvykdyti. Pavyzdžiui, antivirusinės… …   Enciklopedinis kompiuterijos žodynas

  • scheduler — planuoklė statusas T sritis informatika apibrėžtis Kompiuterio sisteminės programinės įrangos dalis – operacinės sistemos komponentas, koordinuojantis įvairių kompiuterio arba kompiuterių tinklo išteklių ir įtaisų (procesorių, atmintinių, įvedimo …   Enciklopedinis kompiuterijos žodynas

  • scheduler — schedule ► NOUN 1) a plan for carrying out a process or procedure, giving lists of intended events and times. 2) a timetable. 3) chiefly Law an appendix to a formal document or statute, especially as a list, table, or inventory. ► VERB 1) arrange …   English terms dictionary


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.