Mod 2: Critical Section / Mutual Exclusion Flashcards
What are some mechanisms to control access to shared resources?
(1) Locks
(2) Mutexes
(3) Semaphores
(4) Monitors
(5) Condition variables
What are some patterns for coordinating accesses to shared resources?
(1) Write-Reader
(2) Producer-Consumer (bounded buffer)
What is mutual exclusion?
Allowing only one thread to be in its critical section at a certain time, it means “not simultaneous”
How is mutual exclusion usually programmed?
By using locks
What is “condition synchronization”?
Signaling a condition (via shared variable) to allow threads waiting for an event signaled from another thread
What causes busy wait?
When something is waiting for a condition to come through and repeatedly test a variable until it comes true
When is synchronization needed?
Whenever a shared resource (a variable) is to be accessed by multiple threads
What is “critical sections/regions”?
Code blocks that may get incorrect results if executed simultaneously, these often access shared variables and must be protected
i.e statement that must not be executed by more than one thread at the time or part of code manipulating shared modifiable resources
What is mutual exclusion?
Mechanism that allows only one thread to enter the CS (critical section) at a time
What should we do to avoid race condition?
(1) Determine which part of the code is critical
(2) Ensure mutual exclusion
What is four requirements for CS solution?
(1) ME
(2) Progress (no deadlock or starvation)
(3) Fairness (no starvation)
(4) No assumption on performance
What does the requirement “progress” mean in CS context?
When no thread is in a CS, any thread requesting to enter must be allowed to do so without delay
What does “Fairness” mean in CS context?
That any thread waiting to access CS will at some point do that
What does “no assumption on performance” mean in CS context?
Overhead of entering and exiting should be small
What does “bounded wait” mean?
That there’s an uppe bound to the number of times a thread is allowed to enter its CS while other threads are waiting
How is a lock used?
(1) Aquire lock before entering CS
(2) Execute CS
(3) Release lock
Aquiring a lock must a atomic
How do we aquire a lock in Java?
By using the keyword SYNCHRONIZED
Explain the CS properties
(1) ME: only one thread at a time can execute CS
(2) Progress: a thread outside CS cannot prevent another from entering CS
(3) Bounded waitin: a thread waiting to ENTER CS will eventually do so
(4) Performance: overhead of entering and exiting should be small
(5) Fairness: some thread should not wait longer than others
What does “overhead” mean?
overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to perform a specific task
What is the “read-write-problem”?
When one or more threads look up data while other threads change values in the same data, eg. database record may be read while other threads update the records
What are the fundamentals rules for the “read/write problems solution”?
(1) Only mulitple readers can have concurrent access
(2) Writes cannot have concurrent access
(2) a reader and a write cannot have concurrent access
What method can be used for condition synchronization in Java?
wait( )
notify( )
notifyAll( )
