Synchronization, Locks, and the Producer-Consumer Pattern

Many concurrent algorithms do not fit neatly into parallel for loops. Problems involving task queues, asynchronous message passing, and producer-consumer patterns require explicit synchronization primitives.

In this chapter, we explore advanced shared-memory synchronization: explicit barriers, the atomic directive, named critical sections, and OpenMP locks.

---

5.12 The Producer-Consumer Queue Model

A queue is a First-In, First-Out (FIFO) data structure where elements are inserted at the rear (enqueued) and removed from the front (dequeued).

In a multithreaded environment, producer threads generate tasks or data, while consumer threads process them.

flowchart LR
  subgraph ProdCons["Figure 5.6: Producer-Consumer Message Passing on Shared Memory"]
      direction LR
      P0["Thread 0 (Producer)"] -->|Enqueue| Q1["Queue 1 (Thread 1)"]
      P1["Thread 1 (Producer)"] -->|Enqueue| Q0["Queue 0 (Thread 0)"]
      Q0 -->|Dequeue| C0["Thread 0 (Consumer)"]
      Q1 -->|Dequeue| C1["Thread 1 (Consumer)"]
  end

Shared-Memory Message Passing

Consider a system where each thread owns a dedicated message queue. When Thread $u$ sends a message to Thread $v$, it enqueues the item in Thread $v$‘s queue. Thread $v$ receives messages by dequeuing from its own queue.

Each thread alternates between sending and receiving:

for (sent_msgs = 0; sent_msgs < send_max; sent_msgs++) {
    Send_msg();
    Try_receive();
}
while (!Done()) {
    Try_receive();
}

---

5.13 Synchronization Challenges in Queues

1. Enqueue Concurrency

When a thread enqueues a message, it updates the queue’s rear pointer. If two threads enqueue into the same queue simultaneously, their operations conflict, causing lost messages and corrupting pointers. Enqueuing is a critical section:

mesg = random();
dest = random() % thread_count;
#pragma omp critical
Enqueue(queue, dest, my_rank, mesg);

---

2. Dequeue Concurrency

Only the queue owner dequeues from its own queue.

• If there are at least two messages in the queue, Enqueue modifies the rear pointer while Dequeue modifies the front pointer. Because the pointers are distinct, no synchronization is necessary!
• Synchronization is only required when queue_size == 1, where front and rear refer to the same node.

queue_size = enqueued - dequeued;
if (queue_size == 0) return;
else if (queue_size == 1) {
    #pragma omp critical
    Dequeue(queue, &src, &mesg);
} else {
    Dequeue(queue, &src, &mesg); /* Lock-free fast path */
}
Print_message(src, mesg);

---

3. Termination Detection

A thread cannot simply exit when its local queue_size == 0. Another thread may still be running and attempt to send a message to it.

To safely detect termination, a shared counter done_sending is tracked:

queue_size = enqueued - dequeued;
if (queue_size == 0 && done_sending == thread_count)
    return TRUE;
else
    return FALSE;

---

5.14 Explicit Barriers: #pragma omp barrier

When the application starts, the master thread allocates an array of queue pointers. If child threads begin executing before memory allocation completes, threads will dereference null pointers and crash.

OpenMP directives like parallel for provide an implicit barrier at the end of their block. However, inside a general parallel region, threads must be synchronized explicitly:

#pragma omp barrier

When a thread encounters #pragma omp barrier, it blocks until every thread in the team reaches the barrier. Once all threads arrive, all threads proceed simultaneously.

---

5.15 High-Performance Synchronization: #pragma omp atomic

When a thread finishes its sending loop, it increments done_sending. Protecting this increment with #pragma omp critical is unnecessarily expensive:

OpenMP provides the lightweight atomic directive:

#pragma omp atomic
done_sending++;

Why atomic is Faster than critical

Modern processors provide dedicated hardware instructions for atomic operations (such as load-linked/store-conditional or LOCK CMPXCHG on x86). The atomic directive leverages hardware atomic instructions directly without entering operating system mutexes or software lock structures.

Legal Forms for atomic:

The statement must be a single C assignment matching one of:

• x <op>= <expression>;
• x++; • ++x; • x--; • --x;

Where <op> is one of: +, *, -, /, &, ^, |, <<, or >>.

Atomic Scope Restrictions

The <expression> on the right-hand side must not reference x. Furthermore, only the load and store of x are atomic; any evaluation of operands within <expression> is not protected.

---

5.16 Critical Sections vs. OpenMP Locks

The Hidden Bottleneck of Unnamed critical Directives

By default, OpenMP treats all unnamed #pragma omp critical directives in a program as part of a single global critical section:

/* Thread 0 trying to enqueue into Queue 1 */
#pragma omp critical
Enqueue(q1, ...);

/* Thread 2 trying to enqueue into Queue 3 */
#pragma omp critical
Enqueue(q3, ...);

Even though Queue 1 and Queue 3 are completely separate data structures, Thread 2 is forced to wait for Thread 0! This completely serializes execution across all queues.

Named Critical Sections

OpenMP allows naming critical sections:

#pragma omp critical(queue_lock)
Enqueue(...);

Critical sections with different names can execute simultaneously. However, critical section names are compile-time identifiers. They cannot be dynamically instantiated per queue at runtime.

---

5.17 OpenMP Locks: omp_lock_t

To provide dynamic, fine-grained mutual exclusion for data structures, OpenMP provides simple locks:

#include <omp.h>

void omp_init_lock(omp_lock_t* lock_p);      /* Initializes lock in unlocked state */
void omp_set_lock(omp_lock_t* lock_p);       /* Blocks until lock is acquired      */
void omp_unset_lock(omp_lock_t* lock_p);     /* Releases the lock                  */
void omp_destroy_lock(omp_lock_t* lock_p);   /* Deallocates lock resources         */

Per-Queue Locking in Message Passing

We embed an omp_lock_t directly inside each queue structure:

struct Queue {
    omp_lock_t lock;
    int enqueued;
    int dequeued;
    /* queue buffer pointers ... */
};

/* Enqueue with fine-grained lock */
omp_set_lock(&(q_p->lock));
Enqueue(q_p, my_rank, mesg);
omp_unset_lock(&(q_p->lock));

Now, Thread 0 enqueuing into Queue 1 and Thread 2 enqueuing into Queue 3 proceed in parallel without blocking each other.

---

5.18 Decision Matrix: atomic, critical, or Locks?

Table 5.5: Mutual Exclusion Mechanisms Comparison

Mechanism	Speed / Overhead	Granularity	Best Use Case
#pragma omp atomic	Fastest (Hardware instruction)	Single variable statement	Counter updates (x++), accumulators
#pragma omp critical	Moderate (Software mutex)	Coarse code block	Simple multi-line updates to shared data
OpenMP Locks (omp_lock_t)	Fine-grained (Data structure bound)	Dynamic runtime objects	Per-object locking (e.g., hash tables, queues, graph nodes)

---

5.19 Critical Pitfalls: Deadlocks and Fairness

1. Never Mix Mutual Exclusion Types: An atomic directive on variable x will not block another thread executing a critical section that updates x. Always use consistent synchronization for a given variable.
2. No Fairness Guarantee: OpenMP does not guarantee FIFO order among threads waiting for a lock. A thread can experience starvation if other threads continually acquire the lock first.
3. Nested Critical Sections Cause Deadlock:

   /* DEADLOCK: Thread hangs forever */
   #pragma omp critical
   {
       y = f(x);
   }
   
   double f(double x) {
       #pragma omp critical /* DEADLOCK: Same thread tries to re-enter */
       z = g(x);
   }

4. Acquisition Ordering: If threads acquire multiple locks or named critical sections in different orders (e.g., Thread A locks $L_1$ then $L_2$, while Thread B locks $L_2$ then $L_1$), the program will deadlock. Locks must always be acquired in a globally consistent order.