Risorse e condivisione

I processi sono i programmi in evoluzione. Per poter evolvere hanno bisogno delle risorse del sistema di elaborazione: si pu immaginare il sistema di elaborazione come composto da un insieme di risorse da assegnare ai processi affinch questi possano svolgere il proprio compito
Si pu definire risorsa: ogni componente, riusabile o no, sia hardware che software, necessario al processo o al sistema

Per accedere alle risorse i processi sono in competizione in quanto spesso esse non sono sufficienti per tutti e pertanto risulta necessaria una forma di condivisione affinch tutti possano utilizzarle; per esempio, i processi competono per avere a disposizione la RAM e per utilizzare linterfaccia di rete e soprattutto il processore Le risorse disponibili possono essere suddivise in classi e le risorse appartenenti alla stessa classe sono equivalenti, come per esempio i bytes della memoria o stampanti dello stesso tipo
Risorse
Suddivisione in classi Classe

Classe Classe Classe

Classe Classe

Classe

Classe e istanze
Le risorse di una classe vengono dette istanze della classe Il numero di risorse in una classe viene detto molteplicit di una risorsa Quando un processo necessita di una risorsa generalmente non pu chiedere una particolare risorsa ma soltanto una istanza di una specifica classe: quindi una richiesta di risorse viene fatta per una classe di risorse e pu essere soddisfatta da parte del SO assegnando al richiedente una qualsiasi istanza di quel tipo
Risorse
Classe Suddivisione in classi

Istanze

In altre parole, la molteplicit di una risorsa indica il numero massimo di processi che la possono utilizzare contemporaneamente: se il numero dei processi maggiore di quello della molteplicit allora essa deve essere condivisa tra i processi che vi accedono concorrentemente

Esempio
In un pc presente un solo microprocessore e di conseguenza la molteplicit della sua risorsa uguale ad uno: il numero massimo di processi che possono evolvere contemporaneamente pertanto uno e quando si ha la necessit di far evolvere pi processi assieme questi condividono lunica istanza della risorsa e competono per ottenerla

Per risorse di elaborazione condivise si intendono dispositivi assegnati alternativamente ai singoli processi che le richiedono
Risulta quindi necessaria una gestione delle risorse che pu essere organizzata in fasi, alcune delle quali sono di natura statica e riguardano la loro assegnazione (pianificazione) mentre altre sono di natura dinamica e sono relative al loro utilizzo (controllo) Le attivit elencate sopra vengono svolte dal SO e per le risorse di molteplicit finita necessario controllare gli accessi a ciascuna di esse in modo che il loro utilizzo sia costruttivo Per ogni risorsa il SO mette a disposizione

un gestore della risorsa: programma che ne regola lutilizzo

protocollo di accesso alla risorsa: procedura con la quale un processo effettua la richiesta della risorsa, la ottiene, la utilizza e la rilascia affinch possa essere utilizzata da altri processi

Classificazione delle richieste

I processi competono nellaccesso alle risorse, effettuando delle richieste per ottenere lassegnazione di quanto gli necessita per evolvere Classificazione delle richieste Secondo il numero Singola: il caso riferito alla singola risorsa di una classe definita, il processo richiede una singola risorsa alla volta
Una risorsa alla volta

multipla: si riferisce a una o pi classi e per ogni classe a una o pi risorse e deve essere soddisfatta integralmente; esso il caso in cui il processo richiede contemporaneamente almeno due risorse per evolvere
Almeno due risorse

Classificazione delle richieste

Secondo il tipo di richiesta Bloccante: il caso in cui il processo necessita immediatamente di quella risorsa e se non gli viene assegnata immediatamente si sospende, passa nello stato di attesa e la sua richiesta viene accodata e considerata nuovamente dal gestore della risorsa ogni volta che essa viene rilasciata dal processo che la sta utilizzando Non bloccante: caso in cui viene effettuata una notifica di non disponibilit di una risorsa ma il processo continua la propria elaborazione anche in mancanza di essa

Classificazione dellassegnazione
Lassegnazione delle richieste avviene in due modalit Statica: essa avviene nel momento della creazione di un processo stesso e rimane ad esso dedicata fino alla sua terminazione Dinamica: caso in cui i processi utilizzano le risorse che vengono loro assegnate e le rilasciano quando non sono pi necessarie (avviene soprattutto quando le risorse sono condivise)

Classificazione delle risorse

In base alla mutua esclusivit Seriali: il caso delle risorse che non possono essere assegnate a pi processi contemporaneamente ma ognuno di essi deve attenderne la disponibilit (coda dei processi, come ad esempio le stampanti o i cd-rom) Non seriali: ammettono laccesso contemporaneo di pi processi e quindi possono considerarsi di molteplicit infinita (ad esempio i file di lettura)

Classificazione delle risorse

In base alla modalit di utilizzo Risorse prerilasciabile: viene detta prerilasciabile o preemptable una risorsa che mentre viene utilizzata da un processo pu ad esso essere sottratta prima che abbia terminato di utilizzarla, senza che ci danneggi il lavoro che sta effettuando, riprendendo il lavoro dal punto in cui stato interrotto nel momento in cui gli viene restituita Risorse non prerilasciabili: non prerilasciabili o nonpreemptable sono risorse che una volta assegnate ad un processo non possono essere ad esso sottratte senza provocare un danno al compito che stava eseguendo (esempio masterizzatore)

Grafo di Holt
Il grafo di Holt (1972), detto anche grafo di allocazione risorse o grafo delle attese, permette di rappresentare tutte le situazioni in cui si possono venire a trovare i processi e le richieste di risorse. Esso particolarmente utile al fine di individuare situazioni di criticit tra processi e risorse
Nel grafo di Holt risorse e processi costituiscono due sottoinsiemi e sono rappresentati mediante nodi di due tipi:

di forma quadrata le risorse (o di forma rettangolare nel caso di classi di risorsa e/o con risorsa multipla);
di forma rotonda i processi

Risorse e processi del grafo di Holt vengono collegati mediante frecce la freccia che connette una risorsa al processo indica che la risorsa assegnata al processo
R R
P

la freccia che connette un processo ad una risorsa indica che il processo ha richiesto la risorsa e che non gli viene assegnata poich al momento della richiesta non disponibile
P R

Il grafo di Holt cos ottenuto orientato diretto (directed graph), con le frecce che hanno una sola direzione, e bipartito, in modo che non esistano frecce che collegano nodi dello stesso sottoinsieme: esse possono solo connettere nodi di diverso tipo Se sono presenti pi istanze della medesima classe di risorse si effettua una ripartizione della risorsa indicando la molteplicit con dei punti allinterno del box della risorsa (Grafo di Holt generale)

Esempio
P1 richiede R1 P2 richiede R2 // gli viene assegnata // gli viene assegnata R1 R2 R3

P3 richiede R1

// non gli viene assegnata P1 P2

P3

Esempio grafo di Holt

Si supponga di avere classi di risorse con molteplicit diversa, come
classe R1 con molteplicit 2; classe R2 con molteplicit 1; classe R3 con molteplicit 3 e la situazione sia P1 richiede R1 P2 richiede R1 // gli viene assegnata // gli viene assegnata

P2 richiede R2
P2 richiede R3 P2 richiede R3 P3 richiede R1 P1 richiede R2

// gli viene assegnata

// gli viene assegnata // gli viene assegnata // non gli viene assegnata, rimane in attesa // non gli viene assegnata, rimane in attesa

Esempio grafo di Holt

Allora la rappresentazione mediante il grafo di Holt diventa

R1

R2

P1

P2

P3

R3

Si nota come nei grafi di Holt le frecce uscenti dai processi non rappresentano le richieste che possono essere soddisfatte ma soltanto quelle pendenti: esse infatti indicano quelle mancanti ai processi per evolvere, poich assegnate ad altri

Riducibilit di un grafo di Holt

Il concetto fondamentale che sta alla base della riduzione di un grafo di Holt la certezza che un processo, per evolvere, prima o poi terminer sicuramente la sua elaborazione rilasciando le risorse che sta utilizzando e quindi non un ostacolo per quei processi che utilizzano la stessa risorsa e la stanno aspettando: le risorse diventeranno libere e il grafo ridotto evidenzia questa situazione. Esso risulta utile perch permette di individuare situazioni critiche di blocco del sistema (stallo) Il grafo ridotto ottenuto eliminando le situazioni in cui un processo in grado di evolvere e in cui liberer le risorse che sta utilizzando a favore di altri processi: un processo non attende nessuna risorsa e ha pertanto solo frecce entranti nei processi (risorse assegnate) senza quelle uscenti (risorse in sospeso)
Un grafo di Holt si dice riducibile se esiste almeno un nodo di tipo processo con solo frecce entranti

Esempio grafo di Holt ridotto

Si supponga di avere classi di risorse con molteplicit diversa, come
classe R1 con molteplicit 3; classe R2 con molteplicit 1; e la situazione sia P1 richiede R1 P1 richiede R1 P1 richiede R2 // gli viene assegnata // gli viene assegnata // gli viene assegnata

P2 richiede R1
P2 richiede R2

// gli viene assegnata

// non gli viene assegnata, rimane in attesa

Esempio grafo di Holt ridotto

Si ha che al processo P1 sono associate tre risorse e, dato che non in attesa di altre, sta evolvendo, quindi presto lascer quelle che sta utilizzando
R1

P1

P2

R2

Effettuando una riduzione per P1 si ottiene un nuovo grafo di Holt, nel quale si considera terminata lelaborazione di P1: vengono eliminate le frecce entranti in 1 e di conseguenza si rilasciano le corrispondenti risorse utilizzate

Esempio grafo di Holt ridotto

Riducendo rispetto a P1 allora:

R1

P1

P2

R2

Adesso anche il processo P2 in grado di evolvere, dal momento che ha tutte le risorse che gli sono necessarie, e quindi possibile continuare riducendo per P2

Esempio grafo di Holt ridotto

Riducendo poi rispetto a P2 si ottiene:

R1

P1

P2

R2

La successiva applicazione delle riduzioni ha portato ad un grafo di Holt ridotto nella quale non si individuano situazioni critiche per il sistema (nessuno stallo)
Come detto in precedenza, il grafo di Holt di partenza era riducibile e questo poich aveva almeno un nodo di tipo processo con solo frecce entranti

Verifica per casa

Dato il grafico di Holt della figura sottostante:

R1

R2
Gruppo 1

P1

P2

P3

R3

1. indicare per quale processo possibile farne una riduzione

2. rappresentare il grafo di Holt ridotto 3. rappresentare levoluzione della riduzione del grafo di Holt in Java 4. Indicare la condizione in cui il grafo di Holt non potrebbe essere ridotto

Verifica per casa

Dato il grafico di Holt della figura sottostante:

R1

R2
Gruppo 2

P1

P2

P3

R3

1. indicare per quale processo possibile farne una riduzione

2. rappresentare il grafo di Holt ridotto 3. rappresentare levoluzione della riduzione del grafo di Holt in Java 4. Indicare la condizione in cui il grafo di Holt non potrebbe essere ridotto

Verifica per casa

Dato il grafico di Holt della figura sottostante:

R1

R2
Gruppo 3

P1

P2

P3

R3

1. indicare per quale processo possibile farne una riduzione

2. rappresentare il grafo di Holt ridotto 3. rappresentare levoluzione della riduzione del grafo di Holt in Java 4. Indicare la condizione in cui il grafo di Holt non potrebbe essere ridotto

Verifica per casa

Dato il grafico di Holt della figura sottostante:

R1

R2
Gruppo 4

P1

P2

P3

R3

1. indicare per quale processo possibile farne una riduzione

2. rappresentare il grafo di Holt ridotto 3. rappresentare levoluzione della riduzione del grafo di Holt in Java 4. Indicare la condizione in cui il grafo di Holt non potrebbe essere ridotto

Verifica per casa

Dato il grafico di Holt della figura sottostante:

R1

R2

P1

P2

P3

R3

Indicare se possibile farne una riduzione

Un grafo di Holt si dice riducibile se esiste almeno un nodo di tipo processo con sole frecce entranti

Elaborazione sequenziale e concorrente

Una elaborazione sequenziale tale quando svolge una sola azione alla volta sulla base di un programma, detto anchesso sequenziale Con il termine elaborazione sequenziale si intende lesecuzione di un programma sequenziale che genera un processo sequenziale con ordinamento totale alle azioni che vengono eseguite

Lelaborazione sequenziale pertanto un concetto fondamentale nellinformatica in quanto gli algoritmi computati sono composti da una sequenza finita di istruzioni in corrispondenza delle quali, durante la loro esecuzione, lelaboratore passa attraverso una sequenza di stati (traccia dellesecuzione)

Non tutti gli elaboratori hanno una singola CPU e inoltre alcune attivit del processore possono essere parallelizzate, come per esempio le lunghe fasi di input che provocano enorme spreco di tempo macchina nei processi ad alta interattivit con lutente, applicazioni che per loro natura necessitano di attivit parallele come i server, i games multiplayer, e per essi la codifica sequenziale delle attivit propria della programmazione sequenziale non in grado di adempiere opportunamente alle presenti situazioni.

Esse necessitano di un diverso modello in grado di effettuare la programmazione di un esecutore concorrente, ovvero un elaboratore in grado di eseguire pi istruzioni in contemporanea

Per programmazione concorrente si indicano le tecniche e gli strumenti impiegati per descrivere il comportamento di pi attivit o processi che si intende far eseguire contemporaneamente in un sistema di calcolo (processi paralleli)

In realt si nella situazione di elaborazione contemporanea reale soltanto nel caso in cui lesecutore sia dotato di una architettura multiprocessore, cio con pi processori che possono eseguire ciascuno un singolo programma: nei sistemi monoprocessore il parallelismo avviene solo virtualmente, grazie alla multiprogrammazione, e pi processi evolvono in parallelo solo attraverso il tempo che viene loro assegnato dallo scheduling del SO

Il SO per eccellenza lesempio di programmazione concorrente: esso infatti assegna le risorse hardware dellelaboratore ai processi utente che ne fanno richiesta e uso cercando di massimizzarne lefficienza nella loro utilizzo. Le attivit del SO devono essere eseguite concorrentemente in modo da consentire lesecuzione contemporanea di pi programmi utente: ogni attivit interagisce con le altre sia in modo indiretto, occupando le risorse comuni, sia in modo diretto, scambiando informazioni in merito allo stato delle risorse e dei programmi utente per realizzare la multiprogrammazione In un sistema multiprogrammato i programmi dutente e le singole funzioni svolte dal SO possono essere considerati come un insieme di processi che competono per le stesse risorse

Quindi per sistema concorrente si intende un sistema software implementato su vari tipi di hardware che evolve in contemporanea una molteplicit di attivit diverse, tra loro correlate, che possono cooperare ad un obiettivo comune oppure possono competere per utilizzare risorse diverse due processi si dicono concorrenti se la prima operazione di uno di essi ha inizio prima del completamento dellultima operazione da parte dellaltro
P1 Software
Hardware Hardware Hardware Hardware

P2

P3

Sistema concorrente

Processi non sequenziali e grafo di precedenza

Nei processi sequenziali la sequenza degli eventi che costituisce il processo totalmente ordinata: se viene rappresentata attraverso un grafo orientato si ottiene che essa risulter sempre la stessa Un grafo che descrive lordine con cui le azioni (o gli eventi) si eseguono nel tempo viene detto grafo delle precedenze Nei processi paralleli, invece, lordinamento non completo poich per alcune istruzioni lesecutore libero di scegliere quali iniziare prima e quali dopo senza che il risultato sia compromesso: nella elaborazione parallela lesecuzione delle istruzioni segue un ordinamento parziale

In un processo sequenziale il grafo delle precedenze degenera in una lista ordinata mentre nel processo parallelo diventa una grafo orientato aciclico e i percorsi alternativi indicano la possibilit di esecuzione contemporanea di pi istruzioni Per la descrizione del grafo delle precedenze si usano i simboli:
A Attivit (istruzione o sequenza di istruzioni) Vincolo di precedenza A B Attivit seriale (B inizia dopo il termine di A)

B A C B A C

Le attivit B e C possono essere eseguite in parallelo dopo il termine dellattivit A

Lattivit A pu essere eseguita solo dopo il completamento di B e C che sono in parallelo

Esempio grafo delle precedenze

Esempio di algoritmo che legge tre numeri e ne individua il maggiore. Per prima cosa necessario scrivere il codice sequenziale dellalgoritmo

Inizio

1. Leggi x; 2. Leggi y; 3. Leggi z; 4. K = max(x;y) 5. K = max(k;z) 6. Scrivi K

Fine

Riportando le istruzioni del grafo per lesecuzione si osserva che: leggi x e leggi y non devono essere eseguite per forza in questo ordine ma potrebbero anche essere eseguite in parallelo; anche la lettura di z, inoltre, pu essere eseguita dopo listruzione 4 oppure in parallelo con essa. Le istruzioni 5 e 6 chiudono sempre la sequenza

Esempio grafo delle precedenze

Il grafo delle precedenze diventa Inizio

Leggi x

Leggi y

K = max (x,y)

Leggi z

K = max (k,z)

Scrivi k

Fine

Esempio grafo delle precedenze

Esso non per lunico grafo delle precedenze possibile per lalgoritmo in questione
Inizio

Leggi x

Leggi y

Leggi z

K = max (x,y)

Infatti la lettura di z potrebbe essere eseguita dal ramo che effettua quella di x e il calcolo del max tra x ed y al suo posto,

K = max (k,z)

Scrivi k

ottenendo un altro grafo

comunque corretto

Fine

Esempio grafo delle precedenze

I grafi ottenuti sono quindi grafi a ordinamento parziale; se essi vengono posti uno accanto allalto si nota infatti che a differenza dei processi sequenziali, in un processo parallelo possibile scegliere quali attivit iniziare prima senza che il risultato sia compromesso
Inizio Inizio

Leggi x K = max (x,y)

Leggi y

Leggi x Leggi z

Leggi y
K = max (x,y)

Leggi z

K = max (k,z)

K = max (k,z) Scrivi k Fine

Scrivi k
Fine