Mod 2: Critical Section / Mutual Exclusion

Question 1

What are some mechanisms to control access to shared resources?

Answer 1

(1) Locks
(2) Mutexes
(3) Semaphores
(4) Monitors
(5) Condition variables

Question 2

What are some patterns for coordinating accesses to shared resources?

Answer 2

(1) Write-Reader
(2) Producer-Consumer (bounded buffer)

Question 3

What is mutual exclusion?

Answer 3

Allowing only one thread to be in its critical section at a certain time, it means “not simultaneous”

Question 4

How is mutual exclusion usually programmed?

Answer 4

By using locks

Question 5

What is “condition synchronization”?

Answer 5

Signaling a condition (via shared variable) to allow threads waiting for an event signaled from another thread

Question 6

What causes busy wait?

Answer 6

When something is waiting for a condition to come through and repeatedly test a variable until it comes true

Question 7

When is synchronization needed?

Answer 7

Whenever a shared resource (a variable) is to be accessed by multiple threads

Question 8

What is “critical sections/regions”?

Answer 8

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

Question 9

What is mutual exclusion?

Answer 9

Mechanism that allows only one thread to enter the CS (critical section) at a time

Question 10

What should we do to avoid race condition?

Answer 10

(1) Determine which part of the code is critical
(2) Ensure mutual exclusion

Question 11

What is four requirements for CS solution?

Answer 11

(1) ME
(2) Progress (no deadlock or starvation)
(3) Fairness (no starvation)
(4) No assumption on performance

Question 12

What does the requirement “progress” mean in CS context?

Answer 12

When no thread is in a CS, any thread requesting to enter must be allowed to do so without delay

Question 13

What does “Fairness” mean in CS context?

Answer 13

That any thread waiting to access CS will at some point do that

Question 14

What does “no assumption on performance” mean in CS context?

Answer 14

Overhead of entering and exiting should be small

Question 15

What does “bounded wait” mean?

Answer 15

That there’s an uppe bound to the number of times a thread is allowed to enter its CS while other threads are waiting

Question 16

How is a lock used?

Answer 16

(1) Aquire lock before entering CS
(2) Execute CS
(3) Release lock

Aquiring a lock must a atomic

Question 17

How do we aquire a lock in Java?

Answer 17

By using the keyword SYNCHRONIZED

Question 18

Explain the CS properties

Answer 18

(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

Question 19

What does “overhead” mean?

Answer 19

overhead is any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to perform a specific task

Question 20

What is the “read-write-problem”?

Answer 20

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

Question 21

What are the fundamentals rules for the “read/write problems solution”?

Answer 21

(1) Only mulitple readers can have concurrent access
(2) Writes cannot have concurrent access
(2) a reader and a write cannot have concurrent access

Question 22

What method can be used for condition synchronization in Java?

Answer 22

wait( )
notify( )
notifyAll( )