Sistemi di calcolo 2

OSS

Algoritmo di Dijkstra

Assunzioni:

- I processi comunicano leggendo e scrivendo variabili comuni

- Lettura e scrittura di una variabile sono azioni atomiche

Non ci sono assunzioni sul tempo richiesto per un operazione 2

Protocollo: i k i, k

1. Ciclo while (sentinella) => il processo tenta di impostare al suo id essendo

variabile condivisa tra i processi vale solo l’ultimo cambiamento effettuato dell’ultimo

k

processo che vi ha acceduto => indica l’ultimo valore, corrispondente al numero del

processo, uscito dal ciclo.

2. Ciclo for => controlla che non ci siano stati passaggi concorrenti attraverso il primo

ciclo testando che x[j] = false per ogni altro processo

Dimostrazioni: i j

ME => si suppone per contraddizione che e sono in SC contemporaneamente.

i x[j] = false

Se è entrato in SC vuol dire che ha trovato in linea 8, ovvero l’ha

j

eseguita prima che eseguisse la linea 6 e cambiasse il suo stato.

(a -> b indica che a è avvenuto prima di b)

Quindi i.8 -> j.6 e dato che i.6 -> i.8 implica i.6 -> j.6, per avere lo stesso risultato

j

per si dovrebbe avere j.6 -> i.6 e quindi i.6 -> i.6 => CONTRADDIZIONE

ND => si suppone per contraddizione di avere un insieme D di processi in deadlock.

d

Questo vuol dire che ogni processo appartenente a D ha y[d] = true.

i k,

Supponendo che sia l’ultimo processo ad aver assegnato per mantenerlo

j

deve appartenere a D, altrimenti un altro processo trovando y[i] = y[k] = true

k.

setterebbe nuovamente d

Così facendo prima o poi ogni processo in D/{i} avrà x[d] = false e si bloccherà

nel ciclo while, ma questo implica che il processo i, saltato il while poiché vale

ancora i = k, entrerà sicuramente in SC poiché tutti i valori x[d] = false.

i

MA se entra in SC non può appartenere a D => CONTRADDIZIONE

NS => non supportata da questo algoritmo

note:

Questo algoritmo può essere realmente implementato solo su architetture a singolo

processore poiché nel caso di architetture multiprocessore non si può garantire che le

operazioni di letture e scrittura e siano operazione atomiche 3

Algoritmo del panettiere di Lamport

Assunzioni:

- lettura e scrittura NON sono operazioni atomiche

- Ogni variabile condivisa è di proprietà di un processo e solo lui può scriverci, gli altri

possono solo leggerla

- Nessun processo può emettere 2 scritture insieme

- Le velocità dei processori non sono correlate

Protocollo: i

1. DOORWAY => il processo segnala agli altri processi di esser entrato nella Doorway

impostando choosing[i] = true, quindi verifica il numero di attesa maggiore ed imposta

il suo ad uno di più, dopodiché inizializza nuovamente choosing prima di uscire

OSS simile ad una panetteria dove l’ultimo arrivato prende l’ultimo numeretto

i

2. BAKERY => il ciclo for permette di assicurarsi che il processo sia il prossimo a dover

accedere alla sezione critica, tramite:

• While L6 => controlla che nessun altro processo stia eseguendo operazioni di

scrittura, permette quindi a tutti i processi di terminare la Doorway correttamente.

j

Serve per assicurarsi che nessun processo sia stato schedulato tra le la L3 e la L4

i.

e quindi abbia in realtà un numero di attesa minore di quello di

• i

While L7 => pone in attesa il processo finché questo non arriva ad avere il

numero d'attesa più piccolo, se due processi hanno lo stesso numero passa prima

quello con ID più piccolo 4

Dimostrazioni: i j, i j

ME => dati 2 processi e se è nella Bakery e nella Doorway allora vale la proprietà

{num[i],i} < {num[j],j}, quindi ipotizzando per assurdo che entrambi si trovino in SC

si avrebbe che {num[i],i} < {num[j],j} e {num[j],j} < {num[i],i} contemporaneamente

=> ASSURDO

ND => data da NS => ND

NS => num garantisce che prima o poi ogni processo entrerà in SC

Note:

Questo algoritmo inoltre gode della proprietà SCFS (first-come-first-served)

Algoritmo di Lamport per sistemi distribuiti 5

Assunzioni:

lettura e scrittura NON sono operazioni atomiche

• Ogni variabile condivisa è di proprietà di un processo e solo lui può scriverci, gli altri

• possono solo leggerla

Nessun processo può emettere 2 scritture insieme

• Le velocità dei processori non sono correlate

•

- I processi leggono e scrivono messaggi attraverso il message passing con un ritardo

indefinito ma comunque finito

- I canali sono affidabili, ogni messaggio arriva a destinazione

Per lo più uguali a versione base

Protocollo: i

I. DOORWAY => il processo segnala agli altri sistemi di esser entrato nella Doorway

impostando il suo choosing = true, quindi richiede a tutti gli altri sistemi i numeri

d’attesa ed imposta il suo ad uno di più del maggiore, dopodiché inizializza

nuovamente choosing prima di uscire i

II. BAKERY => il ciclo for permette di assicurarsi che il processo sia il prossimo a dover

accedere alla sezione critica, tramite:

• L10 - L13 => controlla che nessun altro processo stia eseguendo operazioni di

scrittura, permette quindi a tutti i processi di terminare la Doorway correttamente.

j

Serve per assicurarsi che nessun processo sia stato schedulato tra le la L3 e la L4

i.

e quindi abbia in realtà un numero di attesa minore di quello di

• i

L14 - L17 => pone in attesa il processo finché questo non arriva ad avere il

numero d'attesa più piccolo, se due processi hanno lo stesso numero passa prima

quello con ID più piccolo

OSS Concettualmente uguale a versione base ma con l’aggiunta di funzioni send e

receive per effettuare lo scambio dei messaggi che potrebbero rallentare notevolmente le

interazioni, inoltre implica la creazione di thread concorrenti per le interazioni multiple

Note: i

Detto non cooperante poiché ad ogni interazione il processo generico (server), che vuole

definire il proprio numero d’attesa, invia e riceve dati da ogni altro processo nel sistema

(clients) che però non hanno alcun ruolo attivo nella scelta.

Questo scambio non cooperante implica un rallentamento notevole dell’algoritmo, può

essere quindi ottimizzato tramite una versione decentralizzata peer-to-peer come

l’algoritmo di Ricart-Agrawala 6

Algoritmo di Ricart-Agrawala

Assunzioni:

lettura e scrittura NON sono operazioni atomiche

• Ogni variabile condivisa è di proprietà di un processo e solo lui può scriverci, gli altri

• possono solo leggerla

Nessun processo può emettere 2 scritture insieme

• Le velocità dei processori non sono correlate

• I processi leggono e scrivono messaggi attraverso il message passing con un ritardo

• indefinito ma comunque finito

I canali sono affidabili, ogni messaggio arriva a destinazione

•

- La linea 2 viene eseguita atomicamente

Una sola assunzione in più rispetto alla versione non cooperante 7

Protocollo:

In questa versione ogni processo invece di chiedere a tutti qual'è il numero più grande

ogni volta che vuole entrare in SC per poi calcolare il suo, trasmette direttamente il suo

numero agli altri processi utilizzando un contatore interno.

Questo è possibile poiché ad ogni richiesta da parte di un processo tutti i sistemi

aumentano il loro contatore interno.

1. L1 - L3 => una volta modificate le variabili interne il sistema invia la richiesta

contenente il suo numero agli altri sistemi

OSS aumenta num subito per evitare di perdere il posto nel caso dovesse ricevere

una richiesta da un altro processo prima di completare il suo accesso alla SC

2. L4 => il processo quindi si mette in attesa finché non riceve un REPLY da ogni altro

sistema, una volta collezionati tutti gli N-1 REPLY potrà accedere alla SC

La mutua esclusione è quindi possibile poiché nel caso un cui un processo è già in

sezione critica oppure ha un numero inferiore ritarda il REPLY finché il suo turno non è

finito, le richieste vengono inserite nella coda Q

Dimostrazione: i j i

ME => si suppone per contraddizione che e sono in SC contemporaneamente, quindi

j

ha inviato un REPLY a e viceversa. Sono quindi possibili 3 casi:

i j

1. spedisce REPLY a prima di scegliere il proprio numero in L2, poi invia una

j.

richiesta che quindi avrà un numero con valore più alto rispetto a quella di

i j

Quando la richiesta di arriva a questo la inserisce nella sua coda Q,

poiché il suo numero ha un valore più basso (oppure è in già in SC).

Di conseguenza i e j non possono essere entrambi in SC insieme.

i j

2. identico invertendo e

3. sia i che j inviano un REPLY all’altro dopo aver scelto il num, a questo punto

uno dei due invia un REPLY all’altro e l’altro lo mette in coda.

Di conseguenza i e j non possono essere entrambi in SC insieme.

ND => data da NS => ND i

NS => si suppone per contraddizione che dopo aver inviato la richiesta con il suo num

attenda indefinitivamente l’accesso alla SC.

Poiché i messaggi arrivano a destinazione in tempo finito questo vuol dire che un

set non vuoto di processi S non invia il messaggio REPLY, ma questo può

∈

j

accadere solo se esiste almeno un processo S che si trova in SC oppure ha un

numero d’attesa inferiore.

Quindi si possono avere 2 casi:

j i.

1. Nel primo caso esce dalla SC ed invia il REPLY e sbloccando

∈

2. Nel secondo esiste un altro processo k S/{j} che blocca j, quindi si crea una

versione ricorsiva del primo caso 8

La rete

Middleware

Il middleware consiste in un set di strumenti

software (API) interposti tra sistema operativo

e applicazioni che forniscono le astrazioni per

il dialogo tra sistemi eterogenei

1

Client/server computing and application

Interazione generalmente usata dai database, i dispositivi connessi sono di 2 tipi:

- Server => high performance computer che provvede allo scambio dei dati e permette

la connessione tra i client, esegue le operazioni di computazione sui dati e poi li invia al

server.

- Clients => single-user PCs che si collegano al server al quale inviano e ricevono dati,

permettono interfaccia user-friendly

OSS in alcuni casi si può avere una struttura a 3 livello che aggiunge anche un Middle-tier

server che funge da middleware e si occupa della distribuzione del carico su più server e

la protezione degli accessi

sistemi eterogenei = sistemi con hardware, sistema operativo e protocolli differenti

1 9

Classi applicazioni client/server

• Host-