Hi Leute!
Ich hab hier eine kleine Übung zum FIFO- bzw.
LRU-Page-Replacement-Algorithm. Ich bin mir nicht ganz sicher, ob das
stimmt was ich da zusammengemacht habe! Vielleicht könnte jemand von
euch mit etwas mehr Ahnung kurz drüber schaun?
Hier die Aufgabe:
Die Hauptspeicheraufteilung erfolgt in 4 Frames.
Das ist der Referenzstring auf den der Algorithmus ausgeführt werden
soll:
1
1234534167878978954542
Meine Lösung zur Aufgabe (FIFO) sieht so aus:
1
11115xx5558xx8xxx88xx2
2
2222xx1111xx9xxx99xx9
3
333xx3666xx6xxx55xx5
4
44xx4477xx7xxx74xx4
Meine Lösung zur Aufgabe (LRU) sieht so aus:
1
11115xx5558xx8xxx88xx2
2
2222xx1111xx9xxx99xx9
3
333xx3666xx6xxx55xx5
4
44xx4477xx7xxx74xx4
Da wo ich "x" geschrieben habe, kam ein Wert der schon in einem Frame
drin war...
Was mich nun an meiner Lösung stört, ist die Tatsache, dass ich bei
beiden Algorithmen auf das gleiche Ergebnis komme! Kann das sein?
Würd mich freun wenn ich Antworten dazu bekommen würde!
Danke!
Hans Wurst schrieb:> beiden Algorithmen auf das gleiche Ergebnis komme! Kann das sein?
Das kann schon sein.
Ich finde allerdings deine Darstellung nicht besonders übersichtlich,
daher hab ich nicht versucht nachzuvollziehen, ob du irgendwo einen
Fehler gemacht hast.
In deiner Darstellung sieht man nicht
FIFO welcher ist denn derjenige der als nächstes rausfliegt
LRU welcher ist den derjenige, der am wenigsten oft benutzt wurde
FIFO würde ich so darstellen (wieder deine Sequenz)
1
1234534167878978954542
2
3
1: 1 x x x ( x steht für uninteressant )
4
2: 2 1 x x
5
3: 3 2 1 x
6
4: 4 3 2 1 ( 1 ist als erster ins Set gekommen und fliegt als daher als erster raus
7
5: 5 4 3 2
8
3: 5 4 3 2 ( 3 ist schon im Set, keine Aktion erforderlich)
9
4: 5 4 3 2
10
1: 1 5 4 3
11
6: 6 1 5 4
12
....
während ich bei LRU im Prinzip dasselbe mache, nur dass ich, wenn eine
Page angefordert wird, die schon im Set ist, diese an die erste Stelle
hole. Die Page ganz rechts ist daher die, die schon am längsten nicht
benutzt wurde.
1
1234534167878978954542
2
3
1: 1 x x x
4
2: 2 1 x x
5
3: 3 2 1 x
6
4: 4 3 2 1
7
5: 5 4 3 2
8
3: 3 5 4 2
9
4: 4 3 5 2
10
1: 1 4 3 5
11
6: 6 1 4 3
12
....
(und jetzt sieht man auch, dass es einen Unterschied gibt)
Hm, ok soweit.
Mal eine grundsätzliche Frage. Ist FIFO das gleiche wie FCFS?
First Come - First Served
Müsste wohl so sein. Das ist beides das Warteschlangenprinzip. Wer sich
zuerst anstellt, kommt als erster drann. Und wenn das 'erster drann' nur
datin besteht, dass er als erster wieder bei der Tür rausfliegt.
Gut. Ich hab mir jetzt deine Lösung nochmals angeschaut und muss sagen
mir leuchtet deine Lösung auch viel eher ein!
Aber:
In meinen Vorlesungsfolien hab ich dieses Beispiel drin. Das Beispiel
siehst du an dem Bild welche als Anhang dabei ist. Nach diesem Beispiel
hab ich dann auch meinen Referenzstring vom Eröffnungspost lösen wollen.
Es ist zwar jetzt leider ein anderer String, aber wenn ich den String
aus dem Bild im Anhang mit deiner Methode lösen will, komm ich (leider)
auf ganz andere Ergebnisse, als das, was in dem Bild gezeigt wird!
Wie kommt das jetzt? Welche Methode ist nun richtig?
Hans Wurst schrieb:> Es ist zwar jetzt leider ein anderer String, aber wenn ich den String> aus dem Bild im Anhang mit deiner Methode lösen will, komm ich (leider)> auf ganz andere Ergebnisse, als das, was in dem Bild gezeigt wird!
Wieso? Passt doch.
Die Reihenfolge der Pages im Set spielt ja keine Rolle. Darum spricht
man ja auch vom Page "Set" (Set = ungeordnete Menge)
Edit:
Jetzt hab ich dich. In deiner Zeichnung werden die Kästchen auch gleich
als reale Page-Frames aufgefasst. OK. So gesehen muss man das dann so
machen, auch wenn ich es nach wie vor unübersichtlich finde, weil man
sich merken muss, in welchem Kästchen jetzt gerade das Ende der FIFO
liegt. Für einen COmputer kein Problem, aber für einen Menschen (mit
schwachem Gedächtnis, so wie ich) schon.
Ok. Jetzt glaub ich sprechen wir vom Selben...
Ich muss es also dennoch so machen wie ich es "rausgefunden" habe. Denn:
Zum "Algorithmus" als solchen schweigen sich diese dummen Folien nämlich
schön brav aus. Da muss man dann hergehen und den tieferen Sinn selber
finden :-(
-> Könntest du dann vielleicht meine zwei Beispiele die ich Eingangs
gezeigt habe nochmals durchschaun und sagen ob das so passt? Das wäre
sehr nett!
Dann hab ich gleich noch eine Frage:
Ich soll dann laut Aufgabe auch noch angeben, was die minimal mögliche
Anzahl von Pagefaults bei dieser Hauptspeicheraufteilung von 4 Frames
ist.
Was ein Pagefault ist weiß ich soweit. Bspw.: Ein Pogramm will auf einen
Speicherbereich zugreifen, der sich aber im Moment nicht im
Hauptspeicher befindet, sondern ausgelagert wurde. Bspw. auf die HDD.
Wie lege ich dieses Wissen nun auf diese Aufgabe um?
EDIT: Schwaches Gedächtnis? Das hab ich auch. Vielleicht hilft es dir
auch, wenn du beim Referenzstring einen Zeiger mitgehen lässt. So weißt
du immer welches Element das nächste ist. Also mir hat's ein bisschen
geholfen :-)
Hans Wurst schrieb:> Ok. Jetzt glaub ich sprechen wir vom Selben...>> Ich muss es also dennoch so machen wie ich es "rausgefunden" habe. Denn:> Zum "Algorithmus" als solchen schweigen sich diese dummen Folien nämlich> schön brav aus. Da muss man dann hergehen und den tieferen Sinn selber> finden :-(
Ich würde es parallel mit beiden Systemen machen. Bei einer Klausur wäre
mir nämlich das Risiko zu groß, da einen blöden Fehler heinzuhauen
Beim letzten Beispiel - FIFO
Request Set Pages
7 7 x x 7 x x
0 0 7 x 7 0 x
1 1 0 7 7 0 1
2 2 1 0 2 0 1
0 2 1 0 2 0 1
3 3 2 1 2 3 1
0 0 3 2 2 3 0
4 4 0 3 4 3 0
2 2 4 0 4 2 0
....
die neue Anforderung kommt links an das Set ran, dafür fällt rechts
einer weg. Der der wegfällt, den such ich mir in den Pages und schreib
dort die neue Page rein. Am Beispiel: in deiner Folie geht es weiter mit
einem Request der Page 3
3
die kommt im Set links drann
3 3 2 4 0
dafür fällt die 0 raus
3 3 2 4
und in den Pages wird daher die vorhergehende Page mit der 0 durch die
Page 3 ersetzt
3 3 2 4 4 2 3
Und mit dem LRU mach ichs genauso. Nur dort ist es sogar noch wichtiger,
weil ich ja über die Reihenfolge Buch führen muss, welche Page am
längsten nicht benutzt wurde. Mit so einem Hilfskonstrukt des Sets geht
das ganz einfach.
Hallo! Ich bin's nochmal.
Kannst du mir vielleicht eine Übersicht der realen page frame Verteilung
des Strings
1
1234534167878978954542
mit dem LRU-Algo. machen?
Ich glaub ich hab den Algo. an sich noch nicht verstanden! Ich komme da
immer noch auf die exakt gleiche Verteilung wie beim FIFO Algo...
LRU heißt least recentliy used. Das bedeutet auf deutsch: am längsten
nicht verwendet.
Beispiel:
1
1234534167878978954542
1
1111
2
222
3
33
4
4
Soweit ist das ja noch klar. Aber wie gehts jetzt weiter? Ich muss ja
jetzt die 5 anschaun. Welches dieser Elemente im page frame ist das "am
längsten nicht verwendete" Element?
Das wäre sehr nett!
Hans Wurst schrieb:> Hallo! Ich bin's nochmal.>> Kannst du mir vielleicht eine Übersicht der realen page frame Verteilung> des Strings
1
1234534167878978954542
mit dem LRU-Algo.
> machen?> LRU heißt least recentliy used. Das bedeutet auf deutsch: am längsten> nicht verwendet.
Genau
>
1
1234534167878978954542
>>
1
> 1111
2
> 222
3
> 33
4
> 4
5
>
> Soweit ist das ja noch klar. Aber wie gehts jetzt weiter? Ich muss ja> jetzt die 5 anschaun. Welches dieser Elemente im page frame ist das "am> längsten nicht verwendete" Element?
Und genau aus dem Grund habe ich oben diese Zusatzinfo benutzt.
Der aktuell benutzte kommt immer links drann.
1 1
2 1 1 2
3 2 1 1 2 3
4 3 2 1 1 2 3 4
jetzt kommt 5 links drann.
5 4 3 2 1 1 2 3 4
Offensichtlich ist dann das Element am rechten Rand das am längsten
nicht benutzte. Also 1. Die Page 1 wird durch die Page 5 ersetzt
5 4 3 2 5 2 3 4
Page 3 wird angefordert. Page 3 ist schon im Set. Ich schieb sie nur an
den linken Rand um damit zu dokumentieren: Egal was vorher war, 3 ist
die aktuell jüngste im Set.
3 5 4 2 5 2 3 4
Page 4 wird angefordert. Wieder: Um zu doumentieren, dass 4 die jüngste
ist, schiebe ich sie an den linken Rand in meinem Set
4 3 5 2 5 2 3 4
(und sehe gleichzeitig auch, dass jetzt 2 die älteste Page ist). Denn
jetzt kommt die Anforderung nach Page 1
1 4 3 5 2
welche die Page 2 rausschiesst (weil es die älteste ist) und daher wird
Page 2 durch Page 1 ersetzt
1 4 3 5 5 1 3 4
Alles eine reine Frage der Organisation. In diesem Fall lautet die
Frage: wie kann ich mir ein Hilfskonstrukt machen, mit dem ich leicht
feststellen kann, welches die jeweils älteste Page ist. Der linke Teil
meiner Spalten ist also nichts anderes als eine Reihung der Pages nach
Alter, während der rechte Teil die logischen Pagenummern in den
physischen Pages anordnet.
Ich hab jetzt auch nochmal versucht den LRU Algo. mit deiner Set und
Pages Methode nachzuvollziehen. Leider ist das mir auch nicht so
gelungen. So weit bin ich gekommen:
1
Request Set Pages
2
1 1xxx 1xxx
3
2 21xx 12xx
4
3 321x 123x
5
4 4321 1234
6
5
Als nächste käme nun die 5. Welche Set-Stelle bzw. Page-Stelle muss ich
jetzt mit der 5 überschreiben? Und vor allem was ergibt dabei nun den
pagefault? Immer wenn eine Stelle überschrieben wird, oder?
Edit: Da hat sich wohl der Eintrag etwas überschnitten. Ich arbeite
jetzt erstmal deine letzte Antwort durch! Ich denke, dass ist genau das
was ich suche :-)
Hans Wurst schrieb:> Ich hab jetzt auch nochmal versucht den LRU Algo. mit deiner Set und> Pages Methode nachzuvollziehen. Leider ist das mir auch nicht so> gelungen. So weit bin ich gekommen:>>
1
> Request Set Pages
2
> 1 1xxx 1xxx
3
> 2 21xx 12xx
4
> 3 321x 123x
5
> 4 4321 1234
6
> 5
7
>
>> Als nächste käme nun die 5. Welche Set-Stelle bzw. Page-Stelle muss ich> jetzt mit der 5 überschreiben?
Siehe letztes Posting
> Und vor allem was ergibt dabei nun den> pagefault? Immer wenn eine Stelle überschrieben wird, oder?
Was ist denn ein Pagefault?
Wenn eine Page angefordert wird, die physisch nicht gemappt ist.
In deinem Schrieb ist das genau dann der Fall, wenn du in der rechten
Spalte etwas verändern musst. Denn die rechte Spalte sagt dir ja, wie
die Pages im Speicher liegen. Wenn du dort nichts verändern musst, hast
du auch keinen Pagefault.
Karl Heinz Buchegger schrieb:> feststellen kann, welches die jeweils älteste Page ist. Der linke Teil> meiner Spalten ist also nichts anderes als eine Reihung der Pages nach> Alter, während der rechte Teil die logischen Pagenummern in den> physischen Pages anordnet.
Die rechte Spalte ist das was du auf deinen Lösungszettel schreibst, die
linke Spalte ist das, was du auf einem Schmierzettel bei der
Beantwortung der Frage nebenher mitführst.
Und dein Dozent wird dich ob deines guten Gedächtnisses bewundern :-)
So, jetzt soll ich auf diesen gewohnten String noch den "optimal
Algorithm" anwenden. Also quasi den Algorithmus, der am wenigsten
Seitenfehler produziert. Dir schaut quasi in die Zukunft des Strings.
1
1234534167878978954542
Geht da deine Methode auch wieder? In meiner etwas unübersichtlicheren
Methode hab ich den "optimal Algorithmus" schon durchschaut. Aber wie
kann man das jetzt auf deine Methode übertragen bzw. gibt's da auch so
eine schöne Methode?
Thread beobachten
Seitenaufteilung abschalten