Post#3 » Tue Aug 26, 2008 1:05 pm
Ik heb ze onlangs teruggevonden.
21/1/2008, namiddag:
Bij het beantwoorden van eventuele ja/nee vragen wordt steeds verwacht dat je ook een woordje uitleg voorziet.
- REAL-TIME SCHEDULING: Bespreek de werking vban het algoritme van Moore en Hodgson dat tracht het aantal taken dat zijn deadline niet haalt te minimaliseren. geef de exacte voorwaarden waaronder dit algoritme optimaal is.
- DEADLOCK PREVENTIE: Wanneer wordt de toestand van een systeem safe of unsafe genoemd? Wat impliceert dit met betrekking tot deadlocks? Hoe controleert het Banker's algoritme of een toestand safe is (wat is de complexiteit)? Hoe voorkomt het Banker's algoritme hiermee deadlocks?
- FILE SYSTEMEN: Welke allocatie methoden wordt er door de File Allocation Table (FAT) gebruikt? Welke voor- en nadelen biedt deze methode (voor onder andere de snelheid waarmee sequential en random kunnen plaatsvinden)? Welke vorm van free-space management vinden we bij de FAT terug?
Praktijk:
- Beschouw de cache simulator met de volgende functie, zoals gebruikt in het practicum:
Code: Select all
int acces_cache(unsigned long memoryAddress);
Stel dat we de grootte van de cache reeds hebben bepaald en dat we nu de associativiteit van de cache willen bepalen met de volgende code:Code: Select all
int associativity = 1;
access_cache(0);
while (access_cache(0)) {
access_cache(associativity * cache_size);
associativity *= 2;
}
return associativity / 2;
Veronderstel dat de cache reeds is gevuld met adressen ver boven de cachegrootte. In welke van de volgende 6 gevallen geeft deze code het juiste resultaat? Verklaar waarom (niet). In de gevallen dat de code het foute resultaat berekent, welk resultaat is dit dan?
<tabel met {LRU,FIFO} x {Direct mapped, 2-way associatief, 4-way associatief}>
- In het practicum "Scheduling" heb je het volgende probleem bekeken:
Veronderstel dat we N_1 jobs hebben met hard deadlines d_j (met hun gezamenlijke load kleiner dof gelijk aan 1). Daarnaast zijn er nog N_2 jobs met soft deadlines. Het overschrijden van een hard deadline is niet toegelaten, terwijl soft deadlines beperkt mogen overschreden worden.
Ontwerp nu een algoritme dat:
- Alle hard deadlines haalt.
- De maximale lateness van de soft deadlines minimaliseert, of nog max_{j\in N_2}(C_j - d_j) zo klein mogelijk maakt.
Het systeem laat preemption toe.
- Leg bondig je oplossing uit en leg uit hoe je tot die oplossing bent gekomen.
- Is je oplossing optimaal? Indien niet, hoe goed werkt ze dan wel?