Scheduling (computing): Difference between revisions

Revision as of 16:45, 2 September 2023

Revision as of 16:46, 2 September 2023

Line 285:

| date=2007-04-13}}</ref> CFS is the first implementation of a fair queuing [[process scheduler]] widely used in a general-purpose operating system.<ref name="dwrr">{{cite web|url=http://happyli.org/tongli/papers/dwrr.pdf|title=Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin|author1=Tong Li|author2=Dan Baumberger|author3=Scott Hahn|website=Happyli.org|access-date=2016-12-09}}</ref>

The [[Completely Fair Scheduler]] (CFS) uses a well-studied, classic scheduling algorithm called [[fair queuing]] originally invented for [[packet network]]s. Fair queuing had been previously applied to CPU scheduling under the name [[stride scheduling]]. The fair queuing CFS scheduler has a scheduling complexity of <math>O(\log N)</math>, where {{mvar|N}} is the number of tasks in the [[run queue|runqueue]]. Choosing a task can be done in constant time, but reinserting a task after it has run requires <math>O(\log N)</math> operations, because the [[run queue]] is implemented as a [[red–black tree]].

The [[Brain Fuck Scheduler]], also created by Con Kolivas, is an alternative to the CFS.