Programmazione parallela e concorrente

Sistemi operativi paralleli e concorrenti

1. Siano P1 e P2 due processi. Siano R1, R2, R3 tre risorse, R1 prerilasciabile mutuamente esclusiva, R2 prerilasciabile non esclusiva, R3 non prerilasciabile mutuamente esclusiva.
   P1 nel suo quanto richiede in modo bloccante sia R1, che R2, che tiene per 3 quanti.
   P2 nel suo quanto richiede in modo bloccante R2 e R3, che tiene per 2 quanti.
   Considerato che i due processi hanno uguale priorità, mostrare la tabella delle assegnazioni al termine di ogni quanto, fino a quando le risorse vengono rilasciate.
2. Siano P1,P2,P3,P4 quattro processi. Siano R1, R2 due risorse, R1 prerilasciabile e mutuamente esclusiva, R2 prerilasciabile ma non esclusiva. Ciascun processo richiede entrambe le risorse in modo bloccante, che tiene per 2 quanti. Indicare il numero di quanti che servono perchè ogni processo usi le risorse almeno 2 volte.
3. Siano P1,P2,P3,P4,P5 cinque processi.Siano R1,R2,R3,R4,R5 cinque risorse non prerilasciabili mutuamente esclusive. P1 nel suo quanto richiede R1 e R2P2 nel suo quanto richiede R2 e R3. P3 nel suo quanto richiede R3 e R4. P4 nel suo quanto richiede R4 e R5. P5 nel suo quanto richiede R5 e R1. Ogni processo quando ottiene una risorsa la tiene per due quanti. Indicare il numero dei quanti che servono perchè ogni processo usi almeno una risorsa.
4. Dati i seguenti processi P1..P4 con tempi di esecuzione [100, 130, 250, 400] e priorità [15%, 20%, 30%, 35%] calcolare i tempi effettivi di esecuzione in un sistema quad-core con quanto di 5 ms e context switch di 1ms.
5. Dati i seguenti processi P1..P4 con tempi di esecuzione [130, 90, 150] e priorità [25%, 30%, 45%] calcolare i tempi effettivi di esecuzione in un sistema quad-core con quanto di 5 ms e  context switch di 1ms.
6. Sia dato il seguente gruppo di processi con le seguenti latenze sequenziali [180, 220, 110, 190] (ms) e priorità [33%, 33%, 10%, 23%] calcolare i tempi di latenza in questi due scenari:
   • a) sistema quad-core con quanto 10ms e tempo di context switch di 0,5ms
   • b) sistema octa-core con quanto di 4ms e tempo di context switch di 1ms
7. Sia dato il seguente gruppo di processi con le seguenti latenze sequenziali [500, 800, 1300] (ms), priorità [20%, 30%, 50%] e percentuale parallelizzabile [50%, 70%, 90%] calcolare i tempi di latenza in un sistema dual-core con quanto 10ms e tempo di context switch di 0,5ms.
8. Sia dato un task con latenza in sistema monoprocessore è di 250ms di cui il 90% parallelizzabile. Calcolare, secondo la legge di Amdahl, le latenze per un sistema a 2, 4 e 8 processori e la latenza minima per infiniti processori.
9. P1, P2, P3 siano 3 processi con tempi esecuzione rispettivamente di [150, 200, 250], priorità rispettivamente di [35%, 44%, 29%]. Essi vengono eseguiti su due sistemi differenti qui sotto indicati. Calcolare il tempo di esecuzione effettivo dei processi. Calcolare il throughput.
   • a) un pc con 4 cpu ed un sistema operativo con quanto q=5ms e tempo di context switch cs=0,5ms.
   • b) un pc con 8 cpu, ed un sistema operativo con quanto q=8ms e tempo di context switch cs=1ms
10. Dato lo scenario dell’esercizio precedente, i tre processi vengono scorporati in una parte sequenziale ed una parallela come sotto indicato. Calcolare utilizzando la legge di Amdahl  (T = T_S + T_P) le singole latenze e il throughput finale.
    • P1: T_S = 100, T_P=50
    • P2: T_S = 100, T_P=100
    • P3: T_S = 100, T_P=250
11. Definire cosa sono la programmazione parallela e la programmazione concorrente, e fare un esempio di programmazione parallela ma non concorrente, ed un esempio di programmazione concorrente ma non parallela.
12. Definire il throughput e la latenza e fare un esempio concreto di utilizzo.
13. Sia dato il seguente gruppo di processi con le seguenti latenze sequenziali [500, 100, 800] (ms), priorità [30%, 10%, 60%] e percentuale parallelizzabile [50%, 10%, 90%] calcolare i tempi di latenza in un sistema dual-core con quanto 10ms e tempo di context switch di 0,5ms.
14. Al casello di Melegnano sono aperti 3 valichi del Telepass. Se ad ogni attraversamento del valico una macchina ci mette 5 secondi, indicare il numero di auto al minuto che possono essere gestite senza creare coda.
15. Indicare in cosa consiste la legge di Moore e che impatto ha avuto nell’evoluzione dell’informatica.

Programmazione concorrente

1. Spiegare in cosa consiste la fork e spiegare come viene riconosciuto il processo padre ed il processo figlio.
2. Un parcheggio ha 10 posti disponibili, con una entrata ed una uscita separate (da ciascuna passa una sola auto). Scrivere il codice del thread “auto” che cerca di entrare, si ferma per 10 minuti (usare la funzione sleep) e poi esce.
3. Sia data una funzione che calcola il prodotto di un array per uno scalare:
   void calc(int input[], int output[], int scalar, int len) {
  for (int i=0; i<len; i++) {
   output[i] = input[i] * scalar;
  }
}
   Ipotizzando di avere array di grandi dimensioni (len molto grande) e un sistema multithread, modificare la funzione per eseguire il calcolo in parallelo in un sistema multithread dove la funzione è assegnata ad un singolo thread. 
4. Sia data una funzione che calcola la somma di due array a[] e b[]
   void calc(int a[], int b[], int sum[], int len) {
  for (int i=0; i<len; i++) {
      sum[i] = a[i] + b[i];
  }
}
   Ipotizzando di avere array di grandi dimensioni (len molto grande) e un sistema multithread, modificare la funzione per farla eseguire in parallelo su più thread.
5. In un sistema operativo, i thread A (1 produttore) e B (1 consumatore) cooperano scambiandosi messaggi attraverso un array di 10 celle, ciascuna capace di contenere un valore numerico. Scrivere il codice dei due thread utilizzando i semafori (non è necessario scrivere il codice delle funzioni p e v).
6.  In un distributore di benzina ci sono delle pompe a cui accedono le automobili. Quando arriva l’autobotte per ricaricare il distributore questa aspetta che non ci sia più nessuna auto. Mentre l’autobotte ricarica il distributore non può accedere nessuna auto. Scrivere il codice dell’autobotte e dell’automobile, ipotizzando che siano dei thread.
7. Descrivere il problema del produttore e del consumatore, e come risolverlo.
8. Definire in cosa consiste il deadlock, fare un esempio e indicare una soluzione.