Parallel Programming 8

Fine-grained Synchronization & Lock-free Programming

Deadlock 발생 조건 (모두 만족해야 함)

• Mutual exclusion
• Hold and wait
• No preemption
• Circular wait

Livelock : a state where a system is executing many operations, but no thread is making meaningful progress. example : Operations continually abort and retry

Starvation : State where a system is making overall progress, but some progresses make no progress.

Usually not a permanent state

Coarse-grain locks

장점 : easy to make correct

단점 : limits parallelism, no two critical sections can proceed in parallel

 

Fine-grain locks

장점 : Fast, critical sections can proceed in parallel

단점 : Easy to make mistakes, tricky to ensure correctness

 

Lock-free data structures

why?

• Acquiring locks is expensive
• 99% of the time un-necessary
  • Most concurrent actions don’t actually share data

Non-blocking algorithms are lock-free if some thread is guaranteed to make progress