Basekernel OS

Aufgabe 1. Aus wie vielen Schichten ist der basekernel zusammengesetzt?

Aufgabe 2. Welche Aufgabe hat ein Bussystem in einem Rechner?

Aufgabe 3. Was ist der Unterschied zwischen physischen und virtuellen Adressräumen? Wieseo werden virtuelle Adressräume benötigt?

Speicherverwaltung

Hinweise

Tabellenbasierte Speicherverwaltung

In dieser Übung soll ein tieferer Einstieg in Algorithmen für Speicherverwaltung erfolgen.

Es gibt folgende Elemente:

• Nur Datentyp vorzeichenbehaftete Ganzzahl ⇒ int
• Datenvariablen, Arrays und Zeiger
• Boolesche, Logische, und Arithmetische Rechenoperationen
• Enumeration und Typdefinition
• Präprozessormakros
• Eigene Funktionen, Main und printf Funktionen
• Arrays

Speicher

Es soll der Hauptspeicher eines Rechners mit einem linearen Bytearray ds implementiert werden. Die Größe ist frei wählbar (aber mindestens 1024, maximal 32000) und soll statisch im Programm erzeugt werden:

#define MEMSIZE 4096
#define BLOCKSIZE 128
#define BLOCKS (MEMSIZE/BLOCKSIZE)

#define ENCODE(pid,size) ((size<<8)+pid)
#define DECODESIZE(ps) (ps >> 8)
#define DECODEPID(ps) (ps & 0xFF)

Der Speicher soll in Blöcke der Größe M (z.B. 256 Bytes) unterteilt werden. Speicher kann nur in Einheiten der Blockgröße vergeben werden (Eine Anforderung 5 ist möglich, liefert dann aber 256 Bytes == 1 Block).

Funktionen

Es sollen drei Funtionen implementiert werden die den DS Speicher verwalten:

1. Speicher anfordern (durch einen imaginären Prozess p): memalloc(int *bytesize,int processid) -> unsigned char*
2. Speicher zurückgeben: memfree(unsigned char* addr,int processid)
3. Speicherbereich erweitern oder verkleinern: memrealloc(unsigned char* addr, int *bytesize,int processid) -> unsigned char*. Dabei ist bytesize die neue Größe.

Datenstruktur

Freie und belegte Speicherbereiche sollen über eine statische Tabelle mema verwaltet werden. Jeder Eintrag entspricht einem Block in ds:

#define BLOCKS MEMSIZE/BLOCKSIZE
int mema[BLOCKS];
#define BLOCKADDR(A) (A/BLOCKSIZE)
unsigned char ds[MEMSIZE];

Wird ein Speicherblock einem Prozess übergeben, so wird in der Tabelle die Prozessid+1 sowie dessen Größe in jedem belegent Block eingetragen (Prozessnummern beginnen ab 0). Ein freier Block wird mit 0 markiert. Es soll einen ersten (0) Block geben der reserviert ist (Null Pointer!), einfach mit -1 markiert.

Algorithmus

Wir wollen hier zuerst den First-Fit Algorithmus implementieren:

function memalloc(size,pid) {
  size=int((size+BLOCKSIZE)/BLOCKSIZE) // wir brauchen die Blockgröße ganzzahlig
  n=0;begin=-1
  for(i=0;i<BLOCKS;i++) {
    n=1;begin=i
    if (mema[i]==0) {
      for(j=i+1;j<BLOCKS && n<size;j++,n++) {
        if (mema[i]!=0) break;
      }
    }
    if (n==size) break;
    begin=-1
    n=0
  }
  if (n==size) {
    for(i=0;i<n;i++) {
      mema[i+begin]=pid;
    }
    return begin*BLOCKSIZE;
  }
  return -1;
}

Aufgabe 4. Implementiere den Speicher ds und die Tabelle mema. Dann implementiere die Funktionen memalloc(int *bytesize,int processid) -> unsigned char*, memfree(unsigned char* addr,int processid) und memrealloc(unsigned char* addr, int *bytesize,int processid) -> unsigned char* sowie eine Funktion die die Belegung der Tabelle ausgibt, einmal nur akkumulativ freier und belegter Platz, dann (verbose=1) die gesamte Tabelle. Es ist ein meminit() erforderlich wo die mema Tabelle initialisiert wird. Test die Implementierung.

I2luY2x1ZGUgImNsaWIuaCIKCiNkZWZpbmUgTUVNU0laRSA0MDk2CiNkZWZpbmUgQkxPQ0tTSVpFIDEyOAojZGVmaW5lIEJMT0NLUyAoTUVNU0laRS9CTE9DS1NJWkUpCgojZGVmaW5lIEVOQ09ERShwaWQsc2l6ZSkgKChzaXplPDw4KStwaWQpCiNkZWZpbmUgREVDT0RFU0laRShwcykgKHBzID4+IDgpCiNkZWZpbmUgREVDT0RFUElEKHBzKSAocHMgJiAweEZGKQoKdW5zaWduZWQgY2hhciBkc1tNRU1TSVpFXTsKaW50IG1lbWFbQkxPQ0tTXTsKCnZvaWQgbWVtaW5pdCgpIHsKICBpbnQgaTsKICBmb3IoaT0wO2k8QkxPQ0tTO2krKykgewogICAgbWVtYVtpXT0wOwogIH0KICBtZW1hWzBdPS0xOyAvLyByZXNlcnZlZAp9Cgp1bnNpZ25lZCBjaGFyKiBtZW1hbGxvYyhpbnQgc2l6ZSxpbnQgcGlkKSB7CiAgaW50IGksaixuLGJlZ2luOwogIHNpemU9KChzaXplK0JMT0NLU0laRSkvQkxPQ0tTSVpFKTsgLy8gd2lyIGJyYXVjaGVuIGRpZSBCbG9ja2dyw7bDn2UgZ2FuenphaGxpZwogIG49MDtiZWdpbj0tMTsKICBmb3IoaT0wO2k8QkxPQ0tTO2krKykgewogICAgaWYgKG1lbWFbaV09PTApIHsKICAgICAgbj0xO2JlZ2luPWk7CiAgICAgIGlmIChuPHNpemUpIHsKICAgICAgICBmb3Ioaj1pKzE7ajxCTE9DS1MgJiYgbjxzaXplO2orKyxuKyspIHsKICAgICAgICAgIGlmIChtZW1hW2ldIT0wKSBicmVhazsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIGlmIChuPT1zaXplKSBicmVhazsKICAgIGJlZ2luPS0xOwogICAgbj0wOwogIH0KICBpZiAobj09c2l6ZSkgewogICAgZm9yKGk9MDtpPG47aSsrKSB7CiAgICAgIG1lbWFbaStiZWdpbl09RU5DT0RFKHBpZCxzaXplKTsKICAgIH0KICAgIHJldHVybiAodW5zaWduZWQgY2hhciopKGJlZ2luKkJMT0NLU0laRSk7CiAgfQogIHJldHVybiAodW5zaWduZWQgY2hhciopIDA7Cn0KCnZvaWQgbWVtZnJlZSh1bnNpZ25lZCBjaGFyICphZGRyLCBpbnQgcGlkKSB7CiAgaW50IGJlZ2luPShpbnQpYWRkci9CTE9DS1NJWkUsCiAgICAgIHNpemU7CiAgc2l6ZT1ERUNPREVTSVpFKG1lbWFbYmVnaW5dKTsKICBpZiAoREVDT0RFUElEKG1lbWFbYmVnaW5dKSE9cGlkKSByZXR1cm4gMDsKICBpbnQgaTsKICBmb3IoaT1iZWdpbjtpPChiZWdpbitzaXplKTtpKyspIHsKICAgIG1lbWFbaV09MDsKICB9Cn0Kdm9pZCBtZW1wcmludCgpIHsKICBpbnQgaSxmcmVlPTAsYWxsb2NhdGVkPTA7CiAgZm9yKGk9MDtpPEJMT0NLUztpKyspIHsKICAgIGlmIChtZW1hW2ldPT0wKSBmcmVlKys7CiAgICBlbHNlIGFsbG9jYXRlZCsrOwogIH0KICBwcmludGYoIkZSRUU9JWQgQUxMT0M9JWRcbiIsZnJlZSxhbGxvY2F0ZWQpOwp9CgppbnQgbWFpbigpIHsKICB1bnNpZ25lZCBjaGFyICphLCpiOwogIG1lbWluaXQoKTsKICBhPW1lbWFsbG9jKDQwMCwxKTsKICBiPW1lbWFsbG9jKDEwMCwxKTsKICBwcmludGYoIkFMTE9DQVs0MDBdPSVkXG4iLGEpOwogIHByaW50ZigiQUxMT0NBWzQwMF09JWRcbiIsYik7CiAgbWVtZnJlZShhLDEpOwogIG1lbXByaW50KCk7Cn0=

Aufgabe 5. Teste die Implementierung mit folgenden Testmuster. Notiere die Ausgabe von memprint.

a=memalloc(400,1);
a=memalloc(300,1);
b=memalloc(200,1);
memfree(a);
a=memalloc(200,4);
memfree(b);
a=memalloc(100,1);
b=memalloc(200,3);
memprint()