Scheduling

Scheduling is de manier waarop processen prioriteiten worden gegeven in een prioriteitenwachtrij van multitasking- en multiprocessing besturingssystemen en in het ontwerp van een realtimebesturingssysteem. Deze taak wordt uitgevoerd door software die bekendstaat als een scheduler of CPU scheduler.

De processor (CPU) moet regelmatig lange tijd wachten op in- en uitvoer. Tijdens deze wachttijd kan dan een deel van een ander proces uitgevoerd worden. Om te bepalen welk proces uitgevoerd mag worden, wordt een scheduler gebruikt. De scheduler moet de processorbelasting balanceren en voorkomen dat één proces alle CPU-tijd gebruikt, of juist geen CPU-tijd krijgt. In realtimeomgevingen, zoals industriële robots, zorgt de scheduler er ook voor dat processen zich aan hun deadline kunnen houden; dit is cruciaal om het systeem stabiel te houden.

Er bestaan verschillende methoden om scheduling te implementeren. Deze kunnen in twee groepen ingedeeld worden:

preemptive scheduling: de processen worden onderbroken tijdens hun uitvoer zodat de scheduler een ander proces kan hervatten. De processen kunnen onderbroken worden
non-preemptive: de scheduler kan pas een ander proces starten nadat het huidige proces klaar is. De processen kunnen niet onderbroken worden

De term scheduler wordt ook gebruikt als benaming voor een programma dat op gezette tijden andere programma's start. Een voorbeeld hiervan is het programma cron in Unix-achtige besturingssystemen. Scheduling met cron gebeurt op een enkele machine. Scheduling op meerdere machines kan met Cronacle van Redwood, AutoSys van Computer Associates of Tivoli Workload Scheduler van IBM.

Databases zoals Oracle en MySQL kennen ook een ingebouwd schedulingmechanisme.

Vereisten voor de scheduler

De verschillende algoritmen hebben verschillende eigenschappen en bij het kiezen van het algoritme voor de scheduler zal het karakter van het besturingssysteem bepalen welk algoritme gekozen wordt. Sommige systemen (bijvoorbeeld realtimebesturingssystemen) stellen strikte eisen aan het algoritme. Een aantal criteria voor de keuze van de scheduler zijn:

CPU-gebruik: de mate waarin de processor gebruikt wordt door de verschillende processen.
debiet: het aantal processen dat zijn werk voltooit in een bepaalde tijd.
turnaround-tijd: de tijd die nodig is om een proces te voltooien.
wachttijd: de som van alle tijd die een proces doorbrengt in een wachtrij.
responstijd: de tijd die nodig is om een reactie te krijgen. Het is de tijd tussen het indienen van een aanvraag en het krijgen van een antwoord.

Voorbeelden van algoritmen

First-come-first-served-scheduling (FCFS)

Dit is het eenvoudigste algoritme. Wanneer een proces als eerste om de cpu vraagt dan zal hij die ook krijgen. Processen die erna komen moeten wachten. Deze vorm van scheduling kan geïmplementeerd worden door een First-in-first-out (FIFO) model. Wanneer een proces lang zal duren, zullen korte processen die erna komen lang moeten wachten.

Shortest-job-first-scheduling (SJF)

Bij dit algoritme zal de scheduler het proces met de kleinste lengte uitvoeren. Een probleem is het voorspellen van de lengte van een proces. Dit kan gedaan worden door bijvoorbeeld het aantal instructies te tellen of het aantal in- en uitvoer aanvragen. Een voordeel ten opzichte van het FCFS-algoritme is dat de wachttijd bij SJF kleiner is. Het SJF-algoritme bestaat in twee vormen, de preemptive en de non-preemptive vorm. Een gevaar bij SJF-scheduling is dat een heel lang proces nooit uitgevoerd zal worden, verhongering (starvation).

Prioriteits-scheduling

Bij dit algoritme zal aan elk proces een prioriteit gekoppeld worden. Deze prioriteiten kunnen extern door de gebruiker of intern door het besturingssysteem toegekend worden. Het besturingssysteem kan de prioriteit van een proces berekenen aan de hand van meetbare waarden. We kunnen het voorgaande SJF-algoritme onderbrengen bij prioriteits-scheduling. Lange processen hebben dan een lagere prioriteit dan korte processen. Ook hier is er gevaar op starvation, een proces met een heel lage prioriteit kan uiteindelijk helemaal niet uitgevoerd worden. Starvation kan opgelost worden door veroudering (aging). Naarmate het proces langer in de wachtrij staat zal zijn prioriteit verhogen.

Round-Robin-scheduling (RR)

In dit scheduling algoritme wordt gebruikgemaakt van een vaste tijdswaarde, ook wel tijdkwantum genoemd. Wanneer dit tijdkwantum overschreden wordt, zal de scheduler het proces onderbreken en een volgend proces inladen. Een moeilijkheid is het bepalen van de grootte van het tijdkwantum. Een te groot tijdkwantum zal ervoor zorgen dat we een FCFS karakter krijgen en een te klein tijdkwantum zal voor een overhead aan context switches zorgen. Een context switch is het wisselen van processen. Wanneer de scheduler een proces onderbreekt zal hij de huidige status van het proces bewaren. Bij een te klein tijdskwantum zal de processor meer bezig zijn met het verwerken van context switches dan met het uitvoeren van processen.

Zie ook

Earliest deadline first scheduling