Corso di Informatica

(1)

04/05/2014 M. Malatesta 2-Organizzazione della memoria-07

1

Modulo T4

2-Organizzazione della memoria

Corso di Informatica

2

Prerequisiti

Struttura elementare del computer

Struttura elementare della memoria centrale

Multiprogrammazione

Uso pratico elementare di un sistema operativo

Concetto intuitivo di struttura dati tabella

Concetto intuitivo di lista

(2)

3

Introduzione

In questa Unità vediamo le tecniche più comuni con le quali il SO gestisce la memoria. Si tratta ovviamente di tecniche trasparenti al

programmatore, ma che il tecnico informatico deve conoscere, soprattutto nell’ambito della programmazione di sistema.

Come si può gestire la RAM per permettere la multiprogrammazione?

Quali problemi si presentano allocando e deallocando programmi in RAM?

Quali possono essere le possibili strutture del descrittore della memoria?

A queste domande diamo una risposta in questa Unità.

4

SO e memoria centrale

In generale, la memoria centrale è destinata a contenere sia il SO che i programmi in esecuzione.

Programmi utente Sistema operativo Quindi è necessario che:

il SO utilizzi in minima parte la memoria, per lasciare spazio al software applicativo (programmi utente, compilatori, software di sviluppo);

siano presenti opportuni meccanismi di protezione, al fine di impedire al software generico di invadere le aree destinate al SO.

(3)

5

Allocazione della RAM

Le principali tecniche per allocare la memoria fisica ai processi sono:

1. allocazione singola 2. partizioni fisse 3. partizioni variabili

6

Allocazione della RAM

1. allocazione singola

L’allocazione singola veniva normalmente utilizzata nei sistemi monoprogrammati, come indicato nello schema.

Programmi utente

Sistema operativo Area libera

Indirizzi crescenti La protezione si realizzava mediante un

registro limite (bound register) che specificava la zona alla quale i programmi non potevano accedere. Durante

l’esecuzione di un programma, qualunque operazione di indirizzamento era sottoposta al confronto con il valore del bound register così da evitare l’invasione dell’area destinata al SO.

(4)

7

Allocazione della RAM

1. allocazione singola

Questa tecnica prevede che in memoria siano presenti il SO e un singolo processo utente, quindi non è possibile la multiprogrammazione.

In particolare, il SO può essere allocato:

nella parte bassa della RAM (fig. a);

nella memoria alta (ROM, v. fig. b);

parte nella RAM e parte (i driver delle periferiche) in ROM (fig. c).

Area libera Programma

utente SO (ROM)

Indirizzi crescenti

fig. a Programma

utente SO Area libera

fig. b

Driver (ROM)

Programma utente

SO Area libera

fig. c

8

Allocazione della RAM

2. partizioni fisse

Una successiva tecnica, consente un migliore utilizzo della memoria ed è basata sulla suddivisione di questa in partizioni di lunghezza prefissata (generalmente diversa l’una dall’altra).

P1 P2

Sistema operativo P3

Indirizzi crescenti Partizioni

In questo caso, ogni partizione può essere occupata da un programma e quindi è possibile la multiprogrammazione.

(5)

9

Allocazione della RAM

Quando un programma P deve essere caricato in memoria, il gestore della memoria controlla se esiste una partizione libera sufficiente a contenere P:

in caso affermativo, P viene caricato ed eseguito, e la partizione viene considerata occupata

altrimenti deve attendere che si liberi una partizione adeguata.

La protezione si realizza mediante due registri limite che contengono gli indirizzi inferiore e superiore della partizione assegnata al programma in esecuzione (in ogni istante un solo processo può avanzare effettivamente, e pertanto è sufficiente una sola coppia di tali registri)

10

Allocazione della RAM

OSSERVAZIONI:

Se la dimensione di P è maggiore della dimensione della partizione più grande, P non può essere caricato.

Programma C Programma A Area libera Programma B

Sistema operativo Area libera

Indirizzi crescenti

Qualora esistano più partizioni libere adatte a contenere P, il gestore di memoria sceglie la più piccola, poichè la parte inutilizzata non può essere allocata ad altri processi. Si crea però il problema della frammentazione.

(6)

11

Allocazione della RAM

D’altra parte, se si usa la strategia di assegnare a un processo la più piccola partizione libera sufficiente a contenerlo, potrebbe verificarsi il caso che un processo debba attendere, pur disponendo di grosse partizioni libere.

Se si usa la strategia di mantenere tutti i processi in un’unica lista e di prelevare di volta in volta quello che può essere ospitato nella prima partizione resasi libera, si corre il rischio che piccoli programmi tengano occupate grosse partizioni.

12

Allocazione della RAM

Quest’ultimo problema può essere risolto come mostrato in figura; ad ogni singola partizione è associata una coda dei processi che essa può ospitare.

(7)

13

Allocazione della RAM

Nel caso delle partizioni fisse, il descrittore di memoria può essere semplicemente e convenientemente rappresentato con una tabella (detta anche tabella di occupazione della memoria). Per l’esempio precedente, potremmo avere:

180 401

60 581

100 301

200 101

100 0

OCCUPANTE LUNGHEZZA

ORIGINE

Puntatori ai descrittori di processo

14

Allocazione della RAM

Quando un processo richiede una partizione di dimensione n si effettua una ricerca sulla tabella:

in caso di insuccesso, il processo resta in attesa;

altrimenti il suo descrittore viene allocato in tabella, secondo le tecniche scelte di rilocazione (statica o dinamica, quest’ultima essendo quella quasi sempre usata).

(8)

15

Allocazione della RAM

3. partizioni variabili

I problemi accennati causati dalla tecnica a partizioni fisse (limiti alla multiprogrammazione, frammentazione, utilizzo non efficiente della memoria) possono essere abbastanza bene risolti mediante una tecnica più evoluta di partizionamento.

Questa tecnica consiste nel creare partizioni variabili. Poichè può variare la loro ampiezza, di conseguenza varia anche il loro numero.

In questo modo, il gestore della memoria assegna ad ogni programma P la quantità di memoria effettivamente necessaria.

16

Allocazione della RAM

Quando P chiede l’esecuzione, il gestore della memoria controlla l’esistenza di una partizione libera adatta a contenerlo. Quando viene trovata, P viene allocato e se nella partizione scelta resta spazio disponibile, questo PUO’ essere in generale allocato ad un altro processo.

Inoltre, quando P termina, la partizione liberata può essere fusa con altre partizioni libere adiacenti.

(9)

17

Allocazione della RAM

Vediamo un esempio di utilizzo delle partizioni variabili.

a) I 3 programmi A, B e C vengono allocati in memoria.

b) Il programma B termina la sua esecuzione

c) Viene allocato il programma D

18

Allocazione della RAM

Anche nella tecnica a partizioni variabili, la protezione viene assicurata mediante una coppia di registri limite come descritto in precedenza.

d) Il programma A termina la sua esecuzione

e) Viene allocato il programma E

(10)

19

Allocazione della RAM

Il programma E, se avesse dimensione opportuna, potrebbe essere caricato nello spazio residuo della partizione sottostante quella occupoata da D, lasciando libera la prima partizione, abbandonata da A.

d) Il programma A termina la sua esecuzione

e) Viene allocato il programma E

20

Allocazione della RAM

Il descrittore di memoria in questo caso sarà rappresentato da una lista i cui elementi hanno la struttura seguente (si fa riferimento all’ultimo esempio e) mostrato):

50 64 64

0

OCCUPANTE LUNGHEZZA

ORIGINE

10

114 124 80

Puntatori ai descrittori di processo

(11)

21

Allocazione della RAM

Si può notare che, dopo l’allocazione del programma E, risultano 32K di spazio libero, ma suddiviso in piccole parti (frammentazione).

Possono presentarsi diversi casi:

se la frammentazione non è troppo spinta, se ci sono più partizioni libere in cui un programma può essere caricato, ciò può essere fatto in base a specifiche tecniche, che descriviamo di seguito;

se la frammentazione arriva a livelli tali da far degradare le prestazioni del sistema, si rende necessaria un’operazione di compattamento, che presenta comunque costi elevati, in quanto tutta la memoria deve essere letta e riscritta.

22

Allocazione della RAM

Come vedremo, alcuni problemi possono essere ridotti o eliminati, se si adotta la tecnica della paginazione, in quanto:

le aree libere hanno dimensioni multiple della dimensione della pagina;

le pagine di un singolo processo non devono essere allocate in spazi contigui.

(12)

23

Allocazione della RAM

Come anticipato, se la frammentazione è entro i limiti accettabili, possiamo progettare il gestore di memoria in modo che, quando un processo P richiede una partizione di dimensione n, si comporti secondo una delle seguenti strategie:

a. first fit b. best fit c. worst fit

Vediamo in cosa consistono.

24

Allocazione della RAM

3. partizioni variabili (first fit)

La strategia first fit consiste nell’allocare il processo nella prima partizione libera di dimensione sufficiente a contenerlo.

In pratica:

il gestore di memoria scandisce la lista delle partizioni finché trova la prima zona libera abbastanza grande:

la zona viene divisa in due parti, una per il processo e una per la memoria non utilizzata.

Si tratta di una strategia che, limitando al massimo le operazioni di ricerca, privilegia la velocità, ma non tiene conto della frammentazione, poichè allocare il processo nella prima partizione trovata, potrebbe aggravare lo stato di frammentazione esistente.

(13)

25

Allocazione della RAM

3. partizioni variabili (best fit)

La strategia best fit consiste nell’allocare il processo nella più piccola partizione libera di dimensione sufficiente a contenerlo.

Si tratta di una strategia più lenta di first fit, che non privilegia certo la velocità (a causa della necessaria scansione di tutto il descrittore di memoria per trovare la partizione di dimensione adeguata), ma cerca di limitare il fenomeno della frammentazione.

Tuttavia, se la partizione scelta è sufficientemente piccola (ma sempre abbastanza ampia da contenere il processo), la parte non occupata diventa spesso inutilizzabile..

26

Allocazione della RAM

3. partizioni variabili (worst fit)

La strategia worst fit consiste nell’allocare il processo nella più grande partizione libera di dimensione sufficiente a contenerlo.

Si tratta di una strategia che, come la best fit, non privilegia la velocità, ma limita il fenomeno della frammentazione.

Infatti, se la partizione scelta è sufficientemente grande (e comunque sempre abbastanza ampia da contenere il processo), la parte inutilizzata è ancora abbastanza grande da poter accogliere un altro processo.

(14)

27

Allocazione della RAM

Una necessaria operazione di recupero deve avvenire quando un processo rilascia una partizione.In questo caso occorre, se possibile, fondere la partizione rilasciata con quelle libere adiacenti.

Se nonostante questi accorgimenti, le prestazioni del sistema iniziano a degradare (tempi di attesa troppo lunghi a causa dell’eccessiva frammentazione), si rende necessario il compattamento

28

Allocazione della RAM

Il compattamento consiste nello spostare i programmi all’interno della memoria, in modo da fondere gli spazi liberi, per creare nuove partizioni abbastanza ampie da poter ospitare altri processi (v. figura in basso) Ovviamente, ciò risulta possibile soltanto nel caso che il loader effettui una

rilocazione dinamica.

(15)

29

Argomenti

SO e memoria centrale

Allocazione della RAM 1. allocazione singola 2. partizioni fisse 3. partizioni variabili

first fit

best fit

worst fit

30

Altre fonti di informazione

A. Lorenzi, D.Rossi – I fondamenti della programmazione-ATLAS