Tentamen A2 (deel b) 24-06-2004 Geef (liefst beknopte en heldere) motivatie bij je antwoorden; dus niet enkel ‘ja’ of ‘nee’ antwoorden, maar ook waarom. Geef van berekeningen niet alleen het eindresultaat, maar ook hoe je hieraan komt. Succes!
Vraag 1 (2 punten) Een virtual memory systeem gebruikt enkel segmentation, en geen paging. De maximale grootte van een segment is 16 Kbytes (=214 bytes). Virtuele adressen zijn 16-bits; de meest significante bits geven het segment nummer, en de minst significante bits de offset binnen het segment. Elk adres addresseert ´e´en byte. Stel de segment table voor een proces ziet er als volgt uit: segment nummer 0 1 2 3
P 1 0 0 1
M 0 0 1 0
lengte base 300 0 100 3000 900 2000 260 2000
Een M-bit 0 geeft aan dat een segment niet veranderd is, een P-bit 0 dat een segment niet aanwezig is in het hoofdgeheugen. Segmenten zijn 214 bytes, dus van de 16-bits virtuele adressen zijn 2 bits voor het seg-nr en 14 voor de offset a. Welk virtueel adres correspondeert met fysiek adres 2005 ? Fysiek adres 2005 ligt in segment 3, offset 5. (Segment 2 heeft weliswaar dezelfde base als segment 3, maar segment 2 is niet present.) niet in segment 2, want dat is niet present. Het bbh virtuele adres is dus 3 ∗ 21 2 + 5. b. Beschrijf precies wat er allemaal gebeurt bij de volgende operaties. (Zeg of de segment table verandert en zo ja hoe, op welke fysieke locatie wordt gelezen of geschreven, en wat er verder eventueel nog gebeurt.) (i) Een schrijf-opdracht naar virtueel adres 200 seg 0, offset 200 - seg 0 is aanwezig - schrijf 200 en set M bit (ii) Een lees-opdracht van virtueel adres 1224 seg 0, offset 1224 - maar 1224 is groter dan de lengte van segment 2 dus Segmentation fault (iii) Een lees-opdracht van virtueel adres 2148 seg 0, offset 2148 - idem
c. Hoe lang is een entry in de segment-table, als er 4 Mb (=222 bytes) fysiek geheugen is? 2 bits voor P en M + 14 bits voor lengte + 22 bits base = 38 bits. (De 2-bits segmentnr’s hoeven niet in de entries te staan.) Hoeveel bytes groot kan een segment-table maximaal zijn? 4 segmenten * 38 bits = 19 bytes
Vraag 2 (1 punt) Een I/O module voor een hard disk slaat bij het lezen van een sector van de disk de gelezen bytes op in een lokale buffer. Vervolgens, als de hele sector gelezen is, wordt de inhoud van deze buffer byte voor byte naar het hoofdgeheugen gekopieerd, zonder dat de CPU hier verder bij betrokken is. Er zijn dus 2 schrijfoperaties nodig voor elke gelezen byte, ´e´en in het lokale geheugen van de I/O module en ´e´en in het hoofdgeheugen. We gaan ervan uit dat allebei deze schrijfoperaties even lang duren. Iemand stelt voor om de gelezen bytes direct in het hoofdgeheugen weg te schrijven (door de I/O module, dus weer zonder dat de CPU hier verder bij betrokken is). Wat vind je van dit voorstel? Dit is een slecht voorstel, omdat de I/O module de bus veel langer bezet zou houden dan nu het geval is. Bij de huidige opzet hoeft bij het (trage) lezen van de disk enkel de lokale buffer gebruikt te worden, en hoeft enkel als dat klaar is de bus even gebruikt te worden om de lokale buffer (snel) naar main memory te kopi¨eren. Bij dit alternatief zou de I/O module tijdens het (trage) lezen van de disk telkens de bus moeten gebruiken, en dus de CPU in de weg zitten.
Vraag 3 (1.5 punt) a. Als een C programma crasht met een ‘segmentation fault’, kan het zijn dat dit eigenlijk het gevolg is van een page fault ? Nee, een page fault veroorzaakt enkel wat vertraging om een pagina van disk te halen. b. Is bounds checking – het nagaan of een berekend fysiek adres wel in de geheugenruimte van een proces ligt – eenvoudiger bij paging of bij segmentation? Of maakt dat niet uit? Bij paging is dit eenvoudiger: bij segmentation moeten er gekeken worden of de offset binnen het segment niet groter is dan de lengte van het segment, bij paging hoeft dat niet want een offset is altijd een vast aantal bits dat nooit groter dan de page-lengte kan zijn. c. Geeft paging betere memory protection dan segmentation, of andersom? Of maakt dat niet uit? Segmentation is beter omdat er verschillende protectie per segment kan zijn. 2
Vraag 4 (1.5 punten) Stel we hebben een paging systeem met pagina’s met lengte 200 bytes, en dat LRU (least recently used) als page replacement strategie gebruikt. We hebben een proces dat een 2-dimensionale byte array M bewerkt. In pagina 0 van dit proces, dwz. op virtuele adressen 0 t/m 199, bevindt zich de programmacode die deze array bewerkt. In de volgende pagina’s staat het array M. Het is een array met 100 bij 100 entries, waarbij M[0,0] op virtueel adres 200 staat, M[0,1] op virtueel adres 201, . . . M[0,99] op virtueel adres 299 staat, M[1,0] op virtueel adres 300 staat, etc. Het proces heeft drie frames ter beschikking, waarvan initieel het eerste frame de programmacode (dwz page 0) bevat, en de twee andere frames leeg zijn. a. Hoeveel page faults treden er op als het proces dan begint met het uitvoeren van de volgende repetitie for( i=0; i<100; i++) { for( j=0; j<100; j++) M[i,j] := 0 } ? 50 page faults, dwz. het aantal pages dat de array beslaat. b. Idem, maar voor for( j=0; j<100; j++) { for( i=0; i<100; i++) M[i,j] := 0 } ? 50*100 page faults, omdat voor elke slag vd. buitenste repititie alle pagina’s dat het array beslaat een keer nodig zijn.
3
Vraag 5 (2 punten) Een hard disk draait met 100 rotaties per seconde en heeft 25 sectors per track. De seek time, in milliseconden, is gegeven door de formule tseek = 5 + d/10 waar d de afstand in tracks is. a. Stel de lees/schrijf kop staat op track 0, en de disk krijgt een verzoek om 5 opeenvolgende sectors op track 100 te lezen. Even later krijgt de disk weer een verzoek om 5 (andere) sectors op track 100 te lezen (terwijl er in de tussentijd geen ander requests voor de disk waren). Wat is de totale verwachte tijd nodig om de leesopdrachten uit te voeren? seek time = 5 + 100/10 =15msec, verwacht rotational delay time = halve draai = 0.5 * 1/100 seconde = 5 msec, leestijd = 1/5 draai = 1-/5 = 2msec, dus totaal = 150 + 2* ( 5 + 2 ) = 29 msec. (of 34, als je ervanuit gaat dat voor het 2e request nog 5 + 0/10 seektime nodig is.) b. De disk controller wordt uitgebreid met een track buffer, dwz. geheugen om de inhoud van ´e´en hele track te cachen. Deze track buffer wordt als volgt gebruikt: Bij een lees-request gebruikt de controller de track buffer, als daar toevallig de goede track gecached is; dit kost geen tijd. Zoniet, dan zet de controller de kop naar de gevraagde track, en leest deze hele track naar de track buffer (dit kan zonder rotational delay, want de hele track wordt gelezen); daarna wordt de sector uit de buffer gelezen, wat weer geen tijd kost. Wat is nu de totale verwachte tijd om de leesopdrachten uit te voeren, voor hetzelfde scenario als hierboven? De lees/schrijf kop staat initieel weer op track 0. (dezelfde) seek time, 15 msec, + 1 rotatie , 1/100 sec = 15+10 = 25msec. c. Zijn er scenario’s denkbaar waarvoor de toevoeging van de track buffer de zaak langzamer maakt? Ja, als je telkens een klein stukje track van steeds verschillende sectors moet lezen. Zoja, denk je dat de toevoeging van de track buffer eigenlijk wel een goed idee was? Ogv. het lokaliteitsprincipe zou ik verwachten van wel.
4
Vraag 6 (2 punten) Voor deze vraag beschouwen we een UNIX-achtig file systeem met i-nodes. De wortel inode voor een file bevat 10 direct pointers, 1 singly indirect pointer en 1 double indirect pointer. Stel de blockgrootte is B en een blockpointer is 4 byte. Dus de single en double indirect blokken bevatten B/4 pointers. a. Definieer de interne fragmentatie als de ongebruikte ruimte in datablokken (oftewel gegevensblokken) plus de ongebruikte ruimte in indirect blokken. De interne fragmentatie bestaat dus uit ruimte in gealloceerde datablokken die (nog) niet wordt gebruikt om inhoud van het bestand op te slaan, en de ruimte in gealloceerde indirect blokken die (nog) niet wordt gebruikt om pointers in op te slaan. We laten de wortel i-node van de file buiten beschouwing. Bijvoorbeeld, als er in een datablock maar 1 byte gebruikt wordt voor de inhoud van de file, dan levert dat (B − 1) bytes interne fragmentatie op. Als er in een indirect block maar 1 pointer staat, levert dat (B − 4) bytes interne fragmentatie op. Wat is de maximum interne fragmentatie die kan optreden? De maximum interne fragmentatie treedt op als je net de eerste double indirect block nodig hebt. Hierin staat dan 1 pointer naar een indirect block, en hierin staat weer net 1 pointer naar een datablock, waarvan net 1 byte wordt gebruikt. De interne fragmentatie is dan (B-4) bytes in double indirect + (B-4) bytes in indirect blok + (B-1) in het datablock = 3B-9 bytes. Bij welke filegrootte treedt dit op? 10B+ (B/4)*B+1. De eerste 10 datablokken geven 10B bytes. Het singly indirect blok bevat B/4 pointers naar blokken van elk B bytes, dus dit geeft (B/4)*B bytes. Verder hebben we nog de ene byte die de double indirect nodig maakt. singly indirect block, dat B/4 pointers naar datablokken bevat. b. Stel we hebben een file van B 2 bytes. Als we deze file helemaal willen lezen, moeten we behalve B datablokken ook een paar indirect blokken lezen. Hoeveel? Ga er hierbij van uit dat B veel groter is dan 10. 5 (de wortel i-node niet meegerekend) De wortel i-node verwijst naar de eerste 10B bytes. Het singly indirect block verwijst naar de volgende (B/4) ∗ B = 0.25 ∗ B 2 bytes. Daarn moeten we dus nog het double indirect block lezen. We moeten de eerste 3 pointers daarin volgen; die wijzen weer naar singly indirect blocken die elk 0.25 ∗ B 2 bytes geven. Dus we moeten het singly indirect block, het double indirect block, en de eerste 3 singly indirect block waarin daar naar verwezen word lezen.
5
