L’allocazione della memoria

(1)

1

L’allocazione della memoria

Il Sistema Operativo si occupa anche di assegnare aree di memoria ai processi e, per poter svolgere questo compito, deve sempre sapere quante e quali aree di memoria ha a disposizione. Deve consultare periodicamente una sorta di mappa che indichi le zone libere e quelle occupate. In genere questa mappa è rappresentata con una lista concatenata di nodi, ciascuno per un’area di memoria, che descrivono indirizzo iniziale, lunghezza e stato (occupata o libera). Le varie aree di memoria sono di dimensioni variabili. Con questa struttura è sufficiente assegnare nuovi valori ad un paio di puntatori per implementare le operazioni di allocazione e rilascio delle aree di memoria.

Vediamo ora, con un esempio, quali tecniche utilizza il Sistema Operativo per decidere quali aree di memoria assegnare ai processi che le richiedono.

Supponiamo che la memoria, in un determinato istante, si presenti come in figura dove in rosso sono indicate le aree occupate ed in verde quelle libere. Il primo numero indica il blocco di partenza ed il secondo i blocchi liberi o occupati.

1 0, 12

2 12, 5

3 17, 6

4 23, 15

5 38, 5

6 43, 12

7 55, 10

8 65, 8

Immaginiamo che ci siano 3 processi P

1

, P

2

e P

3

che, uno dopo l’altro, richiedano blocchi di memoria di lunghezza 7, 10 e 1.

Analizziamo, una per una, le tecniche utilizzabili.

First fit

Con questa tecnica si assegna al processo richiedente il primo blocco di memoria sufficiente a soddisfare la richiesta.

Il processo P

1

richiede 7 blocchi.

Il primo blocco idoneo è il numero 4. Ridisegniamo la mappa della memoria dopo questa allocazione.

1 0, 12

2 12, 5

3 17, 6

4 23, 7

5 30, 8

6 38, 5

7 43, 12

8 55, 10

9 65, 8

Adesso il processo P

2

chiede 10 blocchi.

(2)

2 Il primo blocco che soddisfa questa richiesta è il settimo. La mappa diventa:

1 0, 12

2 12, 5

3 17, 6

4 23, 7

5 30, 8

6 38, 5

7 43, 10

8 53, 2

9 55, 10

10 65, 8

Adesso è il turno di P

3

che richiede un solo blocco.

1 0, 12

2 12, 1

3 13, 4

4 17, 6

5 23, 7

6 30, 8

7 38, 5

8 43, 10

9 53, 2

10 55, 10

11 65, 8

Best fit

Con questa tecnica si assegna al processo richiedente il blocco di memoria di dimensione minore sufficiente a soddisfare la richiesta.

Il processo P

1

richiede 7 blocchi.

Il primo blocco idoneo è il numero 8. Ridisegniamo la mappa della memoria dopo questa allocazione.

1 0, 12

2 12, 5

3 17, 6

4 23, 15

5 38, 5

6 43, 12

7 55, 10

8 65, 7

9 72, 1

Adesso il processo P

2

chiede 10 blocchi.

(3)

3 Il primo blocco che soddisfa questa richiesta è il numero 6. La mappa diventa:

1 0, 12

2 12, 5

3 17, 6

4 23, 15

5 38, 5

6 43, 10

7 53, 2

8 55, 10

9 65, 7

10 72, 1

Infine il processo P

3

richiede un solo blocco. Utilizzando questa tecnica dobbiamo inserirlo nella decima area.

1 0, 12

2 12, 5

3 17, 6

4 23, 15

5 38, 5

6 43, 10

7 53, 2

8 55, 10

9 65, 7

10 72, 1

Worst fit

Con questa tecnica si assegna al processo richiedente il blocco di memoria di dimensione massima.

Il processo P

1

richiede 7 blocchi.

Il primo blocco idoneo è il numero 4. Ridisegniamo la mappa della memoria dopo questa allocazione.

1 0, 12

2 12, 5

3 17, 6

4 23, 7

5 30, 8

6 38, 5

7 43, 12

8 55, 10

9 65, 8

Il processo P

2

chiede 10 blocchi.

(4)

4 Il primo blocco che soddisfa questa richiesta è il numero 7. La mappa diventa:

1 0, 12

2 12, 5

3 17, 6

4 23, 7

5 30, 8

6 38, 5

7 43, 10

8 53, 2

9 55, 10

10 65, 8

Adesso è il turno di P

3

che richiede un solo blocco. Con il worst fit dobbiamo inserirlo nel blocco numero 5.