Besturingssystemen en geavanceerde systeemsoftware

http://www.kuleuven.be/onderwijs/aanbod/syllabi/H04G1AN.htm

Examenvragen

Het open boek examen verloopt in twee delen:

• Eerste deel: 4-tal theorie-vragen. Hiervoor heb je maximaal 50 minuten om je antwoord voor te bereiden. Je geeft je voorbereiding af in ruil voor de opgave van het tweede deel.
• Tweede deel: een synchronisatie-oefening. Hiervoor is geen maximale tijd voorzien, maar dit zou toch in 30-45 minuten moeten opgelost kunnen worden.

Beiden worden mondeling verdedigd! Je mag bijvragen verwachten.

Gelieve een kopie van je Linux-paper mee te brengen naar het examen.

Puntenverdeling:

• 1/3 op de paper
• 1/3 op de theorievragen
• 1/3 op de synchronisatieoefening

Om lang wachttijden te vermijden, word je verzocht je op het aangeduide uur aan te bieden.

2009-01-29 voormiddag

Deel 1: Theorie (max 50 min.)

1. Soms kan het CPU-scheduling algoritme herleid worden tot binair scheduling. Wat betekent dit en onder welke omstandigheden kan dit gebeuren?
2. Schets een implementatie van een symbolische link als een (apart) klein bestand. Hoeveel leesoperaties zijn er nodig om een bestand te openen dat aangeduid wordt via een symbolische link?
3. Wat is een digipass (token device)? Waarvoor wordt het gebruikt? Welk voordeel heeft het t.o.v. een traditioneel wachtwoord? Heeft het ook nadelen?
4. Beschouw een systeem waarbij men deadlock probeert te vermijden (deadlock avoidance). Het systeem bevindt zich momenteel in een veilige toestand. Geef voor elk van de volgende gebeurtenissen aan of het systeem steeds veilig blijft of zeker onveilig wordt of dat niet te voorspellen is welke richting het uit wal gaan (veilig/onveilig):
   • een proces krijgt een extra hulpmiddel toegewezen,
   • een proces geeft enkele hulpmiddelen vrij,
   • een proces wordt door het OS verplicht om te wachten op een aangevraagd hulpmiddel dat toch beschikbaar is,
   • een proces moet wachten omdat het gevraagde hulpmiddel miet beschikbaar is.

Deel 2: Oefening (±30 min.)

De toegang tot een voetbalstadium wordt geautomatiseerd. Het stadium wordt in twee strikt gescheiden vakken opgedeeld. Supporters voor de thuisploeg en deze voor de bezoekende ploeg worden elk in hun eigen vak ondergebracht. Daarnaast zijn er nog neutrale supporters; deze kunnen afhankelijk van de beschikbare plaatsen in beide vakken worden ondergebracht. Op het einde van de wedstrijd moeten de supporters gescheiden het stadium verlaten. Eerst moet het vak van de supporters voor de bezoekende ploeg leeg gemaakt worden daarna dit van de supporters voor de thuisploeg. Ontwerp een monitor die de toegang tot het stadium regelt. De monitor heeft vijf publieke methodes:

• int toegang(int supporter)

{Een supporter wil toegang tot het stadium. De parameter geeft aan of hij/zij een supporter voor thuisploeg is (1), voor de bezoekende ploeg (-1) of een neutrale supporter is (0). Indien er geen plaats meer is in het betreffende vak, dan geeft de methode 0 terug; anders wordt het vaknummer waarin ze moeten plaatsnemen teruggegeven (1 of -1). Neutrale supporters moeten wachten om een vak toegewezen te krijgen tot de wedstrijd begint, tenwij er reeds voldoende supporters wijn om beide vakken volledig te vullen; in dat geval geeft de methode onmiddellijk 0 terug.}

• void startWedstrijd()

{De wedstrijd gaat beginnen. De neutrale supporters krijgen een vaknummer toegewezen. Eerst wordt het vak van de thuisploeg opgevuld, daarna het van van de bezoekende ploeg. De deuren worden gesloten. Niemand mag het stadium verlaten tot de wedstrijd afgelopen is. Er worden ook geen nieuwe supporters meer toegelaten.}

• void eindWedstrijd()

{De wedstrijd is gedaan. De deuren van het vak van de bezoekende ploeg worden geopend en deze supporters mogen het stadium verlaten.}

• void naar_buiten(int vak)

{Een supporter uit vak 'vak' (-1 of 1) wil naar buiten. Hij krijgt slechts toestemming als de betreffende deuren van zijn vak open staan. Merk op, bij het verlaten wordt geen rekening meer gehouden of een supporter neutraal is of niet. Hij/zij behoort tot de groep van het vak.}

• void buiten()

{Een supporter, die tevoren toelating gekregen had om zijn vak te verlaten, is buiten. Indien hij de laatste supporter van zijn vak is, dan worden de deuren van het andere vak opgezet en mogen deze supporters nu op hun beurt hun vak verlaten.}

Aan de volgende beperkingen moet steeds voldaan zijn:

• In elk vak is slechts plaats voor N supporters. N is een parameter die bij de creatie van de monitor wordt opgegeven. In het ganse stadium is dus plaats voor 2*N personen.
• Een supporter van de thuisploeg komt dus steeds terecht in vak 1; een supporter voor de bezoekende ploeg in van -1; een neutrale supporter mag zowel in vak 1 als in vak -1 terecht komen.
• De toewijzing van een vaknummer aan een neutrale supporter gebeurt pas op het ogenblik dat de wedstrijd begint (tenzij een vak of het ganse stadium reeds vol zou zitten).
• Zodra de wedstrijd begint, worden geen nieuwe supporters meer toegelaten.
• Niemand mag het stadium verlaten voor de wedstrijd gespeeld is.
• De supportersgroepen moeten gescheiden het stadium verlaten. Eerst wordt het vak van de supporters van de bezoekende ploeg leeggemaakt daarna dat van de supporters voor de thuisploeg.

Geef een implementatie d.m.v. een monitor. In plaats van een monitor te ontwerpen mag je ook een Java klasse schrijven waarbij je dan gebruik maakt van de synchronisatie-mechanismen van Java (je beschikt dan niet op conditievariabelen maar wel over synchronised methods, wait(), notify() en notifyAll()).