Speicherverwaltung in GFA-BASIC

Irgendwann kam mir der Gedanke, selbst einen Texteditor zu schreiben. Bei meinen Vorbetrachtungen kam ich zu dem Schluss, den Text in verzeigerte und gegen Systemzugriffe geschützte Speicherblöcke zu schreiben.

Normalerweise alloziert man Speicher mittels Malloc (GEMDOS-Funktion 72). Die TOS-Version 1.0 vom 6.2.86 gestattet aber nur ca. 280 bis 290 solcher Aufrufe (TOS-Version 1.2 vom 22.4.87 ca. 800 Aufrufe). Dies genügt für einen Texteditor auf keinen Fall, so daß ich selbst gefordert war, eine Speicherverwaltung zu implementieren.

Die Aufgaben einer Speicherverwaltung sind schnell Umrissen. Auf Anforderung soll möglichst schnell ein passender Speicherblock gefunden werden, und, falls nicht vorhanden, ein größerer Block aufgespalten werden.

Bei der Rückgabe von Blöcken sollen benachbarte Speicherblöcke möglichst schnell zu einem Großen zusammengelegt werden.

Hier kam mir ein Artikel von Peter Sollich zur Hilfe, der ausführlich das Prinzip einer Speicherverwaltung behandelte. Um schnell einen der Anforderung entsprechenden Speicherblock zu finden, sortiert und verzeigert man die freien Speicher der Größe nach. Hier spricht man von der Root. Treten mehrere Blöcke mit gleicher Größe auf, so wird einer in die Root eingehängt, alle weitern enthalten nur noch Zeiger auf einen gleichgroßen. Auf der Root liegende Speicher enthalten drei Zeiger, die je vier Byte beanspruchen, plus vier Byte für den Größeneintrag. Daraus ergibt sich, daß jeder freie Block mindestens 16 Byte groß sein muß. Die verzeigerten Freispeicher nennt man Freelist. Zur Verschmelzung von benachbarten Blöcken wird eine Bitmap angelegt, in der jedes Bit 16 Byte freien Speicher repräsentiert. Die Bitmap gibt einen Überblick über den Speicher, der verwaltet wird. Jedes gesetzte Bit repräsentiert 16 Byte freien Speicher, jedes nicht gesetzte Bit 16 Byte reservierten Speicher. Bei der Prüfung auf benachbarte Blöcke muß also nur das rechte und linke Bit neben dem zurückgegebenen Block untersucht werden.

Bei der Installation der Verwaltung werden neben der Bitmap noch drei Speicherblöcke angelegt. Ein Block, der die Größe 0 repräsentiert, und ein weiterer für die Größe unendlich. Zwischen diese beiden, nennen wir sie größter und kleinster, wird nun der dritte Block eingehängt, der eigentliche freie Speicher. In der Bitmap werden die Bits für größter und kleinster gelöscht, also als reserviert markiert. Zudem wird das letzte Bit in der Bitmap auf Null gesetzt, um ein Überschreiben der Bitmap zu verhindern. Alle anderen Bits werden gesetzt.

Nun zu den Zeigern (Bild 1): Jeder Speicherblock enthält in den ersten vier Bytes seine Größe. Liegt ein freier Speicherblock auf der Root, so enthält er in Byte fünf bis acht die Startadresse des nächstgrößeren, in Byte neun bis zwölf einen Zeiger auf den nächstkleineren und schließlich in Byte dreizehn bis sechzehn die Adresse des nächsten gleichgroßen. Sollte kein gleicher Block vorhanden sein, so steht hier FALSE. Speicherblöcke, die nicht auf der Root liegen, enthalten nur den Zeiger auf den nächsten gleichen.

Zudem enthalten Blöcke, deren Größe 16 Bytes überschreiten, in den letzten vier Bytes ihre eigene Startadresse. Dieser zusätzliche Zeiger wird zur schnellen Zusammenlegung mit evtl. vorhandenen linken Nachbarn benötigt. Bei links gelegenen Nachbarn müßte in der Bitmap sonst jedes Bit, das links neben dem zurückgegebenen Block liegt, getestet werden, bis auf ein nicht gesetztes Bit getroffen wird. Aus dessen Position in der Bitmap könnte man dann die Startadresse des Nachbarn errechnen. Bei einer Speicherblockgröße von 16 kByte müßten immerhin 1000 Bits getestet werden. Soviel zum Prinzip dieser Speicherverwaltung, nun zur Implementierung in GFA-BASIC.

back%=FN speicher_inst(bytes%)

Wird hier -1 übergeben, so erhalten Sie als Rückgabe, wieviele Bytes maximal als Freispeicher installiert werden können. Ist der Übergabeparameter größer Null, wird die Verwaltung installiert. Bei korrekter Ausführung erhalten Sie TRUE, tritt ein Fehler auf, FALSE.

Bild 1

Zur Funktion selbst: In Zeile fünf wird getestet, wieviel Speicher alloziert werden kann (bei Übergabe-Parameter -1). Danach errechnet das Programm, wieviel Bytes für die Bitmap benötigt werden (allozierbarer Speicher geteilt durch 128). Das Teilen erfolgt durch Verschieben der Bits, was etwas schneller ist als dividieren. Zudem wird der Nachkommateil vernachlässigt, weil nur ganze Bytes in die Bitmap aufgenommen werden. Daraus ergibt sich, daß nur Größen, die ein Vielfaches von 128 sind, installiert werden. In Zeile sieben wird die Bitmap-Größe vom allozierbaren Speicher subtrahiert und in Zeile acht die Rückgabe errechnet. Bitmap-Größe mal 128 ergibt den maximal verwaltbaren Speicher. Davon werden je 16 Byte für größter und kleinster abgezogen. Weitere 16 Bytes werden benötigt, um das letzte Bit der Bitmap auf Null zu setzen. Wie schon erwähnt, schützt dies die Bitmap vor dem Überschreiben. In Zeile neun erfolgt der Rücksprung.

Nun zur eigentlichen Installation. In den Zeilen 11 bis 21 wird anhand des Übergabe-Parameters der zu allozierende Speicher berechnet. Danach wird mittels GEMDOS 72 Speicher vom Betriebssystem angefordert und dessen Startadresse in malloc_adr% abgelegt. Dies ist auch die einzige globale Variable in allen fünf Funktionen. Ab Zeile 23 werden die Größen und Zeiger eingetragen und zum Schluß die nötigen Bits in der Bitmap gesetzt. Bild 2 zeigt die fertig installierte Speicherverwaltung (Übergabeparameter 208 Bytes). Bei der Installation der Speicherverwaltung ist darauf zu achten, daß dem GEM noch genügend freier Speicher zur Verfügung steht (64 Kilobyte genügen), da sonst zum Beispiel keine Fileselectbox mehr auf dem Bildschirm erscheint. Außerdem ist eine evtl, benötigte RSC-Datei vor der Installation einzuladen.

back%=FN speicher_res(bytes%)

Diese Function reserviert bei Aufruf die in bytes% angeforderte Menge Speicher und gibt dessen Startadresse zurück. Steht kein genügend großer Speicherblock zur Verfügung, wird FALSE zurückgegeben. Die beantragte Größe kann die aufrufende Anwendung in Startadresse-4 im Langwortformat auslesen.

Zum Ablauf von Speicher res: Zu Beginn wird die beantragte Speichergröße in real% zwischengespeichert. Zum Übergabeparameter werden vier aufaddiert (für Größeneintrag) und dann geprüft, ob es sich um ein Vielfaches von 16 handelt. Ist dies nicht der Fall, wird darauf erweitert. Als nächstes wird geprüft, ob der größte freie Speicher größer oder gleich bytesVc ist. Trifft dies nicht zu, so erfolgt der Rücksprung zur Anwendung. Nun wird die Größe von bytes% vom Gesamtspeicher subtrahiert (steht in malloc_adr% +5) und danach werden die Freispeicher auf der Root durchlaufen, bis ein Block gleich oder größer bytes% gefunden wird. Dieses Durchlaufen der auf der Root liegenden Freispeicher wiederholt sich in einigen Functions und wird mit einer Repeat...Until Schleife realisiert. Ausgangspunkt ist dabei immer malloc_adr% und innerhalb der Schleife wird jedesmal der Zeiger auf den nächstgrößeren abgefragt. Ist nun ein der Anforderung passender Speicherblock gefunden, wird nach vier Fällen unterschieden:

Nun ist ein Speicherblock gefunden, ausgelöst und dessen Startadresse in back% abgelegt. Es muß also nur noch die Bitmap angepaßt werden. Anhand der Speicherblockgröße geteilt durch 16 wird errechnet, wieviele Bits zu löschen sind. Danach wird das Startbit errechnet, und daraus, im wievielten Byte der Bitmap mit der Löschaktion begonnen wird. Nun braucht man noch die Bit-Nummer und schon kann's losgehen. Um bei größeren Speicherblöcken eine höhere Geschwindigkeit zu erreichen, wird immer ein ganzes Byte auf Null gesetzt, falls dies möglich ist. Zum Schluß wird noch die beantragte Speicherblockgröße in die Startadresse geschrieben. Vor dem Rücksprung wird die Startadresse noch um vier erhöht, so daß die Größe in Startadresse minus vier steht und die Anwendung ab Startadresse mit dem Speicherblock tun und lassen kann, was sie will.

back%=FN speicher_frei(adr%)

Mittels speicher_frei kann schon beantragter Speicher wieder an die Verwaltung zurückgegeben werden. Übergabeparameter ist die Startadresse des als frei zu markierenden Speicherblockes. Als Rückgabe erhalten sie TRUE, tritt ein Fehler auf, FALSE.

Nun zum Ablauf: In den ersten 20 Zeilen wird auf eventuell vorhandene Fehler geprüft und die Größe wieder auf ein Vielfaches von 16 angepaßt. Danach wird errechnet, wieviele Bits in der Bitmap als frei markiert werden müssen und welches Bit die Startadresse der Rückgabe repräsentiert. Zugleich wird noch das Bit errechnet, das die Startadresse eines eventuell vorhandenen rechten Nachbarn repräsentiert, ebenfalls das letzte Bit des linken Nachbarn. Daraufhin wird die Rückgabe in der Bitmap als frei markiert. Nun erfolgt der Test auf einen rechten Nachbarn. Ist dieser vorhanden, so wird er aus der Freelist ausgetragen und dessen Größe zur Rückgabe addiert. Jetzt erfolgt der Test auf den linken Nachbarn. Für den Fall, daß ein linker Nachbar vorhanden ist, also das Bit links neben der Rückgabe gesetzt ist, wird zusätzlich ein Bit weiter links getestet. Ist dieses gesetzt, steht die Startadresse des linken Nachbarn in dessen letzten vier Bytes, ansonsten ist die Startadresse Rückgabeadresse minus 16. Auch dieser Block wird ausgelöst und zu dessen Größe die Rückgabegröße (die bereits um rechten Nachbarn erhöht ist) addiert. Nun braucht nur noch der ganze Block in die Freelist eingetragen werden.

back!= FN speicher_shrink(adr%,ngrs%)

Mit dieser Funktion können Sie reservierten Speicher einschränken. Als Übergabeparameter werden die Startadresse des Speicherblocks und die neue gewünschte Größe gefordert. Als Rückgabe erhalten Sie wieder TRUE und. falls ein Fehler auftritt. FALSE. Diese Function schneidet lediglich am unteren Ende des Speicherblocks die nicht mehr benötigten Bytes ab und gibt sie mittels FN speicher_frei an die Verwaltung zurück.

back%=FN Speicher kill(modus|)

Mit speicher_kill können Sie mit Übergabeparameter 0 die Speicherverwaltung abmelden, was bedeutet, daß der in speicher_inst allozierte Speicher ans Betriebssystem zurückgeben wird. Als Rückgabe erhalten Sie Null, wenn kein Fehler auftritt. Bei Übergabe von eins erhalten Sie als Rückgabe die Größe des Freispeichers, bei Übergabeparameter zwei die Größe des größten zusammenhängenden Freispeichers.

Bild 2
' (c) MAXON Computer GmbH
FUNCTION speicher_frei(adr%)
    LOCAL back!,bitz%,startbit%,ltest%,rtest%, sbyte%
    LOCAL bitnr&,bitm%,radr%,ladr%,suchadr% , startadr%
    LOCAL bytes%,startbyte2%,ltest2%,bitnr2&
    SUB adr%,4
    bitm%={malloc_adr%+12}
    IF adr%<malloc_adr%+32 OR ODD(adr%) 
        back!=FALSE 
        RETURN back!
    ENDIF
    bytes%={adr%}
    ADD bytes%,4
    IF ROL(SHR(bytes%,4),4)<bytes% 
        bytes%=ROL(SHR(bytes%,4),4)+16 
    ENDIF
    IF adr%+bytes%>bitm%-15 
        back!=FALSE 
        RETURN back!
    ENDIF
    {adr%}=bytes%
    {malloc_adr%+8}={malloc_adr%+8}+{adr%) 
    bitz%=SHR({adr%},4)
    startbit%=SHR(adr%-malloc_adr%,4)+1
    ltest%=startbit%-1
    ltest2%=startbit%-2
    rtest%=SHR(adr%+{adr%}-malloc_adr%,4)+1 
    sbyte%=SHR(startbit%, 3)
    IF ROL(SHR(startbit%,3),3)<startbit%
        INC sbyte%
    ENDIF
    bitnr&=ROL(sbyte%,3)-startbit%
    DEC sbyte%
    REPEAT
        IF bitz%>7 AND bitnr&=7 
            BYTE{bitm%+sbyte%}=255 
            SUB bitz%,8 
            INC sbyte%
        ELSE
            BYTE{bitm%+sbyte%}=BSET(BYTE{bitm%+sbyte%},bitnr&)
            DEC bitz%
            DEC bitnr&
            IF bitnr&=-1 
                INC sbyte% 
                bitnr&=7 
            ENDIF 
        ENDIF 
    UNTIL bitz%=0 
    sbyte%=SHR(rtest%,3)
    IF ROL(SHR(rtest%,3),3)<rtest%
        INC sbyte%
    ENDIF
    bitnr&=ROL(sbyte%,3)-rtest%
    DEC sbyte%
    IF BTST(BYTE{bitm%+sbyte%},bitnr&) 
        radr%=malloc_adr%+ROL(rtest%-1,4)
        {adr%}={adr%}+{radr%} 
        startadr%=malloc_adr%
        REPEAT
            startadr%={startadr%+4}
        UNTIL {startadr%}={radr%}
        IF startadr%=radr%
            IF {radr%+12}=FALSE
                {{radr%+8}+4}={radr%+4}
                {{radr%+4}+8}={radr%+8}
            ELSE
                {{radr%+8}+4}={radr%+12}
                {{radr%+4}+8}={radr%+12}
                BMOVE radr%+4,{radr%+12}+4,8 
            ENDIF 
        ELSE 
            DO
                EXIT IF {startadr%+12}=radr% 
                startadr%={startadr%+12}
            LOOP
            {startadr%+12}={radr%+12}
        ENDIF
    ENDIF
    sbyte%=SHR(ltest%,3)
    IF ROL(SHR(ltest%,3),3)<ltest%
        INC sbyte%
    ENDIF
    bitnr&=ROL(sbyte%,3)-ltest%
    DEC sbyte%
    IF BTST(BYTE{bitm%+sbyte%},bitnr&) 
        startbyte2%=SHR(ltest2%,3)
        IF ROL(SHR(ltest2%,3),3)<ltest2%
            INC startbyte2%
        ENDIF
        bitnr2&=ROL(startbyte2%,3)-ltest2%
        DEC startbyte2%
        IF BTST(BYTE{bitm%+startbyte2%},bitnr2&) 
            ladr%={adr%-4}
        ELSE
            ladr%=adr%-16
        ENDIF
        startadr%=malloc_adr%
        REPEAT
            startadr%={startadr%+4}
        UNTIL {startadr%}={ladr%}
        IF startadr%=ladr%
            IF {ladr%+12}=FALSE
                {{ladr%+8}+4}={ladr%+4}
                {{ladr%+4}+8}={ladr%+8}
            ELSE
                {{ladr%+8}+4}={ladr%+12}
                {{ladr%+4}+8}={ladr%+12}
                BMOVE ladr%+4,{ladr%+12}+4,8 
            ENDIF 
        ELSE 
            DO
                EXIT IF {startadr%+12}=ladr% 
                startadr%={startadr%+12}
            LOOP
            {startadr%+12}={ladr%+12}
        ENDIF
        {ladr%}={ladr%}+{adr%} 
        adr%=ladr%
    ENDIF
    IF {adr%}>16
        {{adr%}+adr%-4}=adr%
    ENDIF
    suchadr%=malloc_adr%
    REPEAT
        suchadr%={suchadr%+4}
    UNTIL {suchadr%}=>{adr%}
    IF {suchadr%}={adr%}
        {adr%+12}={suchadr%+12}
        {suchadr%+12}=adr%
    ELSE
        {adr%+4}=suchadr%
        {adr%+8}={suchadr%+8}
        {adr%+12}=FALSE 
        {{adr%+8}+4}=adr%
        {{adr%+4}+8}=adr%
    ENDIF
    back!=TRUE 
    RETURN back!
ENDFUNC

Listing 1: Speicher freigeben

' (c) MAXON Computer GmbH
FUNCTION speicher_res(bytes%)
    LOCAL real%,back%,adr%,such_adr%,flag!
    LOCAL bitz%,startbit%,sbyte%,bitm%,bitnr& 
    real%=bytes%
    ADD bytes%,4
    IF ROL(SHR(bytes%,4),4)<bytes% 
        bytes%=ROL(SHR(bytes%,4),4)+16 
    ENDIF
    IF {(malloc_adr%+24}}<bytes% 
        back%=FALSE 
        RETURN back%
    ENDIF
    {malloc_adr%+8}={malloc_adr%+8}-bytes% 
    adr%=malloc_adr%
    REPEAT
        adr%={adr%+4}
    UNTIL {adr%}=>bytes%
    IF {adr%}=bytes% AND {adr%+12}=FALSE 
        {{adr%+8}+4}={adr%+4}
        {{adr%+4}+8}={adr%+8} 
        back%=adr%
    ELSE IF {adr%}=bytes% AND {adr%+12}<>FALSE 
        back%={adr%+12}
        {adr%+12}={back%+12}
    ELSE IF {adr%}>bytes% AND (adr%+12}=FALSE 
        {{adr%+8}+4}={adr%+4}
        {{adr%+4}+8}={adr%+8} 
        flag!=TRUE
    ELSE IF {adr%}>bytes% AND {adr%+12}<>FALSE 
        {{adr%+8}+4}={adr%+12}
        {{adr%+4}+8}={adr%+12}
        BMOVE adr%+4,{adr%+12}+4,8 
        flag!=TRUE 
    ENDIF 
    IF flag!
        {adr%}={adr%}-bytes% 
        back%=adr%+{adr%}
        IF {adr%}>16
            {back%-4}=adr%
        ENDIF
        such_adr%=malloc_adr%
        flag!=FALSE
        REPEAT
            such_adr%={such_adr%+4}
            IF {such_adr%}={adr%}
                {adr%+12}={such_adr%+12}
                {such_adr%+12}=adr% 
                flag!=TRUE 
            ELSE IF {such_adr%}>{adr%}
                {adr%+8}={such_adr%+8}
                {adr%+4}=such_adr%
                {adr%+12}=FALSE 
                {such_adr%+8}=adr%
                {{adr%+8}+4}=adr% 
                flag!=TRUE 
            ENDIF 
        UNTIL flag!
    ENDIF
    bitz%=SHR(bytes%,4)
    startbit%=SHR(back%-malloc_adr%,4)+1 
    sbyte%=SHR(startbit%,3)
    IF ROL(SHR(startbit%,3),3)<startbit%
        INC sbyte%
    ENDIF
    bitnr&=ROL(sbyte%,3)-startbit% 
    bitm%={malloc_adr%+12}
    DEC sbyte%
    REPEAT
        IF bitz%>7 AND bitnr&=7 
            BYTE{bitm%+sbyte%}=0 
            SUB bitz%,8 
            INC sbyte%
        ELSE
            BYTE{bitm%+sbyte%}=BCLR(BYTE{bitm%+sbyte%},bitnr&)
            DEC bitz%
            DEC bitnr&
            IF bitnr&=-1 
                INC sbyte% 
                bitnr&=7 
            ENDIF 
        ENDIF 
    UNTIL bitz%=0 
    {back%}=real%
    ADD back%,4 
    RETURN back%
ENDFUNC

Listing 2: Speicher reservieren

' (c) MAXON Computer GmbH
FUNCTION speicher_inst(bytes%)
    LOCAL bitm_gr%,spei_gr%,malloc_gr%,back% 
    LOCAL offset%,bitm_adr%
    IF bytes%=-1
        malloc_gr%=MALLOC(-1) 
        bitm_gr%=SHR(malloc_gr%,7)
        SUB malloc_gr%,bitra_gr% 
        back%=ROL(SHR(malloc_gr%,7),7)-48 
        RETURN back%
    ENDIF
    ADD bytes%,48 
    bitm_gr%=SHR(bytes%, 7)
    IF ROL(SHR(bytes%,7),7)<bytes%
        INC bitm_gr%
    ENDIF
    spei_gr%=ROL(bitm_gr%,7) 
    malloc_gr%=spei_gr%+bitm gr%
    IF MALLOC(-1)<malloc_gr% OR bitm_gr%<2 
        back%=FALSE 
        RETURN back%
    ENDIF
    malloc_adr%=MALLOC(malloc_gr%) 
    {malloc_adr%}=0 
    {malloc_adr%+16}=spei_gr%-16 
    {malloc_adr%+12}=malloc_adr%+spei_gr% 
    {malloc_adr%+32}=spei_gr%-48 
    {malloc_adr%+8}=spei_gr%-48 
    {malloc_adr%+4}=malloc_adr%+32 
    {malloc_adr%+24}=malloc_adr%+32 
    {malloc_adr%+36}=malloc_adr%+16 
    {malloc_adr%+40}=malloc_adr% 
    {malloc_adr%+44}=FALSE 
    bitm_adr%={malloc_adr%+12}
    REPEAT
        IF bitm_gr%>3
            {bitm_adr%+offset%}=-1 
            SUB bitm_gr%,4 
            ADD offset%,4 
        ELSE
            BYTE{bitm_adr%+offset%}=255 
            DEC bitm_gr%
            INC offset%
        ENDIF 
    UNTIL bitm_gr%=0 
    BYTE{bitm_adr%}=63 
    BYTE{bitm_adr%+offset%-1}=254 
    back%=TRUE 
    RETURN back%
ENDFUNC

Listing 3: Speicher installieren

' (c) MAXON Computer GmbH

FUNCTION speicher_kill(modus|) 
    LOCAL back%
    SELECT modus|
    CASE 0
        ' Speicherverwaltung abmelden 
        back%=MFREE(malloc_adr%)
    CASE 1
        ' ges. Freispeicher 
        back%={malloc_adr%+8}
    CASE 2
        ' größter Speicherblock 
        back%={{malloc_adr%+24}} 
    ENDSELECT 
    RETURN back%
ENDFUNC

Listing 4: Speicher freigeben

' (c) MAXON Computer GmbH
FUNCTION speicher_shrink(adr%,ngrs%)
    LOCAL agrs%,frei%,backadr%,back!,rgr%,real% 
    back!=FALSE 
    SUB adr%,4 
    real%=ngrs%
    IF adr%<malloc_adr%+32 OR ODD(adr%)
        RETURN back!
    ENDIF
    agrs%={adr%} 
    rgr%=agrs%+4
    IF ROL(SHR(rgr%,4),4)<rgr% 
        rgr%=ROL(SHR(rgr%,4),4)+16 
    ENDIF
    IF agrs%<ngrs% OR adr%+rgr%=>{malloc_adr%+12}-15
        RETURN back!
    ENDIF
    ADD ngrs%, 4
    IF ROL(SHR(ngrs%,4),4)<ngrs% 
        ngrs%=ROL(SHR(ngrs%,4),4)+16 
    ENDIF
    frei%=rgr%-ngrs% 
    back!=TRUE 
    IF frei%>0
        backadr%=adr%+ngrs%
        {backadr%}=frei%-4 
        ADD backadr%,4
        back!=FN speicher_frei(backadr%)
        IF back!
            {adr%}=real%
        ENDIF
    ENDIF
    RETURN back!
ENDFUNC

Listing 5: Teil des reservierten Speichers zurückgeben


Manfred Müller
Links

Copyright-Bestimmungen: siehe Über diese Seite
Classic Computer Magazines
[ Join Now | Ring Hub | Random | << Prev | Next >> ]