Ruud - 3 - Semaforen en synchronisatie

Question 1

Wat is een race-conditie?

Answer 1

Een race-condition is een ongewenste situatie waarbij het resultaat afhankelijk is van de volgorde
waarin de instructies worden uitgevoerd.

Question 2

In thread A moet codeblok A en in thread B moet codeblok B uitgevoerd worden.
Pas als codeblok A en codeblok B beide uitgevoerd zijn, moet in thread C een codeblok C
worden uitgevoerd.
a) Beschrijf hoe men met behulp van een tellende semafoor dit synchronisatieprobleem
kan oplossen.

b) Beschrijf hoe men met behulp van binaire semaforen dit synchronisatieprobleem kan
oplossen.

Answer 2

a) initialisatie van de tellende semafoor sem1 op 0.
Thread A Thread B Thread C
Code A code B semTake(sem1);
semTake(sem1);
semGive (sem1); semGive (sem1); code C

b) initialisatie van de binaire semaforen sem1 en sem2 op nul.
Thread A Thread B Thread C
Code A code B semTake(sem1);
semTake(sem2);
semGive (sem1); semGive (sem2); code C

Question 3

Wat verstaat men onder een kritieke sectie (in de context van semaforen)?

Answer 3

Een kritieke sectie is een stuk code dat ingesloten is tussen semTake() en
semGive().
Vanuit een kritieke sectie kan er geen context-switch plaatsvinden naar een andere
kritieke sectie die bij dezelfde semafoor behoort.

Question 4

Wat is een atomaire functie?

Answer 4

Een atomaire functie is een functie waarbij er geen context switch kan
plaatsvinden tijdens de uitvoer van zo’n functie.

Question 5

Een operating systeem beheert bij elke semafoor een rij (queue). Wat zijn de elementen van zo’n queue ?

Answer 5

De elementen van de semafoor-queue zijn proces-identificatienummers van
processen die de semTake() functie hebben aangeroepen, nadat de semafoor-
variabele (al) op nul stond

Question 6

Beschouw de onderstaande softwarematige oplossing voor wederzijdse uitsluiting.De vlaggen (flag[0] en flag[1]) zijn op 0 geïnitialiseerd. Leg uit dat bij deze oplossing een deadlock kan ontstaan.

Thread 0 Thread 1
flag[0] = TRUE; flag[1] = TRUE;
while flag[1] do nothing; while flag[0] do nothing;

<CRITICAL> <CRITICAL>
flag[0] = FALSE; flag[1] = FALSE;
</CRITICAL></CRITICAL>

Answer 6

In de onderstaande figuur zijn met grijze vlakken de context-switches aangegeven waarbij een deadlock ontstaat. Beide threads blijven in dat geval in een oneindige while-lus “hangen”.

Thread 0 Thread 1
flag[0] = TRUE;
flag[1] = TRUE;
* while flag[0] ;
*while flag[1];

<CRITICAL> <CRITICAL>
flag[0] = FALSE; flag[1] = FALSE;
</CRITICAL></CRITICAL>

Question 7

Een bekende softwarematige oplossing voor wederzijdse uitsluiting is het algoritme van Peterson
Welke groot nadeel kleeft er aan dit algoritme?

Answer 7

Het grote nadeel van het algoritme van Peterson is dat een thread die moet
wachten om een kritieke sectie in te gaan processortijd “verspilt”; het betreft een
zogenaamd actief wachten (busy waiting

Question 8

Geef een beschrijving van de volgende begrippen:
a) mutex b) monitor

Answer 8

Mutex: Een speciale binaire semafoor voor het realiseren van wederzijdse uitsluiting;
Monitor: Een klasse met de bijzondere eigenschap dat er slechts één thread
tegelijkertijd actief mag zijn binnen de klasse.

Question 9

Wat houdt het “producer-consumer probleem” in?

Answer 9

Het probleem gaat om 2 processen die een begrensde buffer gemeenschapelijk hebben. De producer wil in de buffer data wegschrijven en de consumer data
lezen.

Het probleem is dat een producer bij toegang tot de buffer een volle buffer
kan aantreffen (daarmee zou data verloren kunnen gaan).

Question 10

Geef een korte omschrijving van prioriteitsinversie. Noem verder een algoritme om prioriteitsinversie te vermijden.

Answer 10

Prioriteitsinversie is een situatie waarin een thread met een hogere prioriteit blokkeert op een semafoor, die vastgehouden wordt door een thread met een
lagere prioriteit.

Dit probleem kan verholpen worden door toepassing van het priority inheritance protocol.

Question 11

Leg uit hoe het priority inheritance algoritme functioneert

Answer 11

Priority inheritance houdt in dat een thread die in een kritieke sectie komt (dus semTake() passeert), gedurende de executie in de kritieke sectie een
variabele prioriteit krijgt toegewezen, die steeds gelijk is aan het maximum van zijn huidige prioriteit en alle prioriteiten van de threads die op dat ogenblik op de
semafoor geblokkeerd zijn

Question 12

Geef een voorbeeld in pseudocode met semaforen waarbij een deadlock kan ontstaan.

Answer 12

void threadA(void)
{
semTake (sem1,WAIT_FOREVER);
// //&raquo_space;» context switch naar thread B
semTake (sem2,WAIT_FOREVER); //
semGive(sem2);
semGive(sem1);
}
void threadB(void)
{
semTake (sem2,WAIT_FOREVER);
// // Hier kan thread B “vastlopen”.
semTake (sem1,WAIT_FOREVER);
//
semGive(sem1);
semGive(sem2);
}

Question 13

Gegeven zijn de threads. In de 6 threads moeten respectievelijk codefragmenten A, B, C,
D, E en F worden uitgevoerd in de volgorde zoals weergegeven in de ondrestaande
figuur. Geef een oplossing voor dit synchronisatieprobleem (in pseudocode).

Code A -> Code C
|. |.
Code B -> Code D
|. |.
Code E -> Code F

Answer 13

TaakA() { …; V(AB);V(AC);}
TaakB() {P(AB); …; V(BD);V(BE);}
TaakC() {P(AC); …; V(CD);}
TaakD() {P(BD);P(CD); …; V(DF);}
TaakE() {P(BE) …; V(EF);}
TaakF() {P(EF);P(DF); …;}

Question 14

Leg uit waarom er na disabling van hardware-interrupts geen context switch mogelijk is.

Answer 14

Door het uitschakelen van interrupts komen er geen kloktikken meer van de systeemklok. Context switches vinden uitsluitend plaats bij interrupts van de systeemklok.

Question 15

Geef in pseudocode een mogelijke implementatie van de semTake()-functie gebaseerd op interrupt-diasabling.

Answer 15

void semTake()
{ disable interrupts.
if (s.count = = 1) // als de semafoor vrij is;
s.count = 0; // semafoor voor volgende threads
blokkeren;
else {Plaats de aanroepende thread in de
wachtrij s.queue en en zet deze
thread in de wachttoestand (pending
state) };
enable interrupts.
}

Question 16

Wat is een thread-safe function
Leg uit waarom de onderstaande functie niet thread-safe is. Breng vervolgens een wijziging in de functie aan zodanig dat de functie wel thread-safe wordt.

char arr[10];
int index=0;

int func (char c)
{ arr[index]=c;
index++;
return index;
}

Answer 16

Een functie heet thread-safe als de functie door verschillende threads tegelijk gebruikt kan worden waarbij er geen ongewenste resultaten ontstaan door context-switches tussen threads die de functie aanroepen.

De gegeven functie is niet thread-safe.
Bijv. Thread1: arr[5]=40; context switch ; arr [5]=60
De waarde in arr[5] wordt dus dan ongewenst overschreven.

Thread-safe solution:
char arr[10];
int index=0;

int func (char c)
{ mutex_aquire(mut1);
arr[index]=c;
index++;
mutex_release(mut1);
return index;
}