Skip to content

Two Types of Concurrency

Message Passing

Each procedure has its own private memory

Interaction via message

ASYCHRONOUS, DISTRIBUTED

Shared Memory

Each procedure has access to the shared memory.

SYCHRONOUS, CENTRALIZED

Multi-threaded Program

#include<pthread.h>

pthread_create: create a thread.

pthread_join: wait until the thread terminate.

Thread Interleaving

If there are \(n\) threads, each thread has \(m\) statement.

The number of possible permutation of execution of statements are

\[ \frac{(n\cdot m)!}{(m!)^n}. \]

Safety and Concurrency Error

Race Condition

Similar to write-after-read in computer architecture.

Example:

The thread first read the global variable cnt, write cnt+1 to cnt.

If we create two threads, this may happen:

cnt=0 initially

  • thread 1 read cnt
  • thread 2 readcnt
  • thread 1 write cnt+1=1 to cnt
  • thread 2 write cnt+1=1 to cnt

The expected value of cnt is 2. Assertion failed.

Deadlock

How to solve race condition? Introduce mutex to lock the cnt.

But sometimes deadlock will introduce deadlock!

Example:

Thread A:

  1. Lock a
  2. Lock b
  3. Do something
  4. Release b
  5. Release a

Thread B:

  1. Lock b
  2. Lock a
  3. Do something
  4. Release a
  5. Release b

If we run both threads at the same time, this may happen:

  • Thread A locks a
  • Thread B locks b
  • Thread A waits for b and Thread B waits for a. DEADLOCK!

Concurrency and Complex Systems

A concurrency program is a complex system.

Local VS Global behavior