Deadlock

A deadlock in concurrent programming occurs when two or more processes are unable to proceed because each is waiting for resources held by another, creating a circular wait condition.

Coffman Conditions:

Mutual Exclusion: Resources cannot be shared (e.g. a mutex)
Hold and Wait: Processes hold resources while waiting for others
No Preemption: Resources cannot be forcibly taken away
Circular Wait: Circular chain of processes waiting for resources

Prevention Techniques:

Global Resource Ordering: Always lock mutex 1 before mutex 2
Timed Locks: Detect potential deadlocks by using timeouts
Try-lock pattern: Non-blocking resource acquisition

Example

Thread 1 locks mutex 1 and then tries to lock mutex 2
Thread 2 locks mutex 2 and then tries to lock mutex 1
Both threads now wait forever for the mutexes to unlock

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutex2 = PTHREAD_MUTEX_INITIALIZER;

void* thread1_function(void* arg) {
    pthread_mutex_lock(&mutex1);  // thread 1 locking mutex1
    sleep(1);                     // race condition
    pthread_mutex_lock(&mutex2);  // locked by thread 2

    /* DEADLOCK */

    pthread_mutex_unlock(&mutex2);
    pthread_mutex_unlock(&mutex1);
    return NULL;
}

void* thread2_function(void* arg) {
    pthread_mutex_lock(&mutex2);  // thread 2 locking mutex2
    sleep(1);                     // race condition
    pthread_mutex_lock(&mutex1);  // locked by thread 1

    /* DEADLOCK */

    pthread_mutex_unlock(&mutex1);
    pthread_mutex_unlock(&mutex2);
    return NULL;
}

int main() {
    pthread_t thread1, thread2;
    pthread_create(&thread1, NULL, thread1_function, NULL);
    pthread_create(&thread2, NULL, thread2_function, NULL);
    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
    return 0;
}