M2.F3: Critical Section & Mutual Exclusion

Question 1

Ge fem exempel på mekanismer som kontrollerar åtkomsten till delade resurser:

Answer 1

• Locks
• Mutexes
• Semaphores
• Monitors
• Condition variables

Question 2

Vad finns det för mönster för att koordinera åtkomst till delade resurser?

Answer 2

Writer-Reader och Producer-Consumer (bounded buffer)

Question 3

Vad är mutual exclusion?

Answer 3

När bara en tråd åt gången får vara i sin critical region vid ett särskilt tillfälle

Question 4

Hur programmerar man oftast mutual exclusion?

Answer 4

Genom att använda locks

Question 5

Vad är condition synchronization?

Answer 5

När man signalerar ett tillstånd mellan trådar genom en delad variabel

Question 6

Hur implementerar man condition synchronization?

Answer 6

Genom att låta en tråd vänta på ett event som signaleras från en annan tråd.

Question 7

Vad är busy waiting?

Answer 7

När en process väntar på ett tillstånd och upprepat testar en variabel (ett villkor) tills den blir sann

Question 8

Vad är en critical section/region?

Answer 8

Sekvenser av instruktioner med modifierbara gemensamma resurser, som kan ge inkorrekta resultat om de körs simultant.

Question 9

Vad finns ofta i en critical section?

Answer 9

Delade variabler

Question 10

När används atomic actions och critical sections?

Answer 10

När man har trådar som vill komma åt delade resurser

Question 11

Vad är en fine-grained atomic action?

Answer 11

En som kan implementeras i ett enda steg, av en instruktion

Question 12

Vad är en coarse-grained atomic action?

Answer 12

En som kan implementeras i flera steg som en kritisk sektion

Question 13

Med vad kan man genomföra en atomic operation?

Answer 13

Med ett lock, en mutex, en monitor eller en binär semafor.

Question 14

Vad uppstår när flera trådar har en överlappad (interleaved) körning av en kritisk sektion?

Answer 14

En non-deterministic situation.

Question 15

Vad är en deterministisk och non-deterministisk situation?

Answer 15

Deterministiskt är när man får samma output med samma input varje gång koden körs, non är när man inte vet vilken output man kommer få av samma input.

Question 16

Vad behöver trådar ha för att undvika race condition?

Answer 16

Exklusiv åtkomst till sin kritiska sektion.

Question 17

Vad bör man göra för två saker för att undvika race condition?

Answer 17

• Avgöra vilken del av koden som är kritisk, dvs vilken innehåller delade resurser
• Säkerställa mutual exclusion

Question 18

Vad finns det för fyra krav på en lösning till critical sectionproblemet?

Answer 18

Mutual Exclusion - endast en process åt gången tillåts i sin kritiska sektion
Progress(no deadlock/livelock) - om ingen tråd är i sin kritiska sektion måste en tråd som vill in i sin CS få komma in utan fördröjning
Fairness (no starvation) - om en tråd väntar på sin kritiska sektion skall den få komma dit så småningom och det finns en övre gräns på hur många gånger en tråd får gå in i sin CS medan andra väntar
No assumption on performance: kraven för alla sorters CPUs måste mötas

Question 19

Hur sätter man ett “lock” med java?

Answer 19

Genom att skriva synchronized i metodsignaturen

Question 20

Vad har ett lock för två tillstånd?

Answer 20

Held (locked) - låset används och not held - låset används inte

Question 21

Vad har lock för två operationer?

Answer 21

1. Låsa/vänta på låsning

2. Släppa låset

Question 22

Om en tråd har utfört en lock, kan andra trådar låsa andra saker samtidigt?

Answer 22

Ja

Question 23

Hur bör man tänka med lås på kritiska sektioner?

Answer 23

Använda samma lås på kritiska sektioner som når samma delade resurser

Question 24

Vad finns det för fem fundamentala regler för Reader/Writerlösningen?

Answer 24

• Två eller fler som läser kan få tillgång till den delade datan överlappande (concurrently)
• Den delade resursen kan vara ett objekt eller en buffer
• En reader och en writer bör inte få tillgång till den delade resurser concurrently
• Två eller flera writers bör inte få tillgång till den delade resursen samtidigt
• trådar måste vänta på varandra när de inte får gå in i viss kod överlappande

Question 25

Vad finns det för två regler för Producer/Consumer-problemet?

Answer 25

• Producern bör inte lägga till ett föremål i buffern när buffern är full.
• Consumern bör inte försöka ta ut ett item ur buffern när buffern är tom

Question 26

Vad är en delad resurs?

Answer 26

Antingen delat minne eller en öppen fil.