Deadlocks

More than one mutexes in one data structure is not uncommon. Used for protecting different parts.

Using a blocking syncrhonzation construct such as a semaphore and mutexes can lead to a deadlock.

• e.g., Thread 1 aquires obj->lock and waits to acquire obj->lock2. Thread 2 aquires obj->lock2 and waits to acquire obj->lock2. Then neither thread can make progress.

A deadlock can only occur if a thread attempts to acquire multiple locks simultaneously, and there is not a globally-consistent lock aquisition order.

Trivially, if threads only acquire one lock at a time, deaadlocks can't occur. Maintaining a consistent lock acquisition order also works.

A self deadlock would be :

pthread_mutex_lock(&obj->lock);
obj->count++;
pthread_mutex_lock(&obj->lock);

• mutexes and pthreads are not recursive, meaning that if a thread aquires a mutex it is already holding, it'll deadlock itself.
• This is why you should use guard objects.

A self deadlock can also occur if multiple functions have critical sections, and they call each other.

To avoid self-deadlocks,

• avoid acquiring locks in helper functions
• make "higher-level" functions (often the "public" API functions of the locked data structure) responsible for acquiring locks.

Resource allocation graph

In a resource allocation graph:

• nodes represent threads and lockable resources
• edges between threads and resources
• edges from resource to thread: thread has locked the resources
• edges from thread to resource: thread is waiting to lock the resource.

A cycle would indicate a deadlock.

Condition Variables

Condition variables are another type of synchronization construct supported by pthreads.

They allow threads to wait for a condition to become true. For example,

• wait for a queue to become non-empty
• wait for a queue to become non-full
• etc.

They work in conjection with a mutex

The data type is pthread_cond_t and contains the functions

• pthread_cond_init: initialize a condition variable
• pthread_cond_destroy: destroy a condition variable
• pthread_cond_wait: wait on a condition variable, unlocking mutex (so other threads can enter critical sections)
• pthread_cond_broadcast: wake up waiting threads because condition may have been enabled

Principles for using conditional variables

• each condition variable must be associated with a mutex
• multiple condition variables can be associated with the same mutex
• the mutex must be locked when waiting on a condition variable
  • pthread_cond_wait releases the mutex, then reqcuires it when the wait is ended (by another thread doing a broadcast)
• pthread_cond_wait must be done in a loop
  • spurious wakeups are possible, so waited-for condition must be re-checked.
• use pthread_cond_broadcast whenever a condition might be enabled.

Bounded Queue Example

BoundedQueue data type:

    typedef struct {
      void **data;
      unsigned max_items, count, head, tail;
      pthread_mutex_t lock;      
      pthread_cond_t not_empty, not_full;
    } BoundedQueue;

• It's a good idea to name the condition to reflect what it is waiting for.

Creating a BoundedQueue

BoundedQueue *bqueue_create(unsigned max_items) {
	BoundedQueue *bq = malloc(sizeof(BoundedQueue));
	bq->data = malloc(max_items * sizeof(void *));
	bq->max_items = max_items;
	bq->count = bq->head = bq->tail = 0;
	pthread_mutex_init(&bq->lock, NULL);
	// initialize the conditional variables
	pthread_cond_init(&bq->not_full, NULL);
	pthread_cond_init(&bq->not_empty, NULL);
	return bq; 
}

Enqueuing an item:

void bqueue_enqueue(BoundedQueue *bq, void *item) {
	pthread_mutex_lock(&bq->lock);

	// wait for queue to become non-full
	while (bq->count >= bq->max_items) {
		pthread_cond_wait(&bq->not_full, &bq->lock);
	}

	// add item to queue
	bq->data[bq->head] = item;
	bq->head = (bq->head + 1) % bq->max_items;
	bq->count++;

	// wake up threads waiting for teh queue to be non-empty
	pthread_cond_broadcast(&bq->not_empty);
	
	pthread_mutex_unlock(&bq->lock);
}

• A conditional wait stops it from executing until the condition becomes true.
• In this example, we wait until the queue is non-full.
• While a thread is waiting, it will temporarily release its mutex so that something else can make the condition true.

Amdahl's Law

Speedup

We parallelize a computation to make it complete as fast as apossible.

A speedup (denoted as S) is $t_ s / t_p$ where $t_s$ is the sequential running time and $t_p$ is the parallel running time.

If $P$ is the number of processor cores, then in theory, speedup $S$ cannot be greater than $P$. This is because in the ideal case, $S=P=t_s/t_p$ which implies that $t_p = t_s / P$.

• If the speedup $S=P$, then we have perfect scalability. However, this is difficult to achieve in practice because parallel computations generally have some sequential overhead which cannot easily be parallelized.

Amdahl's Law

Say that the proportions of inherently sequential and parallelizable computations are $w_s$ and $w_p$ respectively.

• $w_s + w_p = 1$, so $w_p = 1- w_s$.
• Normalized sequential execution time $t_s = 1 = w_s + w_p$
  • Parallel execution time using $P$ cores: $t_p = w_s + w_p = w_s + \frac{1-w_s}{P}$.
  • Using $P$ cores, then S --> $\frac{1}{w_s}$. This means that if $w_s = 0.05$, then maximum speedup is $20$ regardless of how many cores we use.

Gustafson-Barsis's Law

While Amdahl's Law assumes that the proportion of inherently sequential computation $w_s$ is independent of the problem size, Gustafson-Barsis's Law says that for some computations, the proportion of paralleliable computation scales with the problem size.

• These are called scalable computations
• Such computations can realize speedups proportional to $P$ for a large number of processors.

Atomicity

We noted previously that incrementing an integer variable is not atomic (appear instantaneous). However, modern processors typically support atomic machine instructions. These are atomic even when used on shared variables by multiple threads.

The various ways to use these:

• assembly language
• compiler intrinsics
• language support

Typical machine instructions.

• increment
• decrement
• exchange (swap contents of two variables)
• compare and swap (compare, if equal, swap variable's content with another value)
• load linked/store conditional (load from variable, store back to variable only if the variable wasn't updated concurrently).

Atomic increment in x86-64. In x86-64, memory instructions can have a lock prefix to guarantee atomicity. Example:

	.globl atomic_increment
atomic increment:
	lock; incl (%rdi)
	red

Then you call it from your C code:

void atomic_increment(volatile int *p)

...

atomic_increment(&obj->count)

You can also use gcc intrinsics. Gcc has a number of intrinsic functions for atomic operations. E.g., for atomic increment:

__atomic_fetch_add(&obj->count, 1, __ATOMIC_ACQ_REL);

You can also use the C11 standard's _Atomic type qualifier. Defining shared counter type:

typedef struct {
	_Atomic int count;
} Shared;

Incrementing the shared counter: obj->count++;

Lock-free data strcutures atomic machine instructions can be the basis for lock-free data structures. Basic ideas

• data srtucture must always be in a vlaid state
• transactional: mutators speculatively create a proposed update and attempt to commit it using compare-and-swap (or load linked/store conditional)
  • retry transaction if another thread committed an update concurrently invalidating proposed update.

Issue: waits and wake-ups are not really possible

• e.g., when trying to dequeue from an empty queue, can't easily wait for item to be available, calling thread must spin.