Mastering Multithreading: Synchronization and Concurrency

Understanding Synchronization

Synchronization ensures the correct ordering of instructions across threads. It relies on hardware support to achieve two primary concurrency objectives:

• Mutual Exclusion: Solved using locks.
• Ordering: Solved using locks and semaphores.

A condition variable acts as a queue for waiting threads. Maintain state alongside condition variables; they are used to signal threads when state changes. If the state is already as needed, the thread does not wait for a signal. Whenever a lock is acquired, recheck assumptions about the state. Some libraries experience spurious wakeups, where multiple threads may wake up unexpectedly. To wake the right thread, use specific condition variables per condition rather than waking all threads.

Thread Architecture

Threads within a single process share the address space, including the heap and page table base register (PTBR) contents. However, each thread maintains its own:

• Program Counter (PC)
• Stack and Stack Pointer
• Registers
• Thread ID (TID)

Thread Context Switch: The system traps to the kernel, saves the machine state of the current thread into its stack, restores the next thread, and resumes execution at the new PC without changing the address space.

User-Level vs. Kernel-Level Threads

• User-Level Threads: Managed by user libraries. The OS is unaware of these threads, treating the process as a single unit. This offers lower overhead but cannot leverage multiprocessors, and the entire process blocks if one thread blocks.
• Kernel-Level Threads (1:1): The OS provides each user thread with a kernel thread. These are scheduled independently, can run in parallel, and do not block the entire process if one thread stalls, though they incur higher overhead.

Locks and Mutual Exclusion

A critical section is code that accesses shared variables and must not be executed concurrently by more than one thread. Mutual exclusion ensures only one thread executes the critical section at a time, while atomicity ensures instructions run fully or never.

Locking Mechanisms

• Disabling Interrupts: Works for single-processor systems but fails on multiprocessors and can lead to system instability if interrupts are disabled for too long.
• Spin Locks: Threads spin in a loop waiting for a lock. While inefficient, they work well on multi-CPU systems. Ticket locks can be used to ensure fairness.
• Yielding and Sleeping: To avoid wasting CPU cycles, threads can use yield(), park(), or unpark() to deschedule themselves.
• Two-Phase Locks: Combine spinning and sleeping for optimal performance.

Condition Variables and Semaphores

Condition variables allow threads to wait for specific state changes. Always use a while loop rather than an if statement when checking conditions to handle spurious wakeups. Always hold the associated mutex while calling wait() or signal() to prevent race conditions.

Semaphores

A semaphore is an integer variable used for mutual exclusion and event ordering:

• Binary Semaphore (Mutex): Initialized to 1.
• Ordering Semaphore: Initialized to 0.
• Producer/Consumer: Uses two semaphores (empty and full) to manage buffer slots.

Deadlock Prevention

Deadlock occurs when four conditions are met: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. To prevent deadlock, ensure at least one of these conditions does not hold, such as acquiring all required locks atomically or using a single lock for the application.

Key Takeaways

• Kernel-level threads: If one thread blocks, others continue.
• Spin-waiting: Periodically yielding the processor reduces wasted time.
• Efficiency: More code within a mutex decreases concurrency.
• Ordering: Use condition variables or semaphores, not locks.