Che materia stai cercando?

Sistemi di calcolo 2

Appunti di Sistemi di calcolo 2 basati su appunti personali del publisher presi alle lezioni del prof. Baldoni dell’università degli Studi La Sapienza - Uniroma1, facoltà di Ingegneria dell'informazione, Corso di laurea in ingegneria informatica e automatica. Scarica il file in formato PDF!

Esame di Sistemi di calcolo docente Prof. R. Baldoni

Anteprima

ESTRATTO DOCUMENTO

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-based => il client serve solo per mostrare le informazioni, tutta la logica è affidata

al server

• Server-based => il client in questo caso si occupa anche della componente grafica ma

il resto delle operazioni viene gestito solo dal server

• Client-based => il client si occupa della grafica e delle operazioni base che però

devono comunque essere ampliate dalla componente server

• Cooperative => parte del server viene caricato sul client rendendo operazioni più

veloci 10

RPC

Trasforma l’interazione client/server in una chiamata a procedura nascondendo al

programmatore i meccanismi implementativi che la compongono, come:

- Interscambio dei messaggi

- Localizzazione del server

- Possibili protocolli differenti tra le macchine

mascheramento

Il avviene in 3 fasi:

scrittura del codice

1. Tempo di => RPC usate vengono dichiarate esplicitamente dal

programmatore attraverso import/export dalle interfacce

compilazione

2. Tempo di => durante la compilazione vengono associate le linee di

codice dello stub che permettono le operazioni standard sui dati e le chiamate al RPC

runtime-support

esecuzione

3. Tempo di => tramite RPC runtime-support vengono eseguite le funzioni

nascoste come localizzazione del server e registrazione nuovi servizi

Metodi per la localizzazione del server

- statico

Metodo => IP del server cablato nel client

- dinamico

Metodo => lo stub del client, mentre impacchetta i dati, invia

concorrentemente un broadcast richiedento l’indirizzo di una macchina in grado di

eseguire la RPC desiderata

- Name server => il collegamento tra client e server viene effettuato mediante il name

server che alla richiesta di una RPC del client consulta la sua tabella interna e gli

fornisce un server in grado di eseguirla 11

Passaggio dei parametri

Effettuato dallo stub

- Call by reference => passaggio di un puntatore (SCONSIGLIATO)

- Call by copy/restore => copia diretta dei valori

ex.

Con “call by ref” si ha “a = 5” poiché sullo stesso calcolatore si ha che x = a

e y = a quindi a = 0 + 2 + 3 = 5

Con “call by copy/restore” il risultato è randomico poichè si ha che solo x

oppure y verrà usato come valore di ritorno di a

Possibili semantiche delle RPC

- At least once => il client esegue n volte la richiesta, il server ne riceve n

- At most once => il client esegue la richiesta al massimo una volta e non è detto che

server la riceva, nel caso di più tentativi ritorna codice d’errore

- Exactly once => equivalente a chiamata locale, implica:

Server => immagazzina tutti i risultati nel logger, se la chiamata è già stata

• ricevuta riprende il risultato dal logger

Client => numera tutte le richieste e ne tiene il conto tramite il numero di

• reincarnazione che viene inviato in caso di guasto della RPC

Sottosistema di comunicazione

Il protocollo usato a livello di trasporto dalle RPC è UDP, il quale però non implementa

controlli sulla consegna dei pacchetti rendendo necessario l’utilizzo di protocolli

supplementari. (ex. BLAST, CHAN e SELECT)

ex. 12


PAGINE

24

PESO

8.12 MB

AUTORE

duke0000

PUBBLICATO

6 mesi fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica e automatica
SSD:
A.A.: 2018-2019

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher duke0000 di informazioni apprese con la frequenza delle lezioni di Sistemi di calcolo e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università La Sapienza - Uniroma1 o del prof Baldoni Roberto.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Sistemi di calcolo

Sistemi di Calcolo parte 2 - Tutta la teoria
Appunto
Sistemi di calcolo 1 (Teoria + Esercizi)
Appunto
Linguaggi e Tecnologie per il Web - Come fare gli esercizi 4, 5 e 6
Appunto
Algoritmi e Strutture Dati - Tutta la teoria e tutti i codici che servono
Appunto