Lezione 2

LEZIONE 2

RISORSE E CONDIVISICENE

IN QUESTA LEZIONE IMPAREREMO.

il concetto di risorsa condivisa
le richieste e le modalità di accesso alle risorse
Il grafo di Holt per descrivere processi e risorse

• Generalità
I processi sono i programmi i n evoluzione e per poter evolvere hanno bisogno delle risorse del
sistema di elaborazione: possiamo proprio vedere i l sistema di elaborazione come composto da un
insieme di risorse da assegnare ai processi affinché questi possano svolgere i l proprio compito.

Una prima definizione di risorsa è la seguente:

RISORSA
O g n i c o m p o n e n t e riusabile o m e n o , sia h a r d w a r e , sia software necessario al p r o c e s s o
o al sistema.

Per accedere alle risorse i processi sono i n competizione i n quanto spesso esse non sono sufficienti
per t u t t i e quindi è necessario "accaparrarsele" per poterle utilizzare; per esempio i processi c o m -
p e t o n o per avere a disposizione la memoria RAM, per utilizzare l'interfaccia di rete, le stampanti
ecc., e soprattutto i l processore che, nelle nostre architetture, è singolo e senza d i esso nessun
processo può evolvere.

Le risorse possono essere suddivise i n classi e le risorse appartenenti alla stessa classe sono equiva-
lenti, per esempio bytes della memoria, stampanti dello stesso tipo ecc.

CLASSE E ISTANZE
Le risorse d i una classe v e n g o n o d e t t e istanze della classe; il n u m e r o d i risorse in una
classe v i e n e d e t t o m o l t e p l i c i t à d e l t i p o di risorsa.

11
 Quando u n processo necessità di una risorsa generalmente non può richiedere una particolare ri-
sorsa ma solo una istanza d i una specifica classe: quindi una richiesta di risorse viene fatta per una
classe d i risorse e può essere soddisfatta da parte del SO assegnando al richiedente una qualsiasi
istanza di quel tipo.

In altre parole, la molteplicità di una risorsa ci indica i l numero massimo d i processi che la possono
usare contemporaneamente: se i l numero di processi è maggiore della molteplicità d i una risorsa,
questa deve essere condivisa tra i processi che v i accedono concorrentemente.

ESEMPIO Ti
Abbiamo detto che i n u n PC è presente u n solo processore, quindi la molteplicità della risorsa pro-
cessore è uguale a uno: i l numero massimo di processi che possono evolvere contemporaneamente
è quindi uno e quando abbiamo la necessità d i far evolvere più processi assieme, questi condividono
l'unica istanza della risorsa e competono per ottenerla.

Condivisione e gestione
Cerchiamo d i chiarire meglio i l concetto di condivisione prendendo spunto da una "legge ferrovia-
ria" del secolo scorso:

•4 " W h e n t w o trains approach each other at a crossing, b o t h shall come t o a full stop and
l ther shall start up again until the other has g o n e " Legge del Kansas •

In questo caso i due treni condividono l'incrocio.

Gli esempi nella vita quotidiana d i condivisione sono molteplici a partire da quelli d i "natura strada-
le o ferroviaria" (incroci, posteggi, ponti ecc.) a quelli di natura sociale ("lo stesso bagno", "lo stesso
tetto", "la stessa bandiera", "la stessa causa", la stessa opinione" ecc.).

Possiamo dire che condividere è sinonimo d i " a v e r e in comune" e quando parliamo di risorse d i
elaborazione intendiamo dispositivi hardware o componenti software che devono essere assegnati
alternativamente ai singoli processi che le richiedono.

È quindi necessaria una g e s t i o n e d e l l e risorse che può essere organizzata i n fasi, alcune delle quali
sono di natura statica e riguardano la loro assegnazione (pianificazione), mentre altre sono di natu-
ra dinamica e sono relative al loro utilizzo (controllo):
• pianificazione della organizzazione:
- allocazione;
- disponibilità;
- costo;
• controllo delle risorse:
- controllo d i accesso (locale o remoto);
- ottimizzazione;
- autenticazione;
- controllo di correttezza operazioni ed eccezioni.

Le attività sopra elencate vengono svolte dal sistema operativo e per le risorse di molteplicità finita
è necessario controllare gli accessi a ciascuna d i esse i n modo che i l loro l'utilizzo risulti costruttivo.

12
 Risorse e condivisione Lezione 2

Per ogni risorsa i l SO mette a disposizione:

I u n g e s t o r e della risorsa, che è u n programma che ne regola i l suo utilizzo;
> u n p r o t o c o l l o d i accesso alla risorsa, che consiste nella procedura con la quale un processo effet-
tua la richiesta della risorsa, la ottiene e quindi la utilizza e alla fine la rilascia affinché gli altri
processi la possano utilizzare.

• Classificazioni
Tra processi e risorse esiste u n legame molto stretto:

I I processi c o m p e t o n o nell'accesso alle , effettuando delle

g n a z i o n e d i q u a n t o gli necessita p e r p o t e r e v o l v e r e .
p e r o t t e n e r e I'

In merito alla interazione tra risorse e processi possiamo effettuare la classificazione i n base:
I al tipo d i richieste;
• alla modalità di assegnazioni;
I alla tipologia delle risorse.

Classificazione delle richieste

Le richieste possono essere classificate secondo vari criteri.

O s e c o n d o il n u m e r o :
D singola: la richiesta singola è i l caso normale e si riferisce a una singola risorsa di una classe
definita, cioè u n processo richiede una sola risorsa alla volta.
El multipla: si riferisce a una o più classi, e per ogni classe, a una o più risorse e deve essere
soddisfatta integralmente; è i l caso i n cui u n processo richieda contemporaneamente almeno
due risorse per poter evolvere.

0 s e c o n d o ¡I t i p o d i richiesta c h e e f f e t t u a n o :
D richiesta bloccante: è i l caso i n cui i l processo necessità immediatamente d i quella risorsa
e se non gli viene assegnata immediatamente (in quanto occupata e quindi già i n situazione
di utilizzo da parte d i atri processi) si sospende, passa nello stato di attesa e la sua richiesta
viene accodata e riconsiderata dal gestore di quella risorsa ogni volta che viene rilasciata dal
processo che la sta utilizzando.
0 richiesta non bloccante: i n questo caso i l processo può evolvere ugualmente e nel caso d i
mancanza di disponibilità gli viene effettuata una notifica che il processo richiedente esamina
ma continuando la sua evoluzione senza cioè sospendere la propria elaborazione.

Classificazione dell'assegnazione
L'assegnazione delle risorse avviene i n due modalità:

D statica: l'assegnazione statica d i una risorsa a un processo avviene al momento della creazione
del processo stesso e rimane a esso "dedicata" fino alla sua terminazione; l'esempio più signifi-
cativo è i l descrittore di processo oppure l'area di memoria RAM nella quale è caricato (se non
viene effettuato lo swapping);
El dinamica: è i l caso più frequente e generale nella naturale vita d i u n processo che avviene so-
prattutto per le risorse condivise che i processi richiedono durante la loro esistenza, le utilizzano
quando sono a loro assegnate e le rilasciano quando non sono più necessarie oppure alla loro
terminazione (esempio tipico sono le periferiche di I/O).

13
 Processi sequenziali e paralleli

Classificazione delle risorse

Anche le risorse possono sottostare a varie classificazioni e tra esse ricordiamo le più importanti:

© in b a s e alla mutua esclusività

D risorse seriali: è i l caso d i risorse che non possono essere assegnate a più processi contempo-
raneamente ma questi devo attendere i l loro turno per poterle utilizzare (si devono mettere
in coda, cioè i n "serie", uno dietro all'altro); questo tipo d i risorsa si dice che ha accesso m u -
tuamente esclusivo da parte dei processi, i n quanto quando ne entra i n possesso un processo
gli altri devono aspettare che questo la rilasci per poterla utilizzare. Esempi tipici d i risorsa
con accesso seriale sono le stampanti e i CD-ROM.
El risorse non seriali: ammettono l'accesso contemporaneo d i più processi e quindi possono
considerarsi risorse di molteplicità infinita, come per esempio i file a sola lettura, che possono
essere letti contemporaneamente da u n numero qualsivoglia di processi.

0 in b a s e alla modalità di utilizzo

D risorse prerilasciabili: si dice prelilasciabile o preemptable una risorsa che mentre viene uti-
lizzata da u n processo può essere "liberata", cioè può essere sottratta al processo prima che
abbia terminato di utilizzarla, senza che questo fatto danneggi i l lavoro che stava effettuando
e, pertanto, nel momento che gli viene restituita, esso può riprendere i l lavoro dal punto i n
cui è stato interrotto senza "subire danni".

I li p r o c e s s o che subisce il prerilascio f o r z a t o (o a n t i c i p a t o ) d e v e s o s p e n d e r s i ; la risorsa p r e r i -

lasciata sarà s u c c e s s i v a m e n t e restituita a q u e l p r o c e s s o che r i p r e n d e r à la sua e v o l u z i o n e dal
p u n t o in cui l'aveva i n t e r r o t t a .

Affinché una risorsa sia prerilasciabile deve avere le seguenti caratteristiche:

• i l suo stato non si modifica durante l'utilizzo;
• i l suo stato può essere facilmente salvato e ripristinato.

Gli esempi più "classici" di risorsa preemptive sono i l processore e le aree d i memoria.

Possiamo quindi definire una risorsa preemptable o rilasciabile come

RISORSA PREEMPTIVE O RILASCIABILE

Una risorsa si d i c e prerilasciabile se il suo g e s t o r e p u ò s o t t r a r l a a un p r o c e s s o p r i m a che
q u e s t o l'abbia e f f e t t i v a m e n t e rilasciata.
ti

EI risorse non prerilasciabili: una risorsa si dice non prerilasciabile o non-preemptive se una volta
assegnata a u n processo non è possibile "sottrargliela" senza che si provochi u n danno al compi-
to che esso sta eseguendo, con i l pericolo d i dover ripetere completamente la sua esecuzione.
Esempi tipici di risorse non-preemptive sono la stampante e i l masterizzatore: se interrompiamo
il processo che le sta utilizzando, molto probabilmente viene danneggiato, se non del tutto com-
promesso, i l lavoro i n fase di svolgimento.

• Grafo di Holt
Holt nel 1972 ha proposto u n sistema di rappresentazione mediante u n grafo che da lui ha preso i l
nome (grafo di Ilolt anche chiamato grafo d i allocazione risorse o grafo delle attese) che permette
di rappresentare tutte le situazioni i n cui si possono venire a trovare i processi e le richieste d i r i -
sorse, ed è particolarmente utile, come vedremo nelle prossime lezioni, per individuare situazioni
di criticità tra processi e risorse.

Risorse e processi costituiscono due sottoinsiemi e sono rappresentati mediami nodi d i due tipi:
I d i forma q u a d r a t a le risorse (o di forma r e t t a n g o l a r e nel caso d i classi di risorsa e/o con risorsa
multipla);
• d i forma rotonda (cerchi) i processi.
Tra di essi vengono effettuati collegamenti orientati medianti archi:
I l'arco che connette una risorsa a processo indica che la risorsa è assegnata al processo

©
I l'arco che connette un processo a una risorsa indica che i l processo ha richiesto la risorsa e che
non gli viene assegnata dato che al momento della richiesta questa non è disponibile.

I
In q u e s t o m o d o si realizza un g r a f o o r i e n t a t o d i r e t t o {< directed graph • ) , c o n gli archi c h e
h a n n o una sola d i r e z i o n e , e b i p a r t i t , in m o d o c h e n o n esistano archi che c o l l e g a n o n o d i
d e l l o stesso s o t t o i n s i e m e : gli archi p o s s o n o solo c o n n e t t e r e n o d i d i t i p o diver .

Se sono presenti più istanze della medesima classe di risorse, si effettua un partizione della risorsa
stessa indicando la molteplicità con dei punti all'interno del box della risorsa (Grafo di Holt generale).

Directed graphs • . The directed graphs have t w o kinds of nodes: processes, shown as cir-
I cles, and resources, shown as squares. An arc from a resource n o d e (square) t o a process node
(circle) means that the resource has previously been requested by, g r a n t e d t o , and is currently held by
that process. Holt (1972) showed how the Coffman conditions that must hold for there t o be a deadlock
I can be m o d e l e d using directed graphs. •

ESEMPIO 2
Nel primo esempio abbiamo tre processi ( p i , p2 e p3) e tre risorse ( R I , R2 ed R3) con molteplicità 1
che durante la loro evoluzione generano la seguente situazione:

PI r i c h i e d e RI / / g l i viene assegnata
P2 r i c h i e d e R2 / / g l i viene assegnata
P3 r i c h i e d e RI //NON g l i viene assegnata, P3 rimane i n a t t e s a

La rappresentazione mediante i l grafo d i Ilolt è la seguente:

15
UdA 1 Processi sequenziali e paralleli

Supponiamo ora di avere classi d i risorse con molteplicità diversa, per esempio:

• la classe R I : molteplicità 2
• la classe R2: molteplicità 1
• la classe R3: molteplicità 3

e la situazione è la seguente:

PI richiede RI //gli viene assegnata

P2 richiede RI //gli viene assegnata
P2 richiede R2 //gli viene assegnata
P2 richiede R3 //gli viene assegnata
P2 richiede R3 //gli viene assegnata
P3 richiede RI //NON g l i viene assegnata, P3 rimane i n a t t e s a
PI richiede R2 //NON g l i viene assegnata, P I rimane i n a t t e s a

Alcuni autori utilizzano una rappresentazione alternativa per indicare la molteplicità di risorsa
utilizzata/richiesta da u n processo indicando con u n numero sulla freccia i l grado di molteplicità
e all'interno della classe i l numero di risorse non ancora assegnate, cioè quante istanze di quella
classe sono ancora disponibili.

Zoom su..
FORMALISMO DEI GRAFI DI HOLT
La scrittura f o r m a l e d e i d u e s o t t o i n s i e m i d e l g r a f o d i H o l t è la s e g u e n t e :
• Set d i vertici V = P U R d o v e :
- P = { P , P i , . . . , P } (processi)
0 n

- R={Ro, Ri,...,R|J (classi d i risorse)

> Set d i archi E d o v e
- arco d i richiesta: Pi -* Rj se un processo Pj ha richiesto un'istanza d i risorsa Rj
- arco d i a s s e g n a z i o n e : Rj -* ? se un'istanza d i risorsa Rj è stata assegnata al processo P|
t

16
 È i m p o r t a n t e s o t t o l i n e a r e c o m e nei grafi d i H o l t n o n si r a p p r e s e n t i n o le richieste che p o s s o -
no essere s o d d i s f a t t e ma s o l o q u e l l e p e n d e n t i : q u i n d i le frecce uscenti d a i processi verso le
risorse i n d i c a n o le "risorse m a n c a n t i " ai processi p e r e v o l v e r e , c h e s o n o in q u e l m o m e n t o
a s s e g n a t e a d altri processi.

Riducibilità di un grafo di Holt

Spesso è utile avere una visione della situazione tra processi e risorse "spostata i n avanti nel tem-
po", cioè trasformare i l grafo d i Holt i n u n grafo chiamato ridotto nel quale sono state tolte le si-
tuazioni i n cui u n processo è i n grado di evolvere e che quindi sicuramente libererà le risorse che
sta utilizzando a favore degli altri processi: siamo nel caso i n cui u n processo non attende nessuna
risorsa e quindi graficamente ha solo archi entranti (risorse assegnate) e non ha archi uscenti ( r i -
chieste i n sospeso).

Il c o n c e t t o f o n d a m e n t a l e c h e sta alla base della r i d u z i o n e d i un g r a f o è la certezza c h e u n

processo che n o n ha b i s o g n o d i altre risorse p e r e v o l v e r e
la sua e l a b o r a z i o n e rilasciando le risorse c h e sta utilizzando e q u i n d i n o n è un o s t a c o l o p e r
i processi c h e necessitano d i q u e l l e risorse e le s t a n n o a s p e t t a n d o : s i c u r a m e n t e nel f u t u r o
p r o s s i m o le risorse saranno libere e il g r a f o ri evidenzia g i à q u e s t a situazione c h e , c o m e
v e d r e m o in s e g u i t o , sarà utile p e r c h é la m a g g i o r e a p p l i c a z i o n e d e i grafi d i è quella che
ci p e r m e t t e d i i n d i v i d u a r e situazioni critiche d i b l o c c o d e l sistema ( ).

GRAFO RIDUCIBILE
Un g r a f o d i H o l t si d i c e riducibile se esiste a l m e n o un n o d o d i t i p o processo c o n s o l o
archi e n t r a n t i .

17
Processi sequenziali e paralleli

ESEMPIO 4
Nel seguente esempio abbiamo i l processo P I che sta utilizzando tre risorse e, dato che non è i n
attesa d i altre, sta sicuramente evolvendo e, sicuramente, presto rilascerà quanto sta utilizzando:

effettuando la riduzione per PI si ottiene u n nuovo grafo dove si considera terminata l'elaborazione
di P I , si eliminano gli archi entranti e si rilasciano le risorse:

Ora anche i l processo P2 può evolvere, dato che ha tutte le risorse che gli sono necessarie, e quindi
possiamo anche effettuare la riduzione per P2, ottenendo: