SoppalcoFC
19-06-2008, 09:17
Il problema
Si vuole realizzare un allocatore di memoria dinamica (per un sistema che non dispone di particolari supporti hardware quali una MMU per la memoria virtuale) capace di compattare la memoria allocata, quando necessario, per cercare di soddisfare le richieste di allocazione anche in caso di memoria frammentata. L'allocatore deve fornire servizi analoghi a quelli di malloc() e free(), ma in più deve essere in grado di spostare i blocchi di memoria, senza ovviamente alterare l'esecuzione del programma, se necessario per
soddisfare alcune richieste. Si è scelto di realizzare l'allocatore tramite il sistema degli handle (doppi puntatori): in pratica, quando un programma richiede un blocco di memoria, non viene restituito direttamente un puntatore alla memoria allocata (come fa, per esempio, la malloc()), bensì un puntatore a un puntatore alla memoria allocata. Se p è un handle a un blocco allocato, **p punterà al primo byte del blocco di
memoria allocata. Il puntatore intermedio è sotto controllo dell'allocatore stesso: *p sarà quindi un puntatore contenuto in un'area speciale della memoria riservata agli handle, e l'allocatore potrà modificare il contenuto di *p (ma non quello di p, visto che p è una variabile del programma che usa l'allocatore) per riflettere l'eventuale spostamento di un blocco in memoria. Lo spostamento va effettuato tutte le volte che nello heap gestito dall'allocatore c'è sufficiente memoria complessiva a soddisfare una richiesta, ma questa memoria non è contigua (per esempio, in conseguenza a numerose allocazione e deallocazioni in ordine sparso),
cosicché non è possibile trovare un blocco contiguo di memoria della dimensione richiesta. In questa situazione, l'allocatore deve ricompattare i blocchi allocati, aggiornare i puntatori intermedi nell'area degli handle, e infine allocare il blocco richiesto.
API
L'allocatore di memoria deve fornire la seguente API:
heap *createH(int nhandles, int size) – crea un nuovo heap, capace di gestire al più nhandles handle, e con uno spazio per i dati di size bytes.
void **allocH(heap *h, int size) – alloca size bytes nello heap h, restituisce il puntatore a un handle (o NULL in caso di errore). Se c'è sufficiente spazio disponibile, ma non contiguo, effettua una ricompattazione e poi alloca il blocco.
void freeH(heap *h, void **handle) – libera la memoria allocata dall'handle handle nello heap h. L'handle deve essere stato ottenuto da una precedente chiamata a allocH().
int availH(heap *h) – restituisce la quantità di spazio libero nello heap h (ovvero, la somma della dimensione di tutti gli eventuali frammenti liberi).
void compactH(heap *h) – forza una ricompattazione dello heap h.
void destroyH(heap *h) – distrugge lo heap h; dopo questa operazione, tutti gli handle ottenuti da allocH() su quello heap sono invalidi.
Io ho pensato a gestire le strutture dati nel modo seguente:
Codice:
#define N_HEAP 100
typedef struct handle {
char *dati;
int size;
} handle;
typedef struct heap {
int nhandles;
int size;
handle ** hl;
void* mem;
} heap;
// struttura che utilizzo per tener traccia degli heap effettivamente creati con all'interno
// il puntatore all'area di memoria corrispondente al primo byte
static heap * Heap_Used[N_HEAP];
Secondo voi va bene questa scelta o c'e' un modo migliore per procedere nello svolgimento del progetto? Grazie per l'aiuto!!
Si vuole realizzare un allocatore di memoria dinamica (per un sistema che non dispone di particolari supporti hardware quali una MMU per la memoria virtuale) capace di compattare la memoria allocata, quando necessario, per cercare di soddisfare le richieste di allocazione anche in caso di memoria frammentata. L'allocatore deve fornire servizi analoghi a quelli di malloc() e free(), ma in più deve essere in grado di spostare i blocchi di memoria, senza ovviamente alterare l'esecuzione del programma, se necessario per
soddisfare alcune richieste. Si è scelto di realizzare l'allocatore tramite il sistema degli handle (doppi puntatori): in pratica, quando un programma richiede un blocco di memoria, non viene restituito direttamente un puntatore alla memoria allocata (come fa, per esempio, la malloc()), bensì un puntatore a un puntatore alla memoria allocata. Se p è un handle a un blocco allocato, **p punterà al primo byte del blocco di
memoria allocata. Il puntatore intermedio è sotto controllo dell'allocatore stesso: *p sarà quindi un puntatore contenuto in un'area speciale della memoria riservata agli handle, e l'allocatore potrà modificare il contenuto di *p (ma non quello di p, visto che p è una variabile del programma che usa l'allocatore) per riflettere l'eventuale spostamento di un blocco in memoria. Lo spostamento va effettuato tutte le volte che nello heap gestito dall'allocatore c'è sufficiente memoria complessiva a soddisfare una richiesta, ma questa memoria non è contigua (per esempio, in conseguenza a numerose allocazione e deallocazioni in ordine sparso),
cosicché non è possibile trovare un blocco contiguo di memoria della dimensione richiesta. In questa situazione, l'allocatore deve ricompattare i blocchi allocati, aggiornare i puntatori intermedi nell'area degli handle, e infine allocare il blocco richiesto.
API
L'allocatore di memoria deve fornire la seguente API:
heap *createH(int nhandles, int size) – crea un nuovo heap, capace di gestire al più nhandles handle, e con uno spazio per i dati di size bytes.
void **allocH(heap *h, int size) – alloca size bytes nello heap h, restituisce il puntatore a un handle (o NULL in caso di errore). Se c'è sufficiente spazio disponibile, ma non contiguo, effettua una ricompattazione e poi alloca il blocco.
void freeH(heap *h, void **handle) – libera la memoria allocata dall'handle handle nello heap h. L'handle deve essere stato ottenuto da una precedente chiamata a allocH().
int availH(heap *h) – restituisce la quantità di spazio libero nello heap h (ovvero, la somma della dimensione di tutti gli eventuali frammenti liberi).
void compactH(heap *h) – forza una ricompattazione dello heap h.
void destroyH(heap *h) – distrugge lo heap h; dopo questa operazione, tutti gli handle ottenuti da allocH() su quello heap sono invalidi.
Io ho pensato a gestire le strutture dati nel modo seguente:
Codice:
#define N_HEAP 100
typedef struct handle {
char *dati;
int size;
} handle;
typedef struct heap {
int nhandles;
int size;
handle ** hl;
void* mem;
} heap;
// struttura che utilizzo per tener traccia degli heap effettivamente creati con all'interno
// il puntatore all'area di memoria corrispondente al primo byte
static heap * Heap_Used[N_HEAP];
Secondo voi va bene questa scelta o c'e' un modo migliore per procedere nello svolgimento del progetto? Grazie per l'aiuto!!