Thema: Problem bei Physikalischer Speicherverwaltung (Bitmap)

[s137]

Hallo zusammen,

Bei der Programmierung der physikalischen Speicherverwaltung ( in Form einer Bitmap) für meinen Kernel, bin ich auf folgendes Problem gestoßen:

Wenn ich Speicher für ein Programm freigeben will, suche ich ja nach einem gesetzten Bit ( frei = 1 ) in der Bitmap, und gebe dann die Adresse zurück. Jedoch ist dass dann ja nur ein Speicherblock mit 4kB. Was wenn mein Programm mehr Speicher benötigt? Und wie kann ich herausfinden wieviel Speicher mein Programm überhaupt benötigt?

Schon mal vielen Dank im Vorraus
s137

[Svenska]

Wenn ein Programm sagt "ich will 4 MB Speicher", dann ist normalerweise eine Bibliothek dafür zuständig, diese 4 MB Speicher zu besorgen und sich zusätzlich zu merken, wieviel Speicher das für diesen Block war. Diese Bibliothek besorgt sich also diese 4 MB Speicher (und wahrscheinlich sogar etwas mehr für die Verwaltung) vom Kernel.

Im Kernel sitzt die virtuelle Speicherverwaltung, die dann 4+ MB Speicher finden muss und auch in den Prozess mappen muss, damit der auch Zugriff darauf hat. Dazu benutzt sie wiederum die physikalische Speicherverwaltung, indem sie genug einzelne Pages (die normalerweise nicht zusammenhängen müssen!) anfordert und zu einem großen virtuellen Block zusammenschweißt.

Deine physikalische Speicherverwaltung weiß davon nichts. Die sieht im Zweifelsfall nur über tausend einzelne Anfragen vom Typ "gib mir eine freie Page, egal welche" und kann das nicht mehr zu irgendwelchen Blöcken zuordnen.

[s137]

ah ok, ich denke ich habs verstanden, vielen Dank d.h. ich brauche auch noch eine Virtuelle Speicherverwaltung die dann über die Physikalische Speicherverwaltung mir den Speicher freigibt. Aber für einen ersten Test mit einem kleinen Programm sollte die Physikalische Speicherverwaltung ja ausreichen.

[Svenska]

Du kannst deiner physischen Speicherverwaltung (nicht physikalische, aber ich mach' den Fehler auch immer mal wieder...) auch beibringen, mehrere aufeinanderfolgende Seiten zu besorgen. Auf dem PC ist das für das Diskettenlaufwerk noch halbwegs sinnvoll, sonst braucht man das aber eigentlich nicht mehr. (Außerhalb der Welt von x86 ist das noch anders.)

[s137]

Oh, ich werds mir merken für die Zukunft^^
Naja wenn ich schonmal anfange dann schon gescheit ^^ Also mit virtueller Speicherverwaltung.. aber jetzt muss ich erstmal die physische hinkriegen^^

[s137]

Ich hab jetz noch konkrete Probleme, bei der Funktion die mir Speicher freigibt. Diese gibt ja eine Adresse zurück, allerdings weiß ich zwar bis jetzt wie ich diese Adresse berechne habe allerdings keine Ahnung wie also in welchem konkreten Format ich diese Adresse zurückgebe also welcher Datentyp.
Soll ich die Adresse noch irgendiwe vorher in Hex umwalndeln?

Das ist bis jetzt der Code meiner Funktion (hab jetzt einfach mal unsigned char* als Datentyp gewählt kann das stimmen? eigtl müsste das doch zu klein sein oder?)

Code: [Auswählen]

unsigned char* pmm_alloc()
{

unsigned char x = 0;
unsigned char flag = 1;
unsigned char* addr;
long i;

for(i=0, i<=32768, i++)
{

  while (x<=31) {

    if (bitmap[i] & flag ) == 1 {

     addr = i*(31*4096) + x*4 // Rueckgabe der Adresse in Bytes

     pmm_mark_used(addr);

     return addr;
     }

     x++;
     flag = (flag << x);

  }

}

return addr;

}

Schonmal Vielen Dank im Vorraus
s137

[Jidder]

Mal eine Gegenfrage: Mit welcher Programmiersprache bist du denn sonst so unterwegs? Könntest du darin eine Funktion schreiben, die in einem Array bestimmter Größe den Index eines Eintrags zurückliefert, der ungleich Null ist? Und könntest du eine weitere Funktion schreiben, die in einem Integer den Index des niedrigsten gesetzten Bits findet? (Darfst sogar annehmen, dass dieser Integer ungleich 0 ist. Kann man ja später mit der ersten Funktion kombinieren.)

Mein Vorschlag wäre, erstmal diese beiden Funktionen (am besten in der dir vertrauten Sprache) zu schreiben und - ganz wichtig - gründlich zu testen. (Randbedingungen/Grenzfälle überlegen!) Es muss (sollte am besten sogar) nicht in deinem OS sein, sondern einfach in einem ganz normalen kleinen Testprogramm unter Linux/Windows/etc. Dann findest du sicherlich selbst viele Probleme, die in dem geposteten Codeschnipsel bestehen. Das ist zumindest meine Hoffnung.

[s137]

Java  sollte machbar sein^^

ich probiers auf jedenfall mal aus.. danke für den Tipp^^

[Jidder]

Das ist perfekt. Für diese Zwecke ist sie C ähnlich genug.

[s137]

ok wie gesagt werds mal versuchen^^

[s137]

Also ich hab des erste jetzt mal versucht in Java zu implementieren:

Ist das so wie du das gemeint hast?:

Code: [Auswählen]

public class MainClass {

public static void main(String[] args) {

        long[] testarr = {0,0,0,3,4,5,0,3,0};

        int index = indexArrayValNotNull(testarr);

        System.out.println(index);
 
}


// Array Eintrag ungleich null?
public static int indexArrayValNotNull(long[] array) {

int i;

for (i=0; i<= array.length; i++)
{
if (array[i] != 0) { return i; }
}

return -1;
}

}


Bei dem 2. bin ich mir allerdings nicht sicher wie ich das hinkriege dass ich das niedrigste gesetzte Bit in einem Integer finde.

Viele Grüße
s137

[Jidder]

Ist das so wie du das gemeint hast?

Jep, genau sowas. Einen Bug sehe ich da allerdings noch. Der macht sich zwar nur in einem der Grenzfälle bemerkbar, aber ein Auge für sowas zu entwickeln, ist nie schlecht. Was passiert wenn, du

Code: [Auswählen]

long[] testarr = {0,0,0,0,0,0,0,0,0}; /* die anzahl nullen ist egal */verwendest? Und wie korrigiert man das? Auf Grund der Uhrzeit¹⁾ entschließe ich mich mal, das als Rätsel zu formulieren. Falls du nicht auf die Lösung kommst, geht die Schnitzeljagd hier los: http://pastebin.com/JdPGFGn1

Die Entdeckung solcher Probleme meinte ich übrigens mit "gründlich Testen". Andere Testfälle, wären beispielsweise noch ein leeres Array, oder ein Array mit 0xfffffffff belegt. Einfach mal gucken, ob die Funktion, da dann auch das tut, was sie soll, auch wenn es ggf. nur eine Fehlermeldung (oder Rückgabewert -1) ist.

Bei dem 2. bin ich mir allerdings nicht sicher wie ich das hinkriege dass ich das niedrigste gesetzte Bit in einem Integer finde.

Das ist schwer zu erklären ohne gleich den Code zu servieren, deswegen hier mal eine einfache Implementierung:

   

Code: [Auswählen]

private static int bitscanforward(int x) {
int i;

for (i = 0; i < 32; i++) {
if ((x & (1 << i)) != 0)
return i;
}

/* ups gar kein bit war gesetzt */
return -1;
}
Ein (32-Bit-)Integer hat 32 Bits. Deswegen habe ich da eine Schleife, die von 0 bis 31 läuft. Der Wert von 1 << i ist mathematisch gesehen 2^i und ist in Binärdarstellung eine Zahl, die genau ein Bit auf 1 gesetzt hat (nämlich das i-te) und alle anderen sind 0. Das heißt wenn wir x & (1 << i) auswerten, hat dieses ein Ergebnis ungleich 0, wenn sowohl x als auch 1 << i an der selben Bitposition ungleich 0 sind. Also genau dann, wenn x an der i-ten Bitposition ungleich 0 ist. Weil wir die Schleife aufsteigend von 0 an durchlaufen, finden wir mit dieser Methode das niedrigste Bit ungleich 0. (Das ist etwas, das man sich im Zweifelsfall mal aufmalen sollte.)

Deine (hoffentlich korrigierte) Funktion und meine Funktion kannst du nun kombinieren, um deine pmm_alloc zu implementieren. Deine Funktion sollte einen Eintrag in der Bitmap ungleich 0 finden, und meine Funktion sollte darin den Index bestimmen. Der Algorithmus ist dann ²⁾

Code: [Auswählen]

index = indexArrayValNotNull(bitmap);
bit = bitscanforward(bitmap[index]);
page_nummer = index * 32 + bit; // 32 pages pro eintrag in "bitmap"
adresse = page_nummer * 4096; // jede page ist 4096 bytes groß
Und zu der Frage, ob nun char* oder void* oder unsigned int: Eigentlich absolut nicht egal, aber solange mir keiner widerspricht: unsigned int.

Zur Fehlerbehandlung: Wenn deine Funktion (gerechtfertigt) -1 zurück gibt, dann ist der Speicher übrigens komplett belegt, und dein OS sollte anhalten. Meine Funktion sollte nie -1 zurückgeben, wenn du sie mit Bitmap-Einträgen fütterst, die ungleich 0 sind.

^1)
2) Individualisierung angebracht und erwünscht

[Svenska]

"-1" als Fehlerwert passt nicht zu "unsigned int" als Datentyp.

[kevin]

Aber zum Glück hat Java ja keine unsigned-Variablen.

In C kann man dann eben (unsigned) -1 nehmen.

[s137]

Aber natürlich -> ArrayIndexOutOfBoundsException: 9 -> nur Elemente mit Index 0-8 im Array und "array.length = 9" also darf ich natürlich nur "< array.length" schreiben, danke für das Rätsel aber ich bin noch selber draufgekommen und hab dann geschaut obs richtig war ^^

Und die 2. Funktion hab ich denke ich jetzt soweit auch verstaden, werde dann mal versuchen das so zu implementieren, vielen Dank für die ausführliche Erklrung.

Viele Grüße
s137

[s137]

Also meine pmm_alloc() sollte jetzt eigentlich funktionieren, jedoch brauche ich ja auch noch eine pmm_free() und eine pmm_mark_used() funktion um speicher wieder freizugeben oder als markiert zu kennzeichnen, als argument erhalten die Funktionen einen Zeiger vom Typ void auf die addresse also: z.B. pmm_free(void* addr)

Jetzt weiß ich nur nicht genau wie ich aus der Adresse wieder auf die genaue Bitposition in meinem Bitmap Array komme... wie genau drehe ich den vorgang um. Vermutlich is es ganz einfache Mathematik und ich seh den Wald vor lauter Bäumen nicht..

Vg
s137

[kevin]

Versuch mal, in Worten (also auf deutsch, nicht in C) zu beschreiben, was der Arrayindex und die Bitnummer für die Page Nummer x ist. Oder wenn dir das zu abstrakt ist, kannst du auch eine konkrete Zahl einsetzen und schauen, wo Page 42 landen würde. Im Zweifelsfall ruhig auch mal ein Blatt Papier hernehmen und die Bitmap aufmalen.

[s137]

Naja ok das find ich jetz ja noch gar nicht so schwierig, also imho ergibt ArrayIndex * 32 + Bitnummer = Pagenummer.

Nur kann ich daraus immer noch nicht genau ableiten was ArrayIndex und Bitnummer für Werte sind. Ich komm zwar durch addresse / 4096 auf die Pagenummer, jedoch weiß ich dann nicht wie ich weiterrechnen soll.Vermutlich ist es einfachste Mathematik und ich komm halt einfach nicht drauf...

[kevin]

Wenn du ein Problem nicht verstehst, mach einfach ein paar Beispiele und schau, ob dir etwas auffällt:

Was sind Arrayindex/Bitnummer für Page 0?
Was sind Arrayindex/Bitnummer für Page 1?
...
Was sind Arrayindex/Bitnummer für Page 31?
Was sind Arrayindex/Bitnummer für Page 32?
...
Was sind Arrayindex/Bitnummer für Page 63?
Was sind Arrayindex/Bitnummer für Page 64?
...
Was sind Arrayindex/Bitnummer für Page 1337?
Was sind Arrayindex/Bitnummer für Page n?

[s137]

Danke, jetz hab ichs rausgefunden... Gepriesen sei der Modulo Operator... den hatt ich fast vergessen^^

Bitnummer = page_nummer % 32;
Array_Index = (page_nummer - Bitnummer) / 32;

Vg s137