Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Verschmelzung
Hey,
in den Folien XII2/24 steht ja , unter welchen Bedingungen man buddy, first-fit und best/worst-fit-Verfahren verschmelzen kann. Jedoch ist der Code dazu sehr kryptisch und ich verstehe nicht ganz, was dieser aussagt (v.a. beim Buddy-Verfahren). Ein Kommilitone meinte, dass eine Bedingung für eine mögliche Verschmelzung beim Buddy-Verfahren wär, dass Buddy A xor Buddy B != 0 sein muss, was ja eig. sowieso der Fall ist… Was genau ist mit dem Paramter Size in dem Code beim first-fit gemeint? Was genau sind dann die Bedingungen für eine mögliche Verschmelzung der genannten Verfahren?
Danke!
Bei allen listenbasierten Verfahren (First-, Next-, Best-, Worst-Fit) kann man zwei Speicherbereiche immer dann verschmelzen, wenn sie direkt nebeneinander liegen. So weit, so simpel.
Beim Buddy-Verfahren ist es ein kleines bisschen komplizierter, denn dort muss jeder Freispeicherblock die beiden folgenden Eigenschaften erfüllen:
- Seine Größe ist eine Zweierpotenz.
- Seine Adresse (bzw. sein Abstand zum Beginn des verwalteten Gesamtspeicherbereichs) ist ein Vielfaches seiner Größe.
Zwei Blöcke dürfen nur dann miteinander verschmolzen werden, wenn der daraus resultierende Block wieder die beiden Eigenschaften erfüllt. In diesem Fall nennt man die beiden Blöcke Buddys - für jeden Block existiert genau ein potenzieller Buddy.
Eigenschaft 2 kann man effizient nachprüfen, indem man das XOR der beiden Adressen bildet. Wenn das Ergebnis Hamminggewicht 1 hat (d. h. in Binärdarstellung enthält es genau eine Eins und sonst lauter Nullen), dann ist die Eigenschaft erfüllt.