2005 / Vraag 9

[Pieter]

Toch nog maar eens proberen:
Weet iemand hoe je vraag 9 (berekenen van geheugengebruik) van examen 2005 oplost?

[maxime]

ja kzou da eig ook wel is duidelijk wille weten...

[wim]

Speciaal voor de laat-avond-studenten zal ik het ook eens proberen uit te leggen (gebaseerd op de uitleg van Tibi).
Verbeteringen zijn altijd welkom.

Hij zegt in zijn vraag dat een adres en een CARDINAL elk 4 bytes groot zijn. Op de volgende manier bereken je dan het geheugen nodig voor de verschillende procedures:

Search:
Return address, static & dynamic links: 3 * 4 bytes (dit zijn 3 adressen die moeten bijgehouden worden)
VAR parameter: 4 bytes (een VAR parameter is ook een adres)
CARDINAL parameter: 4 bytes
CARDINAL terugkeerwaarde: 4 bytes
2 lokale variabelen Min en Max: 2 * 4 bytes
TOTAAL: 32 bytes

Src:
Return address, static & dynamic links: 3 * 4 bytes
2 CARDINAL parameters: 2 x 4 bytes
TOTAAL: 20 bytes

Het gaat hier om het binary search algoritme, waarvan er gezegd is dat die log2(n) keer Src aanroept. n is hier 1000000.
Het totaal aantal bytes nodig voor het aanroepen van Search is dus:
32 + 20 * log2(1000000) bytes
= 32 + 20 * log2(10^6)
= 32 + 120 * log2(10)
= 32 + 120 * 4 (<- eerste gehele getal groter dan log2(10) )
= 512 bytes

Eigenlijk is dit het aantal extra bytes nodig voor de aanroep van Search.
Bij de grootte van het beschikbare geheugen dat nodig is om dit programma te draaien moet dan nog dat van de module Test10 geteld worden. In de vraag staat dat de module Test10 gezien mag worden als een procedure en heeft dus deze hoeveelheid geheugen nodig:

Test10:
Return address, static & dynamic links: 3 * 4 bytes
ARRAY[0..1000000] OF CARDINAL: 1000001 x 4 bytes (vergeet de 0 niet)
2 CARDINALs: 2 x 4 bytes
TOTAAL: 4000024 bytes

TOTAAL van het TOTAAL:
4000024 + 512 = 4000536 bytes

Eerlijk gezegd ben ik het niet eens met deze berekening, want ik heb nog geen enkel besturingssysteem gezien waar programma's zo in het geheugen staan, maar ik zal toch maar meedoen met wat onze professor zegt

[Pieter]

Heel hard bedankt:)

[maxime]

stomme vraag mss ma vanwaar die 3*4 int begin?

[Simen]

3*4 is standaard voor een procedure.
De drie impliceert de adressen die de procedure nodig heeft, de 4 komt van het aantal bytes 1 adres inneemt (uit het gegeven).

[Ruben]

Nooit gedacht dat ik die vraag zou snappen, bedankt wim.
Ruben

[Aushim]

Ik heb twee vragen, hopelijk kan iemand nog antwoorden...

Waarom is het aantal lokale variabelen 2 en niet 3 (min, max en m)?
Van waar kom die CARDINAL terugkeerwaarde?

EDIT: Oups, ik denk dat m je CARDINAL terugkeerwaarde is, niet waar?

[wim]

Sorry, het maakt inderdaad weeral niet meer uit, maar voor alle duidelijkheid: ik had de variabele m niet gezien Het totaal aantal lokale variabelen is dus 3. De CARDINAL terugkeerwaarde is de waarde die de functie Search op het einde geeft bij de RETURN.
Hopelijk hebben zij die dit topic hebben gelezen hun vraag op het examen goed beantwoord

[Tom V]

Hopelijk hebben zij die dit topic hebben gelezen hun vraag op het examen goed beantwoord

Ik hoop alleszins dat gij die vraag op uw examen goed hebt beantwoord