1 of 67

Processi, Thread, Multitasking, Multithreading

(Thread-Fu)

Prof. Giovambattista Ianni

Corso di Sistemi Operativi

Aggiornato all’A.A. 2023-24

Quest'opera è distribuita con Licenza

Creative Commons Attribuzione - Non commerciale 4.0 Internazionale.

2 of 67

NO CHATGPT

(for dummies)

3 of 67

Ingredienti

1 CPU
1 Memoria RAM
Tanti programmi che condividono la stessa memoria

Esigenza di far girare più software «contemporaneamente» (in concorrenza)

4 of 67

Courtesy of prof. Mario Alviano

5 of 67

READ

WRITE

6 of 67

Ciclo di fetch esteso

Classic fetch

0:IR 🡨 Mem[PC]

PC 🡨 PC+1

Esegui istruzione in IR

Goto 0

Fetch con interrupt

0: IR 🡨 Mem[PC]

PC 🡨 PC+1

Esegui IR

If INTR == 1

oldPC 🡨 PC

PC 🡨 IRQR

Goto 0

IRQR = Interrupt request register: contiene l’indirizzo di memoria

dove si trova la interrupt handling routine

7 of 67

Interrupt

Usato dalle periferiche per notificare che un evento urgente deve essere gestito
Esempi:

Clic del mouse 🡪 I/O controller genera interrupt 🡪 CPU gestisce interrupt 🡪 evento clic finisce in coda eventi applicativi
Lettura da disco (vedi esempio su DMA)
Pressione di tasto
Terminazione di operazioni I/O in genere

8 of 67

DMA: Direct Memory Access

DMA: RAM accessibile da più entità, non solo la CPU

Esempio di accesso in scrittura in caso di RAM condivisa:

Ciclo di scrittura senza arbitraggio DMA

MAR 🡨 addr

M[MAR] 🡨 MBR

Ciclo di scrittura con arbitraggio DMA

MAR 🡨 addr

HOLD 🡨 1

0: if HLDA == 0

Goto 0

M[MAR] 🡨 MBR

9 of 67

READ

WRITE

10 of 67

DMA transfer

Esempio: lettura disco via DMA
A = indirizzo RAM dell’operazione DMA
L = numero di byte da trasferire
ID = ID della periferica coinvolta
S = LBA address da leggere sul disco
Operazioni di lettura

CPU imposta A, L, ID, S e invia un comando DMA Read
La periferica ID esegue la lettura e scrive quanto letto da disco su RAM in autonomia, a partire da indirizzo A
Al termine dell’operazione ID genera un interrupt
CPU gestisce questo interrupt

11 of 67

Processi e Thread

Processo:

Associato a un singolo file binario eseguibile
Ha un suo stack e un suo spazio di memoria
Associato a un insieme di thread, che condividono la stessa memoria.
NON ha accesso alla memoria degli altri processi

Thread:

ce ne è uno o più per ciascun processo �(c’è almeno un main thread)
I thread condividono le stesse risorse e la stessa memoria
I thread hanno anche un proprio stack distinto

12 of 67

Multitasking Collaborativo - I

winProc1(...)

{

... codice ...

return;

}

while(true)

{

Evento e = codaeventi.take();

call(e.destinatario.winProc);

}

Programma

Scheduler

winProcN(...)

{

... codice ...

return;

}

Programmi

Utente

13 of 67

Multitasking collaborativo - II

evento

qualcosa che è successa e che va gestita: tipicamente segnalato con un interrupt e poi depositato in una coda FIF

codaeventi

Buffer FIFO di eventi che una certa applicazione deve gestire

winprocA

Funzione associata a una certa applicazione A. Viene chiamata ogni volta che c’è da elaborare un evento destinato ad A. Il programmatore di A definisce come gestire gli eventi.

14 of 67

Multitasking collaborativo - III

Pro:

Facile da capire/programmare
Comodo per multitasking tra task I/O bound

Contro:

Una sola winproc che occupa tempo o va in loop infinito può bloccare tutto il SO/Applicazione/Tab del browser
Non sfrutta i core multipli

Oggi, evoluto in programmazione asincrona, viene usato in:

Gestione eventi in Java
Gestione eventi in Javascript
Python Async I/O

15 of 67

Multitasking Non Collaborativo

while(true)

{

Thread t = codaThreadPronti.take();

impostaTimer();

t.load();

t.exec();

t.save();

inserisci t in

codaThreadPronti

oppure in listaThreadinWait;

}

Programma

Scheduler

16 of 67

Multitasking Non Collaborativo

CodaThreadPronti

FIFO dei thread in stato di «Ready»

ListaThreadInWait

Insieme dei thread in stato di «Wait»

17 of 67

load() e save()

save(): scatta una “fotografia” del thread nel momento in cui si è sospeso, e la salva in memoria (TSS in Intel x86)
load(): carica da memoria il TSS di un thread

EAX = CCCCCCCC EBX = 7FFD8000

ECX = 00000000 EDX = 00141F25

ESI = 00000000 EDI = 0012FF30

EIP = 00401028 ESP = 0012FEE4

EBP = 0012FF30 EFL = 00000206

CS = 001B DS = 0023 ES = 0023

SS = 0023 FS = 003B GS = 0000 OV=0

UP=0 EI=1 PL=0 ZR=0 AC=0 PE=1 CY=0

ST0 = +0.00000000000000000e+0000

ST1 = +0.00000000000000000e+0000

ST2 = +0.00000000000000000e+0000

ST3 = +0.00000000000000000e+0000

ST4 = +0.00000000000000000e+0000

ST5 = +0.00000000000000000e+0000

ST6 = +0.00000000000000000e+0000

ST7 = +0.00000000000000000e+0000

CTRL = 027F STAT = 0000 TAGS = FFFF

EIP = 00000000 CS = 0000 DS = 0000

EDO = 00000000

18 of 67

Che cosa avviene in exec()

EIP registro analogo a PC
assegna EIP = TSS.EIP (analogo a B TSS.EIP)
Esecuzione del codice del thread selezionato
exec() Termina quando:

scade il timer, oppure
il thread va spontaneamente in stato di wait

19 of 67

Stato di ogni thread

Ready

Waiting

Running

Ready: pronto ad essere eseguito

Running: in esecuzione

Waiting: non può essere eseguito, in attesa di un evento esterno

20 of 67

Passaggi di stato

Ready -> Running

Prelevato dalla coda ed eseguito

Ready

Waiting

Running

Waiting -> Ready

Ritorno da una call “bloccante”

Running -> Waiting

Invocazione di una call “bloccante”

Running -> Ready

Time out, cessazione volontaria

21 of 67

Comportamento dei thread

Thread di tipo I/O bound

Usa poco la CPU, spende molto tempo in attesa di eventi esterni. Si trova quasi sempre in stato di wait

Thread di tipo CPU bound

Usa molto la CPU. Si trova quasi sempre in stato di ready

Ovviamente un thread, nell’arco della propria esistenza, può cambiare comportamento a seconda del suo codice

22 of 67

Windows 2000-XP-Vista-7-8-10-11

32 Code

assegnazione del tempo a punti: 6 punti a testa = 1 timeslice
si guardano le code dalla 31 alla 0
possibilità di starvation
meccanismi di promozione da una coda a un’altra
meccanismo di aumento dei punti
Il time-slicing è per thread non per processo!

23 of 67

24 of 67

Linux

Normal process: priorità 100..139

nice level : -20 .. +19

Real-time process: 1 .. 99

Static and dinamic priority
Scheduling types: SCHED_FIFO, SCHED_RR, SCHED_OTHER (CFS, the completely fair scheduler)

25 of 67

“I thread non servono a niente”

Scherzavo

26 of 67

Problemi di inconsistenza - 1

int posto[100];

int allocaposto(int p, int codiceutente)

{

if (!posto[p])

return posto[p] = codiceutente;

else

return 0;

}

27 of 67

Problemi di inconsistenza - 2

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

0

Assembly

x86

28 of 67

Problemi di inconsistenza - 2

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

0

Assembly

x86

29 of 67

Problemi di inconsistenza - 2

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

27049

Assembly

x86

30 of 67

Problemi di inconsistenza - 2

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

27049

11051

Assembly

x86

31 of 67

Problemi di inconsistenza - 2

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

10: {

...

11: if (!posto[p])

mov eax,dword ptr [ebp+8]

cmp dword ptr [eax*4+4237A4h],0

jne allocaposto+37h (0040b7e7)

return posto[p] = codiceutente;

mov ecx,dword ptr [ebp+8]

mov edx,dword ptr [ebp+0Ch]

mov dword ptr [ecx*4+4237A4h],edx

mov eax,dword ptr [ebp+0Ch]

jmp allocaposto+39h (0040b7e9)

13: else

14: return 0;

0040B7E7 xor eax,eax

15: }

0040B7E9 pop edi

0040B7EA pop esi

0040B7EB pop ebx

0040B7EC mov esp,ebp

0040B7EE pop ebp

0040B7EF ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

11051

Assembly

x86

32 of 67

Esempio con assembly ARM

Quest'opera è distribuita con Licenza

Creative Commons Attribuzione - Non commerciale 4.0 Internazionale.

33 of 67

Problemi di inconsistenza - 2

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

0

Assembly

ARM64

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

34 of 67

Problemi di inconsistenza - 2

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

0

Assembly

ARM64

35 of 67

Problemi di inconsistenza - 2

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

27049

Assembly

ARM64

36 of 67

Problemi di inconsistenza - 2

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

10: {

...

if (!posto[p])

4006b8: adrp x0, 489000 <_dl_main_map+0xc0>

4006bc: add x0, x0, #0x9c0

4006c0: ldrsw x1, [sp, #12]

4006c4: ldr w0, [x0, x1, lsl #2]

4006c8: cmp w0, #0x0

4006cc: b.ne 4006f8 <_Z11allocapostoii+0x4c>

return posto[p] = codiceutente;

4006d0: adrp x0, 489000 <_dl_main_map+0xc0>

4006d4: add x0, x0, #0x9c0

4006d8: ldrsw x1, [sp, #12]

4006dc: ldr w2, [sp, #8]

4006e0: str w2, [x0, x1, lsl #2]

4006e4: adrp x0, 489000 <_dl_main_map+0xc0>

4006e8: add x0, x0, #0x9c0

4006ec: ldrsw x1, [sp, #12]

4006f0: ldr w0, [x0, x1, lsl #2]

4006f4: b 4006fc <_Z11allocapostoii+0x50>

else

return 0;

4006f8: mov w0, #0x0

}

4006fc: add sp, sp, #0x10

400700: ret

allocaposto(3,27049)

allocaposto(3,11051)

Posto 3

27049

11051

Assembly

ARM64

37 of 67

Voglio vedere il codice misto anche io!

gcc –g miosorgente.cpp

objdump –S miobinario

�Per aarch64 usare l’accoppiata:

aarch64-linux-gnu-gcc

aarch64-linux-gnu-objdump

38 of 67

Race condition

Situazione in cui due o più thread “competono” senza controllo o disciplina nel modificare o leggere contemporaneamente gli stessi dati

🡪RISULTATI IMPREDICIBILI

Un software che consente race condition incontrollate

non è “Thread-safe”

Un programmatore che non sa gestire le race condition non è un bravo programmatore

39 of 67

Esempi di race condition

def bonifico(A : conto, B : conto, s : int):

A.saldo += s

B.saldo -= s

40 of 67

41 of 67

RARO? Seriamente, RARO?

42 of 67

Ho detto che vi troverò

43 of 67

44 of 67

Paradosso del compleanno

Sito web con N oggetti distinti disponibili
Utenti online in contemporanea necessari ad avere Prob di conflitto >50% = SQRT(N)
Esempio: 365 oggetti 🡪 con 23 persone >50%

45 of 67

Master of race conditions:�Costrutti di sincronizzazione storici

Spinlock
Test & Set
Monitor
Semafori
Lock

46 of 67

Lock e blocchi synchronized

Un lock può essere posseduto da un thread alla volta.
Ogni lock può essere occupato o libero.
acquire(): se il lock è libero, acquisisce il lock e lo marca come occupato. Se un thread T cerca di prendere il possesso di un lock già occupato, T viene posto in stato di Wait.
release(): quando un lock viene liberato, uno tra i thread in Wait sullo stesso lock viene svegliato e posto in stato di «ready» (prenderà probabilmente il possesso del lock); non è garantito che l’ordine di risveglio sia FIFO a meno che l’implementazione del lock non sia esplicitamente di tipo fair (es. FairLock di Java).
Lock rientrante: un thread che possiede un lock rientrante può riacquisirlo quante volte vuole senza bloccarsi (e cioè può invocare acquire()tante volte di fila).
Lock non rientrante: un thread che possiede un lock entra in ciclo di attesa infinito se prova ad acquisire un lock che già possiede (e cioè se invoca acquire() due volte di fila).
(Java) Ogni ISTANZA di classe possiede un UNICO lock nascosto usabile facendo uso di metodi synchronized o blocchi synchronized;

47 of 67

Condition: notify() e wait()

Per ogni lock L, esiste un insieme di thread in attesa di acquisire L (WAIT-L)
Per ogni condition C esiste un insieme di thread in attesa su tale condition (WAIT-C)
Ogni condition C ha un lock padre (uno solo);
C.wait(): libera il lock di appartenenza e pone il thread chiamante in stato di attesa su WAIT-C;
C.notify(): prende un thread scelto in maniera IMPREDICIBILE da WAIT-C e lo sposta in WAIT-L;
C.notify_all(): prende tutti i thread presenti in WAIT-C e li sposta in WAIT-L
NON E’ POSSIBILE chiamare wait(), notify() e notify_all() se non si possiede il lock corrispondente;

48 of 67

Blocking queues

Quest'opera è distribuita con Licenza

Creative Commons Attribuzione - Non commerciale 4.0 Internazionale.

49 of 67

50 of 67

51 of 67

Buffering

52 of 67

Riflessioni

Il buffer della tastiera
Il processo di masterizzazione di un DVD

53 of 67

53

user

agent

user

agent

1

2

mail

server

3

4

mail

server

5

6

54 of 67

Riflessioni - II

Esempi dove è utilissimo usare una coda (bloccante):

La comunicazione tra interlocutori in rete
I mail server
Le pizzerie

55 of 67

Code Bloccanti – Blocking Queue

Uno strumento migliore di un coltellino svizzero
Utile per

Mettere thread e/o processi in comunicazione
Distribuirsi compiti tra thread
Delegare compiti ad altri thread
Compensare velocità di elaborazione diverse

56 of 67

Idea

Pensate al set di ordini per un pizzaiolo

Ingredienti:

1 Buffer FIFO
Metodi pensati per rendere Thread-safe l’accesso a quest’ultimo

57 of 67

Produttori e consumatori

Quando un thread inserisce elementi in una Queue sta giocando il ruolo di Produttore

Quando un thread preleva elementi da una Queue sta giocando il ruolo di Consumatore

58 of 67

Altri vantaggi delle BlockingQueues

Evitare le race condition

Nota che le palluzze prese da una coda diventano valori privati dopo la take() [posto che altri thread modifichino p per riferimento]
Si possono usare dunque le code per passare dati tra thread in maniera safe (message passing, etc. etc.)

p = Q.take() # p è privata, non appena ottenuta

print(p) # posso fare quello che voglio a p, nessuno rompe,

p = p+1 # yeeh

…

Q.put(p) # p è privata fino all’inserimento

59 of 67

Deadlock

Quest'opera è distribuita con Licenza

Creative Commons Attribuzione - Non commerciale 4.0 Internazionale.

60 of 67

Deadlock

Possibile quando si bloccano più risorse in contemporanea, formando un ciclo nel grafo di attesa
Altre condizioni di deadlock più subdole sono possibili (es. usando le BlockingQueue)

61 of 67

Livelock

62 of 67

63 of 67

La tempesta perfetta

Il deadlock si verifica se:

Sono presenti meccanismi di mutua esclusione nel codice (es. lock)
E’ consentito porsi in attesa che un lock si liberi (wait-and-hold)
Non è consentito togliere un lock a un thread brutalmente (no-preemption)
C’è un ciclo nel grafo di allocazione risorse

64 of 67

Evitare il Deadlock

Se possibile, riprogettare l’accesso alle risorse causa del ciclo con una disciplina diversa

A. mettere lock sulle risorse solo se tutte libere oppure aspettare
B. se una risorsa risulta occupata, liberare tutte le risorse e ripetere l’allocazione da capo

Prendere il lock alle risorse sempre nello stesso ordine
Prevenire… evitare di curare

65 of 67

Nested Lockout

import threading

class Lockout:

def __init__(self):

self.a = threading.Lock()

self.b = threading.Lock()

self.c = threading.Condition(self.b)

// T1 esegue questo:

def blocca(self):

self.a.acquire()

self.b.acquire()

while qualcheCondizione:

self.c.wait()

qualcheCondizione = True

self.b.release()

self.a.release()

// T2 esegue questo:

def sblocca(self):

self.a.acquire()

self.b.acquire()

self.qualcheCondizione = False

self.c.notify_all()

self.b.release()

self.a.release()

66 of 67

Starvation

Starvation = possibilità che il tempo di attesa prima di accedere a una determinata risorsa R sia anche infinito

In altre parole, non è garantita l’esistenza di un tempo massimo T entro il quale R viene finalmente acquisita.

67 of 67

Barriera

Consente a più thread di aspettarsi l’un l’altro
Utile per sincronizzare un gruppo di processi che eseguono parti di un compito frazionabile in parti uguali

Implementato in CyclicBarrier di Java
Implementato in Barrier di Python

Un metodo: await() – Java, wait() - Python