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.
buddy-system
was ist denn der nutzen des buddy systems?
man hat ja durchaus sowohl externen als auch internen verschnitt…und lücken suchen muss man auch…
naja im skript steht “effizientes verfahren”, hängt sicher damit zusammen dass die hardware mit dem 2^n zueg gut klar kommt … oder so ähnlich 
Ja ich denke das auch
Wie merkt sich denn da das Betriebssystem welcher Speicher belegt und welcher frei ist?
Das kann man ja im Prinzip als Bitliste oder verkettete Liste realisieren .
IIRC hab ich irgendwo gelesen, dass für jede buddy-größe eine freispeicher
warteschlange zur verwaltung benutzt wird.
IIRC^2 auch, dass die operationen im buddy system O(1) sind.
hab leider noch keine wissensquelle im web gefunden …
Freispeicherverwaltung:
es gibt ein Feld mit Zeigern auf freie Bloecke der Groesse 1,2,4,8,16,32,… usw.
Bloecke gleicher Groesse sind dann einfach untereinander verkettet.
Damit findet man natuerlich extrem schnell einen freien Block der Groesse n.
Einfach auf die naechste 2er-Potenz 2^i aufrunden und im Freizeiger-Feld in Element
i den Zeiger nehmen. Ist das leer nimmt man den Block aus i+i, teilt ihn,
nimmt die eine Haelfte und traegt die andere in Freispeicher(i) ein.
Ist i+1 auch leer geht man halt noch eins weiter und teilt dann zweimal - usw.
Beim Freigeben eines Blocks muss man nachsehen ob die andere Haelfte davon (der Buddy)
auch zufaellig frei ist - wenn nein traegt man den Block einfach in die Freispeicherliste
ein, sonst verschmilzt man mit der anderen Haelfte und traegt den groesseren Block ein
(natuerlich rekursiv bis nix mehr verschmelzbar ist).
Problem hierbei: es ist extrem aufwaendig festzustellen ob der Buddy frei ist.
Loesung: fuer jede Blockgroesse eine Bitmap fuer freie Bloecke - dann findet man
sehr schnell raus ob der Buddy frei ist - Nachteil: fuer kleine Blockgroessen ist so eine
Bitmap ganz schoen gross.
Linux hat benutzt so ein Buddy-System um den physikalischen Speicher zu verwalten
(fuer schnelle DMA-Operationen braucht man oefters zusammenhaengenden phys.
Speicher - d.h. die Pages muessen nebeneinander liegen - das geht damit sehr
gut). Als Einheit benutzt man Pages (also ein Block der Groesse 1 = 1 Page)
Verschnittproblem: externer Verschnitt ist nicht dramatisch - das sind immer noch
ganze Pages. Die kann man immer brauchen.
Die Bitmaps werden damit nicht besonders gross (bei 2G Hauptspeicher
braucht man 32kByte fuer die Bitmap der 1-Page-Bloecke).
Interner Verschnitt: wenn jemand 65 pages anfordert bekommt er ein Teil von
128 Pages - das ist natuerlich schon schlimm. Linux hat deshalb noch einen
zweiten Speicherverwalter, der von so einem Block aus dem Buddy-System
nochmal Stueckchen separart vergeben kann (hat natuerlich wieder den Nachteil,
dass man so einen Block erst wieder frei bekommt, wenn alle Teile aus der
zweiten Speicherverwaltung freigegeben wurden. Wenn man aber z.B. solche
Teile immer nur fuer Speicheranforderungen des gleichen Prozesses hernimmt,
dann hat man nach dem exit des Prozesses auf einen Schlag wieder alles aufgeraeumt-
weiss aber nicht, ob Linux das so macht).
Was den Umgang mit 2er-Potenzen angeht: natuerlich macht das die Operationen sehr
effizient. Aufrunden auf die naechste 2er-Potenz, ermitteln des Index in die
Freispeicher-Felder und Bitlisten, usw.
- das alles geht natuerlich viel effizienter als mit krummen Zahlen.