gestione dinamica della memoria (algoritmo)
vittorio....@googlemail.com
chiedo un consiglio relativo alla gestione della memoria.
sto scrivendo un programma il cui scopo è trovare delle soluzioni a
partire da altre soluzioni (dette varianti) trovate in precedenza.
nel mio caso, una variante di partenza può portare ad 1 oppure ad n
altre varianti ed ad 1 o n altre soluzioni.
questo vuol dire che non sono in grado di prevedere quante varianti/
soluzioni dovrò elaborare a partire data una variante.
ne consengue che ho bisogno di gestire dinamicamente la memoria per
conservare varianti/soluzioni.
una volta finita l'elaborazione, varianti e soluzioni finiscono in un
file e dalla pila delle varianti viene presa una variante successiva
ed il gioco si ripete fino a quando tutte le varianti diventano
soluzioni (per le quali non è più possibile fare nulla)
poichè questo programma potrebbe "girare" su pc con disponibilità di
memoria differente (es: 64 mb, 1 gb, ...)
vorrei implementare un sistema efficiente di gestione della memoria
tenendo in considerazione quanto segue:
- è necessario perdere meno tempo possibile per allocare/deallocare la
memoria (evitare continui realloc)
- è meglio leggere un grosso blocco di varianti dal file una sola
volta piùttosto che piccoli blocchi di varianti ma ripetuti nel tempo)
- è meglio scrivere un grosso blocco di varianti/soluzioni nel file
una sola volta che tanti piccoli blocchi ma ripetuti nel tempo.
- pensando ai punti precedenti, il suggerimento è: meno il programma
usa il disco fisso e meglio è.
inoltre non vorrei incappare in problemi di frammentazione della
memoria.
come mi consigliate di procedere?
dovrei implementare un algoritmo particolare (consigliandone uno)
dovrei usare una Garbage Collection?
grazie per l'attenzione.
vittorio
brix99luftballons
> nel mio caso, una variante di partenza può portare ad 1 oppure ad n
> altre varianti ed ad 1 o n altre soluzioni.
>
> questo vuol dire che non sono in grado di prevedere quante varianti/
> soluzioni dovrò elaborare a partire data una variante.
>
> ne consengue che ho bisogno di gestire dinamicamente la memoria per
> conservare varianti/soluzioni.
>
> una volta finita l'elaborazione, varianti e soluzioni finiscono in un
> file e dalla pila delle varianti viene presa una variante successiva
> ed il gioco si ripete fino a quando tutte le varianti diventano
> soluzioni (per le quali non è più possibile fare nulla)
>
Costa ,rispetto ai tuoi dati uno o due puntatori(se vuoi una lista
doppia con ogni elemento
collegato al precedente e al seguente, se no basta un puntotore all'
elemento seguente ).
Elaborando, se ci sta' tutto in memoria bene, salvi i dati della lista
su disco ....
se l' elaborazione non è finita, ma e' finita la memoria, riutilizzi la
lista allocata in precedenza,
senza deallocare nulla a meno che che gli 'n' elementi non siano molto
diversi tra loro:
in questo caso devi reallocare solo gli elementi troppo piccoli per
contenere i nuovi dati
(se questo il caso, oltre ai puntatori aggiungi un campo maxSize e
curSuze per tenere traccia
delle dimensioni dell' area dati a disposizione e di quella usata).
In alternativa, dealloca tutta la precedente lista e riparti da capo ....
brix
vittorio....@googlemail.com
> Una bella e semplice lista linkata.
> Costa ,rispetto ai tuoi dati uno o due puntatori(se vuoi una lista
> doppia con ogni elemento
> collegato al precedente e al seguente, se no basta un puntotore all'
> elemento seguente ).
> Elaborando, se ci sta' tutto in memoria bene, salvi i dati della lista
> su disco ....
> se l' elaborazione non è finita, ma e' finita la memoria, riutilizzi la
> lista allocata in precedenza,
> senza deallocare nulla a meno che che gli 'n' elementi non siano molto
> diversi tra loro:
> in questo caso devi reallocare solo gli elementi troppo piccoli per
> contenere i nuovi dati
> (se questo il caso, oltre ai puntatori aggiungi un campo maxSize e
> curSuze per tenere traccia
> delle dimensioni dell' area dati a disposizione e di quella usata).
> In alternativa, dealloca tutta la precedente lista e riparti da capo ....
>
> brix
la lista linkata è l'ideale dal punto di vista della massimizzazione
della risorsa disponibile.
essendo le soluzioni grandi solo pochi byte riuscirei ad usare la
memoria al massimo.
però avrei due inconvenienti da risolvere:
per prima cosa, per ogni elemento della lista devo creare uno spazio
in memoria con malloc e questo crea un certo rellentamento
nellesecuzione dell'algoritmo;
secondo non è detto che gli elementi allocati siano contigui in
memoria, per tale motivo dovrei eseguire un'azione di scrittura sul
file per ogni elemento allocato.
stavo pensando di creare un buffer pari al 60%/70% della memoria
disponibile ed usare un solo puntatore per allocare le soluzioni.
a questo punto potrei scrivere nel file l'intero buffer quando questo
si riempie; sarebbe sufficiente poi ripristinare il puntatore
all'inizio del buffer per continuare a raccogliere le soluzioni in
memoria.
ma a questo punto la domanda è: "usando la funzione malloc, il SO
(linux in particolare) restituisce un blocco fisico di memoria oppure
un blocco di memoria virtuale?"
mi spiego meglio...
se ad esempio nella memoria fisica non esiste un blocco tanto grande,
ma di per se in memoria lo spazio ci sarebbe (anche se frammentato),
il sistema operativo consente comunque l'allocazione del blocco?
grazie ancora.
vittorio
Jack
> ma a questo punto la domanda è: "usando la funzione malloc, il SO
> (linux in particolare) restituisce un blocco fisico di memoria oppure
> un blocco di memoria virtuale?"
un blocco di memoria virtuale. O meglio: ogni applicazione in linux ha
uno spazio di memoria dedicato (contiguo, ad esempio dall'indirizzo
0x0000 all'indirizzo 0xFFFF). Questo spazio di memoria viene mappato
dal kernel nella memoria virtuale del sistema (in pagine di 4k credo,
le pagine non necessariamente sono contigue) . Le pagine di memoria
virtuale vengono mappate all'occorrenza nella RAM.
> mi spiego meglio...
>
> se ad esempio nella memoria fisica non esiste un blocco tanto grande,
> ma di per se in memoria lo spazio ci sarebbe (anche se frammentato),
> il sistema operativo consente comunque l'allocazione del blocco?
Si. Il programma non vede in nessun caso la frammentazione della
memoria fisica o virtuale(neanche la malloc, che chiede semplicemente
all'OS della memoria). Al limite vede la frammentazione dello spazio
di memoria dedicato (l'heap), ma non sono sicuro.
Credo ci sia un limite alla quantita' memoria che puoi allocare, prima
che il sistema ritorni un out of memory, ma sinceramente non so
quant'e'.
Ad esempio sono quasi certo che su un sistema a 32bit non si possono
allocare piu' di 4GB di ram (perche' finiscono gli indirizzi), anche
se probabilmente il limite e' piu' basso (normalemente una parte degli
indirizzi servono a mappare registri e periferiche HW e quindi non
possono essere usati dalla RAM.
Tutto questo e' AFAIK. Potrei sbagliarmi o non essere completamente
esatto su alcune cose. I dettagli inoltre dipendono dall'OS e anche
dall'HW.
Ciao Jack