Sistemi di calcolo 2

Tassonomia di Flynn

Classificazione dei calcolatori

I calcolatori possono essere classificati a seconda della molteplicità del flusso di dati e istruzioni che possono gestire contemporaneamente:

• Single Instruction Single Data (SISD) => Nessun parallelismo, istruzioni sequenziali.
• Single Instruction Multiple Data (SIMD) => Più processori eseguono la stessa istruzione su insiemi di dati differenti.
• Multiple Instruction Single Data (MISD) => Più processori eseguono diverse istruzioni su stessi dati. (Inutilizzata)
• Multiple Instruction Multiple Data (MIMD) => Più processori eseguono diverse istruzioni su insiemi di dati differenti o su stessi dati, ovvero più processi indipendenti su processori differenti. (Vedere Asymmetric multiprocessing e SMP, pagina 15)

Logical clock

Il logical clock è un algoritmo di sincronizzazione che rende possibile la coordinazione nei sistemi distribuiti tenendo conto che in molte applicazioni non è importante conoscere quando accadono determinati eventi ma l'ordine in cui questi si susseguono.

La versione implementata da Lamport utilizza un registro (software) monotono crescente assegnato ad ogni processo per individuare il susseguirsi degli eventi. Dato un evento ed L(e) il suo tempo logico:

• Se L(e) < L(e') => è avvenuto prima di e'

Algoritmi di sincronizzazione

Dati N processi, questi ripeteranno il seguente schema di codice: Uscito dal "exit protocol" il processo può rientrare infinite volte nel "trying protocol". Gli algoritmi che gestiscono l'accesso alla SC devono rispettare le proprietà:

• Mutua esclusione (ME) => Due processi non possono essere in sezione critica contemporaneamente
• No deadlock (ND) => Se un processo rimane bloccato nella trying section è perché uno o altri processi stanno uscendo dalla sezione critica (non ci sono stalli)
• No starvation (NS) => Nessun processo rimane bloccato nella trying section (extra) NS => ND

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

Protocollo:

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 processo che vi ha acceduto, indicando 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:

• ME => Si suppone per contraddizione che i e j siano in SC contemporaneamente.
  Se i è entrato in SC vuol dire che ha trovato x[j] = false, ovvero l'ha eseguita prima che j eseguisse la linea 6 e cambiasse il suo stato. Quindi i.8 -> j.6 e dato che i.6 -> i.8 implica i.6 -> j.6, per avere lo stesso risultato per j 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.
  Questo vuol dire che ogni processo appartenente a D ha y[d] = true. Supponendo i sia l'ultimo processo ad aver assegnato j per mantenerlo deve appartenere a D, altrimenti un altro processo trovando y[i] = y[k] = true 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. 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 lettura e scrittura siano operazioni atomiche.

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:

1. DOORWAY => Il processo segnala agli altri processi di esser entrato nella Doorway impostando choosing[i] = true, quindi verifica il numero di attesa maggiore e imposta il suo ad uno di più, dopodiché inizializza nuovamente choosing prima di uscire. Simile ad una panetteria dove l'ultimo arrivato prende l'ultimo numeretto.
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. Serve per assicurarsi che nessun processo sia stato schedulato tra le la L3 e la L4 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.

Dimostrazioni:

• ME => Dati 2 processi i e j se i è nella Bakery e j 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

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

Protocollo:

1. 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.
2. 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.
   • 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.

Note: Concettualmente uguale alla 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.

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.

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 base.