Besturingssystemen en geavanceerde systeemsoftware

Ga naar: navigatie, zoeken

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

Samenvattingen

Klik hier om de samenvattingen te bekijken

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 13:00

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()).

2008-01-16 14:00

Deel 1: Theorie

  1. Geef de verschillende technieken om deadlocks te vermijden/detecteren en op te lossen. Focus vooral op de voor- en nadelen van de verschillende methodes.
  2. Wat is copy on write ?
  3. Wat is een digipass (token device)? Waar wordt het gebruikt?
  4. Hard links en symbolic links. Wat is het verschil? Zijn ze beiden nodig?

Deel 2: Oefening: schrijf een monitor (of in Java)

Treintjes rijden van links naar rechts over een dubbel spoor, behalve in een vallei waar er maar 1 spoor is. Er moet dus gezorgd worden dat ze niet botsen. Het gaat traag, dus is het niet efficiënt om om de beurt 1 van elke kant te laten overrijden. Om ervoor te zorgen dat ze ook niet te lang moeten wachten, worden er na N (meegegeven bij het aanmaken van de monitor) treinen in dezelfde richting in die richting geen treinen meer toegelaten. Bij het veranderen van richting moeten de wissels veranderd worden (methode wissels() gegeven die je moet gebruiken) Bovendien is er ook een HST trein die het enkel spoor moet kruisen. Als deze HST eraan komt, mogen er geen treinen meer toegelaten worden op het enkel spoor. Zijn er nog treinen op het enkel spoor aan het rijden op het moment dat de HST aankomt, moet hij wachten tot het spoor leeg is alvorens over te steken.

Schrijf dus: - reserveer_HST() - vrijgeven_HST() - reserveer(richting) - vrijgeven()

Alle methoden staan nog eens mooi uitgelegd met wat erin moet gebeuren samen met alle voorwaarden op een rijtje.

Deel 3: Paper

Hoe gaat linux om met multiprocessoromgevingen?

2008-01-16 8:00

Deel 1: Theorie

  1. Op welke manieren kan geheugen gebruikt worden in processen. Bespreek vooral voor- en nadelen. Wat met de combinatie?
  2. Race conditions, waar, wie, hoe, ...
  3. Hoeveel schijftoegangen heb je bij Table of pointers minimaal en maximaal nodig om blok N van een file op te slaan.
  4. Beschrijf 2 phase locking. Waarom kan er deadlock ontstaan en wat doe je ermee?

Deel 2: Oefening

Wagentjes op verschillende verdiepen. Lift verplaatst wagentjes van verdiep naar verdiep. Lift kan er maar eentje bevatten.

methodes -> //karretje1 void van_naar(int van, int naar) { karretje meldt zich aan, als de lift vrij is maar op een ander verdiep staat roept het de lift, de methode returned wanneer het karretje binnen kan rijden } //karretje2 void binnen() {rijdt binnen en zet lift in gang} //karretje3 void buiten() {rijdt buiten, als er kar staat te wachten, rijdt die binnen, anders ga (cyclisch) naar het volgende verdiep waar er een karretje aan het wachten is} //opgeroepen door lift na methode 'verplaats(int aantalverdiepen)' die kar verplaatst (en niet geimplementeerd moet worden) void op_bestemming(){als kar vol zit, laat kar leeg, anders laat kar binnen}

Deel 3: Paper

Hij vond em niet super en vroeg hoe linux omgaat met interactieve processen.

2008-01-15 13:00

Deel 1: Theorie

(50 minuten tijd, en gene minuut langer + daarna mondeling 'verdedigen')

  1. Vraag 1. Op welke manieren kan een bestand opgeslagen zijn op een harde schijf? Kan het nuttig zijn meer dan één allocatiemethode te gebruiken?
  2. Vraag 2. Leg uit: klok algoritme. Waarvoor dient de tweede wijzer?
  3. Vraag 3. Wat is een buffer overloop aanval en hoe kan je je daartegen beschermen?
    Tip: voor diegenen die denken, wtf is da (incl mezelf), der staat iet van op slide 80 bij intrusion detection methods (hoofdstuk protection&sec)
  4. Vraag 4. Gegeven: 2 processen, gelijk op slide 40 van hoofdstuk 18. Gevraagd: teken zo een schema (gelijk slide 42), treedt er deadlock op? Zoja, waar juist? blabla

Deel 2: Oefening

(ongeveer op 30 minuten op te lossen + daarna mondeling 'verdedigen')

Implementeer een monitor (mag ook javaklasses zijn, met threads en notifyAll() enzo, tis hoe ge zelf wilt), die een tafel in een kantine automatiseert. Een tafel heeft één robot (=ober) en een maximaal aantal stoelen (die bij het aanmaken van de monitor wordt meegegeven). De klanten zijn hoffelijk en mogen niet aan een tafel gaan zitten als er iemand aan het eten is (en ook niet als de tafel volzet is natuurlijk), mogen niet beginnen eten alsvorens iedereen bediend is en mogen de tafel niet verlaten alvorens iedereen heeft gedaan met eten.

De methodes zijn: a. wacht_op_vrijeplaats_aan_tafel() {De klant wacht een stoel af aan tafel. Als er mensen aan het eten zijn of de tafel zit vol, wacht dan. De methode keert pas terug als de klant aan tafel mag gaan zitten} b. bestel_schotel() {De klant geeft aan dat hij wil bestellen en moet hiervoor desnoods de ober wakker maken. Als hij bedient is, moet hij wachten tot de rest van zijn tafelgenoten bediend is, pas dan mag iedereen beginnen eten en keert de methode terug} c. verlaat_tafel() {De klant wil de tafel verlaten, maar moet wachten tot iedereen gedaan heeft met eten} d. wacht_op_bestelling() {De ober wacht op een bestelling} e. opgediend() {De ober geeft aan dat hij de bestelling heeft opgediend. Als iedereen van de tafel is bediend, geeft hij aan dat ze mogen beginnen eten}

De code die de klant uitvoert: ... wacht_op_vrijeplaats_aan_tafel() ... ... //gaat aan tafel zitten ... bestel_schotel() ... ... //eet zijn bord leeg ... verlaat_tafel()

De code die de ober uitvoert: while(true){ ...wacht_op_bestelling()... ...//maakt eten klaar en bedient ...opgediend() }

Voor diegenen die twijfelen, dit alles (en zelfs nog veel gedetailleerder) is wel degelijk gegeven:)

Deel 3: Paper

(mondeling, onvoorbereid)

heel klein vraagje over de paper zelf + persoonlijke mening (vond je het werkje leuk?:p)

Succes dermee

2008-01-17 13:00

Deel 1: Theorie

  1. Waarom moet een software-ontwikkelaar op de hoogte zijn van het werkingsmechanisme van threads binnen een bepaald OS? (user threads, kernel threads)
  2. Voor het vervangen van pages in het geheugen wordt het klokalgoritme gebruikt. Welk principe tracht dit algoritme te realiseren? Soms wordt een tweede wijzer toegevoegd aan dit algoritme, waarvoor dient deze?
  3. Vraag over safe states: je vetrekt uit een safe state, één van de volgende acties treden op, is de volgende toestand steeds veilig, soms veilig of nooit veilig?
  • een hulpmiddel wordt vrijgegeven
  • een hulpmiddel wordt aan een proces toegewezen
  • het OS geeft signaal om een vrijgekomen hulpmiddel toch niet toe te wijzen
  • ? (weet ik niet meer)
  1. maak een overzicht van de gelijkenissen en verschillen tussen semaforen en conditievariabelen. Betrek ook hun operaties in de vergelijking.

Deel 2: Oefening

Ontwerp een monitor die het volgende systeem regelt:

Een loods wordt geautomatiseerd, verschillende robots worden gebruikt om een rek te vullen. Robots kunnen objecten toevoegen aan het rek en er objecten uit halen. Er mogen enkel objecten toegevoegd worden als er minder dan MAX objecten in het rek zitten, er mogen enkel objecten uit het rek gehaald worden als er meer dan MIN objecten zich in het rek bevinden.

Is je oplossing deadlock/starvation-vrij?

2007-01-16 13:00

Deel 2: Oefening

huwelijksbureau of dating

De eerste die zich aanmeldt mag tussen de volgende twee die zich aanmelden van het andere geslacht kiezen. Andere mensen die zich aanmelden moeten wachten. De eerste maakt zijn keuze zodra er twee van het andere geslacht zijn. Die drie mensen doen daarna niet meer mee. De andere komen nadien aan de beurt op dezelfde manier.

De methode public boolean aanmelden(boolean isVrouw, Profiel info, Object Deelnemer) moet geïmplementeerd worden. Diegene die kiest zal zijn info niet nodig hebben, enkel het object deelnemer voor de methode kies uit te voeren. De methode kies moet niet geimplementeerd worden.

Int keuze = Deelnemer.kies(info1, info2) Keuze is dan 1 of 2.

Zo kan de eerste persoon kiezen tussen de twee andere. Van de twee kandidaten waartussen gekozen wordt, is het object deelnemer niet belangrijk, enkel de info zodat de eerste persoon kan kiezen. De methode geeft true terug voor de eerste persoon en voor diegene die hij gekozen heeft. False voor de persoon die niet gekozen is.

Is er deadlock of starvation mogelijk?

2000-01-01

Deel 1: Theorie

  1. Vraag 1: Waarom moeten WAIT en SIGNAL methodes op events atomisch zijn? bijvraag: hoe zou dit kunnen gedaan worden?
  2. Vraag 2: copy on write: hoe, wat waar?
  3. Vraag 3: ACL vs Capability: vergelijk. bijvraag: hoe zou ge capability kunnen beschermen?
  4. Vraag 4: Leg uit: token = digipass. Voordelen (bv tov wachtwoord)/nadelen?
  5. Vraag 5: stukje code voor 2 processen met semaforen etc...

Welk probleem kan er zich voordoen (deadlock dus) en hoe zou ge dit oplossen met een minimale aanpassing aan de code.

Deel 2: Synch oef op te lossen met monitor of java (syncronized, notify etc). Vergelijkbaar met de laatste oefz over monitors.

En dan nog een klein vraagje over paper.