12 - Thread Synchronization

Class: CSCE-313

Notes:

Atomic Operations

...

Notes:

• An operation that either runs to completion OR not at all.
• Its intermediate state i snot visible to anybody else outside
• Isolation: exectuing a thread completely isolated from other threads

Synchronization Variable - Lock to Provide Mutual Exclusion

...

Notes:

• We are going to place a lock around *p= p* = 1 for example in 11 - Concurrency and Threads#Race Condition Demonstration
• This guarantees that only one of them acquires the lock, which will prevent everybody else from being in the critical section at the same time
• When the thread that has the lock unlocks the lock, then one other thread can enter that critical section.
• This is the developers responsibility: Identifying shared state and critical sections
• In this case, if x had a certain value (x = 0) and then t1 and t2 both wanting to increment it, no matter which ones runs first, the critical sections will be serialized.

What is a mutex?

...

Notes:

• Mutex = mutual exclusion
• Purpose: While one entity has the mutex, another entity cannot get that mutex (cannot acquire the lock at the same time)
• This is basically you making sure that the critical section is serialize, this is called Advisory.
  • Your OS or compiler has no idea what your app semantics are
  • Only you understand what is consistent for your application

What is a critical section?

...

Notes:

• The segment of our program that we need to protect
• Bad things happen when we do not protect it (i.e. overwrites)
• You want to protect code A using a lock and code B using the same lock so that these sections are serialized (happen in order)

Mutex thread synchronization

...

Notes:

• Thread 0 executes completely isolated from thread 1
• In general if the only thing you are doing is read(), then you can get away without locking.
• But if you are writing, this is where critical sections happen
  • It is the entire read-write section that needs to be protected
  • Critical section should include the read that derived the thing you will write to

Mutex thread synchronization

...

Mutex in C++ for Thread Safety

...

...

Notes:

• If they don't use the same mutex, then you are not serializing anything
• This is just a big heavy duty block that basically has one thread finishing, then the second thread executing or the other way around.

Now when we do:

./a.out 1000000
data = 2000000

• You will be able to see a deterministic output

...

Mutex in C++ -- Finer Locking

...

Notes:

• We can only protect the read-modify-write section
• It produces the same correct result
• So yes, we can put locks inside loops to do fine locking

When we do:

./a.out 1000000
data = 2000000

• Once again we are in happy territory

Timeline of Coarse/Fine Grained Locking

Notes:

• Coarse grained: A thread that acquire a lock right at the beginning of the function, and then releases it at the end
• Fine grained: you have much more locks and unlocks, since these happen between small sections of code that are critical

Producer-Consumer Synchronization

...

Notes:

• Mutual exclusion is not enough!
• It is good but for shared variables we may need other types of primitives to be able to do more general things
• Here is an example if a Queue
  • You have multiple consumers and multiple producers
  • You can already see that there are shared variables between consumer and producer
    • producer needs to touch head/tail and size to add an element
    • consumer as it pulls an item from the list needs to change the size and look at head/tail.
    • What if both of them read tail at the same time and both try actions at the same time?
    • The order in which things happens, you can actually lose elements
• This sounds like a problem for mutex
  • Only one guy can be in the mutation at any given time

Producer-Consumer: problems

Notes:

• If the list size is 0, they do a busy wait
• When both think the queue is now empty, they can both try to read/write to the list, which is where bad things happen

Solution:
...

Notes:

• We are guaranteeing that only one thing sis at that critical section at any given time
• Mutexes do not give us dependence order, the order in which to execute things
• For this we need a new primitive
• Example:
  • Lets say that a consumer tried to pull an item from the que and found that the size of the queue was empty, now they will just wait for something to appear but since they are holding the mutex, that won't never happen! the producer is not able to run!
    • You are deadlock!
• Mutexes are not enforcing an ordering
• The only way I can actually test whether I can consume or not is by acquire the lock, but now when I determine that I can actually not do my thing, I want to be able to relinquish this lock and try again later.
• One thing that the consumer can do is to throw an error here, and have the higher level program call consumer again.
  • But this i still a busy wait, we are just trying again repeatedly!