Concurrency Bugs

Key Question: How do we handle the common concurrency bugs?
* Tend to have common patterns. Need to know what to avoid.

Types of bugs

Non-deadlock Bugs

There are two major types of bugs; Atomicity Violation and Order Violation.

• Atomicity Violation: “The desired serializability among multiple memory accesses is violated (i.e. a code region is intended to be atomic, but the atomicity is not enforced during execution).”
  • If code A needs B stays the same, do not interrupt A in the middle such as changing B.
  • This violation, mostly, easily be fixed by implementing a lock (pthread_mutex_t)
• Order Violation: “The desired order between two (groups of) memory accesses is flipped (i.e., A should always be executed before B, but the order is not enforced during execution)”
  • If A needs to be guaranteed before B, then keep the order.
  • Can be fixed by forcing the order using condition varaibles (pthread_cond_t).

Deadlock Bugs

The existence of cycle within a graph implies the possibility of deadlock.

Why is this happening?

• Compelx dependency between components.
  • OS: Virtual memory system access file system for getting disk block. File system needs memory page to losad disk block on its memory, hence access virual memory system. –> Cycle
• Encapsulation property: Modularization and lock do not go well.

Coditions to have deadlock:

• Mutex: Threads claim exclusive control of resources that they require (e.g., a thread grabs a lock) - 독자적인 제어권
• Hold-and-wait: Threads hold resources allocated to them (e.g., locks that they have already acquired) while waiting for additional resources e.g., locks that they wish to acquire). - 자원점유및 대기
• No preemption: Resources (e.g., locks) cannot be forcibly removed from threads that are holding them. - 자원을 강제적으로 가져오지 못함.
• Circular wait: There exists a circular chain of threads such that each thread holds one or more resources (e.g., locks) that are being requested by the next thread in the chain. - cycle

All those four conditions are requried to have deadlock.

Deadlock Prevention:

• Circular Wait: Most common and practical method to prevent a deadlock.
  • Easiest: Set total ordering of getting a lock.
  • Partial Ordering in complex structures.
• Hold and Wait: Allow getting necessary lock at one time.
  • Such as get a prevention lock which prevents context switch within the process of getting locks (critical section).
  • It has problem with encapsulation - as it needs to know all the locks it need -> Hence also lowers the performance.
• No Preemption: trylock() - flexible interface
  • It causes livelock that attempts to get a lock infinitely without progress.
  • It also has problem with encapsulation - if the lock call routine is complicated and expensive, the repetition will be very difficult to implement.
• Mutex: Get rid of mutex by implementing wait-free data structures.
  • Instead of lock-fix-unlock, use compare-and-swap to repetitivelt try to fix the value (yet it has possibility of livelock).

Sometime it is better to “avoid” instead of “preven” the deadlock.
To do so, needs to know which threads will require which locks. Based on this info, schedule the threads to “AVOID” deadlock.
As it is really depends on situations, it is not generally used method.

Deadlock Detection and Recovery

• Detection: Draw resource allocation graph to check the cycle.
• Recovery: Depends on the implementation; whether human based…