Samenvatting Besturingssystemen
Vloeberghs Sam 2 Toegepaste Informatica 4 2007-2008
BESCHRIJVING EN BESTURING VAN PROCESSEN...................................................................................4 WAT IS EEN PROCES?.................................................................................................................................................4 Processen en besturingsblokken......................................................................................................................4 PROCESTOESTANDEN..................................................................................................................................................4 Creëren en beëindigen van processen..............................................................................................................4 Procesmodel met 2 toestanden.........................................................................................................................5 Procesmodel met 5 toestanden.........................................................................................................................6 Redenen voor het opschorten van processen:..................................................................................................7 BESCHRIJVING VAN PROCESSEN....................................................................................................................................7 Beheersstructuren in het besturingssysteem....................................................................................................7 Beheersstructuren voor processen...................................................................................................................7 PROCESBESTURING.....................................................................................................................................................9 Uitvoeringsmodi...............................................................................................................................................9 Creëren van processen.....................................................................................................................................9 Wisselen van processen..................................................................................................................................10 Uitvoering van het besturingssysteem............................................................................................................11 PROCESBEHEER IN UNIX SVR4..............................................................................................................................12 Procestoestanden...........................................................................................................................................12 Beheer van processen.....................................................................................................................................12 THREADS , SMP EN MICROKERNELS.........................................................................................................14 PROCESSEN EN THREADS...........................................................................................................................................14 Multithreading................................................................................................................................................14 Functionaliteiten van threads........................................................................................................................15 Voorbeeld : Adobe Pagemaker......................................................................................................................16 Threads op gebruikersniveau en op kernelniveau.........................................................................................16 Andere indelingen..........................................................................................................................................17 SYMMETRISCHE MULTIPROCESSING..............................................................................................................................17 Architectuur van SMP....................................................................................................................................18 Ontwerpen van besturingssystemen voor SMP..............................................................................................19 MICROKERNELS.......................................................................................................................................................19 Architectuur van een microkernel..................................................................................................................19 Voordelen van een microkernel.....................................................................................................................20 Prestaties van een microkernel......................................................................................................................20 Ontwerp van een microkernel........................................................................................................................21 BEHEER VAN THREADS EN SMP IN SOLARIS...............................................................................................................22 Architectuur met multithreading....................................................................................................................22 Motivering......................................................................................................................................................23 Interrupts als threads.....................................................................................................................................23 BEHEER VAN PROCESSEN EN THREADS IN LINUX...........................................................................................................23 Taken in Linux................................................................................................................................................23 Threads in Linux............................................................................................................................................24 GELIJKTIJDIGHEID : WEDERZIJDSE UITSLUITING EN SYNCHRONISATIE..................................25 PRINCIPES VAN GELIJKTIJDIGHEID...............................................................................................................................25 Een eenvoudig voorbeeld...............................................................................................................................26 Aandachtspunten voor het besturingssysteem................................................................................................27 Interactie van processen................................................................................................................................27 Vereisten voor wederzijdse uitsluiting...........................................................................................................28 WEDERZIJDSE UITSLUITING : HARDWAREONDERSTEUNING................................................................................................28 Uitschakelen van interrupts...........................................................................................................................28 Speciale machine instructies..........................................................................................................................29 SEMAFOREN............................................................................................................................................................30 Wederzijdse uitsluiting...................................................................................................................................31 Implementatie van semaforen........................................................................................................................31 MONITOREN...........................................................................................................................................................31 Monitor met signal.........................................................................................................................................32 GELIJKTIJDIGHEID : DEADLOCKS EN UITHONGERING.....................................................................33
BEGINSELEN VAN DEADLOCK.....................................................................................................................................33 Herbruikbare hulpbronnen............................................................................................................................33 Verbruikbare hulpbronnen.............................................................................................................................33 Condities voor deadlock.................................................................................................................................34 VOORKOMEN VAN DEADLOCK....................................................................................................................................35 Wederzijdse uitsluiting...................................................................................................................................35 Vasthouden en wachten..................................................................................................................................35 Geen preëmptieve onderbreking....................................................................................................................36 Cirkelvormig wachten....................................................................................................................................36 VERMIJDEN VAN DEADLOCK......................................................................................................................................36 Weigeren van een nieuw proces.....................................................................................................................37 Weigeren om bronnen toe te wijzen...............................................................................................................37 DETECTEREN VAN DEADLOCK....................................................................................................................................38 Algoritmen voor detecteren deadlock............................................................................................................38 Herstel............................................................................................................................................................39 GEÏNTEGREERDE AANPAK VAN DEADLOCK....................................................................................................................39 PROBLEEM VAN DE DINERENDE FILOSOFEN...................................................................................................................40 MECHANISMEN VOOR GELIJKTIJDIGHEID IN UNIX........................................................................................................41 Pijpen.............................................................................................................................................................41 Berichten........................................................................................................................................................41 Gedeeld geheugen..........................................................................................................................................41 Semaforen.......................................................................................................................................................41 Signalen..........................................................................................................................................................41 GEHEUGENBEHEER.........................................................................................................................................42 VEREISTEN VOOR GEHEUGENBEHEER...........................................................................................................................42 Relocatie.........................................................................................................................................................42 Bescherming...................................................................................................................................................43 Delen..............................................................................................................................................................43 Logische indeling...........................................................................................................................................43 Fysieke indeling.............................................................................................................................................43 PARTITIONEREN VAN GEHEUGEN.................................................................................................................................44 Vaste indeling van Partities...........................................................................................................................44 Dynamische indeling van partities.................................................................................................................45 Buddysysteem.................................................................................................................................................46 Relocatie.........................................................................................................................................................47 PAGINEREN.............................................................................................................................................................48 SEGMENTEREN........................................................................................................................................................50 VIRTUEEL GEHEUGEN....................................................................................................................................51 HARDWARE EN BESTURINGSSTRUCTUREN.....................................................................................................................51 Lokaliteit en virtueel geheugen......................................................................................................................51 Pagineren.......................................................................................................................................................52 Segmenteren...................................................................................................................................................58 Gecombineerd pagineren en segmenteren.....................................................................................................60 Bescherming en delen....................................................................................................................................60 BESTURINGSSYSTEEMSOFTWARE.................................................................................................................................61 Strategie bij ophalen (fetch policy )...............................................................................................................61 Strategie bij plaatsing....................................................................................................................................61 Strategie bij vervanging.................................................................................................................................62 Beheer van de residente set............................................................................................................................63 Opschoon strategie.........................................................................................................................................66 Toezicht op de procesbelasting......................................................................................................................66
Beschrijving en besturing van processen Wat is een proces? Processen en besturingsblokken We kunnen een proces voorstellen als een entiteit die bestaat uit een aantal elementen. Twee essentiële: 1. de programma code 2. verzameling van gegevens die bij de code hoort Een proces is gekenmerkt door een aantal elementen uit het procesbesturingsblok: o Identificatienummer o Toestand o Prioriteit o Programmateller o Geheugenwijzers o Contextgegevens o IO-toestandsinformatie o Beheersinformatie Het procesbesturingsblok moet voldoende informatie bevatten om een proces dat uitgevoerd wordt te kunnen onderbreken en op een later moment gewoon terug te kunnen starten alsof het nooit onderbroken werd. Het procesbesturingsblok is het belangrijkste hulpmiddel voor een besturingssysteem bij de ondersteuning van verschillende processen, waardoor multiprocessing mogelijk wordt. PROCES = PROGRAMMACODE & BIJHORENDE GEGEVENS + procesbesturingsblok
Procestoestanden We kunnen het gedrag van een individueel proces beschrijven aan de hand van de volgorde van instructies die voor dat proces worden uitgevoerd: deze volgorde wordt een spoor ( trace ) van het proces genoemd. Er kunnen meerdere processen tegelijk uitgevoerd worden. De toedeler ( dispatcher ) wijst de processor wisselend toe aan de verschillende processen. De sporen van deze verschillende processen worden dus ‘ verweven ‘
Creëren en beëindigen van processen Creëren van processen Nieuwe batchtaak Interactieve aanmelding Gecreëerd door het besturingssysteem om een dienst te verzorgen Verwerkt door een bestaand proces
Besturingssysteem ontvangt een jobbesturingsopdracht. Als het besturingssysteem bereid is de nieuwe taak uit te voeren, zal het de volgende reeks opdrachten lezen . Een gebruiker van het werkstation meld zich aan bij het systeem Het besturingssysteem kan een proces aanmaken om een bepaalde dienst af te werken waar de gebruiker om vraagt: bijvoorbeeld printen Een bestaand proces kan kind processen aanmaken die bepaalde bewerkingen afzonderlijk afwerken en het moederproces ondersteunen
Beëindigen van processen Normale voltooiing Tijdslimiet overschreden Onvoldoende geheugen beschikbaar Overtreding geheugengrens Beschermingsfout Rekenkundige fout Tijd verstreken I/O-fout Ongeldige instructie Geprivilegieerde instructie Onjuist gebruik van gegevens Ingreep van de gebruiker of het besturingssysteem Beëindiging van het ouderproces Verzoek van het ouderproces
Proces roept een dienst aan om te melden dat uitvoering voltooid Proces wordt afgesloten omdat het zijn uitvoeringstijd heeft overschreden … Proces probeert toegang te krijgen tot geheugenlocaties die niet voor hem bestemd zijn Het proces probeert iets te doen waar het geen rechten voor heeft, bijvoorbeeld schrijven naar een alleen-lezen bestand. Delen door nul,… Het proces heeft langer gewacht op een gebeurtenis als aangegeven Er is een fout opgetreden bij de invoer of uitvoer van gegevens naar/van het proces Proces probeert instructie uit te voeren die niet bestaat Proces probeert gereserveerde instructie uit te voeren. De gegevens zijn mogelijk niet van het juiste type of zijn nog niet geinitialiseerd. De gebruiker of besturingssysteem roept een instructie aan om het proces te beëindigen Als het ouderproces beëindigt wordt , worden meestal ook de kindprocessen beindigd Het ouderproces kan verzoeken aan een kindproces om er mee te stoppen.
Procesmodel met 2 toestanden
Procesmodel met 5 toestanden
Actief ( running ) Gereed ( ready) Geblokkeerd ( blocked ) Nieuw ( new ) Einde ( exit )
Het proces dat op deze moment wordt uitgevoerd. In dit hoofdstuk gaan we uit van een single core processor => max 1 proces in deze toestand. Een proces dat direct kan worden uitgevoerd als het daar de gelegenheid voor krijgt. Een proces dat niet kan worden uitgevoerd totdat er zich een bepaalde gebeurtenis heeft afgespeeld. Een proces dat onlangs is aangemaakt maar zich nog niet in de ready state bevindt. Het is dus nog niet in het werkgeheugen geladen maar bevat al wel een procesbesturingsblok. Een proces dat door het besturingssysteem wordt ontslagen uit de groep uitvoerbare processen.
Opgeschorte processen ( proces dat zich NIET in het hoofdgeheugen bevindt ) Soms is er het probleem dat de processor sneller is dan I/O dus alle processen kunnen wachten op I/O. De oplossing hiervoor is het ‘swappen’ : dit is processen geheel of gedeeltelijk naar de schijf verplaatsen om hoofdgeheugen vrij te maken. Dit zorgt voor 2 nieuwe toestanden: Geblokkeerd – opgeschort Gereed - opgeschort
Het proces bevindt zich in het secundaire geheugen en wacht op een gebeurtenis Het proces bevindt zich in het secundaire geheugen maar is beschikbaar voor uitvoering zodra het in het hoofdgeheugen is geladen.
Redenen voor het opschorten van processen: Swapping Andere reden van het BS Verzoek van interactieve gebruiker Timing Verzoek van het ouderproces
Het besturingssysteem moet voldoende hoofdgeheugen vrijmaken voor het binnenhalen van een proces dat gereed is om te worden uitgevoerd. Het besturingssysteem kan een achtergrond of hulpproces opschorten of een proces dat ervan wordt verdacht een probleem te veroorzaken Een gebruiker kan de uitvoering van een programma opschorten om fouten te zoeken of om een bron te gebruiken Een proces kan periodiek worden uitgevoerd ( bijvoorbeeld een proces voor administratie of systeembewaking ) en kan worden opgeschort terwijl wordt gewacht op de volgende tijdsinterval Een ouderproces kan de uitvoering van een kindproces opschorten om het te onderzoeken of te wijzigen.
Beschrijving van processen Het besturingssysteem bestuurt gebeurtenissen binnen het computersysteem en verzorgt het inroosteren ( scheduling ) en de toedeling ( dispatching ) van processen voor uitvoering door de processor, wijst bronnen toe en reageert op vragen van gebruikersprogramma’s. Besturingssysteem = Entiteit die het gebruik van systeembronnen door processen beheert
Beheersstructuren in het besturingssysteem Het BS moet informatie bezitten over de huidige status van elk proces/bron. Het BS maakt en onderhoudt tabellen met informatie over elke entiteit die het beheert. Geheugentabellen - de toewijzing van hoofdgeheugen aan processen - de toewijzing van secundair geheugen aan processen - eventuele beschermingsattributen ( machtigingen v processen? ) - alle informatie die nodig is voor het beheren van het virtueel geheugen. I/O tabellen - informatie voor het beheren van I/O-kanalen en – apparaten. Bestandstabellen - informatie over het bestaan van bestanden, locatie, status en andere attributen. Procestabellen - informatie voor het beheren van processen. ( volgende puntje ) - 1 entry per proces = bevat identificatie nummer vh proces.
Beheersstructuren voor processen Proceslocatie De locatie van een procesbeeld is afhankelijk van het geheugenbeheersysteem dat wordt gebruikt. In het eenvoudigste geval wordt het procesbeeld bijgehouden als een aaneengesloten blok geheugen. Dit blok is opgeslagen in het secundaire geheugen, doorgaans op schijf. Het besturingssysteem moet dus de locatie van elk proces op schijf kennen en moet voor elk proces dat zich in het hoofdgeheugen bevindt, bovendien de locatie vh proces in het hoofdgeheugen kennen.
Procesbeeld: Gebruikersgegevens Gebruikersprogramma Systeemstack Procesbesturingsblok
Het deel van de gebruikersruimte dat kan worden gewijzigd. Dit kan bestaan uit programmagegevens, een stackgebied voor de gebruiker en programma’s die kunnen worden gewijzigd. Het uit te voeren programma Met elk proces zijn 1 of meer LIFO systeemstacks verbonden. Een stack wordt gebruikt voor het opslaan van parameters en aanroepadressen voor procedure- en systeemaanroepen. Gegevens die het besturingssysteem nodig heeft voor het beheren van het proces.
Procesattributen We kunnen de informatie in het procesbesturingsblok groeperen tot drie algemene categorieën: Procesidentificatie - unieke numerieke identificatiecode - gebruikersidentificatiecode - ouderidentificatie Processortoestandsinformatie - Registers die zichtbaar zijn voor de gebruiker - Stuur- en statusregisters
Programmateller Conditiecodes Statusinformatie
- Stackwijzers Program Status Word ( PSW ) : Een register of een verzameling registers die statusinformatie bevat. Bvb: * EFLAGS register in Pentium Machines Procesbesturingsinformatie - Scheduling en toestandsinformatie
Procestoestand Prioriteit Scheduling informatie Gebeurenis (code)
- Gegevensstructuur - Communicatie tussen processen - Procesprivileges - Geheugenbeheer - Eigendom en gebruik van bronnen.
Rol van het procesbesturingsblok Elke procesbesturingsblok bevat alle informatie die het BS nodig heeft. De verzameling van procesbesturingsblokken definieert de toestand van het besturingssysteem.
Procesbesturing Uitvoeringsmodi De meeste processors ondersteunen ten minste 2 uitvoeringsmodi: De gebruikersmodus : o Minder geprivilegieerd. Modus voor normale uitvoering van gebruikersprogramma’s De systeem of kernel modus: o Meer privileges. Modus voor uitvoering van kernelfuncties ( IO , proces , geheugen beheer ) Standaardfuncties van de kernel van een BS: Procesbeheer
Geheugenbeheer I/O-beheer Ondersteunende functies
Creëren en beëindigen van processen Inroosteren en toedelen van processen Wisselen tussen processen Synchroniseren van processen + communicatie Beheren van PSB Toewijzen van adresruimte Swapping Beheren van pagina’s en segmenten Beheren van buffers Toewijzen van IO-kanalen en apparaten aan processen Afhandelen van interrupts Administratie + toezicht
De reden voor het gebruik van twee modi is dat het besturingssysteem en de belangrijkste tabellen moeten beschermd worden tegen verstoringen door gebruikersprogramma’s. De processor weet in welke modus hij moet werken en naar welke modus hij moet veranderen door bepaalde bits in het PSW dat de uitvoeringsmodus aanduidt. Deze bits worden veranderd als reactie op bepaalde gebeurtenissen.
Creëren van processen Als het besturingssysteem besloten heeft tot creatie van een nieuw proces dan kan het als volgt gaan: 1. Het BS wijst een unieke procesidentificatie toe aan het nieuwe proces a. Nieuwe ingang bij de primaire procestabel 2. Het BS wijst ruimte toe aan het proces a. Alle elementen van het procesbeeld 3. Het procesbesturingsblok moet worden geïnitialiseerd. a. 4. De juiste koppelingen moeten worden ingesteld 5. Soms moeten andere gegevenstructuren worden gemaakt of uitgebreid.
Wisselen van processen Wanneer moeten processen worden gewisseld Een proceswisseling kan steeds optreden wanneer het besturingssysteem de besturing heeft overgenomen van het proces dat op dit moment wordt uitgevoerd. Mechanismen voor het onderbreken van de procesuitvoering: Mechanisme Oorzaak Interrupt Extern aan de uitvoering van het huidige proces Val Verbonden aan de uitvoering van de huidige instructie Aanroep supervisor Expliciet verzoek
Gebruik Reactie op een asynchrone externe gebeurtenis Afhandelen van een fout of een uitzonderlijke conditie Aanroep van een functie van het besturingssysteem
Systeeminterrupts: Interrupt o Klokinterrupt Het besturingssysteem bepaald of het actieve proces de maximale toegestane uitvoeringstijd benut heeft. Zoja wordt er een ander proces geactiveerd. o
I/O interrupt Is een I/O actie een gebeurtenis waarop één of meerdere processen wachten dan brengt het BS alle processen die hierop wachtten in de toestand Gereed , Gereed-opgeschort.
o
Geheugenfout De processor krijgt een verwijzing naar een woord adres dat zich niet in het hoofdgeheugen bevindt en zal het blok geheugen dat de verwijzing bevat naar het hoofdgeheugen moeten brengen.
o
Bij een val controleert het besturingssysteem of de fout al dan niet fataal is. Is deze fataal dan wordt het proces overgebracht naar de toestand Einde en treedt een proceswisseling op
Val
Supervisoraanroep Wisseling van modus Als er een interrupt wacht dan doet de processor het volgende: 1. De processor stelt de programmateller in op het beginadres van de routine voor de interruptafhandeling 2. De processor wisselt van gebruikersmodus naar kernelmodus, zodat de code voor de interruptverwerking geprivilegieerde instructies kan bevatten. De interruptafhandeling is meestal een kort programma dat enkele basistaken uitvoert die samenhangen met een interrupt. Het stelt bijvoorbeeld de vlag of indicator die de aanwezigheid van een interrupt signaleert, opnieuw in. In de meeste BS leidt het optreden van een interrupt echter niet noodzakelijk tot een proceswisseling. Het is mogelijk dat nadat de interruptafhandeling is uitgevoerd, de uitvoering van het actieve proces wordt voortgezet.
Wisseling van procestoestand Een volledig proceswisseling bestaat uit de volgende stappen: 1. Het opslaan van de context van het proces , inclusief de programmateller en andere registers 2. Het bijwerken van het PSB van het afgebroken proces 3. Het verplaatsen van het betreffende PSB naar de juiste wachtrij ( gereed , geblokkeerd ,.. ) 4. Het selecteren van een ander uit te voeren proces. 5. Het bijwerken van het PSB van het geselecteerde proces 6. Het bijwerken van de gegevensstructuren voor het geheugenbeheer 7. Het terugbrengen van de context van dit proces naar de context zoals deze was op het moment dat het geselecteerd proces het laatst uit de toestand Actief werd gewisseld.
Uitvoering van het besturingssysteem Het besturingssysteem werkt hetzelfde als gewone computersoftware: het is een programma dat wordt uitgevoerd door de processor. Het besturingssysteem geeft de besturing vaak uit handen en is voor het terugkrijgen ervan afhankelijk van de processor. Procesloze kernel De code van het besturingssysteem wordt uitgevoerd als een afzonderlijke entiteit die werkt in een geprivilegieerde modus
Uitvoering binnen gebruikersprocessen Het uitvoeren van vrijwel alle software van het besturingssysteem in de context van een gebruikersproces. Hierbij wordt het besturingssysteem vooral gezien als een verzameling routines die het gebruikersproces aanroept voor het verzorgen van diverse functies die worden uitgevoerd binnen de omgeving van het gebruikersproces. Op processen gebaseerd besturingssysteem Het besturingssysteem wordt geïmplementeerd als een verzameling van systeem processen (modules). Er zijn duidelijke interfaces tussen de modules. De kernelsoftware wordt uitgevoerd in kernelmodus. Dit is een goede aanpak in multi-
Procesbeheer in UNIX SVR4 Procestoestanden User running Kernel running Ready to run , in memory Asleep in memory Ready to Run , swapped Sleeping , swapped Preempted Created Zombie
Uitvoering in gebruikersmodus Uitvoering kernelmodus Gereed om te worden uitgevoerd zodra de kernel het proces inroosterd Kan niet worden uitgevoerd totdat een gebeurtenis optreedt; het proces bevindt zich in hoofdgeheugen ( geblokkeerd ) Het proces is gereed om te worden uitgevoerd, maar moet eerst naar het hoofdgeheugen worden geswapped. Het proces wacht op een gebeurtenis en is naar secundaire opslag geswapt. Het proces keert terug van kernel naar gebruikersmodus, maar de kernel onderbreekt het preemptief en voert een proceswisseling uit om een ander proces in te roosteren Het process is zojuist gecreëerd en is nog niet gereed om te worden uitgevoerd Het proces bestaat niet meer maar laat een record achter voor verwerking door ouderproces
Beheer van processen In Unix wordt een proces gecreëerd met de systeemaanroep fork() in de kernel: 1. het wijst een positie ( slot ) in de procestabel toe aan het nieuwe proces 2. Het wijst een unieke procesidentificatiecode toe aan het kindproces 3. het maakt een kopie van het procesbeeld van de ouder 4. Het verhoogt de tellers voor alle bestande die in het bezit zijn van het ouderproces om aan te geven dat een extra proces deze bestanden nu ook in bezit heeft. 5. Het plaats het kindprocess in een toestand Ready to Run 6. Het geeft de identificatiecode van het kindproces terug aan het ouderproces en geeft waarde 0 aan het kindproces
Al deze bewerking worden uitgevoerd in kernelmodus bij het ouderproces. Als de kernel klaar is met deze functies, dan kan hij één van de volgende bewerking uitvoeren, als onderdeel van het toedelen: 1. In het ouder proces blijven. De besturing gaat terug naar de gebruikersmodus op het punt na de fork aanroep van ht ouderproces 2. De besturing overdragen aan het kindproces. De uitvoering van het kindproces begint op hetzelfde punt in de code als het ouderproces, namelijk bij de return van de fork aanroep 3. De besturing overdragen aan een ander proces.
Threads , SMP en Microkernels Processen en threads Tot nu toe hebben we 2 proceskenmerken besproken: 1. Bezit van bronnen a. Virtuele adresruimte wordt toegewezen voor de opslag van het procesbeeld 2. Inroosteren en uitvoering a. Een proces is een uitvoeringspad door één of meer programma’s ( kan verweven worden ) In de meeste BS vormen deze kenmerken de kern van een proces. Ze worden onafhankelijk behandeld door het besturingssysteem. Onderscheid: Eenheid voor toedeling: thread of lichtgewicht proces Eenheid voor bronbezit: proces of taak
Multithreading Het besturingssysteem ondersteunt de mogelijkheid meerdere threads te gebruiken bij de uitvoering van één proces. Voorbeelden: MS-DOS : 1 gebruikersproces,1 thread UNIX : meerdere gebruikersprocessen , 1 thread per proces WINDOWS : meerdere gebruikersprocessen , meerdere threads per proces In een multithreading omgeving wordt een proces gedefinieerd als een eenheid voor brontoewijzing en voor beveiliging. Het volgende is verbonden met processen: Virtuele adresruimte ( bevat het procesbeeld Beveiligde toegang tot processors, andere processen , bestanden en I/O-bronnen Een thread wordt gedefinieerd als een eenheid van uitvoering. Het volgende is verbonden met threads : Een uitvoeringstoestand ( Actief , Gereed , … ) Context ( opgeslagen als de thread niet uitgevoerd wordt ) Uitvoeringsstack Statische opslagcapaciteit voor lokale variabelen per thread Toegang tot het geheugen en de bronnen van het bijhorende proces(gedeeld door alle threads)
De grootste voordelen van threads hangen samen met de gevolgen voor de prestaties: 1. Minder tijd nodig om een thread te creëren dan om een proces te starten 2. Minder tijd nodig om een thread te beëindigen dan om een proces te beëindigen. 3. Minder tijd nodig om over te schakelen tussen twee threads binnen het zelfde proces 4. een efficiëntere manier van communicatie tussen threads: gedeeld geheugen en bestanden. Dit zonder het activeren van de kernel Voorbeeld : De File Server
Een nieuwe bestandsaanvraag = een nieuwe thread Een file server krijgt veel bestandsaanvragen : de communicatie loopt snel ( creatie en het beëindigen van de threads gaat snel ) Er is snelle en efficiënte communicatie nodig omdat de toegang tot de bestanden gecoördineerd moet worden : Het is sneller om threads te gebruiken i.p.v. processen die uitwisseling van berichten gebruiken.
Nog enkele algemene voorbeelden : o
Werk op de voorgrond en achtergrond - terwijl de gebruiker invoer geeft kan het programma deze invoer op de achtergrond verwerken ( opslaan , berekeningen maken , … )
o
Asynchrone verwerking - Bijvoorbeeld het geregeld wegschrijven van de RAM-buffer naar schijf om eventueel gegevensverlies te voorkomen
o
Uitvoeringssnelheid - 1 thread kan de volgende gegevens lezen, terwijl een andere thread de vorige gegevens verwerkt.
o
Modulaire programma structuur - Programma’s met uiteenlopende activiteiten , verschillende bronnen/uitvoer hebben zijn met threads gemakkelijker te ontwerpen/implementeren
Functionaliteiten van threads Sommige acties op het proces hebben invloed op ALLE threads van het proces: bijvoorbeeld: • Opschorten : alle threads worden opgeschort . • Beëindigen : alle threads worden beëindigt. Threadtoestanden Er zijn 4 basisbewerkingen met threads die samenhangen met een verandering van de threadtoestand : Verwekken Als een nieuw proces wordt verwerkt wordt er automatisch een nieuwe thread verwekt, welke op zijn beurt nieuwe threads kan opwekken. => Gereed voor uitvoering
Blokkeren Als de thread moet wachten op gebeurtenis => Geblokkeerd
Deblokkeren Optreden van gebeurtenis => Gereed voor uitvoering
Beëindigen Thread voltooid : registercontext + stacks worden ongedaan gemaakt.
Leidt het blokkeren van 1 thread tot het blokkeren van het volledige proces?
Synchronisatie van threads Alle threads van een proces delen dezelfde adresruimte en andere bronnen , zoals open bestanden. Een wijziging van een bron door een thread heeft invloed op de omgeving van de andere threads binnen hetzelfde proces. Daarom is het noodzakelijk de activiteiten van de verschillende threads te synchroniseren om te voorkomen dat ze elkaar storen of beschadigen.
Voorbeeld : Adobe Pagemaker Zie boek
Threads op gebruikersniveau en op kernelniveau Threads op gebruikersniveau Al het thread -beheer wordt uitgevoerd door de toepassing De kernel is zich niet bewust van het bestaan van threads. Elk proces heeft zijn threadbibliotheek : pakket van routines voor ULT-beheer Voordelen:
Threadwisseling vereist geen privileges van kernel modus Schedulingsalgoritme kan aangepast worden zonder scheduler van het BS te moeten aanpassen ULT’s kunnen uitgevoerd worden op elk BS : vereist geen aanpassing van onderliggende kernel. De Threadbibliotheek bevindt zich op toepassingsniveau.
Nadelen:
Als de ULT een systeemaanroep doet wordt de thread geblokkeerd + ook alle andere threads van hetzelfde proces Bij een zuivere ULT is er geen voordeel van multiprocessing. Scheduler wijst processor toe aan een proces : slecht 1 thread kan tegelijk uitgevoerd worden.
Threads op kernelniveau Al het werk voor threadbeheer wordt uitgevoerd op kernelniveau Kernel houdt contet informatie bij voor de processen + alle threads binnen de processen Scheduling gebeurt op thread-basis
Voordelen:
Kernel kan meerdere threads van het zelfde proces schedulen op meerdere processors Geblokkeerde thread blokkeert niet het ganse proces
Nadelen:
Moduswisseling is vereist : overhead
Er is dus weliswaar een significante snelheidswinst bij het gebruik van multithreading met KLT’s in plaats van processen met één thread, maar is de snelheidswinst nog groter bij het gebruik van ULT’s. Gecombineerde benaderingen Thread reatie wordt op gebruikersniveau gedaan Grootste deel van de scheduling en de synchronisatie gebeurt binnen de toepassing. ULT’s worden gekoppeld aan evenveel of minder KLT’s Goed ontwerp : combinatie van voordelen van beide benaderingen
Andere indelingen Threads : processen 1:1 M:1 1:M
M:N
Beschrijving Elke uitvoeringsthread is een uniek proces met een eigen adresruimte en bronnen Een proces definieert een adresruimte en dynamisch bezit van bronnen. Binnen het proces kunnen meerdere threads worden gecreëerd en uitgevoerd Een thread kan migreren van de ene naar de andere procesomgeving. Hierdoor kan een thread eenvoudig worden verplaatst tussen verschillende systemen Combineert de eigenschappen van de voorgaande gevallen
Voorbeeldsystemen De oorspronkelijke implementaties van UNIX Windows NT, Solaris, Linux, OS/2, OS/3900 MACH Ra ( Clouds ), Emerald TRIX
Symmetrische multiprocessing Traditioneel werd de computer bezien als een sequentiële machine. ( instructie per instructie, proces per proces , … ) Naarmate de computertechnologie zich verder ontwikkelde en de kosten van de computerhardware daalden, hebben ontwerpers van computers gezocht nar steeds meer mogelijkheden voor parallelle verwerking, meestal om de prestaties te verbeteren en de vertrouwbaarheid te verhogen.
Architectuur van SMP Flynn onderscheidde de volgende computersystemen: SIMD-stroom ( single instruction, multiple data ) Één machine-instructie bestuurd de gelijktijdige uitvoering van een aantal verwerkingselementen in een vast patroon. Met elk verwerkingselement is een gegevensgeheugen verbonden zodat elke instructie door de verschillende processors wordt uitgevoerd met een andere verzameling gegevens.
MISD-stroom ( multiple instruction , single data ) Een reeks gegevens wordt verzonden naar een verzameling processors, die elk een andere instructiereeks uitvoeren. ( nog nooit geïmplementeerd )
MIMD-stroom ( multiple instruction , multiple data ) Een verzameling processors voert tegelijk verschillende instructiereeksen uit met verschillende gegevensverzamelingen.
MIMD-’s kunnen verder worden onderverdeeld op basis van de wijze waarop hun processors communiceren. Hebben de processors elk een eigen geheugen, dan is elke processor een eigen computer. Geen gedeeld geheugen => onafhankelijke computers. De communicatie gebeurd via vaste paden of netwerkvoorzieningen = Cluster of MultiComputer LOOSELY COUPLED Gedeeld geheugen => Communicatie verloopt via dat geheugen. TIGHTLY COUPLED •
MASTER / SLAVE Kernel op 1 bepaalde processor , de andere processors voeren enkel gebruikersprogramma’s uit. De master is verantwoordelijk voor het inroosteren van processen en threads.
•
SMP ( symmetrische multiprocessor ) Bij een SMP kan de kernel op eender welke processor uitgevoerd worden. Elke processor zorgt voor de scheduling van zijn eigen threads en processen. Het ontwerp van SMP’s en clusters is complex want men krijgt te maken met problemen zoals: o De fysieke organisatie o De structuur van onderliggende verbindingen o Communicatie tussen processors o Ontwerp van het BS o Technieken voor softwaretoepassingen
Ontwerpen van besturingssystemen voor SMP Een besturingssysteem voor SMP beheert de processors en andere computerbronnen op zo’n manier dat de gebruiker het systeem op dezelfde wijze kan zijn als een systeem met één processor en multiprogrammering. De belangrijkste aandachtspunten voor het ontwerp zijn : Gelijktijdig samenwerkende processen of threads Bij meerdere processors die dezelfde/verschillende delen vd kernel uitvoeren , moet kerneltabellen en beheerstructuren goed worden beheerd om deadlocks en ongeldige bewerkingen te voorkomen
Scheduling Conflicten moeten worden vermeden.
Synchronisatie De synchronisatie is een voorziening die zorgt voor wederzijdse uitsluiting en het ordenen van gebeurtenissen. Een gebruikelijk mechanisme hiervoor zijn grendels ( locks )
Geheugenbeheer De pagineringmechanismen van verschillende processors moet worden gecoördineerd om consistentie te waarborgen wanneer verschillende processors een pagina / segment delen of besluiten een pagina te vervangen
Betrouwbaarheid en fouttolerantie
Microkernels Een microkernel is een kleine kern van een besturingssysteem die de basis vormt voor modulaire uitbreidingen. Dit is een vrij populair concept. Het begrip microkernel en zijn eigenschappen zijn vrij vaag: Hoe groot moet een microkernel zijn om microkernel te mogen heten? Moet de uitvoering ervan in kernel of gebruikersruimte plaatsvinden? Hoe moet het ontwerp gebeuren en wat moet er allemaal geïmplementeerd worden?
Architectuur van een microkernel De eerste besturingssystemen van de jaren 50 waren monolithische besturingssystemen: Ze hadden geen structuur en waren onbeheersbaar Elke procedure kon bijna elke andere procedure aanroepen Later kwamen er gelaagde besturingssystemen : Met modulaire programmeertechnieken voor het beheersen van software ontwikkeling De meeste of alle lagen worden uitgevoerd in de kernelmodus Nadelen: o Veel interactie tussen aangrenzende lagen o Veranderingen hebben talrijke gevolgen o Beveiliging moeilijk in te bouwen
De filosofie achter een microkernel is dat alleen de essentiële kernfuncties van het besturingssysteem in de kernel zijn opgenomen. Vele diensten die traditioneel tot het BS horen zijn nu geïmplementeerd als externe subsystemen : o Apparaat stuur programma’s ( Drivers ) o Bestandssystemen o Manager voor virtueel geheugen o Venstersysteem o Beveiligingsdiensten
Voordelen van een microkernel o
Uniforme interface bij verzoeken van een proces Processen hoeven geen onderscheid te maken tussen diensten op kernel en gebruikers niveau Alle diensten worden verleend via het uitwisselen van berichten
o
Uitbreidbaarheid Eenvoudig toevoegen van nieuwe diensten
o
Flexibiliteit Nieuwe voorzieningen kunnen gemakkelijk toegevoegd worden Bestaande voorzieningen kunnen gemakkelijk verwijderd worden
o
Overdraagbaarheid Alle processorspecifieke code bevindt zich in de microkernel: Veranderingen om een het BS aan te passen moet hier gebeuren en niet in andere diensten
o
Betrouwbaarheid Modulair ontwerp Kleine microkernel kan uitgebreid getest worden Beperkt aantal API’s
o
Ondersteuning van gedistribueerde systemen Berichten worden verstuurd naar diensten : Een verzendend proces moet niet weten op welke machine de dienst zich bevindt
o
Ondersteuning voor objectgeoriënteerde besturingssystemen ( OOOS ) Componenten zijn objecten met duidelijk gedefinieerde interfaces, en die onderling verbonden kunnen worden om software te bouwen.
Prestaties van een microkernel Een mogelijk nadeel van microkernel dat vaak genoemd wordt zijn de prestaties : Het opstellen en versturen van een bericht en het accepteren en decoderen het antwoord kost meer tijd dan het uitvoeren van 1 dienstaanroep. Veel is afhankelijk van de grootte en de functionaliteit van de microkernel.
Ontwerp van een microkernel Aangezien de functionaliteit en de grootte van verschillende microkernels variëren kunnen geen vaste regels worden opgesteld qua structuur en functionaliteiten. Hier lichten we de minimale verzameling van functies en diensten van de microkernel toe om de indruk te geven van het ontwerp van microkernels. Deze functies worden ingedeeld in de volgende 3 categorieën: Primitief geheugenbeheer De microkernel moet het hardware concept adresruimte ondersteunen om de implementatie van bescherming op procesniveau mogelijk te maken. Zolang de microkernel verantwoordelijk blijft voor het afbeelden van alle virtuele pagina’s op fysieke pagainframes, kan het grootste deel van het geheugenbeheer worden geïmplementeerd buiten de kernel. 1. Thread in toepassing verwijst naar een pagina niet in het hoofdgeheugen. 2. Paginafout en uitvoering valt terug op kernel 3. Kernel stuurt bericht naar pagineerder met de aangeving naar welke pagina verwezen wordt. 4. Pagineerder kan besluiten de pagina te laden 5. Is de pagina eenmaal beschikbaar , dan stuurt de pagineerder een hervattingbericht naar de toepassing Communicatie tussen processen De elementaire vorm van communicatie tussen processen of threads in een BS met een microkernel is het bericht. Een bericht bestaat uit: Een kop : info over verzendende en ontvangende proces Een romp : directe gegevens , verwijzing naar een blok gegevens en/of besturingsinformatie Vaak kunnen we zeggen dat IPC ( Inter Proces Communication ) gebaseerd is op poorten die verbonden zijn met processen. Een poort is hier in wezen een wachtrij met berichten die bestemd zijn voor een bepaald proces ( een proces kan verschillende poorten hebben ) I/O en interruptbeheer Bij een microkernel architectuur is het mogelijk hardware-interrupts af te handelen als berichten en I/ O poorten op te nemen in adresruimten. De microkernel kan interrupts herkennen maar handelt ze niet af. In plaats daarvan genereert de microkernel een bericht voor het proces op gebruikersniveau dat op dit moment is verbonden met die interrupt. Is een interrupt ingeschakeld , dan is een bepaald proces op gebruikersniveau toegewezen aan de interrupt en onderhoudt de kernel de mapping. Het omzetten van interrupts in berichten moet worden uitgevoerd door microkernel maar de microkernels is niet betrokken bij de interruptafhandeling voor specifieke apparaten.
Beheer van threads en SMP in Solaris Solaris gebruikt een ongewone threadvoorziening met meerdere niveaus die ontworpen is met het oog op een hoge flexibiliteit bij het benutten van processorbronnen.
Architectuur met multithreading Solaris gebruikt 4 afzonderlijke, aan threads verwante concepten: 1. Proces: normale UNIX proces , omvat de adresruimte , stack en procesbesturingsblok 2. Threads op gebruikersniveau : geïmplementeerd als een threadbibliotheek in de adresruimte van een proces 3. Lichtgewichtprocessen : Elk LWP ondersteund één of meer ULT’s en is een ‘ afbeelding ‘ naar één kernelthread. 4. Kernelthreads : basisentiteiten die kunnen worden ingeroosterd en toegedeeld worden om te worden uitgevoerd op een van de processors van het systeem
Deze figuur illustreert de relatie tussen deze 4 entiteiten. Er is precies 1 kernelthread voor elk LWP. Elke LWP is verbonden aan 1 toedeelbare kernelthread. • • • • •
Proces 1 bestaat uit één ULT die is gebonden aan één LWP. Proces 2 komt overéén met een zuivere ULT benadering. Alle ULT’s worden ondersteund door 1 kernelthread en daardoor kan maar een ULT tegelijk uitgevoerd worden. Proces 3 toont meerdere threads die veelvoudig zijn verboden aan een kleiner aantal LWP’s. Proces 4 heeft voor elke ULT een kernelthread Proces 5 toont een combinatie van 3 en 4
Motivering De combinatie van threads op gebruikersniveau en threads op kernelniveau biedt de programmeur van toepassingen de mogelijkheid gelijktijdigheid toe te passen op de wijze die het meest efficiënt en het meest geschikt is voor een bepaalde toepassing.
Interrupts als threads De meeste besturingssystemen kennen twee basisvormen van asynchrone activiteit : processen en interrupts. Processen of threads werken met elkaar samen en beheren het gebruik van gedeelde gegevensstructuren door middel van verschillende primitieven die zorgen voor wederzijdse uitsluiting en die hun uitvoering synchroniseren. De reden voor het omzetten van interrupts in threads is het terugbrengen van de overhead. Dit zorgt voor een betere performantie. Oplossing in Solaris: 1. Solaris gebruikt verzameling Kernelthreads voor het afhandelen van interrupts. Zoals elke kernelthread heeft een Interruptthreads een eigen ID , prioriteit , context en stack 2. Voor het afhandelen van interrupts worden de gebruikelijke synchronisatie technieken voor threads gebruikt 3. Interruptthreads krijgen een hogere prioriteit dan alle andere Kernelthreads.
Beheer van processen en threads in Linux Taken in Linux In Linux wordt een proces of taak weergegeven door een task_struct gegevensstructuur. Deze bevat informatie over een aantal onderwerpen: Toestand of status v/h proces ( Uitvoering , Gereed , geblokkeerd , opgeschort , zombie ,… ) Schedulinginformatie ( informatie nodig om processen in te roosteren ) Identificatiecodes : uniek ID per proces + ID voor gebruiker en groep Interprocescommunicatie Verwijzingen ( naar bijvoorbeeld ouder processen of zus-processen ) Tijden en klokken ( creatietijdstip + processortijd die al benut is door het proces ) Bestandssysteem : verwijzigen naar alle gerelateerde bestanden Adresruimte ( definieert de virtuele adresruimte die toegewezen is aan het proces ) Specifieke processorcontext : inhoud van de registers en stack
Bovenstaande figuur toon de uitvoeringstoestanden van een proces/thread in Linux : o o o o o
Actief ( running ) In Uitvoering of Gereed Onderbreekbaar ( Interruptable ) Het proces wacht op een gebeurtenis Ononderbreekbaar ( Uninterruptable ) Het proces wacht op een hardwareconditie en zal op niets anders reageren Gestopt ( stopped ) Het proces is gestopt en kan alleen worden hervat wanneer een ander proces hiervoor actie onderneemt Zombie Het proces in geëindigd maar beschikt nog wel over zijn taakstructuur in de procestabel
Threads in Linux Oudere Linux-versies: geen multithreading Geen onderscheid tussen threads en processen: threads op gebruikersniveau komen overeen met processen op kernelniveau Threads van eenzelfde gebruikersproces: zelfde groepsidentificatiecode op kernelniveau proces creëren: attributen van huidig proces kopiëren a.h.v. clone() fork() geïmplementeerd a.h.v. clone() traditionele fork() wordt geïmplementeerd als clone() met alle clone-vlaggen uit
Gelijktijdigheid : wederzijdse uitsluiting en synchronisatie De hoofdthemas van het ontwerp van besturingssystemen hangen alle samen met het beheer van processen en threads: Multirogrammering ( beheer van meerdere processen in een systeem met 1 processor ) Multiprocessing (het beheer van meerdere processen in een systeem met meerdere processors) Gedistribueerde verwerking ( beheer van meerdere processen op verschillende computersystemen ) Aan de basis van al deze zaken ligt gelijktijdigheid. Gelijktijdigheid treedt op in 3 situaties : o Meerdere toepassingen ( multiprogrammatie ) o Gestructureerde toepassing ( een applicatie kan geprogrammeerd worden als een verzameling gelijktijdige processen ) o Structuur vh BS ( kan ook beschouwd worden als een verzameling van processen of threads. ) Enkele belangrijke termen met betrekking tot gelijktijdigheid: Kritieke sectie
Deadlock Livelock Wederzijdse uitsluiting
Race-conditie Verhongering
Een stuk programmacode binnen een proces waarvoor toegang tot gedeelde bronnen noodzakelijk is en dat mogelijk uitgevoerd wordt terwijl een ander proces in een corresponderend stuk programmacode uitgevoerd wordt. Een situatie waarin 2 of meer processen niet verder verwerkt kunnen worden omdat elk van de processen op een of meerdere andere wacht tot deze iets doen. Een situatie waarin 2 of meer processen continu hun toestand wijzigen als respons op veranderingen in het andere proces/de andere processen, zonder daarvoor enig werk van betekenis te doen. De eis dat wanneer een proces zich in kritieke toestand bevindt waarbij gedeelde bronnen gebruikt worden, geen van de andere processen zich in een kritieke sectie mag bevinden die gebruik kan maken van een of meerdere van de gedeelde bronnen. Een situatie waarin verschillende threads of processen een gedeeld gegeven lezen en schrijven en het uiteindelijke resultaat afhangt van de timing van de uitvoering van de lees- en schrijf bewerkingen. Een situatie waarin een uitvoerbaar proces eindeloos genegeerd wordt door de scheduler; het komt nooit aan de beurt hoewel het gereed is voor uitvoering.
Principes van gelijktijdigheid Bij het verweven en overlappen van processen is er dezelfde problematiek : nl. de relatieve snelheid van uitvoering van processen kan niet voorspeld worden en dit brengt complicaties met zich mee zoals: o Het delen van bronnen kent tal van gevaren. ( tegelijke lees en schrijfbewerkingen kan de integriteit van gegevens in gevaar brengen o Het optimaal beheren van de toewijzing van deze bronnen is een uitdaging voor het besturingssysteem o Programmeerfouten zijn zeer lastig op te sporen omdat fouten niet reproduceerbaar zijn.
Een eenvoudig voorbeeld void echo () { chin = getchar(); chout = chin; putchar =(chout); } Dit programma toont de basiselementen voor de registratie en uitvoer van een toetsaanslag op het scherm. Het delen van hoofdgeheugen door processen is nuttig voor een efficiënte en sterke interactie tussen processen. Dit delen kan echter tot problemen leiden : 1. Proces 1 start echo() en wordt onderbroken net na getchar(). Het laatst ingevoerde teken, x , is in chin opgeslagen. 2. Proces 2 wordt geactiveerd en start echo() die volledig wordt uitgevoerd en de invoer en uitvoer van 1 teken , y , op het scherm weergeeft. 3. Proces 1 wordt hervat . Op dat moment is de waarde in chin overgeschreven en daarmee verloren gegaan. chin bevat nu de waarde , y, en voert deze dan ook uit. => De gedeelde globale variabelen ( en andere gedeelde bronnen ) moeten worden beschermd en dat dit alleen mogelijk is door het bewaken van de code die toegang heeft tot de variabele. Veronderstel nu het zelfde probleem maar dan bij een systeem met meerdere processors, die dezelfde procedure echo aanroepen en dat er geen mechanisme is voor het toegangsbeheer tot de gedeelde globale variabele. Proces P1 . chin = getchar(); . chout = chin; putchar(chout); . .
Proces P2 . . chin = getchar(); chout = chin; . putchar(chout); .
Het resultaat is dat het voor P1 ingevoerde teken verloren gaat voordat het wordt weergegeven en zowel P1 als P2 geven het ingevoerde teken van P2 weer. Nu stellen we de regel in dat er maar 1 proces tegelijk toegang mag hebben tot het proces : 1. Proces P1 en P2 worden beide verwerkt op een afzonderlijke processor en beide roepen de procedure echo aan. 2. Terwijl P1 zich binnen de procedure echo bevindt roept P2 echo aan. Aagenzien P1 zich nog in de procedure echo bevindt, wordt de toegang van P2 tot de procedure geblokkeerd. P2 wordt daarom opgeschort. 3. Voltooit P1 de uitvoering van echo , dan verlaat het de procedure en wordt de uitvoering van P2 hervat en begint P2 met de uitvoering van echo Voorgaand voorbeeld was een race-conditie. Een race conditie onstaat wanneer verschillende processen of threads gegevensitems lezen en schrijven, waardoor het uiteindelijke resultaat afhankelijk is van de volgorde waarin de instructies in de verschillende processen worden uitgevoerd.
Aandachtspunten voor het besturingssysteem 1. Het besturingssysteem moet de verschillende actieve processen kunnen volgen. ( dit gebeurd door middel van de procesbesturingsblokken ) 2. Het besturingssysteem moet bronnen toewijzen en terug afnemen. Bronnen : a. Processortijd b. Geheugen c. Bestanden d. I/O-apparaten 3. Het besturingssysteem moet de gegevens en fysieke bronnen van elk proces beschermen tegen verstoringen door andere processen 4. Resultaat van een proces en de uitvoer ervan moet onafhankelijk zijn van de snelheid van de uitvoering ervan ten opzichte van de snelheid van andere concurrerende processen.
Interactie van processen Mate van bewustzijn Processen zijn zich niet bewust van elkaar Processen zijn zich indirect bewust van elkaar ( gedeeld object) Processen zijn zich direct bewust van elkaar ( communicatie – primitieven )
Relatie
Invloed van proces op een ander proces
o Resultaten van een proces zijn onafhankelijk van de actie van andere processen o Timing van proces kan beïnvloed zijn Samenwerking o Resultaten van een proces kunnen afhankelijk zijn van informatie van door delen andere processen. o Timing van proces kan beïnvloed zijn
Concurrentie
Samenwerking o Resultaten van een proces kunnen afhankelijk zijn van informatie van door andere processen. communicatie o Timing van proces kan beïnvloed
Mogelijke besturings - problemen o Wederzijdse uitsluiting o Deadlock o Uithongering o Wederzijde uitsluiting o Deadlock o Uithongering o Gegevenssamenhang o Deadlock o uithongering
zijn
Concurrentie tussen processen om bronnen Er is behoefte aan wederzijdse uitsluiting. Er is een kritieke bron en een kritieke sectie. o Een kritieke bron is een niet deelbare bron: Bijvoorbeeld een printer. o Een kritieke sectie is een deel van programma dat de kritieke bron gebruikt ( slechts 1 programma tegelijk mag zich in zijn kritieke sectie bevinden ) Dit veroorzaakt twee andere besturingsproblemen : o Deadlock BS wijst Bron1 toe aan Proces2 en Bron2 aan Proces1. Elk proces wacht op een van de twee bronnen. Beide zullen de bron die al bezig is pas vrijgeven wanneer ook de andere bron in bezit gekomen is en vervolgens de functie waarvoor beide bronnen nodig was is uitgevoerd. o Starvation Dit gebeurd wanneer een proces constant genegeerd wordt alhoewel het gereed is om uit te voeren.
Samenwerking tussen processen door delen Aangezien gegevens toegankelijk zijn vanuit bronnen ( apparaten / geheugen ) spelen nu ook de beheersproblemen wederzijdse uitsluiting, deadlocks en uithongering een rol. Het enige verschil is dat gegevenselementen toegankelijk kunnen zijn in 2 verschillende modi ( lezen / schrijven ) en dat alleen het schrijven wederzijds uitgesloten hoeft te zijn. Naast deze problemen bestaat echter een nieuwe belangrijkere vereiste: gegevenssamenhang ( data coherence ) Samenwerking tussen processen door communiceren Werken processen samen door te communiceren, dan nemen de verschillende processen gezamenlijk deel aan een gemeenschappelijke inspanning, die alle processen verenigt. De communicatie is daarbij een middel om de verschillende activiteiten te synchroniseren of te coördineren. De communicatie verloopt via de uitwisseling van berichten. Bij het uitwisselen van berichten wordt niets gedeeld door processen dus wederzijdse uitsluiting is geen controle eis voor dit soort samenwerking. De problemen deadlock en uithongering doen zich wel voor.
Vereisten voor wederzijdse uitsluiting 1. Wederzijde uitsluiting moet dwingend opgelegd worden: slechts 1 proces van alle processen met kritieke secties voor dezelfde bron of hetzelfde gedeelde object wordt tegelijkertijd in de kritieke sectie toegelaten. 2. Een proces dat stopt in zijn niet kritieke sectie moet dat doen zonder andere processen te verstoren 3. Deadlocks en starvation mogen niet voorkomen 4. Een proces dat toegang wil tot een kritieke sectie moet zonder vertraging toegang krijgen, wanneer er geen enkel ander proces zich in zijn kritieke sectie bevindt 5. Geen veronderstellingen gebruikt over de relatieve snelheiden van processen/ aantal processen 6. Een proces mag zich maar een beperkte tijd in zijn kritieke sectie bevinden
Wederzijdse uitsluiting: hardwareondersteuning Uitschakelen van interrupts systeem met 1 processor: concurrerende processen kunnen elkaar niet overlappen een proces wordt afgebroken door een interrupt => ervoor zorgen dat een proces niet kan onderbroken worden door interrupts uit te schakelen (achterliggende theorie: wanneer een interrupt optreedt gaat de processor in kernelmode en voert daar de gewenste code uit, dus, andere code wordt uitgevoerd tussen de kritieke sectie, in het slechtste geval verandert die code iets waarmee het proces in usermode mee bezig was waardoor alles in het water valt. Een ander probleem kan zijn dat de interrupt vereist dat een ander proces wordt toebedeeld aan de processor waardoor het eerste proces geblokkeerd wordt temidden van zijn kritieke sectie. Het kan dan even duren vooraleer dat proces weer vrijkomt (denk maar aan FIFO) waardoor de bron die het proces gebruikt lange tijd geblokkeerd blijft.
while(true) { schakel interrupts uit; voer kritieke sectie uit; schakel interrupts in; rest; } => omdat de kritieke sectie niet kan worden onderbroken is mutual exclusion gegarandeerd! Nadelen: efficiëntie uitvoering daalt want processor wordt beperkt in zijn mogelijkheid om processen te verweven werkt niet in multiprocessoromgeving (!!daar heeft het geen zin om de interrupts op 1 processor even af te zetten met de reden dat de code daarom atomair kan verlopen want op de andere processoren kunnen er processen lopen die tegelijkertijd dingen gaan veranderen aan variabelen die het eerste proces in zijn kritieke sectie gebruikt. een oplossing zou dan zijn om op de gebruikte processor interrupts te disablen en op de andere processen de processen te blokkeren maar dat is zo inefficiënt dat dat geen goed idee is)
Speciale machine instructies de testset en de exchange instructie Beiden zijn machineïnstructies die ervoor zorgen dat de kritieke sectie op atomair niveau wordt uitgevoerd! Parbegin betekent dat het programma deze processen parallel moet uitvoeren Instructie test and set testandset gaat controleren of een integer == 0, zo ja, dan wordt die op 1 gezet en wordt er true gereturnd => uit de while lus en de kritieke sectie wordt uitgevoerd, als er dan ondertussen een ander proces ook zijn kritieke sectie wil uitvoeren, dan wordt er false gereturnd en zit dat proces vast in de lus tot wanneer het vorige proces bolt terug op 0 zet. De processen die zo in de loop terechtkomen zijn zijn dan niet geblokkeerd maar busy waiting (processor wordt maw gebruikt maar is niet nuttig aan het doen, proces zit immers in een loop); busy waiting wil zeggen: een proces kan niets doen tot het toestemming krijgt de kritieke sectie te betreden. Welk het volgende proces wordt dat wordt uitgevoerd wanneer bolt terug 0 is, is het eerste proces dat test of bolt == 0. Dus eigenlijk is dit vrij random (afhankelijk van de schedulingsstrategie) Instructie exchange Wisselt de inhoud van een register met die van een geheugenlocatie. In het voorbeeld is het iets simpeler, daar worden een 0 en een 1 gewisseld. Enkel het proces waarvoor geldt dat keyi == 0 (en dus bolt == 0 bij het begin van de uitvoering) mag de kritieke sectie betreden, al de rest moet wachten tot het eerste proces bolt terug op 0 heeft gezet. Eigenschappen van de benadering met machine-instructies Voordelen van het werken met machine-instructies: 1. toepasbaar op alle processen op een machine met 1 processor en op alle processen op een systeem van multiprocessing die het hoofdgeheugen delen <-> als ze geen geheugen delen, dan delen ze ook geen variabelen en kan er dan ook niet met de waarde van variabelen gewerkt worden!! 2. eenvoudig => makkelijk te controleren
3. kan worden gebruikt voor het ondersteunen van meerdere kritieke secties waarbij elke kritieke sectie zijn eigen variabele kan hebben Nadelen van het werken met machine-instructies: 1. busy-waiting: proces blijft processortijd verbruiken terwijl het niets nuttig aan get doen is 2. starvation kan nog steeds: aangezien het willekeurig is welk proces een proces opvolgt dat uit zijn kritieke sectie komt en als er meerdere processen zijn die 'busy waiting' zijn, dan kan het zijn dat een proces zeer lang in de wachtrij staat 3. deadlock: P1 gaat in kritieke sectie maar wordt onderbroken door P2 dat een hogere prioriteit heeft, echter, om te voltooien heeft P2 dezelfde bron nodig als P1 maar die is geblokkeerd door P2 en P1 wacht op de voltooiing van P2... (dan maakt het niet uit of er even een ander proces wordt geactiveerd want de clue is dat deze twee processen niet verder kunnen, tenzij het OS P2 plots een lagere prioriteit geeft dan P1 waardoor P1 weer actief kan worden...)
Semaforen Grondbeginsel : Twee of meer processen kunnen samenwerken dmv signalen waarbij een proces gedwongen wordt te stoppen op een opgegeven plaats totdat het een signaal ontvangt dat het mag verdergaan. Voor het verzenden van een signaal via semafoor s voert een proces de primitieve semSignal(s) uit. Voor het ontvangen van een signaal de primitieve semWait(s). Principe: semWait(s) => een proces wordt onderbroken totdat semSignal(s) door een ander proces verzonden is. Om het gewenste effect te bereiken kunnen we de semafoor beschouwen als een variabele die een gehele waarde heeft en waarvoor drie bewerkingen zijn gedefinieerd : 1. semafoor wordt geïnitialiseerd op een niet-negatieve waarde 2. semWait(s) verlaagt de waarde van s met 1, wordt de waarde negatief, dan wordt dat proces geblokkeerd 3. semSignal(s) verhoogt de waarde van s, was de waarde niet positief en nu wel, dan wordt een proces dat geblokkeerd was door semWait(s) nu gedeblokkeerd. semWait() en semSignal() zijn primitieven en worden atomair uitgevoerd ( zonder onderbreking ). Een binaire semafoor kan worden geïnitialiseerd op waarde 0 of 1 en kan ook alleen maar deze twee waarden hebben. 1. Bewerking semWaitB() controleert waarde van de semafoor. Als de waarde nul is wordt het proces dat semWaitB() uitvoert geblokkeerd. Als de waarde 1 is wordt het proces verder uitgevoerd en de waarde in 0 veranderd. 2. De bewerking semSignalB() controleeert of er processen op deze semafoor geblokkeerd zijn. Als dat het geval is , wordt een proces dat geblokkeerd is door een bewerking semWaitB vrijgegeven. Zijn er geen geblokkeerde processen , waarde => 1 Niet binaire semaforen worden vaak een tellende of algemene semafoor genoemd. Het proces dat het langst is geblokkeerd wordt als eerste vrijgelaten uit de wachtrij. Bij deze strategie is een semafoor STERK. Als de volgorde van processen uit de wachtrij niet is vastgelegd wordt het een ZWAKKE semafoor. STERKE semaforen garanderen de afwezigheid van uithongering, zwakke niet.
!!!Voordeel t.o.v. machine-instructies: de processen worden hier geblokkeerd => de processor voert ze niet meer uit en verdoet er dan ook zijn tijd niet mee <-> busy waiting bij machine-instructies!!!
Wederzijdse uitsluiting Op elk moment kan de waarde van de semafoor daarbij als volgt worden geïnterpreteerd: De waarde van de semafoor ( bij >= 0 ) is het aantal processen dat semWait(s) zonder onderbreking kan uitvoeren De waarde van de semafoor ( bij < 0 ) is het aantal processen dat is onderbroken in de wachtrij van de semafoor.
Implementatie van semaforen Zoals eerder gezegd is het essentieel dat de bewerkingen semWait en semSignal worden geïmplementeerd als atomaire primitieven. Mogelijkheden : in hard-of firmware software: probleem: als je bvb naar het algoritme van Dekker kijkt, dan is er veel overhead omdat de processor een proces aan het uitvoeren kan zijn dat in wezen niets doet, buiten dan controleren of de vlaggen wel goed staan mutual exclusion door mechanisme in de hardware: testandset en interrupts Bij testandset wordt de de testset gebruikt bij de wait en de signal. Er kan maar 1 proces per keer een semwait(s) doen => wanneer een eerste proces dit wil uitvoeren, dan wordt s.flag op 1 gezet waardoor, als er een tweede proces is dat ook een semWait(s) wil oproepen, even moet wachten vooraleer het de semafoor kan aanpassen => in de while loop (= busy waiting). Wanneer dan het eerste proces de wait heeft uitgevoerd, dan wordt s.flag weer op 0 gezet zodat een proces dat hierop aan het wachten was, uit de loop kan en de semafoor kan aanpassen. Dit staat los van het feit of het proces al dan niet geblokkeerd gaat geraken wanneer de waarde van de semafoor < 0, het zorgt er gewoon voor dat er geen 2 processen tegelijkertijd de semafoor kunnen aanpassen Nadeel is dat er dan gedaan wordt aan busy waiting maar omdat een semwait niet zo lang duurt is dat nog redelijk. Idem voor bij het enabelen en disabelen van interrupts (alleen bij systemen met 1 processor!!!!!). Dit wordt gedaan zodat een semwait en semsignal atomaire acties kunnen zijn (ze kunnen dan niet worden onderbroken door een interrupt) het kleine nadeel is dan wel dat de processor dan even geen processen kan verweven maar omdat semWait en semSignal zo kort duren valt dit nadeel vrij goed mee.
Monitoren Semaforen hebben nadelen :
verantwoordelijkheid voor plaatsing van semWait en semSignal ligt volledig bij de programmeur wat dus de kans op fouten groter maakt dan bij monitors waar deze verantwoordelijkheid gedeeltelijk wordt afgeschoven op het vertaalprogramma. semWait en semSignal kunnen overal verspreid staan over een programma en het is soms moeilijk om te zien wat hun invloed juist is <-> een monitor is meer afgelijnd, het is het creëren van een atomair blok daar waar er eerst geen was
Monitor is een constructie in een programmeertaal die een functionaliteit biedt die vergelijkbaar is met die van semaforen, maar die gemakkelijker te besturen is. Ook is ze geïmplementeerd als een programmabibliotheek. Dit biedt de mogelijkheid grendels op elk object te plaatsen.
Monitor met signal Een monitor is een softwaremodule die bestaat uit een reeks procedures, een initialisatiereeks en een lokale gegevens. Kenmerken : 1. Lokale gegevensvariabelen zijn uitsluitend toegankelijk voor de procedures van de monitor en niet voor andere externe procedures. 2. Een proces benadert de monitor door een van de procedures ervan aan te roepen. 3. Slecht één proces tegelijk kan worden uitgevoerd in de monitor. Door slechts 1 proces tegelijk toe te laten kan de monitor worden gebruikt als een voorziening voor wederzijdse uitsluiting. Een monitor ondersteunt ook synchronisatie door gebruik te maken van conditievariabelen die zijn opgenomen binnen de monitor en die alleen binnen de monitor toegankelijk zijn. 2 functies werken hiermee : 1. cwait(c) : stelt de uitvoering van het aanroepende proces uit op conditie c. De monitor is daarna beschikbaar voor gebruik door een ander proces. 2. csignal(c) : hervat de uitvoering van een bepaald proces dat werd onderbroken na een cwait op dezelfde conditie. Zijn er meerdere van dergelijke processen, kies dan één proces; zijn er geen wachtende , doe dan niets! wanneer er bij monitors een signal wordt verstuurd maar er is helemaal geen proces dat wacht op de conditievariabele (er zit geen proces in de wachtrij van de variabele), dan gebeurt er helemaal niets <> semaforen Dus: monitor toegankelijk voor slechts 1 proces per keer, als eerste proces binnenkomt, dan wordt de conditie gewijzigd waardoor een tweede proces door cwait(c) uit te voeren terechtkomt in een wachtrij van de conditie totdat eerste proces een signal uitvoert dat de monitor vrij is => 1 proces uit de wachtrij hervat zijn uitvoering net na de cwait(x). De verantwoordelijkheid voor de correctheid van de synchronisatie ligt nog steeds bij de programmeur, maar : Voordelen tov semaforen: de synchronisatiefuncties blijven beperkt tot de monitor => overzichtelijker en makkelijker te controleren <-> semaforen: kunnen over het hele programma staan. Nadelen van monitors: een goede synchronisatie vereist dat procedures worden aangeroepen voor en na het gebruik van de gedeelde bron. Gebeurt dit niet of verkeerd, dan bestaat de kans dat een thread of een proces toch nog toegang heeft tot een gedeelde bron terwijl een ander proces daar ook mee bezig is geneste monitoren kunnen deadlocks veroorzaken: P1 zit in een procedure van een high-level monitor en gaat over naar een procedure van een lower-level monitor, daar wordt het proces in een wachtrij geplaatst. Alles goed en wel voor de lower-level monitor, die komt zo vrij voor een ander proces maar de high-level monitor is nog steeds bezet => geen ander proces kan die gebruiken => deadlock
Gelijktijdigheid : Deadlocks en uithongering Deadlock en starvation zijn twee problemen ten gevolge van de oplossingen om gelijktijdige verwerking te ondersteunen
Beginselen van deadlock Deadlock: een permanente blokkering van processen die met elkaar wedijveren om bronnen of die met elkaar communiceren fig 6-2 p 285!!
Herbruikbare hulpbronnen Reusable resource <-> consumable resource bvb.: hoofdgeheugen, secundair geheugen, processor, databases en semaforen Een herbruikbare (hulp)bron is een bron die veilig door 1 proces tegelijkertijd kan worden gebruikt en na dit gebruik is de bron er nog steeds, ze geraakt door gebruik niet op Deadlock: wanneer twee processen een bron vasthouden en verzoeken om een andere bron zie voorbeeld p288 voorbeeld van deadlock bij geheugen: wanneer er gevraagd wordt om geheugen dat nog moet vrijgezet worden door een ander proces dat echter zelf nog om geheugen vraagt en niets kan vrijzetten omdat het wacht op geheugen
Verbruikbare hulpbronnen Consumable resource: een bron die kan worden gemaakt en vernietigd; het aantal verbruikbare bronnen van een bepaald soort is meestal onbeperkt bvb.: interrupts, signalen, berichten(!!! processen die met elkaar communiceren!!) Deadlock: P1 wacht op een bericht van P2 om naar P2 te versturen terwijl P2 wacht op een bericht van P1 om naar P1 te versturen => een deadlock treedt op als het ontvangen blokkerend is brontoewijzingsschema's
Een punt is een voorstelling van een bron, hierboven is er van elke bron maar 1 instantie een proces vraagt om een bron maar die nog niet toegewezen, pas wanneer er een pijl van een bron naar een proces gaat is de bron toegewezen aan dat proces. Voorbeeld van een deadlocksituatie:
Wanneer er meerdere instanties van een herbruikbare bron kunnen toegewezen worden (bvb van I/O apparaten) aan een proces is de kans op een deadlock kleiner
Condities voor deadlock Er zijn drie voorwaarden die er voor zorgen dat een situatie in een deadlock kan verzeild geraken: 1. wederzijdse uitsluiting: een bron mag maar aan 1 proces gelijktijdig worden toegewezen 2. vasthouden en wachten: een proces mag een bron vasthouden terwijl het wacht op de toewijzing van andere bronnen 3. geen preëmptieve onderbreking: een bron kan niet zomaar worden afgenomen van een proces dat de bron vasthoudt
Deze drie voorwaarden zijn echter wenselijk!! mutual exclusion: consistentie van gegevens en gelijktijdigheid geen preëmptieve onderbreking: tenzij met een zeer goed rollback-mechanisme (stel: een proces is bezig met bewerkingen op gegevens uit een bestand, opeens wordt dat bestand afgenomen van dat proces en dat bestand gaat lezen uit dat bestand => een fout)
Noodzaak aan een 4e voorwaarde voor deadlock: 4. Cirkelvormig wachten: een ketting van wachtende processen waarbij de processen wachten op het vrijkomen van een bron dat een ander proces vasthoudt De eerste drie condities kunnen leiden tot de vierde. Wanneer de vierde voorwaarde waar is, dan is er een deadlock. Er zijn drie strategiën om om te gaan met een deadlock: voorkomen, vermijden en detecteren
Samenvatting: aanpak
Toewijzing bronnen
Verschillende vormen
Voordelen
Nadelen
Voorkomen
bronnen worden met mondjesmaat toegewezen
alle bronnen tegelijk aanvragen
+ preëmptieve ingreep is niet nodig + werkt goed bij processen die activiteiten in één klap uitvoeren
- inefficiënt - vertraagt het starten van processen - toekomstige behoefte aan bronnen moet gekend zijn
preëmptieve ingreep
+ goed voor gebruik bij processen waarbij de toestand gemakkelijk kan worden opgeslaan en hersteld
- preëmptieve onderbrekingen treden vaker op dan nodig
ordenen van bronnen
+ implementatie dmv controles tijdens compilatie
- maakt toenemende vragen om bronnen onmogelijk
Vermijden
middenweg tussen detecteren en voorkomen
bijsturen om minstens 1 veilige weg te vinden
+ preëmptieve onderbreking - toekomstige is niet noodzakelijk behoeften aan bronnen moeten bekend zijn - processen kunnen lange tijd geblokkeerd zijn
Detecteren
aangevraagde bronnen indien mogelijk altijd vrijgeven
periodiek aanroepen om te testen op deadlock
+ vertraagt nooit het starten van een proces + maakt online afhandeling mogelijk
- verlies door preëmptieve onderbreking
Voorkomen van deadlock deadlock wordt uitgesloten twee mogelijkheden: 1. indirecte methode: voorkomen van 1 van de 3 noodzakelijke voorwaarden 2. directe methode: voorkomen van het cirkelvormig wachten
Wederzijdse uitsluiting kan niet onmogelijk worden gemaakt: sommige bronnen (bvb naar een bestand schrijven) vereisen nu eenmaal wederzijdse uitsluiting en dan vereist dit ook ondersteuning door OS!
Vasthouden en wachten het proces vraagt in één keer alle vereiste bronnen aan en wordt geblokkeerd zolang er een of meerdere bronnen niet beschikbaar zijn inefficiënt: op die manier kan een proces lang geblokkeerd blijven terwijl het mss al gedeeltelijk kan
uitgevoerd worden met slechts een deel van de bronnen reeds toegewezen bronnen aan een dergelijk geblokkeerd proces zijn ontoegankelijk voor andere processen terwijl deze bronnen niet worden gebruikt
Dit vereist ook dat een proces vanaf het begin weet welke bronnen het zal nodig hebben en dat het weet waar het deze kan vinden
Geen preëmptieve onderbreking er zijn verschillende manieren om tóch preëmptief te onderbreken: een proces bezet een aantal bronnen, verzoekt om een andere -> verzoek wordt geweigerd => proces moet alle bronnen vrijgeven en er een volgende keer terug om verzoeken OS onderbreekt preëmptief een proces dat om een bron vraagt dat bezet is door een ander proces en eisen dat dit zijn bronnen vrijgeeft(voorkomt enkel een deadlock wanneer beide processen een andere prioriteit hebben => preëmptief onderbreken proces met laagste prioriteit) Onderbreken heeft alleen zin bij bronnen waarvan de toestand gemakkelijk kan worden opgeslagen en hersteld, zoals bij de processor
Cirkelvormig wachten Dit is de directe manier door het definiëren van een lineaire rangorde van soorten voorzieningen: aan een proces zijn bronnen toegewezen van het soort R, dan mag dit proces enkel nog maar verzoeken om bronnen met een hogere rangorde dan R volgende situatie kan dan niet meer: P1 heeft bron Ri bezet en vraagt om bron Rj P2 heeft bron Rj bezet en verzoekt om Ri Dit kan niet want als i < j dan kan j !< i dus deze deadlock is opgelost want P2 mag Ri niet aanvragen Inefficiënt want het vertraagt de processen en weigert onnodig de toegang tot bronnen (omdat dit in een bepaalde volgorde moet gebeuren, zelfs al zijn de bronnen vrij)
Vermijden van deadlock voorkomen deadlock: beperkingen opleggen aan bronaanvragen om zo minstens 1 van de vier voorwaarden te omzeilen => inefficiënt gebruik van systeembronnen en inefficiënte uitvoering van processen vermijden van deadlock: de eerste drie voorwaarden zijn toegestaan maar er worden keuzes gemaakt om er voor te zorgen dat het nooit tot een deadlock komt => er is meer ruimte voor gelijktijdigheid maar, dit vereist wel dat op voorhand geweten is om welke bronnen zal gevraagd worden 2 benaderingen om deadlock te vermijden: 1. een proces waarvan de bronaanvragen tot een dead lock kunnen leiden niet starten 2. wanneer een bronaanvraag van een proces kan leiden tot een deadlock, dan wordt deze aanvraag niet verwerkt
Weigeren van een nieuw proces Zeer inefficiënt: Gaat ervan uit dat alle processen tegelijkertijd hun maximale claim kunnen maken => een nieuw proces wordt alleen gestart als het systeem alle bronnen die de reeds bestaande processen kunnen opvragen aan die processen kunnen worden toegewezen en als de bronnen die het nieuw proces kan aanvragen ook kunnen worden toegewezen Probleem: het is niet omdat twee processen een bron tegelijkertijd kunnen opvragen dat dat daarom ook zo is
Weigeren om bronnen toe te wijzen Dit werkt volgens het bankiersalgoritme van Dijkstra. Er worden 2 soorten toestanden onderscheiden: veilige toestand: er is op zijn minst 1 manier waarop de processen bronnen toegewezen kunnen krijgen die niet leidt tot een deadlock onveilige toestand: een mogelijke deadlocksituatie (die wordt vermeden door het systeem door de bronaanvraag niet te behandelen en het proces dat de aanvraag doet te blokkeren) zie fig 6-7 op die figuur is een voorbeeld te zien van een veilige toestand, immers, er is op zijn minst 1 manier waarop de verschillende processen kunnen uitgevoerd worden die niet leidt tot een deadlock fig 6-8 p301: onveilige situatie P1 verzoekt om 1 allocatie van bron 1 en 1 van bron 3 => er zijn geen instanties meer van bron 1 terwijl er daar minstens 1 van nodig is opdat er een proces is dat volledig kan uitgevoerd worden => het toewijzen van de bronnen aan proces 1 leidt tot een deadlock en dit wordt voorkomen door deze aanvraag te negeren en P1 te blokkeren waardoor een ander proces actief wordt (hopelijk P2) dat een aanvraag doet die NIET leidt tot een deadlock
m.a.w. er is geen deadlock opgetreden, er was alleen een toestand waarin er een kon optreden. Want het kan bvb zijn dat P1 achtereenvolgens weer 1 instantie van R1 en R3 vrijgeeft voordat het deze op een later tijdstip weer nodig heeft. Dus: het op deze manier vermijden van een deadlock gaat ook voor de zekerheid (terwijl het niet altijd zeker is dat een onveilige toestand ook daadwerkelijk leidt tot een deadlock) maar het is al wel efficiënter dan de andere vermijdingsstrategie. Er wordt voorkomen dat een deadlock voorkomt, zelfs al kan het zijn dat deze er nooit zou gekomen zijn had men de bronaanvraag wel verwerkt Dus: proces doet verzoek om bron => stel dat aan verzoek wordt tegemoetgekomen: is het resultaat een veilige toestand? => als (veilige toestand) voldoe aan verzoek anders blokkeer proces en geef geen gehoor aan verzoek Voordelen vermijdingsstrategie: het is niet nodig processen preëmptief te onderbreken <-> detecteren het is minder beperkend dan deadlock voorkomen Beperkingen voor het gebruik: per proces moet het maximaal aantal vereiste bronnen gekend zijn de processen die zo worden beoordeeld moeten onafhankelijk zijn: hun volgorde mag nog niet beperkt zijn door een vereiste synchronisatie er moet een vast aantal toe te wijzen bronnen zijn een proces mag niet worden beëindigd terwijl het bronnen vasthoudt, want dan is er geen nood aan dit systeem, dan kan men gewoon bij een tekort aan bronnen, een proces beëindigen en zijn bronnen recupereren Nadeel van vermijden: het is een (zeer) voorzichtige strategie (bij het niet starten van een nieuw proces zeker) wat leidt tot inefficiëntie want het kan zijn dat men een proces niet uitvoert/blokkeert terwijl dat mss helemaal niet nodig was geweest (maar dat weet het systeem pas als het mss te laat is so 'better safe than sorry')
Detecteren van deadlock Deadlocks vermijden: beperkingen opleggen aan processen en het beperken van toegang tot voorzieningen Deadlocks detecteren: geen beperkingen er wordt, in de mate van het mogelijke aan alle bronaanvragen tegemoetgekomen periodiek voert het OS een algoritme uit om 'cirkelvormig wachten' vast te stellen
Algoritmen voor detecteren deadlock Ingrediënten: een matrix van nodige bronnen per proces matrix van reeds gealloceerde bronnen per proces vector nog beschikbare bronnen vector totaal aantal instanties per bron
Stappen: 1. markeren van alle processen waaraan geen enkele bron is toegewezen (dus overal nullen in de 'Allocation' matrix) 2. initialisatie van een tijdelijke vector W die gelijk is aan de vector van nog beschikbare bronnen 3. op zoek naar een proces waarvoor geldt dat het aantal geclaimde instanties van bronnen (matrix Q) kleiner of gelijk is aan het aantal nog beschikbare instanties 4. => wordt zo een proces niet gevonden => algoritme beëindigen; wordt dat wel gevonden => dat proces markeren en de instanties van bronnen uit de matrix Allocation die bij dat proces horen worden bij W opgeteld en we gaan verder Wanneer deadlock: er is sprake van een deadlock als er aan het einde van het algoritme nog ongemarkeerde processen zijn (deze zitten in een deadlock); een proces wordt immers gemarkeerd wanneer het geen bronnen meer vasthoudt en dus ook niet nuttig is voor het vrijgeven van bronnen na uitvoering van het proces
Herstel 4 mogelijke methoden; 1 is de minst geavanceerde -> 4, de meest geavanceerde 1. afbreken van alle processen met een deadlock: meest gebruikte methode in OS 2. rollback van elk proces met een deadlock tot een bepaald punt en herstart alle processen (vereiste is dat rollback en restart zijn ingebouwd in het systeem). Risico dat de deadlock opnieuw zal gebeuren maar aangezien de volgorde bij gelijktijdige verwerking niet vastligt en de processen dus hoogstwsl in een andere volgorde zullen worden uitgevoerd is de kans groot dat de deadlock niet plaatsgrijpt 3. beëindig na elkaar de processen met een deadlock totdat de deadlock niet meer bestaat. Na elke beëindiging moet het algoritme worden uitgevoerd om na te gaan of er nog een deadlock is. De volgorde van beëindiging moet zo zijn dat dit minimale kosten met zich meebrengt 4. Preëmptief bronnen afnemen van de processen totdat deadlock niet meer bestaat. Na elke preëmptieve onderbreking moet het algoritme worden uitgevoerd om na te gaan of er nog een deadlock is + rollback van een dergelijk proces tot het punt voorafgaand aan de toewijzing van de zojuist afgenomen bron aan dat proces. Op basis waarvan worden in 3 en 4 processen beëindigd of bronnen afgenomen: processen die het minste processortijd hebben ingenomen processen met de laagste prioriteit de langste resterende duur heeft de kleinste hoeveelheid toegewezen bronnen heeft
Geïntegreerde aanpak van deadlock Het zou beter zijn dat een systeem, ipv 1 strategie te gebruiken, er meerdere kan toepassen, al naargelang de vereiste daartoe. Zo kan het handig zijn: de bronnen in te delen in een aantal klassen de strategie ter vermijding van cirkelvormig wachten te gebruiken om deadlock te voorkomen tussen klassen van bronnen te voorkomen om per klas een strategie te gebruiken die het best past bij de soorten van bronnen in die klasse
Mogelijke klassen van bronnen: swap-ruimte: geheugen gebruikt voor geswapte processen procesbronnen: apparaten die kunnen worden toegewezen(diskettestation, bestanden) hoofdgeheugen: pagina's of segmenten die aan processen kunnen worden toegekend interne bronnen: bvb I/O kanalen aanpak om deadlock te vermijden binnen elke klasse: swap-ruimte: voorkomen van deadlock door te eisen dat een proces in één keer alle bronnen aanvraagt en dit zolang te blokkeren zolang een bron niet vrij is (vasthouden en wachten); dit kan hier werken omdat dit vereist dat de maximaal vereiste opslagruimten bekend zijn, wat hier zo is vermijden van deadlock procesbronnen: voorkomen door een rangorde aan te brengen (=> cirkelvormig wachten opheffen) vermijden van deadlocks: gaat omdat de processen in deze klasse vooraf aangeven welke voorzieningen ze denken te zullen nodig hebben hoofdgeheugen: voorkomen: processen preëmptief te onderbreken => proces wordt geswapt naar swapgeheugen => er komt ruimte vrij om deadlock op te lossen interne bronnen: voorkomen door gebruik van rangorde
Probleem van de dinerende filosofen Beginsituatie: 5 filosofen 1 tafel met 5 borden en 5 vorken spaghetti wordt gegeten met de twee vorken naast het bord Beperkingen: moet voldoen aan wederzijdse uitsluiting: een vork mag niet tegelijkertijd door meerdere filosofen worden gebruikt geen deadlock of uithongering p306flock://favorites/urn:flock:feed:http%3A%2F%2Fwww.deredactie.be%2Fcm%2Fde.redactie %2Fnewswire%3Fmode%3Datom 6.6.1 Een oplossing met semaforen uitsluiting van deadlock door het aantal processen aan tafel te beperken tot aantal processen – 1 => er is minstens 1 proces dat de nodige bronnen kan gebruiken en volledig kan uitgevoerd worden 6.6.2 Een oplossing met een monitor vector met 5 conditievariabelen: 1 per vork vector met 5 booleans: na te gaan of een vork beschikbaar is, als dat niet is, dan moet het proces in de wachtrij van die vork
Mechanismen voor gelijktijdigheid in UNIX Pijpen
een cirkelvormige buffer waarmee 2 processen kunnen communiceren (producent/consumentmodel) => FIFO wachtrij die wordt geschreven door het ene en gelezen door het andere proces de pijp heeft een vaste grootte aan bytes => wil een proces meer schrijven dan erin kan of wil een proces meer bytes lezen dan erin staan => proces wordt geblokkeerd, zoniet, dan wordt het schrijf-of leesverzoek meteen ingewilligd twee soorten: benoemde(named) en naamloze(nameless) pipe: gerelateerde processen kunnen een nameless pipe gebruiken <-> processen zonder relatie kunnen alleen een benoemde pipe gebruiken
Berichten Bericht: tekst dat vergezeld gaat van een type
proces heeft een wachtrij (postvak); een ander proces stuurt een bericht naar een ander proces zijn postvak. Dat proces kan berichten lezen, ofwel FIFO, ofwel op basis van het type proberen sturen naar een vol postvak => opschorten vd zender proberen lezen uit een leeg postvak => opschorten vh proces een proces wordt NIET opgeschort wanneer het een bericht niet kan lezen
Gedeeld geheugen
snelste vorm van communicatie tss processen processen lezen en schrijven van en naar een gedeeld stuk virtueel geheugen processen kunnen alleen-lezen of alleen-schrijven zijn wederzijdse uitsluiting is een vereiste aangezien er niet én gelezen en tegelijkertijd geschreven mag worden of door twee processen tegelijkertijd mag geschreven worden
Semaforen
Door het gebruik van gewone (dus geen binaire) semaforen kunnen verschillende processen tegelijkertijd worden uitgevoerd de kernel voert alle gevraagde bewerkingen uit op atomair niveau: geen enkel ander proces krijgt toegang tot de semafoor tot de bewerkingen gedaan zijn
Signalen
softwaremechanisme dat een proces informeert over asynchrone gebeurtenissen gelijkwaardig aan interrupt maar kent geen prioriteit => worden allemaal gelijkwaardig behandeld wordt verstuurd door processen onderling of door de kernel reactie van een proces op een signaal: signaal negeren standaardactie functie voor signaalafhandeling uitvoeren
Geheugenbeheer Effectief geheugenbeheer is essentieel bij een systeem met multiprogrammering. Geheugen moet efficiënt worden toegewezen om zoveel mogelijk processen in het geheugen te laden zodat de processortijd optimaal benut wordt.
Vereisten voor geheugenbeheer Relocatie De programmeur weet meestal niet waar het programma in het geheugen geplaatst zal worden bij uitvoering. Tijdens uitvoering van het programma kan het terug naar schijf geswapt worden om dan terug naar het geheugen geplaatst te worden op een andere locatie. Het OS moet de locatie kennen van de procesbesturingsinformatie en van de uitvoeringsstack. Het moet ook weten op welk adres de uitvoering van het programma begint. De processor moet echter ook in staat kunnen zijn om verwijzingen naar code, die in het programma gebeuren, te kunnen omzetten naar een echt adres in het geheugen. Sprongopdrachten bevatten een adres dat verwijst naar de volgende uit te voeren instructie. Dit heeft natuurlijk ook implicaties voor het OS, dat verwijzingen in de code gaat moeten omzetten/translateren naar echte fysische adressen.
Bescherming Processen moeten beschermd worden tegen verstoringen door andere processen : • Processen mogen niet zonder toestemming naar geheugenlocaties in andere processen verwijzen. • Bij Relocatie is de locatie van een programma in het hoofdgeheugen onbekend, dus is het onmogelijk absolute geheugenadressen te controleren bij het compilen. • Geheugenverwijzingen moeten dus at run time gecontroleerd worden. • De vereisten voor geheugenbescherming moeten voldaan zijn door de processor ( hardware ) in plaats van door het besturingssysteem ( software ) o
Het BS kan niet anticiperen op alle geheugenverwijzingen die een programma kan gebruiken.
Delen Bescherming van de processen is noodzakelijk maar het moet wel mogelijk zijn dat processen bepaalde delen van het geheugen delen. Het is ook beter om elk proces toegang te geven tot hetzelfde exemplaar van het programma , in plaats van dat elk proces zijn eigen kopie gebruikt. Dit is het overmatig gebruiken van het werkgeheugen.
Logische indeling De meeste programma’s zijn ingedeeld in modules, waarvan sommige niet kunnen worden gewijzigd (alleen lezen, … ) en waarvan andere modules gegevens bevatten die wel mogen worden gewijzigd. Voordelen van modules : • Modules kunnen onafhankelijk worden geschreven en gecompileerd. Waarbij alle verwijzingen van de ene naar de andere module tijdens de uitvoering worden ingevuld door het systeem • Verschillende modules kunnen andere beschermingsniveaus krijgen ten koste van wat overhead. • Het wordt mogelijk mechanismen te maken waarbij processen modules kunnen delen.
Fysieke indeling Hoofdgeheugen(main memory)
Secundair geheugen(secondary memory)
snelle toegang
langzaam
vluchtig: geen permanente opslag
wel permanente opslag
duur
goedkoop
Het hoofdgeheugen wordt gebruikt voor programma’s die in gebruik zijn en de secundaire voor het opslagen van andere programma’s. Er moet informatie kunnen worden uitgewisseld tussen hoofdgeheugen en secundair geheugen. De verantwoordelijkheid hiervoor ligt echter niet bij de programmeur want:
het kan zijn dat het beschikare geheugen kleiner is dan de plaats die nodig is voor een programma => de programmeur moet een techniek toepassen (overlay): meerdere modules kunnen worden toegekend aan hetzelfde geheugengebied, het is aan het hoofdprogramma om te zorgen dat de modules gewisseld worden. Het gebruik van overlays is echter tijdsabsorberend bij een systeem van multiprogrammering weet een programmeur op voorhand niet hoeveel ruimte er zal vrij zijn en waar die ruimte zal zijn => de programmeur kan geen boodschappen inbouwen waarbij er iets gezegd wordt over geheugenlocaties omdat deze niet vastliggen
Partitioneren van geheugen Belangrijkste taak geheugenbeheer: het inladen van processen zodat ze kunnen uitgevoerd worden. In bijna alle moderne systemen wordt daarvoor virtueel geheugen gebruikt: d.i. gebaseerd op twee basistechnieken: pagineren en segmenteren.
Vaste indeling van Partities Bij de meeste vormen voor geheugenbeheer mogen we aannemen dat het besturingssysteem een vast deel van het hoofdgeheugen bezet en dat de rest van het hoofdgeheugen beschikbaar is voor gebruik door meerdere processen. Grootte van Partities Partities met een vaste grootte kennen twee problemen. • Een programma kan te groot zijn om in een partitie te passen. Dan moet de programmeur het programma ontwerpen dat overlays gebruikt, zodat altijd maar een deel van het programma zich in het hoofdgeheugen hoeft te bevinden. Is er een module nodig die nog niet aanwezig is , dan moet het gebruikersprogramma dit in de partitie van het programma laden en de programma’s of gegevens die zich daar bevinden vervangen. • Er is een inefficiënt gebruik van het geheugen: Elk proces hoe klein ook , bezet meteen een hele partitie => interne fragmentatie Bij gebruik van Partities van ongelijke grootte is er minder interne fragmentatie. Plaatsingsalgoritme Bij Partities van gelijke grootte speelt de plaatsing van processen nauwelijks een rol. Zolang maar een partitie beschikbaar is, kan een proces in die partitie geplaatst worden. Bij Partities met een ongelijke grootte kan: 1. men een proces vast toewijzen aan de kleinste partitie waar het in past. Elke partitie heeft een wachtrij en processen Voordeel: er is een minimalisatie van interne fragmentatie 2. men gebruik maken van 1 wachtrij : als er bvb een proces van < 8mb ingeroosterd moet worden en de Partities van 8 mb zijn op, dan zal er niet gewacht worden maar het proces zal worden geplaatst in een partitie van een grotere grootte. Bovendien kan gezegd worden dat systemen met vaste partitionering relatief eenvoudig zijn en nauwelijks besturingssysteemsoftware en verwerkingsoverhead vereisen. Er zijn echter nadelen : • beperking van het aantal ( niet – opgeschorte ) processen in het geheugen • kleine processen zorgen voor inefficiënt geheugengebruik ( interne fragmentatie )
Dynamische indeling van partities Bij dynamisch Partitioneren wordt een variabel aantal Partities van variabele grootte gebruikt. => wordt een proces overgebracht naar het geheugen, dan krijgt het de hoeveelheid geheugen dat het nodig heeft en niet meer. Nadeel: na verloop van tijd ontstaan er vele kleine gaten in het geheugen die elk apart te klein zijn om een proces te kunnen bevatten: externe fragmentatie : het geheugen wordt buiten de partities gefragmenteerd <-> interne fragmentatie: binnen de partities zelf. Een oplossing voor deze externe fragmentatie is compaction: van tijd tot tijd worden de processen herschoven binnen het geheugen zodat ze aanééngesloten zijn en al het vrije geheugen 1 blok vormt. Er is wel een nadeel : compaction is verspilling van veel processortijd. Een vereiste voor compaction is dynamische Relocatie : het moet mogelijk zijn een programma te verplaatsen van het ene naar het andere gebied zonder de geheugenverwijzingen in het programma ongeldig te maken. Plaatsingsalgoritme 1. Best-fit het toewijzen van een zo klein mogelijke, niet-bezet blok geheugen aan een proces 2. First-fit doorzoekt het geheugen vanaf het begin en wijst het eerste niet-bezette blok toe aan een proces. Dit werkt het snelst. 3. Next-fit doorzoekt het geheugen vanaf de plaats waar de laatste plaatsing is gebeurd en wijst het volgende beschikbare blok toe dat groot genoeg is. Dit algoritme zal vaker geheugen toewijzen dat zich aan het einde van het geheugen bevindt Nadelen per strategie: 1. Best-Fit: Geheugencompactie moet vaker gebeuren dan bij de andere algoritmes: hoofdgeheugen raakt veel sneller vervuild met kleine blokken vrij geheugen die niet bruikbaar zijn om processen aan toe te wijzen => best-fit presteert het slechtst 2. First-fit: het voorste deel van het geheugen gaat snel volzitten met kleine blokken die té klein zijn voor processen. Het probleem is dat deze toch worden doorzocht bij aanvang van het algoritme 3. Next-fit: het grootste blok vrije geheugen (einde van het geheugen) wordt vrij snel opgesplitst in kleine delen => compaction zal vaker nodig zijn Vervangingsalgoritme Om te voorkomen dat processortijd wordt verspild aan wachten tot een wachtend proces gedeblokkeerd raakt, swapt het besturingssysteem een van de processen uit het hoofdgeheugen om ruimte vrij te maken voor een nieuw proces of een proces in de toestand Gereed-opgeschort. Het besturingssysteem moet hierbij beslissen welk proces wordt vervangen.
Buddysysteem Zowel vaste als dynamische partitionering hebben nadelen: vast: beperkt het aantal actieve processen en inefficiënt geheugengebruik dynamisch: veel onderhoud en overhead door compaction volledig beschikare ruimte = 2u wanneer nu een proces moet worden toegewezen aan geheugen, dan wordt gecontroleerd of 2u-1 < s < 2u ->als dat zo is, dan wordt het hele geheugenblok toegewezen aan het proces -> als dat niet zo is, dan wordt het blok opgedeeld in twee gelijke 'buddies' en wordt terug nagekeken of 2u-1 < s < 2u totdat dit zo is en het proces kan worden toegewezen Het buddysysteem omzeilt de problemen van vaste en dynamische partitionering MAAR het virtueel geheugen, gebaseerd op pagineren en segmenteren is veel beter.
Relocatie vaste partitionering met één wachtrij per partitie (fig 7-3a): een proces heeft een vaste partitie => lader met relocatie: wanneer een proces de eerste keer wordt geladen worden de relatieve verwijzingen in de code veranderd in absolute adressen adhv het basisadres van het in te laden proces(dit kan aangezien het altijd aan dezelfde partitie wordt toegewezen) partities van gelijke grootte (fig 7-2) + vaste partitionering met 1 wachtrij voor het hele geheugen(7-3b) + dynamische partitonering: een proces kan per keer dat het ingeladen wordt toegewezen worden aan een andere partitie (bij dyn. zelfs bij compactie) => de uitvoeringscode staat telkens op een ander adres Om dit probleem op te lossen maakt men een onderscheid tussen verschillende soorten adressen: logisch adres: verwijzing naar een locatie onafhankelijk van de huidige toewijzing van gegevens aan het geheugen; een logisch adres moet eerst vertaald worden naar een fysisch adres voordat geheugentoegang mogelijk is relatief adres: een verwijzing naar een locatie vanaf een bepaald punt, doorgaans is dit punt het begin van het programma fysisch adres: het absolute of de echte locatie in het hoofdgeheugen
Om een programma te kunnen uitvoeren moeten de relatieve adressen worden omgezet naar absolute adressen, dit gebeurt hardwarematig proces wordt actief => beginadres wordt ingeladen in basisregister <-> grensregister, bevat het eindadres van het programma (beginadres en einde worden bepaald wanneer een programma in het geheugen wodt geladen of wanneer het procesbeeld naar het geheugen wordt geswapt) elk relatief adres ondergaat twee bewerkingen in de processor: 1. eerst wordt de waarde van het basisregister opgeteld bij het relatief adres om een absoluut adres te krijgen (beginadres + relatief adres = absoluut adres) 2. dat absoluut adres wordt vergeleken met het adres in het grensregister => ligt het verkregen adres niet tussen de grenzen => er wordt een interrupt gegenereerd naar het OS dat moet reageren op deze fout ligt het wel tussen de grenzen, dan mag er verdergegaan worden met de uitvoering van de instructie
Pagineren Partities met een vaste of variabele grootte maken beide inefficiënt gebruik van het geheugen. De vaste grootte leidt tot interne fragmentatie De variabele grootte leidt tot externe fragmentatie Pagineren is het geheugen opdelen in kleine stukken van vaste grootte en welke allemaal even groot zijn. Deel nu elk proces op in stukken van dezelfde grootte. Dergelijke stukken worden pagina’s genoemd. De stukken van het geheugen worden frames genoemd. Het besturingssysteem houdt een pagina tabel bij voor elk proces. Deze tabel bevat • De frame locatie voor elke pagina in het proces • Een geheugenadres bestaande uit een paginanummer en een offset binnen die pagina.
Bovenstaande figuur illustreert het gebruik van pagina’s en frames. Op een bepaald moment zijn sommige frames in het geheugen bezet en zijn andere vrij. Het besturingssysteem houdt een lijst bij van vrije frames. De figuur verduidelijkt zichzelf. Het logische adres is de relatieve locatie van een byte of woord ten opzichte van het begin van het programma. De processor vertaalt dit in een fysiek adres.
Voor adresvertaling bij paginering zijn volgende stappen nodig: • Haal het paginanummer uit de linker n bits van het logische adres • Gebruik het paginanummer als inde in de procespaginatabel om het framenummer k te vinden. • Het fysieke beginadres van het frame is k * 2m , en het fysieke adres van de gezochte bye is gelijk aan dit nummer plus de positie. Dit fysieke adres hoeft niet te worden berekend. Het wordt eenvoudig gevormd door het framenummer toe te voegen aan de positie.
Segmenteren Het alternatief voor het opdelen van een gebruikersprogramma is het segmenteren. Het programma met zijn bijhorende gegevens wordt opgedeeld in een aantal segmenten. Alle segmenten van alle programma’s hoeven niet dezelfde grootte te hebben , maar er is wel een maximumgrootte vastgesteld. Vermits segmenten niet even groot zijn , is segmenteren gelijkaardig aan dynamische partitionering. Segmentatie voorkomt interne fragmentatie maar leidt, net als een dynamische partitionering tot externe fragmentatie. Net als bij paginering gebruikt eenvoudige segmentatie een segmenttabel voor elk proces en een lijst van vrije blokken in het hoofdgeheugen. Elke ingang in een segmenttabel vebat het beginadres van het bijbehorende segment in het hoofdgeheugen. De ingang bevat ook informatie over de lengte van het segment, om te voorkomen dat ongeldige adressen worden gebruikt. Voor adresvertaling bij segmenteren zijn de volgende stappen nodig: • Haal het segment nummer uit de linker n bits van het logische adres. • Gebruik het segmentnummer als index in de segmenttabel van het proces om het fysieke beginadres van het segment te vinden. • Vergelijke de positie, die is vastgelegd in de rechter m bits, met de segment lengte. Is de positie groter dan de lengte , dan is het adres ongeldig.
Virtueel geheugen Hardware en besturingsstructuren Eigenschappen pagineren en segmenteren: 1. relocatie: een proces kan gedurende verschillende momenten verschillende geheugenlocaties innemen wanneer het wordt weggeswapt en weer wordt teruggeswapt. Dit komt omdat de adressering die gebruikt wordt dit toelaat (= at runtime vertaling <-> tijdens compilen want de adressen staan niet hard gecodeerd) 2. proces kan opgebroken worden in meerdere stukken (pagina's of segmenten) 3. de stukken moeten niet aaneengesloten zijn om te kunnen uitgevoerd worden GEVOLG: het is niet nodig dat een volledig proces(alle pagina's/segmenten) in het hoofdgeheugen staat wanneer het uitgevoerd wordt (het stuk met de volgend uit te voeren instructie en met de volgende te gebruiken geheugen locatie is genoeg) Werking: nieuw proces moet worden ingeladen: OS laadt het begin van het proces in en het deel dat de gegevens bevat waarnaar de instructies verwijzen (residente set = deel v/e proces dat zich werkelijk in het hoofdgeheugen bevindt) de processor kan nagaan of de geheugenverwijzingen nog steeds ingeladen zijn. Dit wordt gecontroleerd adhv de logische adressen enerzijds adhv de segment-of paginatabel anderzijds wanneer logisch adres niet meer in het hoofdgeheugen => processor genereert interrupt => OS blokkeert proces => I/O verzoek om het nodige deel van het proces te lezen vd harde schijf => terwijl dat bezig is wordt een ander proces uitgevoerd OS krijgt een interrupt dat I/O bewerking compleet is en zet proces terug in de wachtrij 'Gereed' Gevolgen: 1. er kunnen zich meer processen in het geheugen bevinden => efficiënter gebruik van de processor omdat de kans hoger is dat er ten minste één proces 'Gereed' is 2. een proces kan groter zijn dan het totale hoofdgeheugen: (dit geldt uiteraard niet voor de residente set) <-> geen segmenteren of pagineren, dan moet de programmeur zich wenden tot het gebruik van overlay terwijl nu is er voor de programmeur 1 groot geheugen dat beheerd wordt door de hardware en het OS Twee soorten geheugen: 1. reële geheugen (de plaats waar processen uitgevoerd worden) 2. virtuele geheugen (de ruimte die wordt toegewezen op schijf)
Lokaliteit en virtueel geheugen Virtueel geheugen op basis van uitsluitend pagineren of de combinatie van pagineren en segmenteren is een essentieel onderdeel geworden van de meeste hedendaagse besturingssystemen. Trashing: wanneer de processor meer bezig is met het in en uitswappen van processen dan met de uitvoering ervan. Dit gebeurt wanneer het reële geheugen overvol zit en er continu processen moeten uitgeswapt worden om plaats te maken voor andere stukken van een proces. Wanneer een uitgeswapt deel echter meteen weer nodig is, dan moet dit worden ingeswapt. Veel swappen dus en weinig uitvoer.
Trashing voorkomen door te voorspellen welke delen van een proces in de nabije toekomst zullen nodig zijn op basis van het recente verleden. Dit is gebaseerd op het lokaliteitsbeginsel: verwijzingen naar programma's en gegevens van processen hebben de neiging op te hopen tot een cluster => het is geldig om te veronderstellen dat slechts een deel van een proces nodig is voor een beperkte tijd => het is mogelijk om een voorspelling te maken van de stukken die zullen nodig zijn in de nabije toekomst wat trashing voorkomt fig8-1 illustratie van lokaliteitsbeginsel => virtueel geheugen kan werken aangezien er een voorspelling kan gemaakt worden en trashing kan voorkomen worden, anders was het maar een slecht idee aangezien het na verloop van tijd aanleiding zou geven tot trashing Wat nodig voor virtueel geheugen: 1. hardwareondersteuning: toepassen paginering en segmentering + vertaling van adressen 2. softwareondersteuning: beheren van de verplaatsing van delen proces tussen hoofd-en secundair geheugen
Pagineren Elk proces heeft paginatabel: iedere ingang = framenummer voor de bijhorende pagina in het hoofdgeheugen.
Pagineren + gebruik van virtueel geheugen => complexer want het kan nu zijn dat er slechts een deel van een proces in het geheugen staat => elke page table entry (PTE) bevat nu ook een bit die aangeeft of de pagina in het hoofdgeheugen zit of niet (de present- bit of de p-bit) Een andere bit die aanwezig is in de PTE, is de m(odify)-bit: geeft aan of de pagina gewijzigd is, is dat niet zo, dan moet de pagina niet worden weggeschreven naar het virtueel geheugen bij het swappen aangezien beide versies nog gelijk zijn => efficiënter gebruik maken van het systeem. Paginatabelstructuur
lezen van een woord uit het geheugen: vertalen van een virtueel (logisch) adres(paginanummer en offset) in een fysiek adres(framenummer en offset) paginatabel heeft variabele grootte (afhankelijk van grootte proces) => niet opslaan in registers maar in hoofdgeheugen (zie fig 8-3) proces wordt uitgevoerd => register bevat beginadres van de paginatabel van het proces het paginanummer wordt gebruikt als index in de tabel om het bijhorende framenummer op te zoeken reëel adres = framenummer + offset
De meeste systemen gebruiken 1 paginatabel per proces <-> VAX: ieder proces kan 231 (2 G) groot zijn. Stel: paginagrootte: 512 byte => 222 PTE's => Paginatabel = enorm => paginatabel wordt ook ingedeeld in pagina's en wordt opgeslaan in virtueel geheugen. => wordt een proces uitgevoerd, dan
moet er een deel van de paginatabel in het hoofdgeheugen staan en al zeker de PTE van de huidige pagina. Sommige systemen gebruiken een systeem met twee niveaus: bevat een paginadirectory (elke ingang van deze directory verwijst naar een paginatabel). Is de lengte van het paginaoverzicht X en is de lengte vd paginatabel Y, dan bestaat een proces uit X*Y pagina's
stel:
adressen van 32 bits paginagrootte: 212 (kB) => virtueel geheugen van 232 bytes (4GB) kan 220 aantal pagina's bevatten iedere PTE = 4B => de volledige paginatabelgrootte = 220 * 4 = 222 bytes(4MB) => mogelijkheid om een gebruikerspaginatabel van 210 pagina's in het virtueel geheugen te hebben en bereikbaar te maken a.d.h.v. een basispaginatabel met 210 PTE's en een grootte van 212 (4 kB) in het hoofdgeheugen. De basispaginatabel blijft altijd in het hoofdgeheugen!
fig 8-5 adresvertaling bij een systeem met twee niveaus: eerste 10 bits van virtuele adres = index in de basispaginatabel om de PTE te verkrijgen voor een pagina in de gebruikerspaginatabel(paginafout: refereren naar een pagina die niet aanwezig is in hoofdgeheugen). is de pagina wel aanwezig in het hoofdgeheugen, dan zijn de volgende 10 bits in het adres de index in de gebruikersPTE-pagina om de PTE te vinden van de pagina waarnaar verwezen wordt in het virtuele adres
Geinventeerde paginatabel Nadeel van hogergenoemde paginatabellen is dat de grootte ervan evenredig is met de omvang van de virtuele adresruimte. Bij een ander type paginatabel is dit niet, hierbij wordt er gewerkt met een geïnverteerde paginatabelstructuur (indexeert de items op framenummer ipv op virtueel paginanummer) waarbij het paginanummer (onderdeel van virtueel adres) gehashed wordt en deze hash verwijst naar de geïnverteerde paginatabel. Deze tabel heeft een vaste grootte, namelijk als een fysiek geheugen 2m frames bevat dan is er plaats in de tabel voor 2m items waarbij item z verwijst naar frame i. De geïnverteerde paginatabel bevat 1 item voor elke werkelijke frame ipv 1 item per virtuele pagina collision (de hashes van twee verschillende paginanummers zijn gelijk) is mogelijk => er wordt gewerkt met een kettingtechniek om toch tot het juiste adres te komen Ieder item in de geïnverteerde paginatabel bevat volgende gegevens: Paginanummer: (paginanummer virtueel adres) PID: proces dat deze pagina in bezit heeft (combinatie paginanummer-PID is uniek => kan gebruikt worden als er collision is bij hashing) Besturingsbits: bvb.: modified, referenced, valid, beveiligings- en vergrendelingsinfo Kettingpointer: is 0 als er geen koppelingen zijn met andere pagina's. bevat een nummer van 2m-1 dat het rangnummer is in de tabel van het volgende item in de ketting
Translation lookaside buffer Elke virtuele verwijzing naar het virtuele geheugen kan twee dingen veroorzaken in het fysieke geheugen: ophalen van gegevens ophalen van de juiste PTE Als beiden moeten gebeuren tgv dezelfde verwijzing, dan moet er eerst gezocht worden naar de juiste PTE èn dan nog eens naar de juiste gegevens op de schijf => verdubbeling van geheugentoegangstijd.
Dit wordt opgelost door TLB = speciale cache voor paginatabelingangen; bevat de PTE's die recent het meest gebruikt zijn Werking: processor ontvangt een virtueel adres is de gewenste PTE in de TLB, dan wordt het framenummer opgevraagd en wordt het reële adres gevormd, samen met de offset TLB-miss => met paginanummer als index kijken of de 'present' bit van de pagine in de PTE in de paginatabel op 1 staat => pagina staat in het hoofdgeheugen => het framenummer wordt opgevraagd uit de PTE en het reële adres wordt gevormd + de TLB wordt bijgewerkt door deze nieuwe PTE toe te voegen is de p-bit 0 => paginafout en dan verlaten we de hardware om het OS de pagina re laten laden en om de paginatabel bij te werken
Opmerking bij stroomschema p379 (fig 8-8): wanneer I/O bewerking gebeurt voert processor ondertussen ander proces(sen) uit. Overeenkomstig het beginsel van lokaliteit: de meeste verwijzingen naar virtueel geheugen zijn verwijzingen naar locaties in recent gebruikte pagina's Het opzoeken in de TLB gaat sneller dan het opzoeken in de paginatabel omdat het gaat om cachegeheugen! associatieve vertaling (associative mapping): de hardware is in staat om verschillende TLB entries tegelijkertijd te doorzoeken (daarom is het nodig dat iedere TLB ingang naast het paginanummer ook de volledige PTE bevat)
Directe vertaling die gebruikt wordt om op te zoeken in de paginatabel Het gebruik van een TLB vereist interactie met de hoofdgeheugencache. Stel dat de PTE zich in de TLB bevond of in de paginatabel na een TLB-miss, dan wordt het reëel adres gevormd. Dan wordt er in de hoofdgeheugencache nagekeken of het blok met het vereiste woord zich daarin bevindt. Is dat niet zo, dan moet de processor het inladen uit het hoofdgeheugen. Paginagrootte Afweging: hoe groot moet een pagina nu zijn? Is een kleine beter dan een grote? hoe kleiner een pagina des te kleiner is de interne fragmentatie MAAR des te groter is het aantal pagina's dat het proces nodig heeft (en dus ook meer pagina's die moeten aanwezig zijn in het geheugen => kans ++ dat er veel gaat moeten ingeladen worden uit virtueel geheugen) => een deel van de paginatabellen van actieve processen gaat zich in het virtueel geheugen bevinden => bij 1 verwijzing naar het geheugen kan dan een dubbele paginafout optreden: 1 voor het binnenhalen van de nodige gegevens uit de paginatabel en 1 voor het binnenhalen van de procespagina De meeste apparaten voor secundaire opslag vereisen echter een grotere paginagrootte voor een meer efficiënte blokoverdracht van gegevens (daarvoor dienen ze, om grote hoeveelheden aaneengesloten data te verwerken) Nog iets om mee rekening te houden is de invloed die de paginagrootte heeft mbt paginafouten: paginagrootte klein => weinig paginafouten want er kunnen veel pagina's worden ingeladen in het hoofdgeheugen. Beginsel van lokaliteit: na verloop van tijd bevinden zich in het geheugen alle gedeelten van het programma in de buurt van frequente verwijzingen als de grootte toeneemt, bevat elke afzonderlijke pagina locaties die zich verder an een recente verwijzing bevinden => invloed beginsel lokaloteit neemt af en dan stijgt de foutfrequentie naarmate de pagina's nog groter worden zullen ze groot genoeg worden om ganse processen te bevatten waardoor er geen paginafouten meer optreden
De foutfrequentie is ook afhankelijk van het aantal frames die worden toegewezen aan een proces. Naarmate het aantal toegewezen frames stijgt, daalt het aantal paginafouten Het ontwerp van de paginagrootte hangt ook samen met de grootte van het fysieke hoofdgeheugen en van het programma. Naarmate het geheugen groter wordt, groeit ook de adresruimte die door toepassingen kan worden gebruikt. De invloed van het beginsel van lokaliteit - - op moderne programmeertechnieken: OO-programmeren: verwijzingen worden op korte tijd sterk verspreid over een groot aantal objecten multithreading: abrupte veranderingen in de instructiestroom en tot verspreide geheugenverwijzingen Probleem: als lokaliteit afneemt, dan neemt het aantal hits in de TLB ook af en vormt het opzoeken in de TLB een bottleneck Hoe dit oplossen? grotere TLB kan maar zal minder wsl zijn grotere pagina's => iedere TLB ingang verwijst naar een groter stuk geheugen (maar het vergroten van de grootte kan leiden tot een vermindering aan prestaties) Er is geëxperimenteerd geweest met meerdere paginagrootten waardoor er een flexibiliteit ontstaat die toelaat de TLB efficiënt te gebruiken.
Segmenteren
Gevolgen voor het virtueel geheugen
vereenvoudigt het werken met groeiende gegevensstructuren want OS wijst gegevensstructuur toe aan segment dat kan groeien en krimpen <-> geen segmentatie => programmeur moet inschatten hoeveel plaats hij gaat nodig hebben voor zijn gegevensstructuur moet een segment uitgebreid worden en is er daarvoor onvoldoende ruimte, dan kan het verplaatst worden naar een deel van het geheugen waar er wel genoeg ruimte is of wordt het weggeswapt als er geen blokken zijn die groot genoeg zijn programma's kunnen onafhankelijk van elkaar worden gecompileerd 1 segment kan door meerdere processen gedeeld worden (tabel apart in een segment plaatsen zodat meerdere processen het kunnen gebruiken) de programmeur kan rechten toekennen aan segmenten => bescherming van de gegevens
Organisatie elk proces heeft een eigen segmenttabel Aangezien niet alle segmenten moeten worden ingeladen in het hoofdgeheugen bevat elke segmenttabelingang (STE) naast het beginadres van het overeenkomende segment in het hoofdgeheugen + lengte van het segment ook nog een p-bit en een m-bit + nog eventuele andere besturingsbits. basismechanisme voor lezen van een woord uit het geheugen: vertalen van een virtueel adres(segmentnummer en offset) naar een reëel adres mbv de segmenttabel Een register bevat het beginadres van de segmenttabel, segmentnummer in virtueel adres dient als index voor de juist STE in de tabel. De STE geeft dan weer aan wat het basisadres is van het segment in het hoofdgeheugen. Dat basisadres + offset = reëel adres.
Gecombineerd pagineren en segmenteren Pagineren is transparant voor de programmeur en elimineert externe fragmentatie en zorgt daarmee voor een efficiënt gebruik van het hoofdgeheugen. Segmentatie is zichtbaar voor de gebruiker en heeft de mogelijkheid van werken met groeiende gegevensstructuren , modulariteit en de ondersteuning van delen en bescherming. Elk segment wordt opgedeeld in een pagina’s van vaste grootte.
Bescherming en delen Bescherming: elke STE: een lengte en basisadres => een programma kan geen toegang krijgen buiten de grenzen van een segment Deling: er kan naar een segment verwezen worden in de segmenttabellen van meerdere processen Dit kan ook in een pagineringssysteem maar dan is het onzichtbaar voor de programmeur.
Besturingssysteemsoftware het ontwerp van het geheugenbeheer van een OS is afhankelijk van 3 fundamentele keuzes: 1. gebruik van virtueel geheugen? 2. pagineren, segmenteren of beide? 3. kiezen van algoritmes die worden toegepast voor allerlei aspecten van het geheugenbeheer Ophaalstrategie vraag herpagineren
Beheer residente set grootte residente set vast variabel vervangingsbereik globaal lokaal
Plaatsingsstrategie
Opschoonstrategie vraag vooral opschonen
Vervangingsstrategie optimaal Least recently used (LRU) First in first out Klok Paginabuffering
Beheer van procesbelasting multiprogrammeringsgraad
Strategie bij ophalen (fetch policy ) Deze strategie bepaalt wanneer een pagina moet worden overgebracht naar het hoofdgeheugen. Twee mogelijkheden: 1. vraagpaginering (demand paging): een pagina wordt alleen maar overgebracht naar het hoofdgeheugen bij een verwijzing naar een locatie binnen de pagina (bij de start van een nieuw proces => veel paginafouten want de pagina's waarnaar verwezen wordt zitten nog niet in het geheugen => paginafout; beginsel van lokaliteit stelt dat: naarmate meer en meer pagina's worden ingeladen, de meest toekomstige verwijzingen verwijzingen zullen zijn naar pagina's die nog maar recent zijn gebruikt geweest => aantal paginafouten daalt mettertijd) 2. prepaginering(prepaging): naast de pagina waarnaar verwezen wordt, worden ook nog andere pagin's ingeladen => efficiënter gebruik maken van de harde schijf want nu worden in 1 keer meerdere blokken gelezen ipv telkens te moeten zoeken en lezen (nu maar 1 keer zoektijd en rotatietijd !!). Dit is op het gebied van aantal paginafouten uiteraard pas interessant als de pagina's die worden ingeladen ook gebruikt worden !!!!!!!!Wordt een proces uit het geheugen geswapt ('Opgeschort'), dan worden alle pagina's van de residente van dat proces verwijderd. Wordt het proces opnieuw hervat, dan worden de pagina's die zich van dat proces in het geheugen bevonden terug ingeladen.!!!!!!!!!!!
Strategie bij plaatsing Deze strategie bepaalt waar een stuk van het proces terechtkomt in het geheugen. best-fit, first-fit,... Belangrijk bij segmentering. Bij zuiver pagineren of een combinatie van segmentering en paginering maakt deze strategie niets uit omdat de hardware voor de adresvertaling en de hardware voor geheugentoegang even efficiënt kunnen werken voor elke pagina/framecombinatie
Strategie bij vervanging Welke pagina moet worden vervangen uit de verzameling pagina's doe voor vervanging in aanmerking komen wanneer alle frames in het hoofdgeheugen bezet zijn en er moet een nieuwe pagina worden binnengehaald om te reageren op een paginafout. Iedere aanpak heeft als doel dat de pagina die verwijderd wordt, de pagina is waarbij de kans dat er in de nabije toekomst naar zal worden gerefereerd het kleinst is. Naarmate een strategie uitgebreider en geavanceerder wordt, stijgt de hard-en softwareoverhead. Framevergrendeling Wanneer een frame vergrendeld is (grendelbit staat op 1 in de frame- of de paginatabel) => pagina kan niet worden verwijderd in het hoofdgeheugen om te worden vervangen Elementaire algoritmen 1. Optimaal: vervangt de pagina waarnaar het verst in de toekomst gerefereerd zal worden. Dit is echter puur theoretisch omdat dit van het OS vereist dat het op de hoogte is van alle toekomstige referenties 2. Least recently used (LRU): vervang de pagina waarnaar het minst recent is gerefereerd: volgens beginsel van lokaliteit is dit de pagina met de kleinste kans om in de toekomst naar gerefereerd te worden 3. FIFO: pagina's worden om beurten verwijderd (round robin) => de pagina die het langst in het geheugen is wordt vervangen. Dit is nadelig want het zou kunnen zijn dat die in de nabije toekomst weer nodig is => paginafout. Maar, het voordeel is dat dit gemakkelijk te implementeren is. 4. Klok: aan elk frame wordt een extra bit toegevoegd: de u(se)-bit. Wanneer een pagina voor het eerst in het geheugen wordt geladen, dan wordt de pointer naar het volgende frame gezet. Als naar de pagina verwezen wordt, dan wordt de use bit op 1 gezet. Wanneer een pagina vervangen moet worden, dan wordt het eerste frame dat tegengekomen wordt met een use bit op 0 vervangen. Tijdens het zoeken voor vervanging wordt elke use bit die op 1 staat, op 0 gezet (zie fig 8-15) Het verschil met FIFO is dat sommige frames (met u-bit==1) worden overgeslagen en dat het niet altijd de oudste pagina moet zijn die vervangen wordt. Men heeft gevonden dat, naarmate er meer frames worden toegewezen aan een proces, het verschil in paginafouten kleiner en kleiner wordt tussen de verschillende strategieën => kan het lonen om te opteren voor een simpele strategie omdat deze minder tijd in beslag neemt om uit te voeren. Het klokalgoritme kan krachtiger worden gemaakt wanneer er rekening wordt gehouden met een tweede bit naast de u-bit: de m-bit => 4 categorieën: 1. geen recente toegang, ongewijzigd (u:0;m:0) 2. recente toegang, ongewijzigd (u:1;m:0) 3. geen recente toegang, gewijzigd (u:0;m:1) 4. recente toegang, gewijzigd (u:1;m:1) Het klokalgoritme werkt dan zo: 1. zoek naar frames waarbij u==0 en m==0; het eerste frame dat hieraan voldoet wordt vervangen; 2. mislukt dat, dan wordt het eerste frame met u==0 en m==1 vervangen; 3. mislukt ook dat, dan gaan we nog eens door de frames want nu zijn alle u-bits die daarvoor 1 waren 0 geworden en is er dus zeker 1 frame dat voldoet aan u==0;m==0 OF u==0;m==1
Waarom u==0 en m==1 als tweede keuze: omdat dit frame niet recent is gebruikt en dus is de kans dat het binnenkort opnieuw gaat moeten gebruikt worden klein. Het f rame moet wel weggeschreven worden voordat het wordt vervangen maar dat weegt op tegen het feit dat het mss niet nodig is in de toekomst. Paginabuffering
LRU en klok zijn superieur aan FIFO MAAR complexer en meer overhead de kosten van vervanging van een gewijzigde pagina > die van een ongewijzigde pagina
Paginabuffering: Vervangen pagina gaat niet verloren maar wordt toegevoegd aan volgende lijsten:
één van
Lijst van vrije pagina’s als de pagina niet gewijzigd is Lijst van gewijzigde pagina’s (moeten weggeschreven worden naar secundair geheugen) de pagina wordt niet verwijderd uit het hoofdgeheugen maar de PTE wordt verwijderd uit de paginatabel en in de juiste lijst (vrije/gewijzigde) geplaatst. VOORDELEN paginabuffering:
het kost weinig om de pagina terug in te laden in de residente set, gewoon de PTE uit de lijst halen en in de paginatabel zetten gewijzigde pagina's worden weggeschreven in clusters, niet 1 per 1, dat vermindert het aantal I/Obewerkingen en daarmee ook de schijftoegangstijd
Paginabuffering werkt dan als een soort van cache voor pagina's
Beheer van de residente set Grootte van de residente set
vaste toewijzing(fixed allocation): een proces krijgt een vast aantal pagina's waarbinnen het moet worden uitgevoerd; dat aantal wordt bepaald bij de eerste keer dat het proces geladen wordt. Wanneer tijdens de verwerking een paginafout optreedt, dan moet een procespagina vervangen worden door een nieuw aangevraagde pagina variabele toewijzing(variable allocation): het aantal frames dat is toegewezen aan een proces kan variëren gedurende de levensloop van het proces. Een proces dat veel paginafouten genereert geeft aan dat het beginsel van lokaliteit slechts in beperkte mate geldt voor dat proces. Dan kan het aantal toegewezen frames aangepast(verhoogd) worden. Omgekeerd kan ook, als er zeer weinig paginafouten gegenereerd worden, dan kunnen er gerust minder frames worden toegewezen. Variabele toewijzing hangt samen met het concept 'Vervangingsbereik'
Vervangingsbereik twee methodes die allebei worden geactiveerd wanneer er geen vrije frames zijn en er is een paginafout Lokaal: bij het vervangen wordt een pagina uit de residente set gekozen van het proces Globaal: alle onvergrendelde pagina's kunnen vervangen worden, van wel proces ze ook zijn
Vervangingsbereik hangt samen met grootte residente set: lokale vervanging vaste toewijzing
variabele toewijzing
globale vervanging
- het aantal aan een proces toegewezen frames ligt vast - de te vervangen pagina wordt gekozen uit de frames die zijn toegewezen aan het proces
gaat niet: om de grootte van de residente set gelijk te houden moet een pagina van de residente set vervangen worden door een andere pagina van de residente set
- het aantal toegewezen frames kan wijzigen voor het behoud van de werkset (working set) van het proces - de te vervangen pagina wordt gekozen uit de frames die zijn toegewezen aan het proces
- de te vervangen pagina's worden gekozen uit alle beschikbare (nietvergrendelde) frames in het hoofdgeheugen => de grootte van de residente set kan variëren
Vaste toewijzing met lokaal bereik
proces wordt uitgevoerd in hoofdgeheugen met vast aantal pagina's paginafout => welke pagina vd residente set gaat vervangen worden? van tevoren moet worden beslist hoeveel ruimte wordt toegewezen aan een proces; nadelen: als dit te weinig is: paginafouten te veel: er kunnen te weinig processen ingeladen worden in het hoofdgeheugen => er wordt veel tijd besteed aan het swappen van processen
Variabele toewijzing met globaal bereik
gemakkelijkste vorm om te implementeren paginafout => vrij frame toevoegen aan de frames die zijn toegewezen aan het proces en de pagina daaraan toewijzen zijn er geen vrije frames meer, dan wordt een pagina vervangen van om het even welk proces. De moeilijkheid is deze keuze maken. Dit kan verholpen worden door gebruikt te maken van paginabuffering omdat een pagina opnieuw kan worden gebruikt als die nog niet is weggeschreven naar de harde schijf
Variabele toewijzing met lokaal bereik robeert de problemen die ontstaan door het werken met globaal bereik te omzeilen: wordt een nieuw proces in het hoofdgeheugen geladen, wijs daar dan een bepaald aantal frames aan toe en gebruik prepaginering of vraagpaginering voor het vullen van de rest van de toewijzing paginafout => selecteer de te vervangen pagina uit de residente set van het proces dat de fout heeft veroorzaakt evalueer de toewijzing aan het proces zo nu en dan en verhoog of verlaag het aantal toegewezen frames indien nodig een veelbesproken methode: de werksetbenadering werkset = een verzameling pagina's van een proces waarnaar verwezen is binnen een bepaald tijdsvenster => als tijdsvenster groter wordt, dan wordt de werkset groter De working set hangt nauw samen met lokaliteit: door dat beginsel gebruikt het proces een stabiele set aan pagina's waarvan de inhoud van de werkset slechts minimaal verandert, volgende overgansperioden wijzen op een verandering naar een nieuwe lokaliteit.
Tijdens een overgangsfase blijven een aantal pagina's uit de oude lokaliteit binnen het venster wat leidt tot een forse toename van de grootte van de werkset bij verwijzingen naar nieuwe pagina's. Verschuift het venster over deze paginaverwijzingen, dan neemt de werksetgrootte af totdat de werkset uitsluitend pagina's bevat die behoren tot de nieuwe lokaliteit Werkset kan worden gebruikt als leidraad bij een strategie voor de grootte van de residente set: 1. controleer de grootte van de werkset van elk proces 2. verwijder regelmatig pagina's uit de residente set van een proces die niet voorkomen in de residente set van een proces (vergelijkbaar met LRU) 3. een proces mag alleen worden uitgevoerd als zijn werkset zich in het hoofdgeheugen bevindt = als zijn residente set zijn werkset bevat => minder initiële paginafouten Beperkingen van de werksetbenadering: de toekomst kan niet worden voorspeld op basis van het verleden; zowel de grootte als de samenstelling van de werkset zullen na verloop van tijd veranderen het nauwkeurig meten van de werkset van ieder proces is onpraktisch want dit vereist een timestamp voor iedere paginaverwijzing van elk proces = nogal veel optimale waarde van Δ is onbekend en zal wisselen desalniettemin is de gedachte goed en daarom zijn er een aantal OS'en die het trachten te implementeren In plaats van de werksetgrootte rechtstreeks te bewaken kunnen er vergelijkbare resultaten gehaald worden door de frequentie van paginafouten te bewaken omdat, als de grootte van de residente set stijgt, dan daalt het aantal paginafouten. De werksetgrootte is een punt op een kromme (zie p404). => Ligt de foutfrequentie onder een bepaald minimum, dan is het beter voor het systeem om een kleinere residente set toe te wijzen aan een proces => Ligt de foutfrequentie boven een bepaald maximum, dan is het beter dat er een grotere residente set wordt toegewezen aan het proces Een algoritme die deze benadering volgt is pagina foutfrequentie. Dit vereist dat een use-bit verbonden is aan elke pagina in het geheugen. Bij toegang tot de pagina wordt die ingesteld op 1. Bij paginafout: registratie van de virtuele tijd sinds de laatste paginafout voor dat proces Er wordt een drempel F gedefinieerd. Is de tijd sinds de laatste paginafout < F => er is een fout opgetreden, sneller dan verwacht werd => er wordt een pagina toegevoegd aan de residente set van het proces; is die tijd > F, dan worden alle pagina's met een use-bit die gelijk is aan 0 verwijderd => residente set wordt kleiner en tegelijkertijd worden de use-bits van de resterende pagina's op 0 gezet. Deze strategie kan verfijnd worden door gebruik te maken van een minimum- en maximumdrempel om respectievelijk het verkleinen en het vergroten van de residente set te activeren De tijd tussen paginafouten is omgekeerd evenredig met de foutfrequentie. PFF heeft één groot nadeel: presteert niet goed tijdens overgangsfasen waarin een verschuiving plaatsvindt naar een nieuwe lokaliteit => veel paginafouten Benadering die probeert het fenomeen van overgangen tussen lokaliteiten op te lossen en die een relatief lage overhead heeft => Variable-interval Sampled Working Set Op basis van steekproef-tijdsinterval grootte van residente set aanpassen Gedurende tijdsinterval: pagina’s aan werkset toevoegen waarvoor paginafout optreedt -> Use bit op 1 bij verwijzing naar pagina tijdens tijdsinterval Op einde van tijdsinterval:
alle pagina’s met use bit op 0 uit werkset verwijderen 3 parameters 1. M: minimumduur 2. L: maximumduur 3. Q: aantal paginafouten dat mag optreden 4. t >= L : schort proces op en controleer use bits t < L en Q paginafouten bereikt: t < M: wacht tot M, schort proces op en controleer use bits t >= M : schort proces op en controleer use bits
Opschoon strategie een opschoonstrategie bepaalt wanneer een gewijzigde pagina moet worden weggeschreven naar het secundaire geheugen Twee mogelijkheden: vraagopschoning: een pagina wordt alleen weggeschreven wanneer die geselecteerd is voor vervanging precleaning: gewijzigde pagina's worden weggeschreven voordat hun frames nodig zijn => pagina's kunnen in batches worden weggeschreven Nadelen: vraagopschoning: het schrijven van een vervuilde pagina moet gekoppeld zijn aan het inlezen van een nieuwe pagina. Het processorgebruik kan afnemen omdat het proces dat de paginafout veroorzaakte moet wachten op twee paginaoverdrachten. precleaning: de overdrachtscapaciteit van het secundair geheugen is beperkt en mag niet worden verspild aan onnodig wegschrijven en het wegschrijven van een pagina die toch in het hoofdgeheugen blijft en nog eens gewijzigd wordt, dat is een onnodige schrijfbewerking geweest p407 een betere benadering is paginabuffering: schoon alleen pagina's op die kunnen worden vervangen en koppel de bewerkingen voor het opschonen en vervangen los. Pagina's worden in twee lijsten geplaatst: (on)gewijzigd. De pagina's in de gewijzigde lijst worden periodiek in batches weggeschreven. Een pagina in de lijst van de ongewijzigde pagina's wordt opnieuw gebruikt wanneer ernaar gerefereerd wordt en gaat verloren wanneer zijn frame aan een andere pagina wordt toegewezen.
Toezicht op de procesbelasting dit heeft betrekking op het aantal processen dat resident is in het hoofdgeheugen, het zgn. niveau van multiprogrammering De strategie voor het beheer van procesbelasting is belangrijk voor de efficiëntie van het geheugenbeheer. Zijn er te weinig processen in het geheugen => de kans is groot dat deze processen allemaal geblokkeerd zijn en dat er veel tijd wordt gespendeerd aan swapping. Zijn er te veel processen, dan is de omvang van de residente set van de processen te klein => veel paginafouten => trashing
Niveau van multiprogrammering
Naarmate er meer processen worden ingeladen, hoe kleiner wordt de kans dat daar een geblokkeerd proces bij is (dus dat alle processen geblokkeerd zijn) waardoor het processorgebruik stijgt. Echter, vanaf een bepaald punt zijn er te veel processen wat ertoe leidt dat de gemiddelde grootte van de residente set te klein wordt => veel paginafouten => er moeten veel pagina's worden ingeladen uit virtueel geheugen => weinig echt processorgebruik Er is een algoritme dat dit probleem oplost: PFF: dit beheert impliciet de procesbelasting; alleen processen met een voldoende grote werkset mogen worden uitgevoerd Opschorten van processen
wanneer het niveau van multiprogrammering worden verlaagd, dan moet één of meer van de residente processen worden opgeschort (uit het hoofdgeheugen worden weggeswapt); zes mogelijkheden: 1. proces met de laagste prioriteit 2. proces dat een paginafout veroorzaakt: er is een grotere kans dat de werkset van dit proces niet resident is => de prestaties zullen het minst lijden onder het opschorten van dit proces 3. Laatst geactiveerd proces: hierbij is de kans het grootst dat het geen residente werkset heeft 4. Proces met de kleinste residente werkset: dit vereist de kleinste toekomstige inspanning om het proces weer te laden. Het is echter nadelig voor programma's met een beperkte lokaliteit 5. grootste proces => bij een overvol geheugen onstaan hierdoor de meeste vrije frames waardoor extra inactiveringen in de nabije toekomst onwsl maakt 6. Proces met de grootste resterende uitvoeringstijd: dit neemt immers ook plaats in aangezien het nog even kan duren vooraleer het uit het hoofdgeheugen is verdwenen wanneer het volledig is uitgevoerd
