Er zijn in de loop der jaren veel beleidsmaatregelen en algoritmen voor schijfplanning ontwikkeld, elk met zijn eigen sterke en zwakke punten. De beste keuze hangt sterk af van de specifieke werklast en systeemvereisten. Hier zijn enkele van de meest voorkomende:
Niet-preventief (verzoeken worden afgehandeld op volgorde van binnenkomst):
* Wie het eerst komt, het eerst maalt (FCFS): Eenvoudigste aanpak; verzoeken worden afgehandeld in de volgorde waarin ze binnenkomen. Zeer eenvoudig te implementeren, maar kan leiden tot aanzienlijke verslechtering van de zoektijd en prestaties, vooral bij wijd verspreide verzoeken. Het is gevoelig voor het creëren van lange konvooien met verzoeken.
* Kortste zoektijd eerst (SSTF): Selecteert het verzoek dat de zoektijd vanaf de huidige hoofdpositie minimaliseert. Verbetert over het algemeen de prestaties ten opzichte van FCFS, maar kan leiden tot uithongering voor verzoeken die ver van de huidige hoofdpositie liggen (het "lifteffect").
Preëmptief (verzoeken kunnen worden onderbroken en opnieuw gerangschikt):
* SCAN (liftalgoritme): De schijfkop beweegt in één richting en beantwoordt onderweg verzoeken. Zodra het het einde bereikt, verandert het van richting en gaat het door met het afhandelen van verzoeken in de tegenovergestelde richting. Eerlijker dan SSTF omdat het hongersnood vermijdt.
* C-SCAN (circulaire SCAN): Vergelijkbaar met SCAN, maar wanneer de kop het einde bereikt, springt deze terug naar het begin zonder onderhoudsverzoeken op de terugreis. Dit zorgt voor een gelijkmatigere verdeling van de service en minder variatie in responstijden dan SCAN.
* KIJK en C-LOOK: Dit zijn respectievelijk varianten van SCAN en C-SCAN. Het verschil is dat ze in plaats van helemaal naar het einde van de schijf te gaan, slechts zo ver gaan als het verste verzoek in de huidige richting. Dit vermindert onnodige hoofdbewegingen.
* FSCAN: Een variant die FCFS en SCAN combineert. Het verwerkt verzoeken in FCFS-volgorde binnen elke SCAN-cyclus.
* Wachtrijplanning op meerdere niveaus: Prioriteert verzoeken op basis van hun type (bijvoorbeeld systeemverzoeken versus gebruikersverzoeken). Voor elke wachtrij kunnen verschillende planningsalgoritmen worden gebruikt.
* Wegingsalgoritmen: Wijs gewichten toe aan verzoeken op basis van belangrijkheid of prioriteit. Hoger gewogen verzoeken krijgen voorrang.
Andere algoritmen en overwegingen:
* Deadlineplanning: Prioriteert verzoeken op basis van hun deadlines. Kritieke verzoeken worden als eerste behandeld om ontbrekende deadlines te voorkomen.
* Adaptieve algoritmen: Pas hun planningsstrategie dynamisch aan op basis van waargenomen systeemgedrag en werklastkenmerken.
* Volledig eerlijke wachtrijen (CFQ): Een Linux-kernelplanner die streeft naar een eerlijke toewijzing van bandbreedte tussen processen. Het is strikt genomen geen schijfplanningsalgoritme, maar heeft een aanzienlijke invloed op de schijf-I/O-prestaties.
* Anticipatie: Sommige geavanceerde algoritmen proberen toekomstige verzoeken te voorspellen op basis van patronen uit het verleden en dienovereenkomstig de hoofdbeweging te optimaliseren.
In de praktijk maken moderne besturingssystemen vaak gebruik van een combinatie van deze algoritmen en andere geavanceerde technieken om de I/O-prestaties van schijven te optimaliseren. De specifieke algoritmen die worden gebruikt, zijn mogelijk niet altijd openbaar gedocumenteerd of gemakkelijk te bepalen. Het beste algoritme is afhankelijk van veel factoren, waaronder schijfkenmerken, I/O-patroon en prestatiedoelen. |