Completely Fair Scheduler

Completely Fair Scheduler (CFS) ist ein für Linux konzipierter und dort als Standard vorgesehener Prozess-Scheduler. Solche Scheduler werden verwendet, um die Priorität von Programmabläufen auf Kernelebene von Betriebssystemen zu verwalten. Eine frühere Version des CFS wurde zuerst von Ingo Molnár entwickelt und ersetzte mit Kernelversion 2.6.23 im Oktober 2007 den zuvor verwendeten O(1)-Scheduler.

Der CFS garantiert eine faire Aufteilung der Prozessorzeit. Er verzichtet im Gegensatz zum O(1)-Scheduler dabei auf Heuristiken und Statistiken. Im Idealfall läuft beim CFS jeder Prozess quasiparallel in gleicher Geschwindigkeit. Der CFS benötigt keine Runqueue, keine Timeslices und kein Array-Switching. Stattdessen ist jedem Prozess ein vruntime genannter Wert zugeordnet (virtual runtime), der seine tatsächliche Laufzeit auf Nanosekunden bestimmt abstrahiert und eine Bewertung darüber erlaubt, wie lange der Prozess schon gelaufen ist. Derjenige Prozess mit der jeweils geringsten vruntime wird gewählt. Als Struktur wird dafür ein nach der vruntime sortierter Rot-Schwarz-Baum verwendet.<ref name="This is the CFS scheduler">Ingo Molnár: <templatestyles src="Webarchiv/styles.css" />{{#if:20180225103905

      | {{#ifeq: 20180225103905 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: This is the CFS scheduler. | {{#invoke:WLink|getEscapedTitle|This is the CFS scheduler.}} | {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20180225103905}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: This is the CFS scheduler. | {{#invoke:WLink|getEscapedTitle|This is the CFS scheduler.}} | {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2024-11-19 09:13:46 InternetArchiveBot | 2024-11-19 09:13:46 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20180225103905}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: This is the CFS scheduler. | {{#invoke:WLink|getEscapedTitle|This is the CFS scheduler.}} | {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2024-11-19 09:13:46 InternetArchiveBot | 2024-11-19 09:13:46 InternetArchiveBot |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: This is the CFS scheduler. | {{#invoke:WLink|getEscapedTitle|This is the CFS scheduler.}} | {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if: 2024-11-19 09:13:46 InternetArchiveBot | 2024-11-19 09:13:46 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: This is the CFS scheduler. | {{#invoke:WLink|getEscapedTitle|This is the CFS scheduler.}} | {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}} }} (Memento{{#if: {{#if: 2024-11-19 09:13:46 InternetArchiveBot | 2024-11-19 09:13:46 InternetArchiveBot |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: This is the CFS scheduler. | {{#invoke:WLink|getEscapedTitle|This is the CFS scheduler.}} | {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}} }}  
                 }}}}}}}}{{#if:2024-11-19 09:13:46 InternetArchiveBot
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20180225103905|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: This is the CFS scheduler.
    | {{#if: {{#invoke:WLink|isBracketedLink|This is the CFS scheduler.}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|https://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}, Stand 13. März 2008</ref><ref>Robert Love: Linux Kernel Development. 3. Auflage, Addison-Wesley 2010, ISBN 978-0-672-32946-3. S. 41–67</ref>

Erweiterungen im 2.6.24er-Kernel

Mit dem 2.6.24er-Kernel unterstützt der CFS Task Groups. Dies bedeutet, dass mehrere Prozesse zu Gruppen zusammengefasst werden und dadurch eine faire Aufteilung zwischen den Gruppen stattfindet. Das kann sinnvoll sein, wenn mehrere User an einem System arbeiten.

Folgendes Szenario verdeutlicht den Sachverhalt: Benutzer A lässt zwei Prozesse laufen, Benutzer B dagegen einen. Alle drei Prozesse haben die gleiche Priorität. Der alte O(1)-Scheduler würde dem Benutzer A zwei Drittel und Benutzer B ein Drittel der CPU-Laufzeit zuteilen. Der CFS teilt dagegen beiden Usern 50 % der Rechenzeit zu.<ref name="This is the CFS scheduler" />

Siehe auch

Weblinks

CFS Scheduler – Linux Kernel Documentation
Ingo Molnár: This is the CFS scheduler.
M. Tim Jones: Inside the Linux 2.6 Completely Fair Scheduler. In: IBM developerWorks, 15. Dezember 2009.

Einzelnachweise