Memòria dinàmica
Objectius
- Entendre el concepte de memòria dinàmica.
- Conèixer els mecanismes per a reservar i alliberar memòria.
Introducció
Fins ara hem treballat amb memòria estàtica, és a dir, tota la memòria que utilitzàvem estava fixada des d’un inici i es reservava en executar el nostre programa. Això té un conjunt d’inconvenients, ja que, per exemple, en crear una taula hem de definir una mida màxima, i s’ocupa molt espai innecessari quan aquesta taula està buida i amb una limitació en el nombre màxim d’elements que aquesta taula pot contenir. En aquest mòdul veurem com podem reservar memòria de forma dinàmica durant l’execució del nostre programa.
1. Gestió de la memòria
A continuació es mostra una evolució de l’esquema de memòria que vam veure en la unitat de memòria estàtica:
Podem veure que a les zones ja vistes anteriorment, s’ha afegit l’stack i el heap. Aquestes zones creixen en sentit oposat, i quan es troben significa que el sistema s’ha quedat sense memòria. L’stack o pila de programa és una estructura tipus LIFO (Last In First Out). Cada vegada que el nostre programa fa una crida a una funció o acció, tota la informació referent a aquesta acció o funció s’afegeix a aquesta pila, i en finalitzar la seva execució s’elimina de la pila. No entrarem en els detalls del que es guarda, però hi ha informació sobre on es guarda el retorn, les variables i els paràmetres de la funció. D’altra banda, tenim el heap, que es troba just a continuació del BSS. Quan en un programa reservem memòria dinàmicament, aquesta es reserva a partir del heap i aquest es desplaça.
Gestionar la memòria significa demanar memòria al sistema operatiu per a guardar les nostres dades i, quan ja no la necessitem, alliberar-la perquè altres programes la puguin usar. La clau de tot aquest procés són els punters, que ens permeten apuntar les zones de memòria que reservem. Anem a veure un exemple de com funciona aquest mecanisme. Primer utilitzant solament memòria estàtica:
var
a: integer;
end var
a:=4;
writeInteger(a);
int a;
a=4;
printf("%d\n", a);
Ara una versió del mateix programa, però utilitzant memòria dinàmica:
var
a: pointer to integer;
end var
a:=NULL;
a:=getMemory(1);
if a=NULL then
error("Not enough memory");
end if
a^:=4;
writeInteger(a^);
freeMemory(a);
int *a=NULL;
/* malloc allocate a number of bytes from memory. Since we want an integer, we use the sizeof command to get the length in bytes for the type int*/
a=(int*)malloc(sizeof(int));
if(a==NULL) {
printf("Error: Not enough memory\n");
return;
}
*a=4;
printf("%d\n", *a);
free(a);
Fixeu-vos en els punts següents:
- Treballem amb punters, per tant, la variable a, que és un enter en el primer cas, passa de punter a enter en el segon cas.
- La memòria s’ha de reservar abans de poder utilitzar-la. En llenguatge C, caldrà assignar el tipus correcte al retorn del mètode malloc.
- Comproveu que s’ha pogut reservar la memòria sol·licitada. Si tota la memòria està ocupada, el punter queda assignat a null i, per tant, no podem utilitzar-lo.
- En finalitzar, o quan ja no la necessitem, cal alliberar la memòria.
2. Taules amb memòria dinàmica
Una de les grans limitacions de treballar amb memòria estàtica la trobem a l’hora de definir taules, ja que estem obligats a fixar una mida per al vector que s’utilitza per a definir la taula. Per aquest motiu, fins ara ens hem vist obligats a especificar sempre un nombre màxim d’elements per a la taula. Aquest fet té dues conseqüències no desitjables:
- Estem limitats en el nombre de registres que guarda la taula.
- Estem ocupant sempre el màxim de memòria (com si la taula estigués plena), fins i tot quan la taula està buida.
Quan treballem amb memòria dinàmica, tenim la possibilitat d’anar demanant memòria a mesura que la necessitem. Fixeu-vos en el següent exemple, que mostra com canviar la mida d’un vector de reals:
var
v: pointer to real;
end var
v:=NULL;
v:=getMemory(2);
if v=NULL then
error("Not enough memory");
end if
v[1]:=1.5:
v[2]:=3;
resizeMemory(v, 3);
if v=NULL then
error("Not enough memory");
end if
v[3]:=5.4;
v[1]:=v[1] + v[2] + v[3];
resizeMemory(v, 1);
writeReal(v^);
freeMemory(v);
float *v=NULL;
/* Allocate memory for a vector of 2 float values*/
v=(float*)malloc(2*sizeof(float));
if(v==NULL) {
printf("Error: Not enough memory\n");
return;
}
v[0]=1.5;
v[1]=3;
/* Change the size of the vector to 3 float values*/
v=(float*)realloc(v, 3*sizeof(float));
if (v==NULL) {
printf("Not enough memory");
return;
}
v[2]=5.4;
v[0]=v[0] + v[1] + v[2];
/* Change the size of the vector to 1 float value*/
v=(float*)realloc(v, sizeof(float));
printf("%f\n", *v);
free(v);
Fixeu-vos que en aquest codi:
- Creem un vector de 2 reals.
- Assignem valors a les dues posicions del vector.
- Redimensionem el vector afegint-li una tercera posició. No podem assegurar que la zona de memòria que se’ns assigni comenci al mateix lloc, per tant, cal apuntar el punter a la nova zona de memòria.
- Assignem un valor a aquesta tercera posició (les dues anteriors mantenen els seus valors). S’allibera la memòria que utilitzaven aquestes dues posicions.
- Guardem a la primera posició la suma de les tres posicions del vector.
- Tornem a redimensionar el vector, però ara reduïm la memòria que ocupa a una sola posició, per tant ara és equivalent a un real normal.
- Mostrem el resultat.
- Alliberem la memòria que encara ocupem.
Una vegada tenim un vector que pot canviar de mida, la definició d’una taula amb memòria dinàmica quedaria tal com es mostra al següent apartat.
2.1. Definició de taula amb memòria dinàmica
Recordem que una taula es defineix per un vector que conté els elements de la taula i un enter que ens indica quants elements hi ha guardats. Com que en aquest cas volem que el vector pugui canviar la seva mida, en comptes que tingui una mida fixada, definirem la taula amb un punter. Ara ja no tindrem una mida màxima de la taula. A continuació es mostra la definició d’una taula d’enters.
type
tTable = record
elements: pointer to integer;
numElements: integer;
end record
end type
int *elements;
int numElements;
} tTable;
2.2. Operacions de taules amb memòria dinàmica
En utilitzar memòria dinàmica caldrà fer alguns petits canvis en les operacions sobre aquest tipus. Hem de tenir en compte els fets següents:
- Tot punter ha de ser inicialitzat al valor null, per a saber que no té memòria assignada. Per tant, en inicialitzar la taula caldrà inicialitzar el punter.
- Quan s’afegeixen elements, ja no hi ha un nombre màxim d’elements, però cal redimensionar la mida del vector.
- Quan s’eliminen elements, si no volem utilitzar més espai del necessari, també caldrà redimensionar la mida del vector.
- Quan no necessitem la taula, hem d’alliberar tota la memòria que utilitza.
Tenint en compte aquests punts, les operacions per a la taula anterior queden redefinides com:
2.2.1. Inicialització
Inicialitza una taula passada com a paràmetre.
action initTable(inout table : tTable)
table.numElements := 0;
table.elements := NULL;
end action
table->nElements=0;
table->elements=NULL;
}
2.2.2. Afegir element
Donada una taula i un nou element, afegeix aquest element al final de la taula. Tingueu en compte que quan el punter encara no apunta cap zona de memòria, reservem memòria i no redimensionem el vector.
action addElement(inout table : tTable, e : integer)
if table.numElements = 0 then
table.elements:=getMemory(1);
else
resizeMemory(table.elements, table.numElements+1);
end if
if v=NULL then
error("Not enough memory");
end if
table.numElements := table.numElements + 1;
table.elements[table.numElements] := e;
end action
if(table->numElements == 0) {
table->elements=(int*)malloc(sizeof(int));
} else {
table->elements=(int*)realloc(table->elements, (table->numElements+1) * sizeof(int));
}
if(table->elements == NULL) {
printf("Error: Not enough memory\n");
return;
}
table->numElements++;
table->elements[table->numElements-1] = e;
}
2.2.3. Eliminar element
Donada una taula i la posició de l’element que volem eliminar, elimina l’element que es troba en la posició indicada i compacta la taula. Tingueu en compte que en el cas que la taula quedi buida, cal alliberar la memòria i assignar el punter a NULL, indicant que no hi ha memòria reservada.
action delElement(inout table : tTable, pos : integer)
var
i : integer;
end var
if pos >=1 and pos <= table.numElements then
for i:=pos to table.numElements-1 do
table.elements[i]:=table.elements[i+1];
end for
table.numElements:=table.numElements-1;
resizeMemory(table.elements, table.numElements);
end if
end action
int i;
if(pos>=0 && pos<table->numElements) {
for(i=pos; i< table->numElements-1; i++) {
table->elements[i]=table->elements[i+1];
}
table->numElements--;
if(table->numElements==0) {
free(table->elements);
table->elements=NULL;
} else {
table->elements=(int*)realloc(table->elements, table->numElements * sizeof(int));
if(table->elements == NULL) {
printf("Error: resize memory fail\n");
}
}
}
}
2.2.4. Eliminar taula
Una operació que no era necessària en el cas d’utilitzar memòria estàtica era l’eliminació de la taula. A continuació es defineix un mètode per a fer-ho.
action releaseTable(inout table : tTable)
if table.elements ≠ NULL then
freeMemory(table.elements);
table.numElements:=0;
table.elements:=NULL;
end if
end action
if(table->elements != NULL) {
free(table->elements);
table->numElements=0;
table->elements=NULL;
}
}
Resum
En aquesta unitat hem vist:
- El concepte de memòria dinàmica.
- Com es gestiona la memòria dinàmica, amb els tres comandaments principals per a reservar, redimensionar i alliberar.