-
Notifications
You must be signed in to change notification settings - Fork 0
/
challenges.txt
120 lines (110 loc) · 6.2 KB
/
challenges.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
P1: Ho usato Thread per implementare il prodotto riga-colonna.
Tutto cio' funziona. Si noti che tutti questi thread accedono
alla stessa risorsa in modo non sincrinizzato. Tuttavia non c'e'
nessun pericolo di incosistenza dei dati perche' le scritture
avvengono a indirizzi di memoria diversi (dello stesso spazio).
Il problema nasce nel momento in cui voglio inserire una lettura
della matrice a cavallo delle operazioni di prodotto.
Ho dato il compito di continuare a leggere la matrice a un altro
thread. Putroppo questo thread continuava a stampare la matrice
come se non fosse stata oggetto di nessuna modifica.
Questo accade perche' non e' stata fissata nessuna happens-before
relationships, ovvero non c'e' nessuna garanzia che le scritture
di uno statement siano visibili da un altro statement.
Ho risolto (si fa per dire) il problema mettendo in un blocco
synchronized la scrittura del risultato del prodotto riga-colonna
nella corrispondente entry della matrice; e mettendo
in un blocco synchronized la lettura della matrice. Tuttavia
poiche' non decido io l'ordine di esecuzione dei thread non e'
detto che la stampa avvenga dopo la scrittura di un entry.
Può capitare se sono sfortunato che ci sia una stampa della
matrice nulla e nella successiva tutto il risultato.
Puo' capitare addirittura di avere due stampe consecutive
dello stesso stato della matrice.
Ho provato a implementare delle stampe più granulari dello stato
della matrice usando un wait nel blocco synchronized e un
notify nel blocco synchronized del thread di stampa.
Il risultato non è stato soddisfacente perche' non e'
detto che dopo il notify vada il thread che prima era in attesa.
Il più delle volte è avvenuta una situazione di deadlock
in cui i thread dei prodotti avevano finito e il thread della
stampa è stato messo in esecuzione dopo gli altri e dunque è
andato in uno stato di attesa indefinita.
La classe 'AtomicBoolean' modella il concetto di variabile
booleana che puo' essere scritta/letta in un'operazione atomica.
Questa si e' resa necessaria per far terminare il thread
di stampa nel momento in cui tutti i thread dei prodotti
sono terminati. In generale serve per leggere dati
consistenti.
Dichiarare una variabile 'volatile' fa si che le scritture
e le letture di essa siano operazioni atomiche.
Wait è un metodo dell'oggetto. Deve essere invocato
sull'oggetto di cui il thread possiede il lock e deve essere
invocato quando si ha il lock dell'oggetto, quindi farà parte
di un blocco (o metodo) synchronized.
In realtà la stampa della matrice funziona anche se non è in
un blocco synchronized.
In realtà la stampa della matrice funziona anche se non è, la
sua reference, dichiarata volatile nella classe del prodotto.
In realtà funziona anche in modo non sincronizzato: P1 non
sussisteva. Ovviamente se non sincronizzo le operazioni di
stampa e di scrittura del prodotto, non c'e' garanzia che
quanto stampato rispecchi lo stato corrente della matrice.
Successivamente ho sostituito, nell'inizializzazione della
matrice con numeri casuali, Math.random con un oggetto della
classe Random, ciò oltre a rendere il codice più leggibile,
permette di generare uno stream di numeri casuali in modo
più efficiente (del resto e' una classe appartenente al package
util) e offre la possibilita' di gestire il tipo di numeri
casuali desiderato più comodamente.
Inoltre ho migliorato la gestione delle eccezioni degli argomenti.
In più vengono gestiti: ogni elemento non puo' avere un numero
di substring diverso da 2. Le dimensioni devono potere essere
converite in Int e nel caso non devono essere valori negativi.
Nota che le eccezioni sono catturate nello stesso metodo, nei
catch. Nota anche che NumberFormatException e' una sottoclasse
di IllegalFormatException, per questo l'ho messo per prima,
altimenti sarebbero state tutte trattata con il messaggio piu'
generale. Questo mi consente di essere piu' chiaro nella
segnalazione degli errori. Infine controllarle alla fine dello
stesso ciclo mi permette di discernere ogni possibile errore
del particolare argomento passato da linea di comando... no
non e' vero perche' quando viene lanciata un'eccezione si
scandiscono tutti gli eventuali blocchi catch alla ricerca
di uno che gestisca quella eccezione. Cio' significa che
l'esecuzione riparte dal blocco catch e al termine si passa
all'iterazione successiva del for.
P2:viene fatto il prodotto anche quando le colonne
di A sono maggiori delle righe di B. Il prodotto matriciale
e' ben definito se tali dimensioni sono uguali.
In questo caso vengono trascurate, nel prodotto, le entrate sulle
colonne di A di indice superiore a quello dell'ultima riga di B.
In sostanza e' come si facesse il prodotto tra A monca e B.
Ho risolto cio' aggiungendo un controllo.
Dopo aver usato delle variabili per misurare il tempo di esecuzione
del prodotto con un thread (il main) e con diversi thread,
sono stato sorpreso dal fatto che ci metto di meno con un
thread. Questo non dovrebbe in realta' stupirmi perche'
per ogni entrata della matrice prodotto viene creato
un thread. La gestione di troppi thread crea overhead
considerando l'inizializzazione e i frequenti context switch.
Allora ho provato a limitare il numero di thread al numero
di core disponibili sulla macchina, cosi' tutti thread che
ho creato sono in esecuzione, in modo da minimizzare i context
switch. Inizialmente l'ho fatto
in maniera molto poco efficiente perche' ciascun thread
eseguiva potenzialmente tutti i prodotti. Successivamente
ho distribuito i prodotti in un modo piu' equo
e la situazione e' migliorata. Questo mi permette
di far terminare prima l'esecuzione dei thread.
Inoltre ho rimosso l'accesso sincronizzato alla matrice
prodotto perche' creava ulteriore overhead.
Chiaramente la soluzione con i thread scala meglio per
matrici grandi.
Nota che ho inizializzato 3 thread pur avendo 4 core perche'
ho pensato di lasciarne uno al main thread e in ogni caso
dopo aver confrontato il prodotto con 4 e 3 thread e risultato
mediamente piu' veloce quello con 3.
Ho provato a usare anche quello con 2 thread ma e' più veloce
solamente se le dimensioni sono piccole.
In realta' con 4 scala meglio, per grandi dimensioni meglio 4.