O(n) planlægger

O(n) scheduler [1]  er den scheduler, der bruges i Linux-kernen fra version 2.4 til 2.6. Siden version 2.6.0 er den blevet erstattet af O(1) scheduler og siden 2.6.23 af CFS.

Algoritme

Denne skemalægger opdeler tid i "epoker". Inden for samme epoke blev processerne eksekveret i den tid, de var tildelt. Hvis en proces kørte mindre end den tildelte tid, så blev halvdelen af ​​den tildelte tid lagt til den tid, der vil blive tildelt processen i den næste "epoke". Planlæggeren overvejer alle processer, der er tilgængelige til lancering og finder den proces, hvor værdien af ​​godhedsfunktionen ville være størst.

Fordele

Denne skemalægger klarede sig bedre end sin mere primitive forgænger, som var baseret på en cyklisk kø.

Ulemper

Med en stigning i antallet af processer begynder planlæggerens arbejde at kræve en betydelig mængde processortid. Valget af næste opgave er forbundet med passage af hele listen af ​​processer klar til eksekvering, hvilket betyder at det tager O (n) tid, hvor n er antallet af processer klar til eksekvering. Det var heller ikke egnet til realtidssystemer og kunne ikke skaleres til det nyeste[ hvornår? ] multi-core processorer.

Noter

  1. En kort historie om Linux-planlæggere på ibm.com