Multiprocessor en real-time 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

Dit hoofdstuk vervolgt ons overzicht van proces- en threadscheduling. We beginnen met een bespreking van kwesties die spelen als meer dan één processor beschikbaar is. We gaan in op enkele aandachtspunten bij het ontwerpen. Daarna volgt een overzicht van scheduling van processen bij een multiprocessorsysteem. Vervolgens wordt ingegaan op de enigszins afwijkende manier van het ontwerpen van threadscheduling bij multiprocessing. Het tweede gedeelte van dit hoofdstuk behandelt realtime-scheduling. De paragraaf begint met een overzicht van de kenmerken van realtime-processen en gaat vervolgens in op de aard van het schedulingproces. Twee benaderingen van realtime-scheduling, deadline-scheduling en frequentiescheduling, worden besproken.

10.1. Scheduling bij meerdere processors

Bevat een computersysteem meer dan één processor, dan speelt een aantal nieuwe kwesties een rol bij het ontwerpen van de schedulingfunctie. We beginnen met een beknopt overzicht van multiprocessors, systemen met meerdere processors, en gaan daarna in op de tamelijk sterk afwijkende aanpak van scheduling op procesniveau en scheduling op threadniveau.

We kunnen multiprocessorsystemen verdelen in de volgende categorieën:

  • Losjes gekoppelde of gedistribueerde multiprocessor (loosley coupled) of cluster: bestaat uit een aantal relatief autonome systemen, waarbij elke processor eigen hoofdgeheugen en I/O-kanalen heeft. We behandelen dit configuratietype in hoofdstuk 14.
  • Functioneel gespecialiseerde processors: bijvoorbeeld een I/O-processor. In dit geval is er één algemene hoofdprocessor; de gespecialiseerde processors worden bestuurd door en verzorgen diensten voor de hoofdprocessor. De onderwerpen die samenhangen met I/O-processors, worden behandeld in hoofdstuk 11.
  • Sterk gekoppelde multiprocessing (tightly coupled): bestaat uit een aantal processors die een gemeenschappelijk hoofdgeheugen delen en integraal worden bestuurd door een besturingssysteem.
  • In dit hoofdstuk gaat onze aandacht uit naar de laatste categorie en vooral naar de onderwerpen die samenhangen met scheduling.

    10.1.1. Granulariteit

    Een goede manier om multiprocessors te karakteriseren en deze te plaatsen in de context van andere architecturen, is uitgaan van de granulariteit van de synchronisatie, oftewel de frequentie van synchronisatie tussen processen in het systeem. We kunnen vijf categorieën parallelliteit onderscheiden die verschillen in de mate van granulariteit. Deze worden samengevat in tabel 10.1, die is overgenomen van [GEHR87I en [WOOD89j.

    10.1.1.1. Onafhankelijke parallelliteit

    Bij onafhankelijke parallelliteit is er geen expliciete synchronisatie tussen processen. Elk proces stelt een afzonderlijke, onafhankelijke toepassing of job voor. Een standaardvoorbeeld van dit soort parallelliteit is een systeem met timesharing. Elke gebruiker voert een bepaalde toepassing uit, zoals tekstverwerking of spreadsheet. De multiprocessor verleent hierbij dezelfde diensten als een systeem met één processor met multiprogrammering. Aangezien er meer dan één processor beschikbaar is, zal de gemiddelde antwoordtijd voor de gebruikers kleiner zijn.

    Het is mogelijk een vergelijkbare prestatieverbetering te bereiken door elke gebruiker te voorzien van een personal computer of werkstation. Moeten bestanden of informatie worden gedeeld, dan moet men de afzonderlijke systemen aaneenkoppelen tot een gedistribueerd systeem, dat wordt ondersteund door een netwerk. Deze aanpak komt aan bod in hoofdstuk 14. Daar staat tegenover dat één gedeeld systeem met meerdere processors vaak goedkoper is dan een gedistribueerd systeem; het eerstgenoemde biedt schaalvoordelen door het delen van schijven en andere randapparatuur.

  • Geen expliciete synchronisatie tussen processen onderling.
  • Elk proces stelt een aparte, onafhankelijke toepassing of job voor.
  • Wordt gebruikt op time-sharingsystemen.
  • 10.1.1.2. Grof en zeer grof gegranuleerde parallelliteit

    Bij parallelliteit met een grove of zeer grove granulariteit is er synchronisatie tussen processen, maar die is nogal vaag. Zo’n soort situatie kan gemakkelijk worden behandeld als een verzameling gelijktijdige processen die worden uitgevoerd op een systeem met één processor en multiprogrammering, en kan op een multiprocessor worden ondersteund met weinig tot geen verandering van de gebruikerssoftware.

    Een eenvoudig voorbeeld van een toepassing die het bestaan van een multiprocessor kan benutten, wordt genoemd in [W00D89]. De auteurs hadden een programma ontwikkeld dat een specificatie accepteert van bestanden die moeten worden gecompileerd voor het opnieuw samenstellen van een stuk software. Het programma bepaalt welke van deze compilaties (doorgaans alle) gelijktijdig kunnen worden uitgevoerd. Het programma creëert vervolgens één proces voor elke parallelle compilatie. De auteurs melden dat de snelheidswinst bij een multiprocessor hoger is dan wat men zou verwachten door eenvoudig het aantal gebruikte processors op te tellen. Deze snelheidswinst ontstaat dankzij synergievoordelen in de schijfbuffercaches (een onderwerp dat wordt behandeld in hoofdstuk 11) en het delen van compilercode die slechts één keer in het geheugen wordt geladen.

    In het algemeen kan elke verzameling gelijktijdige processen die moeten communiceren of synchroniseren, baat hebben bij het gebruik van een architectuur mei meerdere processors. Is er maar weinig interactie tussen processen, dan biedt een gedistribueerd systeem een goede ondersteuning. Is er echter wat meer interactie, dan kan de overhead van de communicatie via het netwerk een deel van de mogelijke snelheidswinst tenietdoen. In dit geval biedt de vorm met multiprocessing de meest effectieve ondersteuning.

  • Synchronisatie tussen processen onderling maar op een grof niveau.
  • Grote intervallen tussen elke synchronisatie.
  • 10.1.1.3. Gemiddeld gegranuleerde parallelliteit

    In hoofdstuk 4 zagen we dat één toepassing effectief kan worden geïmplementeerd als een verzameling threads binnen één proces. In dat geval moet de mogelijke parallelliteit van een toepassing expliciet worden gespecificeerd door de programmeur Doorgaans vereist dit een hoge mate van coördinatie en interactie tussen de threads van een toepassing, wat leidt tot een gemiddelde granulariteit van de synchronisatie

    Onafhankelijke, zeer grof en grof gegranuleerde parallelliteit kan worden ondersteund op een multiprogrammeringsysteem met één processor of op een multiprocessor zonder of met slechts minimale gevolgen voor de schedulingfunctie. Maar voor threads zal de scheduling moeten worden aangepast. Aangezien de verschillende threads van een toepassing erg vaak interactie hebben, kunnen schedulingbeslissingen voor één thread gevolgen hebben voor de prestaties van de hele toepassing. Verderop in dit hoofdstuk komen we hierop terug.

  • Onafhankelijk, (zeer) grofkorrelig parallelisme kan zonder of met slechts minimale gevolgen voor de schedulingfunctie zowel op:
  • Multiprogrammeringsysteem met één processor
  • Multiprocessor
  • Scheduler herzien want toepassingen zorgen voor frequente interactie. Dus invloed op de scheduling beslissingen van een enkele draad
  • 10.1.1.4. Fijn gegranuleerde parallelliteit

    Fijn gegranuleerde parallelliteit is een veel complexere toepassing van parallelliteit dan we aantreffen bij het gebruik van threads. Hoewel veel onderzoek is gedaan naar sterk parallelle toepassingen, is dit vooralsnog een gespecialiseerd en gefragmenteerd vakgebied, met veel verschillende benaderingen. In [ALMA89] staat een goed overzicht.

  • Mogelijkheid tot parallel uitvoeren van onafhankelijke draden van 1 proces over verschillende processoren.
  • 10.1.2. Ontwerpaspecten

    Bij scheduling van een multiprocessor is sprake van drie samenhangende aspecten:

  • De toewijzing van processen aan processors;
  • Het gebruik van multiprogrammering op de verschillende processors;
  • De feitelijke toedeling (dispatching) van een proces.
  • Bij het bestuderen van deze drie aspecten is het belangrijk in gedachten te houden dat, in het algemeen, de beste benadering afhankelijk is van de mate van granulariteit van de toepassingen en van het aantal beschikbare processors.

    10.1.2.1. Toewijzing van processen aan processors

    Laten we er eerst van uitgaan dat de architectuur van de multiprocessor uniform is.

    Daarmee bedoelen we dat geen enkele processor speciale eigenschappen heeft met betrekking tot de toegang tot het hoofdgeheugen of I/O-apparaten. In dat geval is de eenvoudigste scheduling benadering de processors te behandelen als één systeembron en processen naar behoefte toe te wijzen aan processors. Daarbij dringt zich de vraag op of de toewijzing statisch of dynamisch moet zijn.

    Wordt een proces vanaf activering tot en met voltooiing permanent toegewezen aan één processor, dan wordt een speciale korte-termijnwachtrij bijgehouden voor elke processor. Een voordeel van deze aanpak is dat het minder overhead kan betekenen voor de schedulingfunctie, omdat de processortoewijzing voor eens en altijd gebeurt. Bovendien maakt het gebruik van speciale processors een benadering mogelijk die ‘groepscheduling’ of ‘gang scheduling’ wordt genoemd; deze wordt behandeld in paragraaf 10.1.4.

    Een nadeel van een statische toewijzing is dat een processor weinig te doen kan hebben en een lege wachtrij heeft, terwijl een andere processor een achterstand in de verwerking heeft. Om die situatie te voorkomen kan een gemeenschappelijke wachtrij worden gebruikt. Alle processen worden toegevoegd aan één algemene wachtrij en worden ingeroosterd op een willekeurige beschikbare processor. Gedurende het bestaan van een proces kan het proces daarmee op andere momenten worden uitgevoerd op andere processors. In een sterk gekoppelde architectuur met gedeeld geheugen is de contextinformatie van alle processen beschikbaar voor alle processors, waardoor de ‘kosten’ van de processcheduling onafhankelijk zijn van de identiteit van de processor waarop het proces wordt ingeroosterd. Nog een andere optie is de dynamische verdeling van de belasting (dynamic bad balancing), waarbij threads vanuit een wachtrij voor de ene processor naar een wachtrij voor een andere processor worden verplaatst; Linux werkt met deze benadering.

    Ongeacht of processen wel of niet permanent worden toegewezen aan een specifieke processor, is een methode nodig om processen toe te wijzen aan processors. Hierbij komen twee vormen voor: master/slave en peer (gelijken). Bij een master/slavearchitectuur worden belangrijke kernelfuncties altijd uitgevoerd op een bepaalde processor. De andere processors kunnen uitsluitend gebruikersprogramma’s uitvoeren. De meester (master) is verantwoordelijk voor de scheduling van jobs. Is een proces eenmaal actief en heeft de slaaf (slave) een dienst nodig (bijvoorbeeld voor een I/O-aanroep), dan moet deze een verzoek sturen naar de master en wachten tot de dienst wordt uitgevoerd. Deze benadering is redelijk eenvoudig en vereist weinig uitbreiding van een besturingssysteem voor één processor met multiprogrammering. De conflictoplossing is eenvoudig omdat één processor het beheer heeft over alle geheugen- en I/O-voorzieningen. Deze benadering heeft twee nadelen: (1) bij een kritieke fout van de master ligt het hele systeem plat en (2) de master kan een knelpunt voor de prestaties worden.

    In een peer-architectuur kan het besturingssysteem worden uitgevoerd op elke processor die gelijkwaardig (peer) is. Elke processor voert zelf de scheduling uit voor de verzameling beschikbare processen. Deze benadering compliceert het besturingssysteem. Het besturingssysteem moet voorkomen dat twee processors hetzelfde proces kiezen en dat processen op een of andere manier verloren gaan uit de wachtrij. Men moet technieken gebruiken voor het oplossen en synchroniseren van concurrerende aanvragen voor systeembronnen.

    Er bestaat natuurlijk een scala van manieren tussen deze twee uitersten. Men kan bijvoorbeeld een gedeelte van de processors reserveren voor de kernelverwerking in plaats van slechts één processor. Een andere benadering is door het verschil in behoeften van kernelprocessen en andere processen eenvoudig te beheren op basis van prioriteit en verwerkingsverleden.

  • Elke processor is dezelfde
  • Twee manieren van toewijzen:
  • Statisch
  • Dynamisch
  • Methodes van toewijzing:
  • Master/slave:
  • Kritische kernelfuncties van het OS draaien steeds op dezelfde processor (master).
  • De andere processors mogen enkel gebruikersprocessen uitvoeren (slaves).
  • Master is verantwoordelijk voor het plannen van de jobs.
  • Als proces actief is en de slave heeft een dienst nodig (b.v. : I/O).
  • Verzoek sturen naar de master.
  • Wachten tot dienst is geleverd.
  • Voordeel: eenvoudige aanpak weinig aanpassingen nodig voor een multiprogramma-uniprocessor besturingssysteem.
  • Nadeel: falen van master legt het systeem plat. De master kan een performantie bottleneck worden.
  • Peer:
  • Kernel kan op elke processor uitvoeren.
  • Elke processor doet zelf de scheduling op basis van beschikbare processen.
  • Nadeel: OS wordt gecompliceerder.
  • 2 processors mogen niet eenzelfde proces kiezen.
  • Zorgen dat processen niet verdwijnen uit de wachtrij.
  • 10.1.2.2. Het gebruik van multiprogrammering voor individuele processors

    Wordt elk proces gedurende zijn hele bestaan statisch toegewezen aan één processor, dan komt een nieuwe vraag op: moet multiprogrammering worden gebruikt voor die processor? Wellicht zal de eerste reactie op deze gestelde vraag wat verbaasd zijn. Reserveren van een processor voor één proces lijkt immers een grote verspilling, omdat dat proces in afwachting van I/O vaak kan worden geblokkeerd of vanwege kwesties die samenhangen met gelijktijdigheid of synchronisatie.

    Bij de traditionele multiprocessor, die te maken heeft met een grove of onafhankelijk granulariteit van synchronisatie (zie tabel 10.1), is het duidelijk dat elke individuele processor tussen meerdere processen moet kunnen wisselen om een hoge bezettingsgraad en daarmee betere prestaties te bereiken. Bij toepassingen met een gemiddelde granulariteit die worden uitgevoerd op een multiprocessor met veel processors, is de situatie echter minder duidelijk. Zijn er veel processors beschikbaar, dan ligt het minder voor de hand dat elke processor zo veel mogelijk bezig moet worden gehouden. In plaats daarvan gaat het ons vooral om de beste gemiddelde prestaties voor de toepassingen. Een toepassing die bestaat uit een aantal threads, kar slecht werken tenzij alle threads beschikbaar zijn voor gelijktijdige uitvoering.

  • Is er bij statische toewijzing nood aan multiprogrammering van de processor?
  • Ja, indien we onafhankelijke of (zwaar) grofkorrelige synchronisatie hebben
  • Onduidelijk bij gemiddeld korrelige synchronisatie
  • 10.1.2.3. Toedeling van processen

    Het laatste aandachtspunt bij het ontwerpen van scheduling voor multiprocessing is de feitelijke selectie van het uit te voeren proces. Bij een systeem met één processor en multiprogrammering hebben we gezien dat prioriteiten of geavanceerde schedulingalgoritmen die zijn gebaseerd op het gebruik in het verleden, beter kunnen werken dan een eenvoudige first-come, first-served (FCFS)-benadering. Kijken we naar multiprocessors, dan kan deze toename in de complexiteit overbodig zijn of zelfs averechts werken en kan een eenvoudige vorm effectiever zijn en minder overhead met zich meebrengen. Bij threadscheduling spelen nieuwe aandachtspunten een rol die belangrijker kunnen zijn dan prioriteiten of het verwerkingsverleden. We zullen deze aandachtspunten een voor een behandelen.

  • Multiprogramma uniprocessor
  • FCFS
  • Prioriteiten
  • Planningsalgoritme
  • Multiprocessors
  • Multiprogramma uniprocessormethodes kunnen overbodig zijn of contraproductief
  • Worden besproken in volgende delen
  • 10.1.3. Scheduling van processen

    In de meeste conventionele multiprocessorsystemen worden processen niet exclusief aan één processor toegewezen. In plaats daarvan wordt één wachtrij gebruikt voor alle processors of zijn er, bij het gebruik van een prioriteitssysteem, meerdere wachtrijen op basis van prioriteiten, die uitmonden in één gemeenschappelijke verzameling processors. In beide gevallen kunnen we het systeem beschouwen als een wachtrij architectuur met meerdere servers.

  • In meeste multiprocessor systemen
  • Processen zijn niet toegewijd aan 1 processor
  • Enkele wachtrij voor alle processen of prioriteitensysteem met een aantal wachtrijen
  • Situatie
  • Dual processorsysteem waarbij elke processor de helft aankan dan de processor bij een uniprocessorsysteem
  • 2 vergelijkingen
  • Round Robin <=> FCFS
  • Shortest Remaining Time <=> FCFS
  • 10.1.4. Scheduling van threads

    Zoals we hebben gezien, staat het concept van de verwerking bij threads los van de rest van de definitie van een proces. Een toepassing kan worden geïmplementeerd als een verzameling threads, die samenwerken en gelijktijdig worden uitgevoerd in dezelfde adresruimte.

    Bij een systeem met één processor kunnen threads worden gebruikt als hulpmiddel voor het structureren van een programma en voor het laten overlappen van de 1/0 en de verwerking. Aangezien een threadwisseling veel eenvoudiger is dan een proceswisseling, kunnen deze voordelen worden gerealiseerd tegen minimale kosten. De ware kracht van threads wordt echter pas goed zichtbaar bij een systeem met meerdere processors. In zo’n omgeving kunnen threads worden gebruikt voor het benutten van echte parallelliteit in een toepassing. Worden de verschillende threads van een toepassing gelijktijdig uitgevoerd op afzonderlijke processors, dan kunnen de prestaties sterk toenemen. Het kan echter worden aangetoond dat bij toepassingen die een sterke interactie tussen threads vereisen (een gemiddelde gegranuleerde parallelliteit), kleine verschillen in het beheer en de scheduling van threads een significante invloed op de prestaties kunnen hebben [ANDE89]. Threadscheduling op multiprocessors is een onderwerp van actueel onderzoek; de bespreking hier geeft een overzicht van de belangrijkste kwesties en manieren van aanpak.

    Uit de vele voorstellen voor threadscheduling en processortoewijzing bij multiprocessors springen vier algemene benaderingen naar voren:

  • Delen van belasting (load sharing): processen worden niet toegewezen aan een bepaalde processor. Er wordt één algemene wachtrij van gereedstaande processen bijgehouden en een processor die niets te doen heeft, selecteert een thread uit deze wachtrij. Het begrip delen van belasting wordt gebruikt om een onderscheid te maken tussen deze aanpak en manieren voor het evenwichtig verdelen van belasting (bad balancing), waarbij werk meer permanent wordt toegewezen (zie bijvoorbeeld [FEIT9Oa]).
  • Groepscheduling (Gang scheduling): een groep gerelateerde threads wordt ingeroosterd om gelijktijdig te worden uitgevoerd op een aantal processors in een verhouding van één op één.
  • Vaste processortoewijzing: dit is het tegenovergestelde van de benadering met het delen van belasting. Hierbij is sprake van een impliciete scheduling door de toewijzing van threads aan processors. Aan elk programma wordt voor de duur van de uitvoering van het programma een aantal processors toegewezen dat gelijk is aan het aantal threads in het programma. Wordt het programma beëindigd, dan worden de processors weer toegevoegd aan de algemene verzameling voor een mogelijke toewijzing aan een ander programma.
  • Dynamische scheduling: het aantal threads in een programma kan tijdens de uitvoering worden aangepast.
  • Scheduling van threads:

  • Op uniprocessorsysteem kan men draden in een programma toevoegen als structuurhulp en om te overlappen met I/O.
  • Bij multiprocessor systemen kunnen we draden gebruiken om parallellisme na te bootsen
  • Als het aantal threads tegelijkertijd lopen op het aantal processoren hebben we een enorme performantiewinst.
  • Vier mogelijke manieren:
  • Gedeelde belasting
  • Eén globale wachtrij met “Ready” processen.
  • Een vrije processor neemt een proces uit die wachtrij.
  • Eenvoudigste en meest gebruikte manier.
  • Groepsplanning
  • Set van samenhorige draden wordt zodanig gepland dat ze op eenzelfde ogenblik zullen uitgevoerd worden op een aantal processoren.
  • Toegewijde processortoekenning
  • Tegenovergestelde van gedeelde belasting. Elk programma krijgt een aantal threads wat gelijk is aan een aantal processors.
  • Dynamische planning
  • Aantal threads in een proces kan veranderen gedurende de uitvoering.
  • Niet altijd mogelijk bij elke toepassing.
  • 10.1.4.1. Delen van belasting

  • Het delen van belasting (bad sharing) is waarschijnlijk de eenvoudigste manier en de vorm die het meest aansluit op een omgeving met één processor. Deze aanpak heeft verschillende voordelen:
  • De werklast wordt gelijkmatig verdeeld over de processors, wat voorkomt dat een processor niets doet zolang er nog werk is.
  • Er is geen gecentraliseerde scheduler nodig: is een processor beschikbaar, dan wordt de schedulingroutine van het besturingssysteem uitgevoerd op die processor om de volgende thread te selecteren.
  • De gemeenschappelijke wachtrij kan worden ingedeeld en gelezen met een van de systemen die zijn besproken in hoofdstuk 9, waaronder op prioriteit gebaseerde manieren en vormen die uitgaan van het verwerkingsverleden of van verwachte verwerkingsbehoeften.
  • [LEUT9O] analyseert drie verschillende versies van het delen van belasting:

  • First come, first served (FCFS). Bij aankomst van een job worden alle threads ervan na elkaar toegevoegd aan het einde van de gedeelde wachtrij. Heeft een processor niets meer te doen, dan selecteert hij de volgende gereedstaande thread, die hij uitvoert totdat de, thread is voltooid of wordt geblokkeerd.
  • Laagste aantal threads eerst. De wachtrij Gereed wordt ingedeeld als een prioriteitswachtrij, waarbij de hoogste prioriteit wordt gegeven aan threads van jobs met het kleinste aantal niet-ingeroosterde threads. Jobs met dezelfde prioriteit worden ingedeeld op basis van de job die het eerst aankomt. Net zoals bij FCFS wordt een thread uitgevoerd totdat deze is voltooid of wordt geblokkeerd.
  • Preëmptief laagste aantal threads eerst. De hoogste prioriteit wordt gegeven aan jobs met het kleinste aantal onvoltooide threads. Komt een nieuwe job binnen met een kleiner aantal threads dan een job die wordt uitgevoerd, dan wordt de uitvoering van de threads van de ingeroosterde job preëmptief onderbroken.
  • Op basis van simulatiemodellen melden de auteurs dat FCFS bij sterk uiteenlopende job kenmerken superieur is aan de twee andere genoemde strategieën. Daarnaast stellen de auteurs vast dat een vorm van groepscheduling, die wordt besproken in de volgende sectie, superieur is aan het delen van belasting.

    10.1.4.2. Groepsscheduling

    Het concept van de gelijktijdige scheduling van een aantal processen op een aantal processors, is ouder dan het gebruik van threads. [JONE8O] noemt het concept groepscheduling, dat de volgende voordelen heeft:

  • Worden sterk samenhangende processen parallel uitgevoerd, dan kan het aantal blokkeringen vanwege synchronisatie worden verminderd, kunnen minder proceswisselingen nodig zijn en zullen de prestaties verbeteren.
  • De schedulingoverhead kan worden verminderd, omdat één beslissing van invloed is op meerdere processors en processen tegelijk.
  • Bij de multiprocessor Cm* wordt de term coscheduling gebruikt [GEHR87]. Coscheduling is gebaseerd op het concept van het inroosteren van een aantal gerelateerde taken, een zogenoemde task force. De afzonderlijke elementen van een task force zijn veelal tamelijk klein en zijn daarmee vergelijkbaar met het begrip thread.

    Het begrip groepscheduling (gang scheduling) gebruikt men voor de gelijktijdige scheduling van de threads die tezamen één proces vormen [FEIT9Ob]. Groepscheduling is noodzakelijk voor toepassingen met een gemiddeld of fijn gegranuleerde parallelliteit waarvan de prestaties sterk afnemen wanneer een deel van de toepassing niet wordt uitgevoerd terwijl andere delen gereed staan voor verwerking. Groepscheduling is ook nuttig bij een gewone parallelle toepassing, zelfs als die niet zo gevoelig voor prestaties is. De noodzaak van groepscheduling wordt algemeen erkend en er bestaan implementaties op uiteenlopende besturingssystemen voor multiprocessors.

    Groepscheduling verbetert de prestaties van een individuele toepassing onder meer duidelijk doordat het aantal proceswisselingen wordt geminimaliseerd. Stel, een thread van een proces wordt verwerkt en bereikt een punt waarop deze moet worden gesynchroniseerd met een andere thread van hetzelfde proces. Wordt die andere thread niet uitgevoerd maar bevindt deze zich in een wachtrij Gereed, dan moet de eerste thread wachten totdat een proceswisseling kan worden uitgevoerd op een andere processor om de benodigde thread binnen te halen. In een toepassing die een nauwgezette coördinatie van threads vereist, kunnen zulke wisselingen de prestaties sterk verminderen. De gelijktijdige scheduling van samenwerkende threads kan ook tijd besparen bij het toewijzen van systeembronnen. Meerdere threads kunnen bij groepscheduling bijvoorbeeld toegang hebben tot een bestand zonder de extra overhead voor vergrendeling tijdens bewerkingen als zoeken en lezen/schrijven.

    Het gebruik van groepscheduling stelt een nieuwe eis aan de processortoewijzing. Eén mogelijkheid is de volgende. Veronderstel dat we N processors hebben en M toepassingen, die elk N of minder threads hebben. Aan elke toepassing kan dan 1/M van de beschikbare tijd op de N processors worden toegewezen met tijdsdeling (time slicing). [FEIT9Oa] merkt op dat deze aanpak inefficiënt kan zijn. Ga bijvoorbeeld uit van een situatie met twee toepassingen waarvan de ene vier threads en de andere één thread heeft. Een uniforme tijdtoewijzing verspilt 37,5% van de verwerkingsvoorziening, omdat bij het uitvoeren van de toepassing met één thread drie processors ongebruikt blijven (zie figuur 10-2). Zijn er meerdere toepassingen met één thread, dan kunnen die alle tegelijkertijd worden uitgevoerd om de bezettingsgraad van de processors te verhogen. Ontbreekt die mogelijkheid, dan is een scheduling die wordt gewogen op basis van het aantal threads een alternatief voor een uniforme scheduling. De toepassing met vier threads kan daarbij 4/5 van de tijd krijgen en de toepassing met één thread slechts 1/5 van de tijd, wat de processorverspilling vermindert tot 15%.

    10.1.4.3. Vaste processortoewijzing

    Een extreme vorm van groepscheduling, die wordt voorgesteld in [TUCK89], is het reserveren van een groep processors voor één toepassing gedurende de gehele levensduur van die toepassing. Dat wil zeggen: wordt een toepassing ingeroosterd, dan krijgt elke thread ervan een processor toegewezen die voor die thread beschikbaar blijft totdat de uitvoering van de toepassing is voltooid.

    Deze benadering lijkt een enorme verspilling van processortijd. Wordt een thread van een toepassing geblokkeerd in afwachting van 1/0 of vanwege synchronisatie met een andere thread, dan blijft de processor van die thread ongebruikt; er is geen multiprogrammering van processors. Twee argumenten spreken echter voor deze aanpak:

    1. In een sterk parallelle multiprocessor met tientallen of honderden processors die elk slechts een fractie van het complete systeem kosten, is het processorgebruik niet meer zo belangrijk als norm voor de effectiviteit of de prestaties.
    2. Het volledig vermijden van proceswisselingen gedurende het bestaan van een programma kan leiden tot een aanzienlijke versnelling van dat programma.

    Zowel [TUCK89] als [ZAHO9O] noemen analyses die de tweede stelling ondersteunen. Figuur 10.3 geeft het resultaat van één experiment [TUCK89]. De auteurs voerden twee toepassingen, een matrixvermenigvuldiging en een snelle Fouriertransformatie, uit op een systeem met zestien processors. Elke toepassing splitst het probleem in een aantal taken, die worden omgezet naar threads die de toepassing uitvoeren. De programma’s zijn zo geschreven dat het aantal te gebruiken threads kan variëren. In feite worden door een toepassing enkele taken gedefinieerd en in een wachtrij geplaatst. Taken worden door de toepassing uit de wachtrij gehaald en omgezet naar de beschikbare threads. Zijn er minder threads dan taken, dan blijven de resterende taken bewaard in de wachtrij en worden opgepikt door threads nadat die hun toegewezen taken hebben voltooid. Vanzelfsprekend kunnen niet alle toepassingen op deze manier worden gestructureerd, maar veel rekenkundige problemen en sommige andere toepassingen kunnen wel zo worden afgehandeld.

    Figuur 10.3 toont de snelheidstoename voor beide toepassingen wanneer het aantal threads dat de taken in elke toepassing uitvoert, wordt gevarieerd van 1 tot en met 24. We zien bijvoorbeeld dat, wanneer beide toepassingen tegelijk worden gestart met elk 24 threads, de snelheidstoename in vergelijking tot één thread per toepassing 2,8 is voor de matrixvermenigvuldiging en 2,4 voor de snelle Fouriertransformatie. De figuur toont dat de prestaties van beide toepassingen duidelijk afnemen wanneer het aantal threads in elke toepassing groter wordt dan 8, het punt waarop het totaal aantal processen in het systeem groter wordt dan het aantal processors (16). We zien bovendien dat de prestaties slechter worden naarmate het aantal threads toeneemt, omdat de frequentie van het preëmptief onderbreken en opnieuw inroosteren van threads toeneemt. De inefficiëntie bij veelvuldige preëmptieve onderbrekingen heeft veel oorzaken. Zo is er de tijd die wordt besteed aan het wachten tot een onderbroken thread zijn kritieke sectie verlaat, de tijd die wordt verspild aan proceswisselingen en een inefficiënt cachegedrag.

    De auteurs concluderen dat een effectieve aanpak is het aantal actieve threads te beperken tot het aantal processors in het systeem. Bestaan de meeste toepassingen uit één thread of kunnen de meeste toepassingen de structuur van de job wachtrij gebruiken, dan zorgt dat voor een effectief en redelijk efficiënt gebruik van de processorvoorzieningen.

    Zowel vaste processortoewijzing als groepscheduling proberen het schedulingprobleem op te lossen door uit te gaan van het toewijzen van processors. Men kan stellen dat het probleem van processortoewijzing bij een multiprocessorsysteem meer lijkt op het probleem van geheugentoewijzing dan op het schedulingprobleem bij een uniprocessorsysteem. Het draait hierbij om het aantal processors dat op elk moment moet worden toegewezen aan een programma. Dit is vergelijkbaar met het aantal paginaframes dat op elk moment moet worden toegewezen aan een bepaald proces. [GEHR87] stelt de term activiteitwerkset voor, naar analogie van de werkset bij virtueel geheugen, voor het minimumaantal activiteiten (threads) dat gelijktijdig moet worden ingeroosterd op processors om de toepassing een redelijke voortgang te laten maken. Net zoals bij virtueel-geheugensystemen kan een mislukte poging tot het inroosteren van alle elementen (threads) van een activiteitwerkset leiden tot processor thrashing. Dit treedt op wanneer het inroosteren van threads waarvan diensten nodig zijn, leidt tot het uitroosteren van andere threads waarvan diensten binnenkort weer nodig zijn. Op overeenkomstige wijze verwijst processorfragmentatie naar een situatie waarin enkele processors overblijven wanneer de overige zijn toegewezen en er niet voldoende overgebleven processors zijn of waarbij de overgebleven processors een ongeschikte indeling hebben om te voorzien in de vereisten van wachtende toepassingen. Groepscheduling en vaste processortoewijzing zijn bedoeld om deze problemen te vermijden.

    10.1.4.4. Dynamische scheduling

    Bij sommige toepassingen is het mogelijk een taal en systeemhulpmiddelen te gebruiken die een dynamische aanpassing van het aantal threads in het proces mogelijk maken. Dit biedt het besturingssysteem de gelegenheid de belasting aan te passen om het processorgebruik te verbeteren.

    [ZAHO9Oj stelt een benadering voor waarbij zowel het besturingssysteem a15 de toepassing betrokken zijn bij het nemen van schedulingbeslissingen. Het besturingssysteem is verantwoordelijk voor het partitioneren van processors over jobs. Elke job gebruikt de processors die op dat moment deel uitmaken van zijn partitie om een gedeelte van zijn uitvoerbare taken te verrichten door deze taken te transformeren naar threads. Het nemen van de juiste beslissing welk gedeelte moet worden uitgevoerd en welke thread moet worden onderbroken wanneer een proces preëmptief wordt onderbroken, wordt overgelaten aan de individuele toepassing (eventueel via een aantal bibliotheekroutines voor verwerking). Deze aanpak za] niet altijd geschikt zijn voor alle toepassingen. Sommige toepassingen kunnen echter standaard één thread gebruiken terwijl andere worden geprogrammeerd voor het benutten van deze speciale mogelijkheid van het besturingssysteem.

    Bij deze benadering blijft voor scheduling de verantwoordelijkheid van het besturingssysteem hoofdzakelijk beperkt tot de processortoewijzing. Deze functie wordt als volgt uitgevoerd. Verzoekt een job om een of meer processors (hetzij wanneer de job voor het eerst binnenkomt, hetzij omdat de behoeften van de job veranderen), dan gebeurt het volgende:

    1. Zijn er ongebruikte processors, dan worden deze gebruikt om te voldoen aan het verzoek.
    2. Zijn er geen ongebruikte processors en is de job die het verzoek plaatst een nieuw binnengekomen job, dan wordt de job toegewezen aan één processor door deze processor te onttrekken aan een job waaraan op dit moment meer dan één processor is toegewezen.
    3. Kan niet worden voldaan aan een deel van het verzoek, dan blijft het verzoek openstaan totdat hiervoor een processor beschikbaar komt of de job het verzoek intrekt (bijvoorbeeld omdat het de extra processors niet meer nodig heeft).

    Na het vrijgeven van een of meer processors (onder andere door de beëindiging van jobs) gebeurt het volgende:

    1. De huidige wachtrij van onbeantwoorde aanvragen voor processors wordt doorzocht. Er wordt één processor toegewezen aan elke job in de lijst die op dit moment geen processors heeft (dat wil zeggen: aan alle wachtende, nieuw binnengekomen jobs). Vervolgens wordt de lijst nog een keer doorzocht, waarbij de rest van de processors wordt toegewezen op basis van FCFS.

    Analyses die worden beschreven in [ZAHO9O] en [MAJU88], suggereren dat deze aanpak voor toepassingen die baat kunnen hebben bij dynamische scheduling, beter werkt dan groepscheduling of vaste processortoewijzing. De overhead bij deze manier zal de geconstateerde prestatieverbetering echter enigszins verminderen. Er is praktijkervaring met systemen nodig om het nut van dynamische scheduling te bewijzen.

    10.2. Realtime-scheduling

    10.2.1. Inleiding

    Realtime-verwerking wordt een steeds belangrijker onderwerp. Het besturingssysteem, en dan vooral de scheduler, is waarschijnlijk het belangrijkste onderdeel van een realtime-systeem. Voorbeelden van actuele toepassingen van realtime-systemen zijn de besturing van laboratoriumexperimenten, de procesbesturing in fabrieken, robots, luchtverkeersleiding, telecommunicatie en militaire commando- en stuursystemen. Tot de systemen van de volgende generatie behoren de autonome landverkenner, controllers voor robots met elastische gewrichten, systemen voor fabricage met kunstmatige intelligentie, het ruimtestation en diepzeeverkenning.

    Realtime-verwerking kan worden gedefinieerd als het soort verwerking waarbij de juistheid van het systeem niet alleen afhankelijk is van het logische resultaat van de berekening, maar tevens van het tijdstip waarop de resultaten worden geproduceerd. We kunnen een realtime-systeem definiëren door te definiëren wat wordt bedoeld met een realtime-proces of taak (task). In het algemeen zijn sommige taken in een realtime-systeem realtime-taken, die een bepaalde mate van urgentie hebben. Zulke taken proberen gebeurtenissen (events) die plaatsvinden in de buitenwereld te besturen of daarop te reageren. Aangezien deze gebeurtenissen op ‘echte tijd’ (real time) optreden, moet een realtime-taak de gebeurtenissen waarop de taak betrekking heeft, kunnen bijhouden. Dit is veelal mogelijk door een deadline te verbinden aan een bepaalde taak, waarbij de deadline een begintijd of een eindtijd bepaalt. Een dergelijke taak kan hard of zacht zijn. Een harde realtime-taak is een taak die moet voldoen aan zijn deadline; voldoet de taak niet aan de deadline, dan leidt dat tot ongewenste schade of een fatale fout in het systeem. Een zachte realtime-taak heeft een deadline die gewenst maar niet verplicht is; het inroosteren en voltooien van de taak blijft zinvol, zelfs als de deadline is overschreden.

    Een ander kenmerk van realtime-taken is of ze periodiek of niet-periodiek zijn. Een niet-periodieke taak heeft een deadline waarop de taak moet eindigen of beginnen of heeft een beperking voor zowel de begintijd als de eindtijd. Bij een periodieke taak kan de vereiste worden geformuleerd als ‘eens per periode T’ of ‘precies om de T eenheden’.

  • OS, planner in het bijzonder, is het belangrijkste onderdeel van een real-time systeem
  • Onmiddellijk bij het optreden van een gebeurtenis kunnen reageren
  • Actieve proces moet wijken voor het proces van de gebeurtenis
  • Toepassingen
  • Robots
  • Simulaties
  • Correctheid van het systeem hangt af van
  • Het resultaat van de berekening
  • De tijd waarbij de resultaten berekend werden
  • In een real-time systeem zijn sommige taken real-time
  • Real-time taak
  • Heeft een bepaalde dringendheid (≈ prioriteit) waarmee het moet uitgevoerd worden
  • Controleert of reageert op gebeurtenissen uit de echte wereld
  • Heeft een deadline (analoog punt 1)
  • Real-time taken kan men opdelen als
  • Hard real-time
  • Moet voldoen aan zijn deadline
  • Bij falen deadline veroorzaakt dit schade van het systeem of kan dit leiden tot een falen van het systeem
  • Zachte real-time
  • Deadline halen is gewenst maar geen noodzaak
  • Periodieke taak
  • Eens per periode T uitvoeren
  • Exact T eenheden uit elkaar
  • Niet-periodieke taak
  • Heeft een deadline wanneer de taak moet starten of beëindigd zijn
  • Beperking of zowel start als eindtijd
  • 10.2.2. Kenmerken van realtime-besturingssystemen

    Realtime-besturingssystemen kunnen worden gekenmerkt als systemen met unieke vereisten op vijf algemene gebieden [MORG92]:

  • Determinisme
  • Reactievermogen
  • Gebruikersinvloed
  • Betrouwbaarheid
  • Fail-soft werking
  • Een systeem is tot op zekere hoogte deterministisch omdat het bewerkingen uitvoert op vaste, vooraf vastgestelde tijdstippen of binnen vooraf vastgestelde tijdsintervallen. Concurreren meerdere processen om voorzieningen of processortijd, dan is geen enkel systeem volledig deterministisch. Bij een realtime-besturingssysteem worden procesverzoeken om bediening gedicteerd door externe gebeurtenissen en tijden. De mate waarin een besturingssysteem deterministisch kan voldoen aan verzoeken, is in de eerste plaats afhankelijk van de snelheid waarmee het kan reageren op interrupts en in de tweede plaats van het feit of het systeem voldoende capaciteit heeft om alle verzoeken binnen de vereiste tijd af te handelen.

    Een nuttige meeteenheid om na te gaan of een besturingssysteem deterministisch kan werken, is de maximumvertraging tussen de aankomst van een apparaatinterrupt met hoge prioriteit en het begin van de bediening ervan. Bij een niet-realtime-besturingssysteem kan deze vertraging een bereik hebben van tientallen tot honderden milliseconden, terwijl die vertraging bij een realtime-besturingssysteem een bovengrens heeft ergens tussen een paar microseconden en een milliseconde.

    Een hiermee samenhangend maar ander kenmerk is het reactievermogen (responsiveness). Determinisme heeft te maken met de vertraging van een besturingssysteem voordat een interrupt wordt bevestigd. Het reactievermogen heeft te maken met de tijd die het besturingssysteem na deze bevestiging nodig heeft om de interrupt af te handelen. Aspecten die samenhangen met het reactievermogen, zijn:

    1. De hoeveelheid tijd die nodig is voor het in eerste instantie afhandelen van interrupt en het uitvoeren van de interruptafhandelingsroutine (interrupt service routine, ISR). Wanneer de uitvoering van de ISR een proceswisseling vereist, duurt de uitvoering langer dan wanneer de ISR kan worden uitgevoerd binnen de context van het huidige proces.
    2. De hoeveelheid tijd die nodig is voor het uitvoeren van de ISR. Dit is doorgaans afhankelijk van het hardwareplatform.
    3. De invloed van het nesten van interrupts. Kan een ISR worden onderbroken door de aankomst van een andere interrupt, dan wordt de bediening vertraagd.

    Determinisme en reactievermogen vormen tezamen de antwoordtijd voor externe gebeurtenissen. Antwoordtijdvereisten zijn kritiek bij realtime-systemen, omdat zulke systemen moeten voldoen aan tijdeisen van personen, apparaten en gegevensstromen buiten het systeem.

    De gebruikersinvioed is bij een realtime-besturingssysteem doorgaans veel ruimer dan bij gewone besturingssystemen. Bij een doorsnee, niet-realtime-besturingssysteem heeft de gebruiker geen invloed op de schedulingfunctie van besturingssysteem of kan hij slechts algemene richtlijnen aangeven, bijvoorbeeld door gebruikers te groeperen tot verschillende prioriteitsklassen. Bij een realtimesysteem is het echter essentieel dat de gebruiker de taakprioriteit nauwkeurig kan opgeven. De gebruiker moet een onderscheid kunnen maken tussen harde en zachte taken en relatieve prioriteiten kunnen specificeren binnen elke klasse. Een realtime-systeem kan de gebruiker ook de mogelijkheid bieden kenmerken te specificeren; bijvoorbeeld het gebruik van paginering of processwapping, welke processen altijd resident moeten zijn in het hoofdgeheugen, welke algoritmen bij schijfoverdracht moeten worden gebruikt, welke rechten de processen in verschillende prioriteitsbanden hebben enzovoort.

    Betrouwbaarheid is doorgaans veel belangrijker bij realtime-systemen dan bij niet-realtime-systemen. Een kortstondige fout kan bij een niet-realtime-systeem worden opgelost door het systeem eenvoudig opnieuw te starten. Een processorfout kan bij een niet-realtime-systeem met meerdere processors leiden tot een verminderd bedieningsniveau totdat de falende processor is gerepareerd of vervangen. Een realtime-systeem daarentegen, bestuurt gebeurtenissen realtime-of reageert realtime-op gebeurtenissen. Een verlies of afname van prestaties kan rampzalige gevolgen hebben, die uiteenlopen van financiële verliezen tot grote schade aan apparatuur en zelfs dodelijke ongelukken.

    Net zoals bij andere onderwerpen is het verschil tussen realtime- en niet-realtime-systemen geen tegenstelling, maar een geleidelijke schaal. Zelfs een realtimesysteem moet ontworpen zijn om te reageren op uiteenlopende foutcondities. Een fail-soft werking is een kenmerk dat verwijst naar de mogelijkheid van het systeemfouten zo op te vangen dat mogelijkheden en gegevens zo veel mogelijk behouden blijven. Detecteert een doorsnee, traditioneel UNIX-systeem bijvoorbeeld een beschadiging van gegevens binnen de kernel, dan verzendt het een foutbericht naar de systeemconsole, kopieert de geheugeninhoud naar schijf voor latere foutanalyse en beëindigt de uitvoering van het systeem. Een realtime-systeem zal echter proberen het probleem op te lossen of de gevolgen te minimaliseren terwijl de uitvoering wordt Voortgezet. Doorgaans bericht het systeem een gebruiker of een gebruikersproces dat moet worden geprobeerd de fout te corrigeren en zet het vervolgens de uitvoering voort op een lager bedieningsniveau. Mocht het uitschakelen van het systeem noodzakelijk zijn, dan wordt geprobeerd bestanden en gegevens consistent te houden.

    Een belangrijk aspect van een fail-soft werking wordt stabiliteit genoemd. Een realtime-systeem is stabiel als het, wanneer het onmogelijk is alle deadlines te halen, de deadlines haalt van de meest kritieke taken met de hoogste prioriteit, zelfs wanneer bij sommige minder kritieke taken de deadlines niet worden gehaald.

    Om aan de voorgaande vereisten te voldoen, hebben moderne, realtimebesturingssystemen doorgaans de volgende kenmerken [STAN89]:

  • Snelle proces- en threadwisseling;
  • Kleine omvang (met bijbehorende minimale functionaliteit);
  • Mogelijkheid snel te reageren op externe interrupts;
  • Multitasking met hulpmiddelen voor de communicatie tussen processen, zoals semaforen, signalen en gebeurtenissen;
  • Gebruik van speciale, sequentiële bestanden die snel gegevens kunnen verzamelen;
  • Preëmptieve scheduling op basis van prioriteit;
  • Minimalisatie van intervallen waarin interrupts zijn uitgeschakeld;
  • Primitieven voor het uitstellen van taken gedurende een vaste hoeveelheid tijd en voor het pauzeren en hervatten van taken;
  • Speciale alarmsignalen en time-outs.
  • Het hart van een realtime-systeem is de korte-termijnscheduler voor taken. Bij het ontwerpen van een dergelijke scheduler zijn eerlijkheid en het minimaliseren van de gemiddelde antwoordtijd niet het meest zwaarwegend. Wat wel belangrijk is, is dat alle harde realtime-taken worden voltooid (of beginnen) op hun deadline en dat zo veel mogelijk zachte realtime-taken worden voltooid (of beginnen) op hun deadline.

    De meeste moderne realtime-besturingssystemen kunnen niet rechtstreeks werken met deadlines. In plaats daarvan zijn ze ontworpen om zo snel mogelijk te reageren op realtime-taken, zodat een taak bij het naderen van een deadline snel kan worden ingeroosterd. Hierdoor vereisen realtime-toepassingen doorgaans deterministische antwoordtijden in het bereik van enkele milliseconden tot minder dan een milliseconde onder sterk uiteenlopende omstandigheden. Hypermoderne toepassingen, bijvoorbeeld simulators voor militaire vliegtuigen, hebben vaak beperkingen in het bereik van 10 tot en met 100 µs [ATLA89].

    Figuur 10.4 illustreert een spectrum van mogelijkheden. In een preëmptieve scheduler die eenvoudige scheduling met round robin gebruikt, wordt een realtimetaak toegevoegd aan een wachtrij Gereed in afwachting van zijn volgende tijdsdeel, zoals wordt geïllustreerd in figuur 10.4a. In dat geval zal de schedulingtijd veelal onacceptabel zijn voor realtime-toepassingen. We zouden ook een niet-preëmptieve scheduler met een schedulingmechanisme op basis van prioriteiten kunnen gebruiken, waarbij realtime-taken een hogere prioriteit wordt gegeven. In dat geval wordt een realtime-taak die gereed is, ingeroosterd zodra het huidige proces wordt geblokkeerd of is voltooid (figuur 10.4b). Dit kan leiden tot een vertraging van enkele seconden wanneer een langzame taak met een lage prioriteit op een kritiek moment wordt uitgevoerd. Ook deze benadering is niet acceptabel. Een meer aantrekkelijke benadering is het combineren van prioriteiten met op een klok gebaseerde interrupts. Preëmptieve onderbrekingspunten treden op met regelmatige intervallen. Treedt een preëmptief onderbrekingspunt op, dan wordt de op dat moment actieve taak preëmptief onderbroken als een taak met een hogere prioriteit wacht. Ook taken die deel uitmaken van de kernel van het besturingssysteem, kunnen preëmptief worden onderbroken. Zo’n vertraging kan een orde van grootte hebben van enkele milliseconden (figuur 10.4c). Deze benadering kan voldoende zijn voor sommige realtime-toepassingen, maar is ontoereikend voor toepassingen met zwaardere vereisten. In die gevallen wordt een benadering gebruikt die soms onmiddellijke preëmptieve verwerking wordt genoemd. In dat geval reageert het besturingssysteem vrijwel onmiddellijk op een interrupt, tenzij het systeem zich in een uitsluitinggebied voor kritieke code bevindt. Schedulingvertragingen voor een realtime-taak kunnen worden gereduceerd tot 100 µs of minder.

    Real-time systeem heeft unieke vereisten in 5 gebieden:

  • Determinisme
  • OS voert operaties uit
  • Op vaste, vooraf vastgelegde tijdstippen
  • Binnen vooraf vastgelegde intervallen
  • Systeem is niet volledig deterministisch als aantal processen concurreren om dezelfde bronnen en processortijd
  • Mate van determinisme meten door
  • Maximale vertraging tussen aankomst van een interrupt van hoge prioriteit en de bevestiging ervan
  • In niet real-time systemen tot paar honderden ms
  • Bij real-time systeem < 1 ms
  • Reactievermogen
  • Wordt bepaald door de tijd tussen het bevestigingen van de interrupt en het effectieve afhandeling ervan
  • Reactievermogen is afhankelijk van
  • Tijd nodig voor het initieel behandelen van de interrupt en het uitvoeren van de Interrupt Service Routine (ISR)
  • Tijd nodig voor het uitvoeren van ISR, afhankelijk van de hardware
  • Effect van geneste interrupts
  • Als een IRS kan onderbroken worden bij het ontvangen van een andere interrupt zal hij vertraagd worden
  • Determinisme + Reactievermogen = antwoordtijd voor externe gebeurtenissen
  • Gebruikerscontrole
  • Veel meer aanwezig bij real-timesysteem dan bij een normaal systeem
  • Bij normaal systeem heeft gebruiker geen controle over scheduling
  • Wel mogelijkheid tot geven van richtlijnen (b.v.: groeperen van gebruikers in klassen met prioriteiten)
  • Bij real-time systeem is het essentieel dat een gebruiker fijnkorrelige controle heeft
  • Gebruiker moet onderscheid kunne maken tussen harde en zachte taken
  • Relatieve prioriteiten toekennen aan het aantal klassen
  • Betrouwbaarheid
  • Veel belangrijker bij real-time systemen
  • Problemen bij niet real-time systeem
  • Kortstondig probleem kan je oplossen met reboot
  • Falen van een processor in een multiprocessor systeem leidt tot lager niveau van bediening tot processor gemaakt of vervangen is
  • Real-time systeem reageert op en controleert gebeurtenissen in real time
  • Geen mogelijkheid tot rebooten van het systeem bij problemen
  • Problemen bij real-time systeem leidt tot
  • Verminderde performantie wat op zijn beurt zal leiden tot
  • Kenmerken van een real-timesysteem:

  • Snel wisselen van processen en draden
  • Kleine grootte (≈ minimale functionaliteit)
  • Vermogen om snel op externe onderbrekingen te reageren
  • Multitasking met communicatie tussen processen onderling dankzij semaforen, signalen en gebeurtenissen
  • Gebruiken van speciale sequentiële bestanden die snel data kunnen accumuleren
  • Voortijdige planning op basis van prioriteiten
  • Minimaliseren van periodes waarin onderbrekingen uitgeschakeld zijn
  • Primitieven om taken te vertragen, pauzeren, verder te zetten
  • Speciale alarmen en time-outs
  • 10.2.3. Real-time-scheduling

    Realtime-scheduling is een onderwerp dat veel aandacht krijgt bij het onderzoek in de informatica. In deze paragraaf geven we een overzicht van de verschillende benaderingen voor realtime-scheduling en bekijken we twee populaire klassen schedulingalgoritmen.

    In een overzicht van algoritmen voor realtime-scheduling merkt [RAMA94I op dat de verschillende schedulingvormen afhankelijk zijn van: (1) of het systeem een analyse uitvoert van de inroosterbaarheid en zo ja, (2) of een dergelijke analyse statisch of dynamisch wordt uitgevoerd en (3) of het resultaat van de analyse zelf een rooster of plan produceert waarmee taken worden toegedeeld tijdens de verwerking. Op basis van deze overwegingen onderscheiden de auteurs de volgende klassen algoritmen:

  • Statische, tabelgestuurde vormen. Deze voeren een statische analyse uit van haalbare roosters voor de toedeling. Het resultaat van de analyse is een rooster dat tijdens de uitvoering bepaalt wanneer de verwerking van een taak moet beginnen.
  • Statische, prioriteitgestuurde, preëmptieve vormen. Ook hierbij wordt een statische analyse uitgevoerd, maar er wordt geen rooster opgesteld. In plaats daarvan wordt de analyse gebruikt om prioriteiten toe te wijzen aan taken, zodat een traditionele, prioriteitgestuurde, preëmptieve scheduler kan worden gebruikt.
  • Dynamische, op planning gebaseerde vormen. De haalbaarheid wordt tijdens de verwerking bepaald (dynamisch) in plaats van offline voorafgaand aan de start van de verwerking (statisch). Een binnenkomende taak wordt uitsluitend voor uitvoering geaccepteerd als de tijdbeperkingen daarvan waarschijnlijk haalbaar zijn. Een van de resultaten van de haalbaarheidsanalyse is een rooster of plan dat wordt gebruikt om te beslissen wanneer de taak wordt uitgevoerd.
  • Dynamisch zo goed mogelijk proberen. Er wordt geen haalbaarheidsanalyse uitgevoerd. Het systeem probeert alle deadlines te halen en breekt een gestart proces af wanneer de deadline daarvan niet is gehaald.
  • Statische, tabelgestuurde scheduling is geschikt voor periodieke taken. De invoer voor de analyse bestaat uit de periodieke aankomsttijd, verwerkingstijd, periodieke einddeadline en relatieve prioriteit van elke taak. De scheduler probeert een rooster te maken waarmee hij kan voldoen aan de vereisten van alle periodieke taken. Dit is een voorspelbare maar inflexibele benadering, omdat elke verandering van taakeisen het opnieuw opstellen van het rooster noodzakelijk maakt. Vroegste-deadline-eerst of een andere periodieke deadlinetechniek (die verderop worden besproken) zijn standaardvoorbeelden van deze categorie schedulingalgoritmen.

    Statische, prioriteitgestuurde, preëmptieve scheduling maakt gebruik van het prioriteitgestuurde, preëmptieve schedulingmechanisme dat gebruikelijk is voor de meeste niet-realtime-multiprogrammeringsystemen. In een niet-realtime-systeem kunnen uiteenlopende factoren worden gebruikt om de prioriteit te bepalen. Bij een timesharingsysteem verandert de prioriteit van een proces bijvoorbeeld afhankelijk van het feit of het processorgebonden of 1/0-gebonden is. In een realtime-systeem hangt de prioriteittoewijzing samen met de tijdbeperkingen die gelden voor elke taak. Een voorbeeld van deze aanpak is de algoritme voor frequentiescheduling (die wordt besproken in paragraaf 10.2.5), die statische prioriteiten toewijst aan taken op basis van hun perioden.

    Bij dynamische, op planning gebaseerde scheduling wordt na aankomst van een taak, maar voor de start van de verwerking, geprobeerd een rooster te maken dat de eerder ingeroosterde taken en de nieuw binnengekomen taak bevat. Kan de nieuw binnengekomen taak zo worden ingeroosterd dat wordt voldaan aan de deadlines van de taak en geen thans ingeroosterde taak een deadline zal missen, dan wordt het rooster herzien om ruimte te bieden aan de nieuwe taak.

    Dynamisch zo goed mogelijk proberen is de aanpak die wordt gebruikt door veel realtime-systemen die op dit moment op de markt zijn. Bij aankomst van een taak wijst het systeem een prioriteit toe op basis van de kenmerken van de taak. Doorgaans wordt een vorm van deadline-scheduling gebruikt, bijvoorbeeld vroegste-deadline-scheduling. Meestal zijn de taken niet-periodiek, waardoor geen statische schedulinganalyse mogelijk is. Bij dit soort scheduling weten we, totdat een deadline binnenkomt of de taak wordt voltooid, niet of aan een tijdbeperking kan worden voldaan. Dat is het grootste nadeel van deze vorm van scheduling. Het voordeel is dat hij gemakkelijk te implementeren is.

    Het aantal aanpakken van planning zijn afhankelijk van:

  • Doet het systeem aan planbaarheidsanalyse
  • Statisch of dynamische planbaarheidsanalyse
  • Of het resultaat van die analyse al dan niet zelf voor een planning zorgt
  • Het aantal klassen van algoritmes:

  • Statische tabelgestuurde aanpak
  • Statische prioriteitgestuurde voortijdige aanpak
  • Dynamische planningsgebaseerde aanpak
  • Dynamische beste pogingaanpak
  • Statische tabelgestuurde aanpak

  • Werking
  • Statische analyse van uitvoerbare planningen
  • Resultaat van de analyse is een planning die at run time bepaald wanneer elke taak moet gestart worden
  • Toepasbaar op periodieke taken
  • Invoer voor de analyse
  • Periodieke aankomsttijd
  • Uitvoeringstijd
  • Periodieke einddeadline
  • Relatieve prioriteit van elke taak
  • Planning zoeken zodat voor alle periodieke taken voldaan is
  • Nadeel: niet flexibel: Verandering van taakvereisten zorgt ervoor dat het schema opnieuw bepaald moet worden
  • Voorbeeld: Earliest-deadline-first
  • Statische prioriteitgestuurdevoortijdige aanpak

  • Analyse produceert geen planning
  • Analyse wordt gebruikt om prioriteiten toe te kennen
  • Schedulergebaseerd op prioriteiten gebruiken
  • Op basis van tijdsbeperkingen die aan elke taak vast hangen
  • B.v.: op basis van de lengte van de periodes van een taak
  • Dynamische aanpak gebaseerd op plannen

  • Haalbaarheid wordt bij run time bepaald (= dynamisch) en niet vooraf (= statisch)
  • Taak wordt enkel uitgevoerd indien zijn haalbaarheid voldoende hoog is
  • Resultaat van deze analyse is een schema dat aanduidt wanneer welke taak uitgevoerd kan worden
  • Werking
  • Indien nieuwe taak aangemaakt wordt
  • Inpassen in het schema op basis van zijn haalbaarheid
  • Rekening houden met oude taken die al in het schema zaten
  • Geen enkele taak die al gepland was mag zijn deadline missen
  • Voert geen haalbaarheidsanalyse uit
  • Probeert alle deadlines te halen
  • Annuleren van gestarte processen die hun deadline gemist hebben
  • Meest gebruikte in real-time systemen
  • Dynamische aanpak gebaseerd op beste poging

  • Werking
  • Als taak binnenkomt kent het systeem een prioriteit toe op basis van de taakeigenschappen
  • Gebruikt een vorm van deadline planning
  • Voordeel: eenvoudig te implementeren
  • Nadeel: We weten niet op voorhand of we een tijdsbeperking zullen halen. Enkel info bij verstrijken deadline of voltooiing taak
  • 10.2.4. Deadline-scheduling

    De meeste huidige realtime-besturingssystemen zijn ontworpen met het doel real-time-taken zo snel mogelijk te starten, waarbij de nadruk ligt op een snelle interruptaffiandeling en taaktoedeling. In feite is dit een niet echt bruikbare norm voor het beoordelen van realtime-besturingssystemen. Realtime-toepassingen zijn meestal niet afhankelijk van pure snelheid maar meer van het voltooien (of starten) van taken op de meest waardevolle tijdstippen, niet te vroeg noch te laat, in een omgeving met dynamische behoeften aan en conflicten om voorzieningen, overbelaste verwerking en hardware- en softwarefouten. Hieruit volgt dat prioriteiten een grof instrument zijn en geen rekening houden met de vereiste voltooiing (of initiatie) op het meest waardevolle tijdstip.

    In de afgelopen jaren zijn enkele voorstellen gedaan voor een meer krachtige en beter geschikte aanpak voor realtime-scheduling. Alle voorstellen zijn gebaseerd op de beschikbaarheid van aanvullende informatie over elke taak. In de meest algemene vorm kan de volgende informatie over een taak worden gebruikt:

  • Tijdstip gereed: tijdstip waarop een taak gereed is voor verwerking. Bij een herhaalde of periodieke taak is dit eigenlijk een reeks tijdstippen die van tevoren bekend is. Bij een niet-periodieke taak kan deze tijd van tevoren bekend zijn of merkt het besturingssysteem het pas wanneer de taak werkelijk gereed staat.
  • Begindeadline: tijdstip waarop een taak moet beginnen.
  • Einddeadline: tijdstip waarop een taak voltooid moet zijn. Een doorsnee real- time-toepassing gebruikt begindeadline of einddeadline maar niet beide.
  • Verwerkingstijd: tijd die nodig is voor het volledig uitvoeren van de taak. Deze tijd is soms bekend. In andere gevallen meet het besturingssysteem een exponentieel gemiddelde. Bij weer andere vormen van scheduling wordt deze informatie niet gebruikt.
  • Voorzieningenvereisten: de verzameling voorzieningen (anders dan de processor) die vereist is voor de uitvoering van deze taak.
  • Prioriteit: meet de relatieve belangrijkheid van de taak. Harde realtime-taken kunnen een ‘absolute’ prioriteit hebben, waarbij het systeem faalt als een deadline wordt gemist. Moet het systeem blijven werken wat er ook gebeurt, dan kunnen aan zowel harde als zachte realtime-taken relatieve prioriteiten worden toegewezen als richtlijn voor de scheduler.
  • Subtaakstructuur: een taak kan worden gesplitst in een verplichte subtaak en een facultatieve subtaak. Alleen de verplichte subtaak heeft een harde deadline.
  • Elke aanpak voor plannen van real-timetaken heeft nood aan extra informatie van de taak:

  • Ready time
  • Tijd wanneer een taak beschikbaar wordt om uitgevoerd te worden
  • Bij herhalings-of periodieke taken = vooraf gekende tijdstippen
  • Bij niet-periodieke taken = niet altijd op voorhand gekend, soms pas wanneer de taak klaar is
  • Startdeadline
  • Tijdstip wanneer de taak moet beginnen
  • Einddeadline
  • Tijdstip waarop de taak moet voltooid zijn
  • Typische real-time toepassing heeft een start of einddeadline, maar niet beiden
  • Elke aanpak voor plannen van real-timetaken heeft nood aan extra informatie van de taak

  • Processing time
  • Tijd nodig om de taak te voltooien (opgegeven of een rekenkundig gemiddelde)
  • Resource requirements
  • Bronnen (andere dan de processor) die nodig zijn voor de uitvoering
  • Prioriteit
  • Meet de relatieve prioriteit van een taak
  • Structuur van de deeltaak
  • Taak kan bestaat uit een verplicht deeltaak en een optionele deeltaak
  • Enkel de verplichte deeltaak heeft een harde deadline
  • Rekening houden bij de planning met

  • Wat is de volgende taak
  • Is voortijdige beëindiging toegelaten?
  • Startdeadline
  • Einddeadline
  • 10.2.5. Frequentie planning

    Een veelbelovende methode voor het oplossen van schedulingconflicten bij meerdere periodieke taken is frequentiescheduling (rate monotonic scheduling, RMS). Het systeem werd voor het eerst voorgesteld in [L1U73], maar heeft pas recent gewonnen aan populariteit [BRIA99I, [SHA94j. RMS wijst prioriteiten toe aan taken op basis van hun frequentie.

    Herhalingsvragen

    1. Noem en omschrijf in het kort vijf verschillende categorieën voor de granulariteit van synchronisatie.

      Fijn: Parallelliteit inherent aan één instructiestroom.
      Gemiddeld: Parallelle verwerking of multitasking binnen één toepassing.
      Grof: Multiprocessing van gelijktijdige processen in een multiprogrammeerbare omgeving. Zeer grof: Gedistribueerde verwerking via netwerkknooppunten voor het vormen van één computeromgeving.
      Onafhankelijk: Meerdere niet-gerelateerde processen.
       
    2. Noem en omschrijf in het kort vier technieken voor de scheduling van threads.

      Delen van belasting (load sharing): Processen worden niet toegewezen aan een bepaalde processor. Er wordt één globale wachtrij van gereedstaande processen bijgehouden en een processor die niets te doen heeft, selecteert een thread uit deze wachtrij. Het begrip delen van belasting wordt gebruikt om een onderscheid te maken tussen deze aanpak en manieren voor evenwichtig verdelen van belasting (load balancing), waarbij werk meer permanent wordt toegewezen.
      Groepsscheduling (Gang scheduling): Een groep gerelateerde threads wordt ingeroosterd om gelijktijdig te worden uitgevoerd op een aantal processors in een verhouding één op één.
      Vaste processortoewijzing: Elk programma wordt voor de duur van de uitvoering van het programma een aantal processors toegewezen dat gelijk is aan het aantal threads in het programma. Wordt het programma beëindigd, dan worden de processors weer toegevoegd aan de algemene verzameling voor een mogelijke toewijzing aan een ander programma.
      Dynamische scheduling: Het aantal threads in een programma kan tijdens de uitvoering worden aangepast.
       
    3. Noem en omschrijf in het kort drie versies voor het verdelen van belasting.

      First come, first served (FCFS). Bij aankomst van een job worden alle threads ervan na elkaar toegevoegd aan het einde van de gedeelde wachtrij. Heeft een processor niets meer te doen, dan selecteert hij de volgende gereedstaande thread, die hij uitvoert totdat de, thread is voltooid of wordt geblokkeerd.
      Laagste aantal threads eerst. De wachtrij Gereed wordt ingedeeld als een prioriteitswachtrij, waarbij de hoogste prioriteit wordt gegeven aan threads van jobs met het kleinste aantal niet-ingeroosterde threads. Jobs met dezelfde prioriteit worden ingedeeld op basis van de job die het eerst aankomt. Net zoals bij FCFS wordt een thread uitgevoerd totdat deze is voltooid of wordt geblokkeerd.
      Preëmptief laagste aantal threads eerst. De hoogste prioriteit wordt gegeven aan jobs met het kleinste aantal onvoltooide threads. Komt een nieuwe job binnen met een kleiner aantal threads dan een job die wordt uitgevoerd, dan wordt de uitvoering van de threads van de ingeroosterde job preëmptief onderbroken.
       
    4. Wat is het verschil tussen harde en zachte realtime-taken?

      Een harde realtime-taak is een taak die moet voldoen aan zijn deadline; voldoet de taak niet aan de deadline, dan leidt dat tot ongewenste schade of een fatale fout in het systeem.
      Een zachte realtime-taak
      heeft een deadline die gewenst maar niet verplicht is; het inroosteren en voltooien van de taak blijft zinvol, zelfs als de deadline is overschreden.
       
    5. Wat is het verschil tussen periodieke en niet-periodieke realtime-taken?

      Een niet-periodieke taak heeft een deadline waarop de taak moet eindigen of beginnen of heeft een beperking voor zowel de begintijd als de eindtijd.
      Bij een periodieke taak kan de vereiste worden geformuleerd als ‘eens per periode T’ of ‘precies om de T eenheden’.
       
    6. Noem en omschrijf in het kort vijf algemene gebieden met vereisten voor een realtime-besturingssysteem.

      Determinisme: Een systeem is tot op zekere hoogte deterministisch omdat het bewerkingen uitvoert op vaste, vooraf vastgestelde tijdstippen of binnen vooraf vastgestelde tijdsintervallen.
      Reactievermogen: Het reactievermogen heeft te maken met de tijd die het besturingssysteem na deze bevestiging nodig heeft om de interrupt af te handelen.
      Gebruikersinvloed: De gebruiker moet een onderscheid kunnen maken tussen harde en zachte taken en relatieve prioriteiten kunnen specificeren binnen elke klasse. Een realtime-systeem kan de gebruiker ook de mogelijkheid bieden kenmerken te specificeren; bijvoorbeeld het gebruik van paginering of processwapping, welke processen altijd resident moeten zijn in het hoofdgeheugen, welke algoritmen bij schijfoverdracht moeten worden gebruikt, welke rechten de processen in verschillende prioriteitsbanden hebben enzovoort.
      Betrouwbaarheid: Betrouwbaarheid is doorgaans veel belangrijker bij realtime-systemen dan bij niet-realtime-systemen. Een kortstondige fout kan bij een niet-realtime-systeem worden opgelost door het systeem eenvoudig opnieuw te starten. Een processorfout kan bij een niet-realtime-systeem met meerdere processors leiden tot een verminderd bedieningsniveau totdat de falende processor is gerepareerd of vervangen. Een realtime-systeem daarentegen, bestuurt gebeurtenissen realtime-of reageert realtime-op gebeurtenissen. Een verlies of afname van prestaties kan rampzalige gevolgen hebben, die uiteenlopen van financiële verliezen tot grote schade aan apparatuur en zelfs dodelijke ongelukken.
      Fail-soft werking: Een fail-soft werking is een kenmerk dat verwijst naar de mogelijkheid van het systeemfouten zo op te vangen dat mogelijkheden en gegevens zo veel mogelijk behouden blijven.
       
    7. Noem en omschrijf in het kort vier klassen van algoritmen voor realtime-scheduling.

      Statische, tabelgestuurde vormen. Deze voeren een statische analyse uit van haalbare roosters voor de toedeling. Het resultaat van de analyse is een rooster dat tijdens de uitvoering bepaalt wanneer de verwerking van een taak moet beginnen.
      Statische, prioriteitgestuurde, preëmptieve vormen. Ook hierbij wordt een statische analyse uitgevoerd, maar er wordt geen rooster opgesteld. In plaats daarvan wordt de analyse gebruikt om prioriteiten toe te wijzen aan taken, zodat een traditionele, prioriteitgestuurde, preëmptieve scheduler kan worden gebruikt.
      Dynamische, op planning gebaseerde vormen. De haalbaarheid wordt tijdens de verwerking bepaald (dynamisch) in plaats van offline voorafgaand aan de start van de verwerking (statisch). Een binnenkomende taak wordt uitsluitend voor uitvoering geaccepteerd als de tijdbeperkingen daarvan waarschijnlijk haalbaar zijn. Een van de resultaten van de haalbaarheidsanalyse is een rooster of plan dat wordt gebruikt om te beslissen wanneer de taak wordt uitgevoerd.
      Dynamisch zo goed mogelijk proberen. Er wordt geen haalbaarheidsanalyse uitgevoerd. Het systeem probeert alle deadlines te halen en breekt een gestart proces af wanneer de deadline daarvan niet is gehaald.
       
    8. Welke vormen van informatie over een taak kunnen nuttig zijn bij realtime-scheduling?

      Tijdstip gereed: tijdstip waarop een taak gereed is voor verwerking. Bij een herhaalde of periodieke taak is dit eigenlijk een reeks tijdstippen die van tevoren bekend is. Bij een niet-periodieke taak kan deze tijd van tevoren bekend zijn of merkt het besturingssysteem het pas wanneer de taak werkelijk gereed staat.
      Begindeadline: tijdstip waarop een taak moet beginnen.
      Einddeadline: tijdstip waarop een taak voltooid moet zijn. Een doorsnee real- time-toepassing gebruikt begindeadline of einddeadline maar niet beide.
      Verwerkingstijd: tijd die nodig is voor het volledig uitvoeren van de taak. Deze tijd is soms bekend. In andere gevallen meet het besturingssysteem een exponentieel gemiddelde. Bij weer andere vormen van scheduling wordt deze informatie niet gebruikt.
      Voorzieningenvereisten: de verzameling voorzieningen (anders dan de processor) die vereist is voor de uitvoering van deze taak.
      Prioriteit: meet de relatieve belangrijkheid van de taak. Harde realtime-taken kunnen een ‘absolute’ prioriteit hebben, waarbij het systeem faalt als een deadline wordt gemist. Moet het systeem blijven werken wat er ook gebeurt, dan kunnen aan zowel harde als zachte realtime-taken relatieve prioriteiten worden toegewezen als richtlijn voor de scheduler.
      Subtaakstructuur: een taak kan worden gesplitst in een verplichte subtaak en een facultatieve subtaak. Alleen de verplichte subtaak heeft een harde deadline.

    Probleemvraagstukken

    1. Ga uit van een verzameling van drie periodieke taken met de verwerkingsprofielen van tabel 10.5. Stel voor deze verzameling taken schedulingdiagrammen op die vergelijkbaar zijn met die van figuur 10.5.
       
    2. Ga uit van een verzameling van vijf niet-periodieke taken met de verwerkingsproficlen van tabel 10.6. Stel voor deze verzameling taken schedulingdiagrammen op die vergehjkbaar zijn met die van figuur 10.6.
       
    3. Deze opgave laat zien dat vergelijking 10.2 voor frequentiescheduling (RMS) een voldoende voorwaarde is voor succesvolle scheduling, maar geen noodzakelijke voorwaarde. (Dat wil zeggen: een succesvolle scheduling is soms ook mogelijk als nie:
      wordt voldaan aan vergehjking 10.2.)
      1. Ga uit van de volgende verzameling onaffiankelijke, periodieke taken:
      2. taak P1:C1 = 20 en T1 = 100;
      3. taak P2:C2 = 30 en T2 = 145.

      Kunnen deze taken succesvol worden ingeroosterd met RMS?

      1. Voeg nu de volgende taak toe aan de verzameling:
      2. taak P3:C3 = 68 en T3 = 150.

      Wordt voldaan aan vergelijking 10.2?

      1. Veronderstel dat de eerste instantie van deze drie taken aankomt op tijdstip t 0. Ga ervan uit dat de eerste deadline voor elke taak als volgt is:

                    D1 = 100;     D2 = 145;     D3 = 150

      Kunnen de drie deadlines alle worden gehaald met frequentiescheduling? En wat kunt u zeggen over de deadlines van toekomstige herhalingen van elke taak?
       

    4. Teken een schema zoals dat in figuur 10-9a. dat de reeks gebeurtenissen laat zien voor hetzelfde voorbeeld met gebruikmaking van een prioriteitplafond.