LRU-Algorithmus (und FIFO)

[Ma Z. (Gast)]

Hallo,

ich habe eine Aufgabe zu Memory Management:
"Ein Programm habe folgenden Referenzfolgen auf virtuellen 
Speicherzellen:
1,2,3,4,5,6,7,4,5,6,7,4,5,6,7,8,9. Anfangs sei der Speicher leer, es 
wird demand paging eingesetzt.
Geben Sie die sortierte Speicherbelegung und die Anzahl der 
aufgetretenen Seitenfehler bei Verwendung des LRU-Algorithmus für m=1 
bis m9 an."

Kann mir jemand mit der Aufgabe helfen? Ich habe es mir 2x erklären 
lassen und hab mir paar Videos angeschaut, trotzdem bekomme ich es nicht 
hin diese Aufgabe zu lösen. Bis m=3 komme ich allein, ich glaube bis 
dahin ist es einfach. Ab m=4 hört es bei mir auf.

[C. A. Rotwang (Gast)]

Ma Z. schrieb:

> "Ein Programm habe folgenden Referenzfolgen auf virtuellen
> Speicherzellen:
> 1,2,3,4,5,6,7,4,5,6,7,4,5,6,7,8,9. Anfangs sei der Speicher leer, es
> wird demand paging eingesetzt.
> Geben Sie die sortierte Speicherbelegung und die Anzahl der
> aufgetretenen Seitenfehler bei Verwendung des LRU-Algorithmus für m=1
> bis m9 an."


Schreib dir doch nen simulator, das sollten nicht mehr als 20 Zeilen 
C-Code sein.

[Ma Z. (Gast)]

ich programmiere nicht gern und wüsste auf anhieb auch nicht wie es 
gehen sollte in c. Ich würde mehr zeit in programmieren verschwenden als 
in verstehen :D

[Carl D. (jcw2)]

Ma Z. schrieb:
> ich programmiere nicht gern und wüsste auf anhieb auch nicht wie es
> gehen sollte in c. Ich würde mehr zeit in programmieren verschwenden als
> in verstehen :D

Dann such dir ein anderes Studienfach.

[Wegstaben V. (wegstabenverbuchsler)]

Ma Z. schrieb:
> ich programmiere nicht gern und wüsste auf anhieb auch nicht wie es
> gehen sollte in c. Ich würde mehr zeit in programmieren verschwenden als
> in verstehen

Du mußt den Algorithmus auch nich in C formulieren. Zur Not kannst du es 
auch in hochdeutsch oder deinen regionalen Sprachdialekt beschreiben.

Aber das allgemeine Verfahren, den Algorithmus, den mußt du schon 
verstanden haben. Und dann klapperst du den Ablauf einfach "im Kopf" 
durch.
https://de.wikipedia.org/wiki/Least_recently_used
https://en.wikipedia.org/wiki/Cache_replacement_policies#Least_Recently_Used_.28LRU.29

ps: Für Sortieralgorithmen gibts auch noch diese Hilfe:
http://icancode.de/2670/getanzte-sortieralgorithmen
du kannst ja dort mal anfragen, ob sie dir einen LRU vortanzen ;-)

[C. A. Rotwang (Gast)]

Ma Z. schrieb:
> ich programmiere nicht gern und wüsste auf anhieb auch nicht wie es
> gehen sollte in c. Ich würde mehr zeit in programmieren verschwenden als
> in verstehen :D

Such mal mit google nach "Pseudo code LRU", beispielsweise dort: 
http://dblab.usc.edu/csci485/LRU-K485.ppt

[Jay (Gast)]

Wegstaben V. schrieb:

> https://en.wikipedia.org/wiki/Cache_replacement_po...

Zugegeben ich kenne mich nicht mit der Materie NULL aus, aber der Name 
suggeriert, dass der "älteste" - bzw. der am längsten nicht benutzte 
Wert überschrieben wird.

Sollte das Wiki Beispiel statt:
A(0) B(1) C(2) D(3)
->
A(0) B(1) C(2) E(4)
nicht so aussehen:
E(4) B(1) C(2) D(3)

???

Das würde auch eher zu den nachfolgenden Zeilen passen.

CU,
Jay