M2.F3: Critical Section & Mutual Exclusion Flashcards
Ge fem exempel på mekanismer som kontrollerar åtkomsten till delade resurser:
- Locks
- Mutexes
- Semaphores
- Monitors
- Condition variables
Vad finns det för mönster för att koordinera åtkomst till delade resurser?
Writer-Reader och Producer-Consumer (bounded buffer)
Vad är mutual exclusion?
När bara en tråd åt gången får vara i sin critical region vid ett särskilt tillfälle
Hur programmerar man oftast mutual exclusion?
Genom att använda locks
Vad är condition synchronization?
När man signalerar ett tillstånd mellan trådar genom en delad variabel
Hur implementerar man condition synchronization?
Genom att låta en tråd vänta på ett event som signaleras från en annan tråd.
Vad är busy waiting?
När en process väntar på ett tillstånd och upprepat testar en variabel (ett villkor) tills den blir sann
Vad är en critical section/region?
Sekvenser av instruktioner med modifierbara gemensamma resurser, som kan ge inkorrekta resultat om de körs simultant.
Vad finns ofta i en critical section?
Delade variabler
När används atomic actions och critical sections?
När man har trådar som vill komma åt delade resurser
Vad är en fine-grained atomic action?
En som kan implementeras i ett enda steg, av en instruktion
Vad är en coarse-grained atomic action?
En som kan implementeras i flera steg som en kritisk sektion
Med vad kan man genomföra en atomic operation?
Med ett lock, en mutex, en monitor eller en binär semafor.
Vad uppstår när flera trådar har en överlappad (interleaved) körning av en kritisk sektion?
En non-deterministic situation.
Vad är en deterministisk och non-deterministisk situation?
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.
Vad behöver trådar ha för att undvika race condition?
Exklusiv åtkomst till sin kritiska sektion.
Vad bör man göra för två saker för att undvika race condition?
- Avgöra vilken del av koden som är kritisk, dvs vilken innehåller delade resurser
- Säkerställa mutual exclusion
Vad finns det för fyra krav på en lösning till critical sectionproblemet?
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
Hur sätter man ett “lock” med java?
Genom att skriva synchronized i metodsignaturen
Vad har ett lock för två tillstånd?
Held (locked) - låset används och not held - låset används inte
Vad har lock för två operationer?
- Låsa/vänta på låsning
2. Släppa låset
Om en tråd har utfört en lock, kan andra trådar låsa andra saker samtidigt?
Ja
Hur bör man tänka med lås på kritiska sektioner?
Använda samma lås på kritiska sektioner som når samma delade resurser
Vad finns det för fem fundamentala regler för Reader/Writerlösningen?
- 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
Vad finns det för två regler för Producer/Consumer-problemet?
- 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
Vad är en delad resurs?
Antingen delat minne eller en öppen fil.