Other Classic Synchronization Problems

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

// BROKEN: Demonstrates the lost wakeup race condition
 
// Shared state (unprotected)
int waiting_customers = 0;
 
void barber() {
    while (true) {
        // RACE CONDITION WINDOW OPENS HERE
        if (waiting_customers == 0) {
            // Suppose a customer arrives RIGHT HERE
            // Customer increments waiting_customers to 1
            // Customer signals wakeup (but barber not sleeping yet!)
            sleep();  // Barber goes to sleep AFTER signal was sent
            // DEADLOCK: Signal was lost, barber sleeps forever
        }
        // Cut hair...
    }
}
 
void customer() {
    waiting_customers++;  // Might happen during barber's check
    wakeup_barber();      // Signal lost if barber not sleeping yet
    // Wait for haircut...
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177

/*
 * The Sleeping Barber Problem - Correct Semaphore Solution
 * 
 * This solution uses Dijkstra's original approach with three semaphores:
 * - customers: signals presence of waiting customers (count)
 * - barber: signals barber readiness (binary-like behavior)
 * - mutex: protects the waiting count variable
 */
 
#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
 
#define CHAIRS 5          // Number of waiting room chairs
 
sem_t customers;          // Counts waiting customers (semaphore value = waiting count)
sem_t barber;             // Signals barber is ready for next customer
pthread_mutex_t mutex;    // Protects 'waiting' variable
 
int waiting = 0;          // Customers currently in waiting room
 
/* ============================================
 * BARBER THREAD
 * ============================================ */
void* barber_thread(void* arg) {
    while (1) {
        /*
         * Step 1: Wait for a customer to arrive
         * 
         * sem_wait decrements 'customers' semaphore.
         * If customers == 0, barber blocks (sleeps) here.
         * When a customer arrives and posts to 'customers',
         * the barber wakes up.
         */
        sem_wait(&customers);
        
        /*
         * Step 2: Acquire mutex to safely decrement waiting count
         * 
         * We must hold the mutex while modifying 'waiting' to prevent
         * race conditions with arriving customers.
         */
        pthread_mutex_lock(&mutex);
        waiting--;  // Customer moved from waiting room to barber chair
        
        /*
         * Step 3: Signal that barber is ready
         * 
         * This wakes up the customer who is waiting for service.
         * The customer was blocked on sem_wait(&barber).
         */
        sem_post(&barber);
        pthread_mutex_unlock(&mutex);
        
        /*
         * Step 4: Cut hair (critical section - service delivery)
         * 
         * The actual work happens here. In a real system,
         * this could be processing a request, handling a connection, etc.
         */
        cut_hair();
    }
    return NULL;
}
 
/* ============================================
 * CUSTOMER THREAD
 * ============================================ */
void* customer_thread(void* arg) {
    int customer_id = *(int*)arg;
    
    /*
     * Step 1: Acquire mutex to check and modify waiting count
     * 
     * We need mutual exclusion because we're doing a compound operation:
     * checking if space is available AND reserving a spot.
     */
    pthread_mutex_lock(&mutex);
    
    /*
     * Step 2: Check if waiting room has space (bounded buffer check)
     */
    if (waiting < CHAIRS) {
        /*
         * Step 3a: Space available - join the queue
         */
        waiting++;  // Reserve a spot in waiting room
        
        /*
         * Step 4: Signal barber that a customer is waiting
         * 
         * sem_post increments 'customers' semaphore.
         * If barber was sleeping (blocked on sem_wait), this wakes him.
         * If barber was busy, this just increments the count.
         */
        sem_post(&customers);
        pthread_mutex_unlock(&mutex);  // Release mutex before blocking
        
        /*
         * Step 5: Wait for barber to be ready
         * 
         * Block until barber signals readiness with sem_post(&barber).
         * This ensures proper handoff between barber and customer.
         */
        sem_wait(&barber);
        
        /*
         * Step 6: Get haircut
         * 
         * Customer is now in barber chair receiving service.
         */
        get_haircut();
        
        printf("Customer %d: haircut complete, leaving satisfied
", customer_id);
    } else {
        /*
         * Step 3b: No space - leave immediately (balk)
         * 
         * Customer cannot wait, must leave without service.
         * This is the "balk" behavior in queueing theory.
         */
        pthread_mutex_unlock(&mutex);
        printf("Customer %d: no space, leaving without haircut
", customer_id);
    }
    
    return NULL;
}
 
/* ============================================
 * SERVICE FUNCTIONS
 * ============================================ */
void cut_hair() {
    printf("Barber: cutting hair...
");
    sleep(3);  // Simulate haircut duration
    printf("Barber: done with this customer
");
}
 
void get_haircut() {
    printf("Customer: getting haircut...
");
    // Duration controlled by cut_hair() - customer just waits
}
 
/* ============================================
 * INITIALIZATION AND MAIN
 * ============================================ */
int main() {
    // Initialize semaphores
    sem_init(&customers, 0, 0);  // Initially no customers waiting
    sem_init(&barber, 0, 0);     // Barber not ready initially
    pthread_mutex_init(&mutex, NULL);
    
    // Create barber thread
    pthread_t barber_tid;
    pthread_create(&barber_tid, NULL, barber_thread, NULL);
    
    // Simulate customer arrivals
    for (int i = 0; i < 20; i++) {
        pthread_t customer_tid;
        int* id = malloc(sizeof(int));
        *id = i;
        pthread_create(&customer_tid, NULL, customer_thread, id);
        
        // Random arrival interval
        usleep((rand() % 1000) * 1000);  // 0-1000ms
    }
    
    // In practice, would join threads and cleanup
    pthread_join(barber_tid, NULL);
    
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

/*
 * Multiple Barbers Extension
 * 
 * The key insight is that multiple barber threads can share
 * the same semaphores. The 'customers' semaphore naturally
 * handles waking one barber per customer.
 */
 
#define NUM_BARBERS 3
#define CHAIRS 10
 
sem_t customers;
sem_t barber_ready[NUM_BARBERS];  // One per barber for debugging
pthread_mutex_t mutex;
int waiting = 0;
 
void* barber_thread(void* arg) {
    int barber_id = *(int*)arg;
    
    while (1) {
        printf("Barber %d: checking for customers...
", barber_id);
        
        // Wait for any customer - multiple barbers compete here
        sem_wait(&customers);
        
        pthread_mutex_lock(&mutex);
        waiting--;
        printf("Barber %d: serving customer, %d still waiting
", 
               barber_id, waiting);
        pthread_mutex_unlock(&mutex);
        
        // Signal ready (for this barber's customer)
        sem_post(&barber_ready[barber_id]);
        
        // Perform haircut
        cut_hair(barber_id);
    }
    return NULL;
}
 
void* customer_thread(void* arg) {
    int customer_id = *(int*)arg;
    
    pthread_mutex_lock(&mutex);
    
    if (waiting < CHAIRS) {
        waiting++;
        int my_position = waiting;
        printf("Customer %d: waiting in position %d
", customer_id, my_position);
        
        sem_post(&customers);  // Wake up any sleeping barber
        pthread_mutex_unlock(&mutex);
        
        // In a fair variant, would need assignment to specific barber
        // Simplified: assume any barber_ready signal works for us
        // Real implementation needs more sophisticated matching
        
        get_haircut();
        printf("Customer %d: haircut complete
", customer_id);
    } else {
        pthread_mutex_unlock(&mutex);
        printf("Customer %d: shop full, leaving
", customer_id);
    }
    
    return NULL;
}
 
/*
 * Note: This simplified version has a subtle fairness issue.
 * The sem_post(&barber_ready[barber_id]) may not go to the
 * customer that originally woke this barber. In practice,
 * you'd use a single barber semaphore or explicit queuing.
 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// WRONG: Holding mutex during semaphore wait
void* customer_wrong(void* arg) {
    pthread_mutex_lock(&mutex);
    
    if (waiting < CHAIRS) {
        waiting++;
        sem_post(&customers);
        
        // BUG: Still holding mutex!
        sem_wait(&barber);  // Blocks while holding mutex
                            // Barber can't acquire mutex to signal
                            // DEADLOCK!
        
        pthread_mutex_unlock(&mutex);
        get_haircut();
    } else {
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}
 
// CORRECT: Release mutex before blocking
void* customer_correct(void* arg) {
    pthread_mutex_lock(&mutex);
    
    if (waiting < CHAIRS) {
        waiting++;
        sem_post(&customers);
        pthread_mutex_unlock(&mutex);  // Release BEFORE waiting
        
        sem_wait(&barber);  // Safe to block now
        get_haircut();
    } else {
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

// WRONG: Signaling before waiting
void* barber_wrong(void* arg) {
    while (1) {
        pthread_mutex_lock(&mutex);
        
        // BUG: Post barber signal before actually ready
        sem_post(&barber);  // Customer can proceed immediately
        
        sem_wait(&customers);  // Now waiting, but customer already gone!
        // Customer thinks they got a haircut but barber hasn't done anything
        
        pthread_mutex_unlock(&mutex);
        cut_hair();  // Cutting hair for nobody
    }
    return NULL;
}
 
// CORRECT: Wait for customer first, then signal ready
void* barber_correct(void* arg) {
    while (1) {
        sem_wait(&customers);  // Wait for customer first
        
        pthread_mutex_lock(&mutex);
        waiting--;
        sem_post(&barber);     // Then signal barber is ready
        pthread_mutex_unlock(&mutex);
        
        cut_hair();  // Actually cut the waiting customer's hair
    }
    return NULL;
}