Race Conditions and Synchronization in Programming

Races

• Races, or race conditions, occur when two or more events depend on each other, but can happen in different orders or simultaneously.
• This can result in an incorrect ordering of events, leading to invalid output.
• For example, a program state might be updated multiple times, and the final output depends on the order of these updates.
• If the incorrect order of updates produces invalid output, a race condition exists.

Synchronization

• Synchronization is the deliberate ordering of events in a computer program.
• It aims to prevent race conditions.
• Synchronization mechanisms may directly order events, prevent simultaneous events, or ensure two events occur at the same time.
• Synchronization is a crucial component to avoid races.

Data Races

• Data races involve concurrent flows modifying shared state.
• The precise order of accesses/modifications matters, and current synchronization may be insufficient.
• A data race occurs when multiple concurrent flows access shared state, at least one flow modifies it, and the order is important for correctness.
• A critical section of code that must be isolated, only accessible by one control flow at a time, is important to prevent data races.

Critical Sections

• A critical section is a region of code that must only be accessed by one control flow at a time.
• In most scenarios any write operation to shared state is considered a critical section.
• Critical sections usually involve accessing to shared state, and only one control flow should be allowed to access a critical section.
• Identifying and defining critical sections correctly is essential for preventing data races.

Atomic Operations

• Atomic operations are the fundamental synchronization mechanism.
• They cannot be interrupted.
• They either succeed completely or fail and have no visible effects, which would show up as multiple operations happening concurrently.
• All atomic operations require hardware support.
• These operations cannot be split up or interrupted, and they occur as a single unit of work.

Atomic Operations in C

• C does not offer guaranteed atomic operations.
• Achieving atomic behavior in C typically necessitates low-level operations like inline assembly, library functions or compiler knowledge/kernel support for correct synchronization.

Mutexes

• A mutex (mutual exclusion) is a software tool for mutual exclusion.
• It has "lock" and "unlock" operations.
• The "lock" operation blocks until the mutex is unlocked.
• Once unlocked, another flow can acquire the lock immediately.
• Implementing/Using mutexes within code usually ensures that only one flow can be inside the critical section at a time, thus preventing races.

Synchronization with Mutexes

• Mutexes can be utilized to create mechanisms that ensure synchronization.
• This guarantees that multiple actions do not happen concurrently or that one action follows another.
• They can guarantee precise order of events within a program.

Using Mutexes around Critical Sections

• Typically, a mutex is used to protect a critical section.
• Ensure only one flow can access the critical section at a time, using locking and unlocking mechanisms.

Semaphores

• Semaphores generalize mutexes by adding a counter.
• Semaphores have "P" (acquire) and "V" (release) operations for controlling and managing access.
• The semaphore counter determines how many flows can concurrently access shared resources.
• Semaphores are implemented using the same locking and unlocking method as a mutex, but have a counter so it can be used for more control.

Semaphores as Mutexes

• Semaphore set to 1 acts like a mutex.
• Initial value of 1 ensures that only one thread can acquire, and the counter will drop to 0 if another is already inside.

Deadlock

• Deadlock is the condition where two or more concurrent flows are waiting for each other, and thus cannot progress beyond their current state, or make any progress.
• This often arises due to concurrent flows needing shared resources (e.g., locks or mutexes).

Necessary Conditions for Deadlocks

• One resource must be mutually exclusive between flows.
• Concurrent flows should hold locks while waiting for other locks.
• Locks cannot be preemptively removed once acquired.
• A circular chain of flows exists, which hold some lock required by the next flow.

Avoiding Deadlock

• A simple solution for deadlock is to set an order for acquiring/releasing mutexes.
• All flows must acquire and release mutexes in the same order to prevent loops and circular waits.
• Maintaining this strict order prevents deadlocks from arising.

Condition Variables

• Condition variables allow a flow to block until a certain condition is met within a loop.
• They assist in efficient blocking and control when a certain condition should allow a flow to proceed.
• If a condition is met, another flow is notified or a broadcast signals any waiting flow.

Mutex Interactions

• When a flow waits using a condition variable, it must hold the mutex.
• The mutex protects the data used in the condition check itself.
• While waiting, the mutex is unlocked.
• Upon waking, the waiting flow re-acquires the mutex.
• This re-acquisition ensures that the data remains in an appropriate state for further operations without inconsistencies or issues if something between acquisition and re-acquisition has modified the data.

Wake and Check Procedure

• The wake and check procedure avoids situations where a waiting thread is falsely signaled, even if the condition wasn't actually met or isn't the exact condition being waited for (due to other operations/events intervening).

Example Condition Control Flow

• This example outlines the basic structure of using mutexes and condition variables to ensure correct synchronization of flows while accessing/modifying shared data.