Uniprocessor planning

Start Omhoog Computersystemen Besturingssystemen Processen Threads Gelijktijdigheid: Wederzijdse uitsluiting Gelijktijdigheid: deadlock en utisterving Geheugenbeheer Virtueel geheugen Uniprocessor planning Multiprocessor en real-time planning Bestandsbeheer I/O beheer en schijfplanning Bash Powershell Begrippen

In een systeem met multiprogrammering kunnen verschillende processen gelijktijdig in het werkgeheugen aanwezig zijn. Elk proces gebruikt afwisselend de processor en wacht tot een bepaalde gebeurtenis optreedt, zoals het voltooien van een I/O-bewerking. De processor of processoren worden aan het werk gehouden door deze een proces uit te laten voeren terwijl de andere processen wachten. De sleutel tot multiprogrammering is planning (scheduling). Meestal zijn hierbij, om precies te zijn, vier soorten scheduling betrokken (tabel 9.1). Een daarvan, I/O-scheduling, wordt voor het gemak behandeld in hoofdstuk 11, dat ingaat op I/O. De overige drie soorten scheduling, die varianten zijn van processorscheduling, worden behandeld in dit en het volgende hoofdstuk.

 

 Dit hoofdstuk begint met een bespreking van de drie vormen processorscheduling en laat zien hoe deze vormen samenhangen. We zien dat scheduling voor de lange termijn en scheduling voor de middellange termijn vooral worden gestuurd door prestatieoverwegingen die samenhangen met de mate van multiprogrammering. Deze kwesties werden tot op zekere hoogte behandeld in hoofdstuk 3 en daarna uitgebreider besproken in hoofdstuk 7 en 8. Daarom concentreren we ons in de rest van dit hoofdstuk op scheduling voor de korte termijn. We beperken ons daarbij tot scheduling in een systeem met één processor, omdat het gebruik van meerdere processors de complexiteit verhoogt. Daarom kunnen we het beste eerst uitgaan van een systeem met één processor, zodat de verschillen tussen de algoritmen voor scheduling duidelijk zichtbaar zijn.

Sectie 9.2 gaat in op de verschillende algoritmen die kunnen worden gebruikt bij het nemen van een beslissing voor scheduling op de korte termijn.

9.1. Types van processorplanning

Het doel van scheduling is het zodanig in de tijd toewijzen van processen die door de processor of processors worden uitgevoerd, dat wordt voldaan aan de doelstellingen van het systeem: voorbeelden hiervan zijn antwoordtijd, doorvoersnelheid of efficiënt gebruik van de processor. Bij veel systemen wordt deze schedulingactiviteit verdeeld in drie afzonderlijke functies: scheduling voor de lange, de middellange en de korte termijn. De namen hebben betrekking op de relatieve tijdschaal waarmee deze functies worden uitgevoerd.

Figuur 9.1 toont de relatie tussen de schedulingfuncties en het overgangsmodel voor procestoestanden (zie figuur 3.8b). Scheduling voor de lange termijn wordt uitgevoerd wanneer een nieuw proces wordt gecreëerd. Dit is de beslissing om een nieuw proces toe te voegen aan de verzameling processen die op dit moment actief zijn. Scheduling voor de middellange termijn is een onderdeel van de swappingfunctie. Dit is een beslissing om een proces toe te voegen aan de processen die zich in elk geval deels in het hoofdgeheugen bevinden en daarmee beschikbaar zijn voor de uitvoering. Scheduling voor de korte termijn is de feitelijke beslissing welk gereedstaand proces als volgende wordt uitgevoerd. Figuur 9.2 is een aangepaste vorm van het toestandsovergangsmodel in figuur 3-8b, dat de interne samenhang van de schedulingfuncties toont.

Scheduling beïnvloedt de prestaties van het systeem, omdat scheduling bepaalt welke processen wachten en welke worden voortgezet. Dit gezichtspunt wordt weergegeven in figuur 9.3, die de wachtrijen toont die betrokken zijn bij de toestandsovergangen van een proces. I In essentie is scheduling een kwestie van het beheren van wachtrijen om wachtrijvertragingen te minimaliseren en prestaties in een wachtrijomgeving te optimaliseren.

9.1.1. Lange-termijn planning

De scheduler voor de lange termijn bepaalt welke programma's voor verwerking worden toegelaten tot het systeem. Deze scheduler bepaalt daarmee de mate van multiprogrammering. Eenmaal toegelaten, wordt een job of gebruikersprogramma een proces dat wordt toegevoegd aan de wachtrij voor de korte-termijnscheduler. Bij sommige systemen begint een zojuist gecreëerd proces in een geswapte toestand in secundair geheugen; in dat geval wordt het toegevoegd aan de wachtrij voor de middellange-termijnscheduler.

Bij een batchsysteem, of bij het batchgedeelte van een algemeen besturingssysteem, worden nieuw toegelaten jobs naar schijf gestuurd en vastgehouden in eer batchwachtrij. Zodra dat kan, creëert de lange-termijnscheduler processen uit deze wachtrij. Hierbij spelen twee beslissingen een rol. In de eerste plaats moet de scheduler beslissen of het besturingssysteem een of meer extra processen kan verwerken. In de tweede plaats moet de scheduler beslissen welke job of jobs worden geaccepteerd en daarmee worden getransformeerd naar processen. We gaan kort in op beide beslissingen.

De beslissing wanneer een proces moet worden gecreëerd, wordt doorgaans gebaseerd op de gewenste mate van multiprogrammering. Hoe meer processen worden gecreëerd, des te kleiner is het percentage tijd dat elk proces krijgt voor uitvoering (omdat meer processen concurreren om dezelfde hoeveelheid processortijd). De lange-termijnscheduler kan dus de mate van multiprogrammering beperken om te zorgen voor voldoende bediening van de huidige verzameling processen. Iedere keer wanneer een job eindigt, kan de scheduler besluiten om een of meer nieuwe jobs toe te voegen. De lange-termijnscheduler kan ook worden aangeroepen als de fractie leeglooptijd van de processor een bepaalde drempel overschrijdt.



De beslissing welke taak als volgende wordt toegelaten, kan eenvoudig worden gebaseerd op het beginsel first-come, first-served (FCFS) of op een hulpmiddel voor het beheren van systeemprestaties. De gebruikte criteria kunnen onder andere worden gebaseerd op prioriteit, verwachte uitvoeringstijd en I/O-vereisten. Als daarover informatie beschikbaar is, kan de scheduler bijvoorbeeld proberen een mengvorm van processorgebonden en I/O-gebonden processen aan te houden.2 De beslissing kan bovendien worden gebaseerd op de I/O-bronnen die worden gevraagd, in een poging een balans te vinden in het I/O-gebruik.

Bij interactieve programma’s in een timesharingsysteem wordt een procesverzoek gegenereerd door de handeling waarmee een gebruiker probeert verbinding te maken met het systeem. Gebruikers van een timesharingsysteem kunnen niet zomaar aansluiten in de wachtrij en wachten totdat het systeem ze kan accepteren. In plaats daarvan accepteert het besturingssysteem alle geautoriseerde nieuwkomers totdat het systeem verzadigd is, waarbij wordt uitgegaan van een van tevoren vastgestelde norm voor het verzadigingspunt. Is dat punt bereikt, dan wordt een verzoek om verbinding beantwoord met een bericht dat meldt dat het systeem vol is en dat de gebruiker het later nog eens moet proberen.

9.1.2. Middellange-termijn planning

Scheduling voor de middellange termijn is een onderdeel van de swappingfunctie. De onderwerpen die hiermee samenhangen, werden besproken in hoofdstuk 3,7 en 8. Doorgaans wordt de beslissing om een opgeschort proces naar het hoofdgeheugen te swappen, gebaseerd op de noodzaak de mate van multiprogrammering te beheren. Ook bij systemen die geen virtueel geheugen gebruiken, speelt geheugen- beheer een rol. Bij de beslissing om naar het hoofdgeheugen te swappen wordt daarom uitgegaan van de geheugenvereisten van de uitgeswapte processen.

9.1.3. Korte-termijn planning

In termen van uitvoeringsfrequentie, wordt de lange-termijnscheduler relatief weinig uitgevoerd; deze neemt de grove beslissing of een nieuwe job al dan niet wordt geaccepteerd en welke nieuwe job wordt toegelaten. De middellange-termijnscheduler wordt iets vaker uitgevoerd om de swappingbeslissing te nemen. De scheduler voor de korte termijn, ook wel de toedeler (dispatcher) genoemd, wordt het vaakst uitgevoerd en neemt veelvuldig de beslissing welk proces als volgende de processor mag gebruiken.

De korte-termijnscheduler (dispatcher) wordt geactiveerd bij het optreden van een gebeurtenis die kan leiden tot het opschorten van het huidige proces of die de gelegenheid biedt een thans actief proces preëmptief te onderbreken ten gunste van een ander proces. Voorbeelden van zulke gebeurtenissen zijn:

  • Klokinterrupts;
  • I/O-interrupts;
  • Besturingssysteemaanroepen;
  • Signalen.
  • 9.2. Planningsalgoritmes

    9.2.1. Korte-termijn planningscriteria

    Het belangrijkste doel van scheduling voor de korte termijn is het zodanig toewijzen van processortijd dat een of meer aspecten van het systeemgedrag worden geoptimaliseerd. Vaak wordt een aantal criteria opgesteld waarmee verschillende schedulingstrategieën kunnen worden beoordeeld.

    De meest gebruikte criteria kunnen in twee richtingen worden opgedeeld in categorieën. In de eerste plaats kunnen we een onderscheid maken tussen gebruikergerichte en systeemgerichte criteria. Gebruikergerichte criteria hangen samen met het gedrag van het systeem zoals de individuele gebruiker of een proces dat waarneemt Een voorbeeld is de antwoordtijd in een interactief systeem. De antwoordtijd is de tijd die verstrijkt tussen het moment waarop een verzoek wordt ingediend en het moment waarop het eerste antwoord verschijnt als uitvoer. Deze kwantiteit is zichtbaar voor de gebruiker en is vanzelfsprekend van belang voor de gebruiker. We streven naar een schedulingstrategie die voorziet in een ‘goede’ bediening van verschillende gebruikers. Voor de antwoordtijd zou een drempel kunnen worden gedefinieerd, bijvoorbeeld twee seconden. Een doel van het schedulingmechanisme zou dan kunnen zijn het aantal gebruikers die een gemiddelde antwoordtijd van twee seconden of minder krijgen, te maximaliseren.

    Andere criteria zijn systeemgericht. Dat wil zeggen: de aandacht gaat uit naar een effectief en efficiënt processorgebruik. Een voorbeeld is de doorvoer (throughput): de snelheid waarmee processen worden voltooid. Dit is beslist een van de meest waardevolle meeteenheden voor de systeemprestaties en een meeteenheid die we graag zouden willen maximaliseren. Dit criterium gaat echter uit van systeemprestaties in plaats van de bediening van de gebruiker. Doorvoer is daarom van belang voor een systeembeheerder, maar niet voor gebruikers.

    Gebruikergerichte criteria zijn belangrijk bij vrijwel alle systemen, maar systeemgerichte criteria zijn in het algemeen nauwelijks van belang bij systemen met één gebruiker. Zolang de snelheid waarmee het systeem reageert op gebruikerstoepassingen aanvaardbaar blijft, is het bereiken van een hoge bezettingsgraad van de processor of een hoge doorvoer bij een systeem met één gebruiker waarschijnlijk onbelangrijk.

    Een tweede invalshoek voor de classificatie van criteria zijn de criteria die samenhangen met prestaties en de criteria die niet direct samenhangen met prestaties. Met prestaties samenhangende criteria zijn kwantitatief en kunnen meestal eenvoudig worden gemeten. Voorbeelden zijn de antwoordtijd en de doorvoer. Criteria die niet samenhangen met prestaties, zijn kwalitatief van aard of zijn niet eenvoudig te meten en analyseren. Een voorbeeld van zo’n criterium is de voorspelbaarheid. We willen graag dat de bediening van gebruikers bepaalde kenmerken vertoont in de tijd, onafhankelijk van ander werk dat het systeem uitvoert. Dit criterium kan tot op zekere hoogte worden gemeten, door variaties te berekenen als functie van de werklast. Dit is echter lang niet zo eenvoudig als het meten van de doorvoer of de antwoordtijd als functie van de werklast.

    Tabel 9.2 vat de belangrijkste criteria voor scheduling samen. De criteria hangen samen en het is onmogelijk ze alle tegelijkertijd te optimaliseren. Een goede antwoordtijd kan bijvoorbeeld een schedulingalgoritme vereisen dat vaak wisselt tussen processen; dit verhoogt de overhead van het systeem en reduceert daarmee de doorvoer. Het ontwerpen van een schedulingstrategie bestaat daarom uit het vinden van een evenwicht in concurrerende vereisten; het relatieve gewicht dat wordt toegekend aan de verschillende vereisten, is afhankelijk van de aard en het gebruik van het systeem.

    Bij de meeste interactieve besturingssystemen, zowel besturingssystemen voor één gebruiker als besturingssystemen met timesharing, is een toereikende antwoordtijd de kritieke vereiste. Omdat deze vereiste belangrijk is en omdat de definitie van ‘toereikend’ van toepassing tot toepassing verschilt, wordt de antwoordtijd uitgebreider behandeld in de bijlage bij dit hoofdstuk.

    9.2.2. Het gebruik van prioriteiten

    Bij veel systemen wordt een prioriteit toegekend aan elk proces en geeft de dispatcher (korte-termijnscheduler) een proces met hogere prioriteit altijd voorrang boven een proces met lagere prioriteit. Figuur 9.4 illustreert het gebruik van prioriteiten. Voor de duidelijkheid is het wachtrijschema vereenvoudigd en wordt het bestaan van meerdere wachtrijen voor de toestanden Geblokkeerd en Opgeschort genegeerd (vergelijk figuur 3.7a). In plaats van één wachtrij Gereed (RQ) gebruiken we een verzameling wachtrijen met een aflopende prioriteit: RQ0, RQ1, ..., RQn met prioriteit [RQi] > prioriteit [RQj] als i < j. Moet een schedulingbeslissing worden genomen, dan begint de scheduler met de wachtrij Gereed met de hoogste prioriteit (RQ0). Bevat de wachtrij een of meer processen, dan wordt een proces geselecteerd met een bepaalde schedulingstrategie. Is RQ0 leeg, dan wordt RQ1 onderzocht enzovoort.

    Een probleem met een schedulingstrategie die uitsluitend uitgaat van de prioriteit, is dat processen met een lagere prioriteit kunnen verhongeren (starvation). Dat kan gebeuren als er een voortdurende aanvoer is van gereedstaande processen met een hogere prioriteit. Als dit gedrag niet gewenst is, kan de prioriteit van een proces worden aangepast aan de verblijfsduur of aan de verwerkingsgeschiedenis ervan. Verderop geven we hiervan een voorbeeld.

    9.2.3. Mogelijke strategieën voor scheduling

    Tabel 9.3 toont enige samenvattende informatie over de verschillende schedulingstrategieën die in deze paragraaf worden behandeld. De selectiefunctie bepaalt welk proces van alle gereedstaande processen als volgende wordt geselecteerd voor uitvoering. Deze functie kan worden gebaseerd op de prioriteit, de vereiste systeem- bronnen of de uitvoeringskenmerken van het proces. In het laatste geval zijn drie grootheden van belang:

  • w = tijd die wachtend is doorgebracht;
  • e = tijd die tot dusverre is besteed aan verwerking;
  • s = totale bedieningstijd die vereist is voor het proces, inclusief e; in het algemeen moet deze grootheid worden geschat of worden aangegeven door de gebruiker.
  • De selectiefunctie max [w] wijst bijvoorbeeld op de beslissingsregel first-come, first-served (FCFS).

    De beslissingsmodus bepaalt op welke tijdstippen de selectiefunctie wordt Uitgevoerd. Hiervoor bestaan twee algemene categorieën:

  • Niet-preëmptief. Bevindt een proces zich hierbij in de toestand Actief (running), dan wordt de verwerking van het proces voortgezet totdat (a) het proces wordt beëindigd of (b) het zichzelf blokkeert om op I/O te wachten of door een bepaalde systeemdienst aan te roepen.
  • Preëmptief. Het proces dat op dit moment wordt uitgevoerd, kan worden onderbroken en naar de toestand Gereed (ready) worden verplaatst door het besturingssysteem. De beslissing een proces preëmptief te onderbreken kan worden genomen bij de aankomst van een nieuw proces, bij het optreden van een interrupt waardoor een geblokkeerd proces in de toestand Gereed komt. Of periodiek op basis van een klokinterrupt.
  • Een preëmptieve strategie heeft een grotere overhead dan een niet-preëmptieve strategie, maar kan zorgen voor een betere bediening van de gehele populatie van processen, omdat het verhindert dat één proces de processor te lang voor zich alleen opeist. Bovendien kunnen de kosten van een preëmptieve verwerking relatief laag worden gehouden door het gebruik van efficiënte mechanismen voor proceswisseling (met zoveel mogelijk ondersteuning door de hardware) en door het gebruik van een groot hoofdgeheugen, om een hoog percentage programma’s aan te houden in het hoofdgeheugen.

    Bij onze beschrijving van de verschillende schedulingstrategieën zullen we de verzameling processen in tabel 9.4 steeds gebruiken als doorlopend voorbeeld. We kunnen deze processen beschouwen als batchjobs, waarbij de bedieningstijd de totale tijd is die vereist is voor de verwerking. We kunnen ze ook beschouwen als doorlopende processen die in een voortdurend herhaalde cyclus wisselend gebruik maken van de processor en I/O. In het laatste geval is de bedieningstijd de processortijd die nodig is tijdens één cyclus. In termen van het wachtrij model komt deze grootheid in beide gevallen overeen met de bedieningstijd.

    Voor het voorbeeld uit tabel 9.4, toont figuur 9.5 het uitvoerend patroon van een cyclus. Tabel 9.5 laat enkele van de belangrijkste resultaten zien. Eerst wordt de eindtijd van elk proces bepaald. Daaruit kunnen we de omlooptijd afleiden. In termen van het wachtrijmodel is de omlooptijd (turnaround time of TAT) de totale tijd Tr (residence time) die een element doorbrengt in het systeem (wachttijd plus bedieningstijd). Een nuttigere figuur is de genormaliseerde omlooptijd, deze is gelijk aan de ratio van de omlooptijd tot de totale bedieningstijd. Deze waarde geeft de relatieve vertraging ontstaan tijdens een proces. Hierbij geldt dat hoe langer de procesverwerkingstijd is, hoe groter het totale vertragingsgetal mag zijn. De laagst mogelijke waarde voor deze ratio is 1.0; hogere waarden staan voor een lager bedieningsniveau.

    9.2.3.1. First-Come-First-Served

    De eenvoudigste schedulingstrategie is first-come, first-served (FCFS), ook bekend als first in, first out (FIFO) of als strikte rijvolgorde. Is een proces gereed, dan wordt het toegevoegd aan de wachtrij Gereed. Wordt de uitvoering van het thans actieve proces gestopt, dan wordt het oudste proces in de wachtrij Gereed geselecteerd voor uitvoering.

    Een ander probleem van FCFS is dat het de neiging heeft processorgebonden processen voorrang te geven boven I/O-gebonden processen. Ga bijvoorbeeld uit van een verzameling processen waarvan er één voornamelijk de processor gebruikt (processorgebonden) en de overige een voorliefde hebben voor I/O (I/O-gebonden). Wordt het processorgebonden proces uitgevoerd, dan moet alle I/O-gebonden processen wachten. Enkele kunnen zich in I/O-wachtrijen bevinden (in de toestand Geblokkeerd), maar kunnen terugkeren naar de wachtrij Gereed terwijl het processorgebonden proces wordt uitgevoerd. In die situatie hebben de meeste of alle I/O-apparaten niets te doen, hoewel potentieel werk ligt te wachten. Verlaat het op dit moment uitgevoerde proces de toestand Actief, dan krijgen de gereedstaande, I/O-gebonden processen snel na elkaar de toestand Actief en worden vervolgens geblokkeerd op I/O-opdrachten. Wordt ook het processorgebonden proces geblokkeerd, dan heeft de processor niets meer te doen. FCFS kan dus leiden tot een inefficiënt gebruik van zowel de processor als de I/O-apparaten.

    FCFS is op zich geen aantrekkelijk alternatief voor een systeem met één processor. FCFS wordt echter vaak met een prioriteitensysteem gecombineerd tot een effectieve scheduler (dispatcher). De scheduler kan dan meerdere wachtrijen bijhouden. Een voor elk prioriteitsniveau, en de processen binnen elke wachtrij toedelen via first-come, first-served. Verderop laten we een voorbeeld van zo’n systeem zien bij de bespreking van scheduling met feedback.

  • Is gelijk aan FIFO of strikt wachtrijsysteem
  • Als proces “Ready” wordt, wordt deze geplaatst in de “Ready” wachtrij.
  • Als huidige draaiende proces stopt met uitvoeren, nemen we het eerste “Ready” proces uit de wachtrij, dat is dus het proces dat al het langste in de wachtrij zit.
  • Dit wachtrijsysteem is goed voor lange processen
  • Goed alternatief voor een uniprocessorsysteem
  • Meestal gecombineerd met een prioriteitensysteem
  • Een wachtrij per prioriteit
  • De TurnaroundTime (Wachttijd + Uitvoeringstijd) is de totale tijd dat een proces spendeert in ons systeem.

    9.2.3.2. Round Robin

    Het nadelige effect van FCFS voor korte jobs kan gemakkelijk worden verminderd door preëmptieve onderbreking op basis van een klok te gebruiken. De eenvoudigste variant van zo’n strategie is round robin (RR). Hierbij wordt een klokinterrupt gegenereerd met periodieke intervallen. Treedt de interrupt op, dan wordt het proces dat op dit moment wordt verwerkt, in de wachtrij Gereed geplaatst en wordt het volgende klaarstaande proces geselecteerd op basis van FCFS. Deze techniek wordt ook wel tijdopdeling (time slicing) genoemd, omdat elk proces een bepaalde hoeveelheid tijd krijgt voordat het wordt onderbroken.

    Bij round robin is het belangrijkste aandachtspunt bij het ontwerp de lengte van het tijdquantum (de grootte van de ‘slice’). Is het quantum erg kort, dan bewegen korte processen relatief snel door het systeem. Daar staat tegenover dat het verwerken van de klokinterrupt en het uitvoeren van de scheduling en toedeling overhead met zich meebrengen. Zeer korte tijdkwanta moeten daarom worden vermeden. Een bruikbare richtlijn is dat het tijdkwantum iets groter moet zijn dan de tijd die nodig is voor een doorsnee ‘interactie’ of procesfunctie. Is het quantum kleiner, dan zullen de meeste processen ten minste twee tijdkwanta vereisen. Figuur 9.6 illustreert de invloed hiervan op de antwoordtijd. Merk op dat round robin overeenkomt met FCFS zodra het tijdquantum langer is dan het langst uitgevoerde proces.

    Round robin is vooral effectief in een algemeen systeem voor timesharing of transactieverwerking. Een nadeel van round robin is de ongelijke behandeling van processorgebonden en I/O-gebonden processen. In het algemeen heeft een I/O- gebonden proces een kortere processorburst (de hoeveelheid tijd die tussen I/O- bewerkingen aan de uitvoering wordt besteed) dan een processorgebonden proces. Is er een mengvorm van processorgebonden en I/O-gebonden processen, dan kan het volgende gebeuren: een I/O-gebonden proces gebruikt de processor gedurende een korte periode en wordt vervolgens geblokkeerd voor I/O; het wacht totdat de I/O-bewerking is voltooid en wordt vervolgens toegevoegd aan de wachtrij Gereed. Een processorgebonden proces daarentegen, gebruikt meestal het volledig tijdquantum voor de verwerking en keert vervolgens onmiddellijk terug naar de wachtrij Gereed. Een processorgebonden proces zal daardoor een onredelijk deel van de processortijd krijgen, wat leidt tot slechte prestaties van I/O-gebonden processen.

    Hoe kan men het nadelige effect van FCFS oplossen voor korte processen?

  • Voortijdige beëindiging op basis van een klok (regelmatige intervallen)
  • De eenvoudigste variant van zo’n strategie is round robin (RR)
  • Als huidige draaiende proces wordt onderbroken:

  • Huidige proces naar de “Ready” wachtrij verplaatsten

  • Eerste klaarstaande proces uit de wachtrij nemen volgens FCFS.

  • Time slicing:

  • Voordeel: Elk proces krijgt per deel evenveel tijd om uit te voeren.
  • Nadeel: Een proces kan meerdere intervallen nodig hebben voor de uitvoering ervan.
  • Wat is nu een goede waarde voor het interval?

  • Indien te kort, te veel overhead bij het afhandelen van kleine processen
  • Korte interval vermijden
  • Interval moet net groter zijn dan de uitvoeringstijd van een normaal proces
  • Indien kleiner zijn er twee intervallen nodig voor een proces om uitgevoerd te geraken
  • 9.2.3.3. Shortest Proces Next

    Een andere benadering die de bevoordeling van lange processen van FCFS vermindert, is de strategie kortste proces eerst (shortestprocess next, SPN). Dit is een niet-preëmptieve strategie waarbij het proces met de kortste verwachte verwerkingstijd het eerst wordt geselecteerd. Een kort proces springt daardoor voorbij langere processen naar het begin van de wachtrij.

    Een risico bij SPN is dat de mogelijkheid bestaat dat langere processen verhongeren zolang er regelmatige aanvoer van kortere processen is. Hoewel SPN de bevoordeling van langere processen vermindert, is ook SPN ongewenst in een omgeving voor timesharing of transactieverwerking, omdat preëmptieve onderbreking ontbreekt.

  • Kiezen van het proces met kleinste verwachte verwerkingstijd
  • Voordeel: geen voortijdige beëindiging
  • Nadeel: mogelijkheid tot uithongering van langere processen
  • 9.2.3.4. Shortest Remaining Time

    De strategie kortste resterende tijd (shortest remaining time, SRT) is een preëmptieve versie van SPN. Bij SRT kiest de scheduler altijd het proces dat de kortste, verwachte, resterende verwerkingstijd heeft. Wordt een nieuw proces toegevoegd aan de wachtrij Gereed, dan kan het een kortere resterende tijd hebben dan het proces dat op dit moment wordt uitgevoerd. Daarom kan de scheduler een proces preëmptief onderbreken zodra een nieuw proces de toestand Gereed krijgt. Net zoals bij SPN moet de scheduler een schatting van de verwerkingstijd gebruiken voor het uitvoeren van de selectiefunctie en bestaat het risico dat langere processen verhongeren.

  • De strategie kortste resterende tijd (SRT) is een versie van kortste proces eerst (SPN) met voortijdige beëindiging.
  • Een proces kiezen met de kleinste verwachte resterende verwerkingstijd.
  • Indien we een nieuw proces toevoegen aan de wachtrij met kleinere verwerkingstijd dan het huidig draaiend proces dan moeten we het huidige proces onderbreken en een nieuw proces uitvoeren.
  • Voordeel: Korte jobs/processen worden onmiddellijk uitgevoerd.
  • Nadeel: Mogelijkheid tot uithongering van langere processen.
  • 9.2.3.5. Highest Response Rate Next

    In tabel 9.5 hebben we de genormaliseerde omlooptijd, de verhouding tussen omlooptijd en werkelijke bedieningstijd, gebruikt als maatstaf. Voor elk afzonderlijk proces willen we deze ratio minimaliseren en we willen de gemiddelde waarde minimaliseren voor alle processen. In het algemeen kunnen we niet vooraf weten hoeveel deze waarde zal zijn. Maar we kunnen deze waarde benaderen op basis van waarnemingen of op basis van een opgave van de gebruiker of systeembeheerder. Van belang hierbij is de volgende verhouding (ratio):

    R = (w + s) / s

    waarbij

    R = responseverhouding;

    w = tijd voor wachten op de processor;

    s = verwachte bedieningstijd.

    Wordt het proces met deze waarde onmiddellijk uitgevoerd, dan is R gelijk aan de genormaliseerde omlooptijd. Merk op dat de minimumwaarde van R 1,0 is, wat het geval is wanneer een proces voor het eerst het systeem binnenkomt.

    Onze schedulingregel luidt daarmee als volgt: is het huidige proces voltooid of geblokkeerd, kies dan het gereedstaande proces met de grootste waarde van R. Deze benadering is aantrekkelijk, omdat zij rekening houdt met de leeftijd van het proces. Kortere processen worden weliswaar bevoordeeld (een kleinere noemer geeft een grotere verhouding), maar bij veroudering zonder bediening stijgt de verhouding, zodat een langere job uiteindelijk voorrang krijgt boven concurrerende, kortere jobs.

    Net zoals bij SRT en SPN moet bij het gebruik van highest response ratio next (HRRN) de verwachte bedieningstijd worden geschat.

  • Volgende proces is het proces met de grootste R waarde.
  • In het begin zijn korte jobs in het voordeel.
  • Na verloop van tijd komen langere jobs eerst.
  • Voordeel: Processen die lang wachten krijgen voorrang.
  • 9.2.3.6. Feedback

    Hebben we geen indicatie van de relatieve lengte van de verschillende processen, dan kunnen we SPN, SRT en HRRN niet gebruiken. Een andere mogelijkheid om voorrang te geven aan kortere processen is het straffen van taken die al langer worden uitgevoerd. Met andere woorden: weten we niets over de resterende uitvoeringstijd, dan kunnen we ons richten op de tijd die tot nu toe is besteed aan de verwerking.

    Hierbij moet men als volgt te werk gaan. De scheduling gebruikt preëmptief onderbreken (met een tijdquantum) en gebruikt een mechanisme voor dynamische prioriteit. Komt een proces voor het eerst het systeem binnen, dan wordt het in RQ0 geplaatst (zie figuur 9.4). Is het voor de eerste keer uitgevoerd en keert het terug naar de toestand Gereed, dan wordt het proces in RQ1 geplaatst. Elke volgende keer wordt het gedegradeerd naar de volgende wachtrij met een lagere prioriteit. Een korter proces wordt snel voltooid, zonder dat het ver omlaag beweegt in deze hiërarchie van wachtrijen. Een langdurig proces zal geleidelijk omlaag zakken. Daardoor krijgen jongere, kortere processen voorrang boven oudere, langere processen. Binnen elke wachtrij, met uitzondering van de wachtrij met de laagste prioriteit, wordt een eenvoudig FCFS-mechanisme gebruikt. Bevindt een proces zich eenmaal in de wachtrij met de laagste prioriteit, dan kan het niet verder degraderen, maar keert herhaaldelijk terug naar deze wachtrij totdat de uitvoering is voltooid. Deze wachtrij wordt daarom behandeld volgens het mechanisme round robin.

    Figuur 9.10 illustreert het schedulingmechanisme met terugkoppeling (feedback FB) aan de hand van het pad dat een proces volgt door de diverse wachtrijen. Deze benadering wordt feedback met meerdere niveaus (multilevel feedback) genoemd. waarmee wordt bedoeld dat het besturingssysteem de processor toewijst aan een proces en het proces terugplaatst in een van de prioriteitswachtrijen wanneer het wordt geblokkeerd of preëmptief wordt onderbroken.

  • Deze techniek geeft voorrang aan kortere processen door het straffen van taken die al langer worden uitgevoerd.
  • Deze techniek maakt gebruikt van voortijdige beëindiging.
  • Bij het aanmaken kennen we hoogste prioriteit en bij elke voortijdige beëindiging verlagen we de prioriteit
  • 9.2.4. Prestatievergelijking

    Het spreekt voor zich dat de prestaties van de verschillende strategieën voor scheduling een kritieke factor zijn bij de keuze van een schedulingstrategie. Het is echter onmogelijk absolute vergelijkingen te maken, omdat de relatieve prestaties afhankelijk zijn van verschillende factoren. Denk hierbij aan de waarschijnlijkheidsverdeling van de bedieningstijden van de diverse processen, de efficiëntie van het mechanisme voor scheduling en contextwisseling, de vorm van I/O-vraag en de prestaties van het I/O-subsysteem.

    9.2.5. Fair-share planning

    Alle schedulingalgoritmen die tot nu toe zijn besproken, behandelen de verzameling gereedstaande processen als één reservoir van processen waaruit het volgende proces wordt geselecteerd voor uitvoering. Dit reservoir kan worden opgesplitst op basis van prioriteit, maar in alle andere opzichten is het homogeen.

    Als echter toepassingen en taken van een individuele gebruiker bij een systeem voor meerdere gebruikers kunnen worden georganiseerd als meerdere processen (of threads), heeft de verzameling processen een structuur die niet wordt herkend door de traditionele scheduler. Vanuit de gebruiker gezien zijn niet zozeer de prestaties van één bepaald proces van belang, maar vooral de prestaties van de groep processen die gezamenlijk één toepassing vormen. Daarom is het zinvol schedulingbeslissingen te nemen op basis van dergelijke procesgroepen. Deze benadering wordt doorgaans eerljk-delenscheduling (fair-share scheduling) genoemd. Dit concept kan verder worden uitgebreid tot groepen gebruikers, zelfs als één gebruiker overeenkomt met één proces. Bij een timesharingsysteem kunnen we bijvoorbeeld alle gebruikers van een bepaalde afdeling beschouwen als leden van dezelfde groep. Schedulingbeslissingen kunnen dan worden genomen op basis van het streven elke groep een vergelijkbare service te geven. Meldt zich een groot aantal mensen van dezelfde afdeling aan bij het systeem, dan zien we daarom graag dat een afname van de antwoordtijd vooral ten laste van die afdeling komt en niet van de gebruikers van andere afdelingen.

  • De voorgaande schedulingalgoritmes zien alle processen als één verzameling waaruit het volgende proces wordt gekozen.
  • Indien we multithreading hebben dan wordt dit niet benut door die schedulers
  • Scheduling wordt gedaan op basis van een groep van processen/toepassingen en hun prioriteit
  • Fair-share: Elke gebruiker krijgt een even groot aandeel uitvoeringstijd volgens zijn “gewicht” (prioriteit).

    Herhalingsvragen

    1. Beschrijf in het kort de drie soorten scheduling van de processor.

      Scheduling voor de lange termijn: De beslissing een proces toe te voegen aan de verzameling processen die worden uitgevoerd.
      Scheduling voor de middellange termijn:
      De beslissing een proces toe te voegen aan de processen die zich gedeeltelijk of geheel in het hoofdgeheugen bevinden.
      Scheduling voor de korte termijn:
      De beslissing welk beschikbaar proces zal worden uitgevoerd door de processor.
       
    2. Wat is meestal de belangrijkste verwerkingsvereiste bij een interactief besturingssysteem?

      Reactietijd.
       
    3. Wat is het verschil tussen omlooptijd en antwoordtijd?

      Omlooptijd is het tijdsinterval tussen het indienen en het voltooien van een proces.
      Antwoordtijd de tijd tussen het indienen van een verzoek en het moment waarop de ontvangst van het antwoord begint.
       
    4. Geeft een lage prioriteitswaarde bij processcheduling een lage of een hoge prioriteit aan?

      In UNIX en veel andere systemen betekent een kleine prioriteitswaarde een hoge prioriteit van het proces. In principe houden we hier de conventie aan. Bij sommige andere systemen, zoals Windows, geldt een tegenovergestelde afspraak: een grote waarde betekent een hoge prioriteit.
       
    5. Wat is het verschil tussen preëmptieve en niet-preëmptieve scheduling?

      Niet-preëmptief: Als een proces zich in de toestand Actief (running) bevindt, dan wordt de verwerking van het proces voortgezet totdat (a) het proces wordt beëindigd of (b) het zichzelf blokkeert om op I/O te wachten of door een bepaalde systeemdienst aan te roepen.
      Preëmtief: Het proces dat op dit moment wordt uitgevoerd, kan worden onderbroken en naar de toestand Gereed (ready) worden verplaatst door het besturingssysteem. De beslissing een proces preëmptief te onderbreken kan worden genomen bij de aankomst van een nieuw proces, bij het optreden van een interrupt waardoor een geblokkeerd proces in de toestand Gereed komt, of periodiek op basis van een klokinterupt.
       
    6. Beschrijf in het kort scheduling met first come. first served (FCFS).

      Als een proces gereed is, dan wordt het toegevoegd aan de wachtrij Gereed. Wordt de uitvoering van het thans actieve proces gestopt, dan wordt het oudste proces in de wachtrij Gereed geselecteerd voor uitvoering.
       
    7. Beschrijf in het kort scheduling met round robin (RR).

      Een klokinterrupt wordt gegenereerd met periodieke intervallen. Treedt een interrupt op, dan wordt het proces dat op dit moment wordt verwerkt, in de wachtrij Gereed geplaatst en wordt het volgende klaarstaande proces geselecteerd op basis van FCFS.
       
    8. Beschrijf in het kort scheduling met shortest process next (SPN).

      Dit is een niet-preëmptieve strategie waarbij het proces met de kortste verwachte verwerkingtijd het eerst wordt geselecteerd.
       
    9. Beschrijf in het kort scheduling met shortest remaining time (SRT).

      Dit is een preëmptieve versie van SPN. Bij SRT kiest de scheduler altijd het proces dat de kortste, verwachte, resterende verwerkingstijd heeft. Wordt een een nieuw proces toegevoegd aan de wachtrij Gereed, dan kan het een kortere resterende tijd hebben dan het proces dat op dit moment wordt uitgevoerd. Daarom kan de scheduler een proces preëmptief onderbreken zodra een nieuw proces de toestand Gereed krijgt.
       
    10. Beschrijf in het kort scheduling met highest response ratio next (HRRN).

      Als het huidig proces is voltooid of geblokkeerd, kies dan het gereedstaande proces met de grootste waarde van R, waar R = (w + s)/s, met w = tijd voor wachten op de processor en s = verwachte bedieningstijd. 
       
    11. Beschrijf in het kort scheduling met feedback (FB).

      De scheduling gebruikt preëmptief onderbreken (met een tijdquantum) en gebruikt een mechanisme voor dynamische prioriteit. Komt een proces voor het eerst het systeem binnen, dan wordt het in RQ0 geplaatst (zie figuur 9.4). Is het voor de eerste keer uitgevoerd en keert het terug naar de toestand Gereed, dan wordt het proces in RQ1 geplaatst. Elke volgende keer wordt het gedegradeerd naar de volgende wachtrij met een lagere prioriteit. Een korter proces wordt snel voltooid, zonder dat het ver omlaag beweegt in deze hiërarchie van wachtrijen. Een langdurig proces zal geleidelijk omlaag zakken. Daardoor krijgen jongere, kortere processen voorrang boven oudere, langere processen. Binnen elke wachtrij, met uitzondering van de wachtrij met de laagste prioriteit, wordt een eenvoudig FCFS-mechanisme gebruikt. Bevindt een proces zich eenmaal in de wachtrij met de laagste prioriteit, dan kan het niet verder degraderen, maar keert herhaaldelijk terug naar deze wachtrij totdat de uitvoering is voltooid.

    Probleemvraagstukken

    1. Consider the following workload:

      Show the schedule using shortest remaining time, nonpreemptive priority (a smaller priority number implies higher priority) and round robin with quantum 30 ms. Use time scale diagram as shown below for the FCFS example to show the schedule for each requested scheduling policy.
      Example for FCFS (1 unit = 10 ms):



      What is the average waiting time of the above scheduling policies?
       
    2. Consider the following set of processes:



      Perform the same analysis as depicted in Table 9.5 and Figure 9.5 for this set.
       
    3. Prove that, among nonpreemptive scheduling algorithms, SPN provides the minimum average waiting time for a batch of jobs that arrive at the same time. Assume that the scheduler must always execute a task if one is available.
       
    4. Assume the following burst-time pattern for a process: 6, 4, 6, 4, 13, 13, 13, and assume that the initial guess is 10. Produce a plot similar to those of Figure 9.9.
       
    5. Consider the following pair of equations as an alternative to Equation (9.3):
      Sn+1 = αTn + (1 - α)Sn
      Xn+1 = min[Ubound, max[Lbound, (βSn+1)]]
      where Ubound and Lbound are prechosen upper and lower bounds on the estimated value of T. The value of Xn+1 is used in the shortest-process-next algorithm, instead of the value of Sn+1. What functions do α and β perform, and what is the effect of higher and lower values on each?
       
    6. In the bottom example in Figure 9.5 , process A runs for two time units before control is passed to process B. Another plausible scenario would be that A runs for three time units before control is passed to process B. What policy differences in the feedbackscheduling algorithm would account for the two different scenarios?
       
    7. In a nonpreemptive uniprocessor system, the ready queue contains three jobs at time t immediately after the completion of a job. These jobs arrived at times t1, t2, and t3 with estimated execution times of r1, r2 , and r3 , respectively. Figure 9.18 shows the linear increase of their response ratios over time. Use this example to find a variant of response ratio scheduling, known as minimax response ratio scheduling, that minimizes the maximum response ratio for a given batch of jobs ignoring further arrivals. (Hint: Decide, first, which job to schedule as the last one.)
       
    8. Prove that the minimax response ratio algorithm of the preceding problem minimizes the maximum response ratio for a given batch of jobs. ( Hint : Focus attention on the job that will achieve the highest response ratio and all jobs executed before it. Consider the same subset of jobs scheduled in any other order and observe the response ratio of the job that is executed as the last one among them. Notice that this subset may now be mixed with other jobs from the total set.)
       
    9. De verblijfstijd Tr, wordt gedefinieerd als de gemiddelde totale tijd die een proces besteedt aan wachten en bediend worden. Laat zien, voor FIFO met een gemiddelde bedieningstijd Ts dat Tr = Ts/(1-ρ), geldt,waarbij ρ staat voor bezettingsgraad.
       
    10. Op een processor wordt verweving met oneindige snelheid toegepast voor alle processen zonder overhead in de wachtrij Gereed. (Dit is een geïdealiseerd model van round-robinscheduling van gereedstaande processen, waarbij tijddeling wordt gebruikt met tijdkwanta die in verhouding tot de gemiddelde bedieningstijd teer klein zijn.) Toon aan dat, uitgaande van een oneindige bron van invoer met een Poisson-verdeling en exponentiële bedieningstijden, de gemiddelde antwoordtijd Rx van een proces met bedieningstijd x gelijk is aan Rx = x/(1-ρ). (Aanwijzing: bekijk de wachtrijvergelijkingen in het document Queuing Analysis bij WilliamStallingscom/StudentSupport_html. Ga vervolgens uit van het aantal wachtende elementen. w, in het systeem na aankomst van het betreffende proces.).
       
    11. De meeste round-robinschedulers gebruiken een quantum met een vaste grootte.
      1. Noem een voordeel van een klein quantum.
      2. Noem vervolgens een voordeel van een groot quantum.
      3. Vergelijk de soorten systemen en jobs waarbij deze voordelen gelden. Zijn er systemen en jobs waarbij kleine en grote kwanta beide voordelig zijn?
         
    12. In een wachtrijsysteem moeten nieuwe jobs even wachten voordat ze worden bediend. Terwijl een job wacht. neemt zijn prioriteit lineair toe in de tijd vanaf nul met een snelheid α. Een job wacht totdat zijn prioriteit het niveau bereikt van de jobs die worden uitgevoerd; daarna deelt de job de processor gelijkelijk met de andere jobs die worden bediend, op basis van round robin; zijn prioriteit blijft toenemen met de lagere snelheid β. Deze algoritme wordt selfish (egoïstische) round robin genoemd, omdat de jobs die worden bediend (tevergeefs) proberen de processor te monopoliseren door hun prioriteit voortdurend te verhogen. Gebruik figuur 9.19 om aan te tonen dat de gemiddelde antwoordtijd Rx. van een job met bedieningstijd x gelijk is aan:



      Hierbij wordt verondersteld dat de aankomst- en bedieningstijden exponentieel verdeeld Zijn met gemiddelden van respectievelijk 1/λ en s. (Aanwijzing: maak een aparte analyse van het volledige systeem en de twee subsystemen.)
       
    13. Een interactief systeem met scheduling op basis van round robin en swapping probeert alledaagse verzoeken als volgt een gegarandeerde antwoordtijd te geven: nadat een round-robincyclus met alle gereedstaande processen is voltooid, berekent het systeem het aan elk gereed proces toe te wijzen tijdquantum voor dc volgende cyclus door de maximale antwoordtijd te delen door het aantal processen dat moet worden bediend. Is dit een redelijke strategie?
       
    14. Welk soort proces wordt doorgaans bevoordeeld door een scheduler volgens feedback met wachtrijen op meerdere niveaus: een processorgebonden proces of een I/O-gebonden proces? Leg kort uit waarom.
       
    15. Bij processcheduling op basis van prioriteiten draagt de scheduler de besturing alleen over aan een bepaald proces als er op dat moment geen andere processen zijn met een hogere prioriteit in de toestand Gereed. Veronderstel dat er geen andere informatie gebruikt wordt bij het nemen van de schedulingbeslissing. Veronderstel ook dat de procesprioriteiten worden bepaald op het moment van het creëren van de processen en daarna niet veranderen. Waarom is de oplossing van Dekker (zie paragraaf 5.2) voor het probleem van wederzijdse uitsluiting 'gevaarlijk' bij een besturingssysteem dat uitgaat van deze aannamen? Leg dit uit door te beschrijven welke ongewenste gebeurtenis kan optreden en hoe die kan optreden.
       
    16. Vijf batchjobs, A tot en met E, arriveren op ongeveer hetzelfde tijdstip bij een computercentrum. Ze hebben een geschatte uitvoeringstijd van respectievelijk 15, 9, 3, 6 en 12 minuten. Hun (extern gedefinieerde) prioriteiten zijn respectievelijk 6, 3, 7, 9 en 4, waarbij een lage waarde overeenkomt met een hoge prioriteit. Bepaal voor ieder van de volgende schedulingalgoritmen de omlooptijd van elk proces en de gemiddelde omlooptijd van alle jobs. Negeer de overhead voor proceswisselingen. Licht toe hoe u aan uw antwoorden bent gekomen. Veronderstel voor de laatste drie gevallen dat slechts één job tegelijkertijd wordt uitgevoerd totdat deze voltooid is en dat alle jobs volledig processorgebonden zijn.
      1. round robin met een tijdquantum van 1;
      2. prioriteitscheduling;
      3. FCFS (uitgevoerd in de volgorde 15,9, 3,6 en 12);
      4. de kortste job eerst.