Locks & Race Conditions

Question 1

Synchronization in Share Memory

Answer 1

Question 2

Shared Memory Synchronization
(Critical Section)

Answer 2

Region of code that accesses variables that are shared between threads.

Question 3

Shared Memory Synchronization
(Shared Resource)

Answer 3

can be anything of interest: bank balance, data structure, device, network connection. Always represented in memory, so we can talk equivalently in terms of Shared Variables.

Question 4

Example: Banking

Answer 4

Two threads called update on the same bank account. The code inside update is the critical region, the shared variable being bal.

Question 5

Problem: Banking

Answer 5

Final result may be that the balance is 5 instead of 10
This is a lost update problem.

Question 6

Problem Source

Answer 6

update of bank account is not atomic, meaning that when one thread is in the middle of updating a bank account, another thread may start updating the same account

Question 7

Problem Nature: Race Condition

Answer 7

The condition where an incorrect program output may be generated depending on the relative order in which instructions from multiple threads are interleaved (executed).

Question 8

Threads Introduce Nondeterminism

Answer 8

• Sequential programs are deterministic: for the same input, the same output
• Threads make a program nondeterministic:
  
  • For the same input, output depends on the interleaving of instructions from different threads. Race condition if output can be incorrect.
• Aim of synchronization: Eliminate race conditions
• Correct output? One influential idea is that any output from interleaving multiple threads is the same as an output from executing the threads sequentially.
• Atomicity of a critical section means that only one thread may be in it and the thread must finish the section before another thread may enter, thus ensuring “sequentiality.”

Question 9

Locks: Solving Banking Problem via Mutual Exclusion

Answer 9

Mutual exclusion for a resource: limits resource access to one thread at a time. Guarantees atomicity.

Lock can be in one of two states
– Held: A thread is in the critical section (no other thread can enter)
– Not held: No thread in the critical section (any thread can enter)

Two operations to move lock between states
– Acquire: mark lock as held, or wait until release
– Release: mark as not held

Question 10

lock_example()

Answer 10

Question 11

Lock Declaration

Answer 11

Declared like a variable
– Lock L;
Programs can have multiple locks
– Lock L, P;
– Call acquire at start of critical section
– Call release at end of critical section
– Achieves mutual exclusion and progress

Acquisition of a lock blocks only threads attempting to acquire the same lock.

Must use same lock for all critical sections accessing the same resource

Question 12

Mutual Exclusion in Java

Answer 12

Every Java object has an implicit (i.e. invisible) lock

Lock is achieved via the synchronized block
– Prevents thread entry to block until lock acquisition
– Lock release on block completion so other threads enter

Question 13

Locks in Java - Method

Answer 13

Question 14

Locks in Java – Code Block

Answer 14

Question 15

Bank_account in action

Answer 15

Question 16

Terminology Recap

Answer 16

Critical section
– Logically, all the code that accesses a shared variable (resource).

Race condition
– Condition where incorrect program output may be generated depending on the interleaving of instructions from multiple threads.

Atomic code
– Code that is executed by a thread indivisibly from the point of view of other threads trying to execute the same code.
– Idea: To avoid race conditions, make critical sections atomic.

Mutual exclusion
– Only one thread may access a shared resource at a time.
– Ensures atomicity

Locks
– A mechanism for guaranteeing mutual exclusion.