Synchronization Basics
Synchronization Basics¶
Overview¶
When concurrently executing processes or threads access shared resources, problems can arise. In this lesson, we'll learn about Race Conditions, Critical Sections, and synchronization methods including Peterson's Solution and hardware-supported approaches.
Table of Contents¶
- Race Condition
- Critical Section Problem
- Critical Section Solution Requirements
- Peterson's Solution
- Hardware Support
- Practice Problems
1. Race Condition¶
Definition¶
Race Condition
= A situation where the result varies depending on the execution order
when multiple processes/threads access shared data simultaneously
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Race Condition Example β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Shared variable: counter = 5 β
β β
β Thread 1: counter++ β
β Thread 2: counter++ β
β β
β Expected result: counter = 7 β
β Actual result: counter = 6 (or 7, non-deterministic) β
β β
β Why? β
β counter++ is not atomic β
β 1. register = counter (read) β
β 2. register = register + 1 (increment) β
β 3. counter = register (write) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Race Condition Execution Process¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β counter++ Race Condition Details β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Initial value: counter = 5 β
β β
β Thread 1 Thread 2 β
β βββββββββ βββββββββ β
β R1 = counter (R1=5) β
β R2 = counter (R2=5) β
β R1 = R1 + 1 (R1=6) β
β R2 = R2 + 1 (R2=6) β
β counter = R1 (counter=6) β
β counter = R2 (counter=6) β
β β
β Final counter = 6 (not 7!) β
β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Timeline: β β
β β β β
β β T1: βreadβββββincrementβββββwriteββ β β
β β T2: ββββreadβββββincrementββββββwriteββ β β
β β β β β
β β Read before T1 writes β β
β ββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
C Code Example¶
#include <stdio.h>
#include <pthread.h>
int counter = 0; // Shared variable
void* increment(void* arg) {
for (int i = 0; i < 1000000; i++) {
counter++; // Race condition!
}
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, increment, NULL);
pthread_create(&t2, NULL, increment, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
// Expected: 2000000
// Actual: A value less than that (varies each run)
printf("Counter: %d\n", counter);
return 0;
}
/*
Example execution results:
$ ./race_condition
Counter: 1523847
$ ./race_condition
Counter: 1678234
$ ./race_condition
Counter: 1432156
*/
Bank Account Example¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Bank Account Race Condition β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Account balance: balance = 1000 β
β β
β Thread 1 (withdraw 200) Thread 2 (deposit 500) β
β βββββββββββββββββββ βββββββββββββββββββ β
β temp = balance (1000) β
β temp = balance (1000) β
β temp = temp - 200 (800) β
β temp = temp + 500 (1500) β
β balance = temp (800) β
β balance = temp (1500) β
β β
β Final: balance = 1500 β
β Correct result: 1000 - 200 + 500 = 1300 β
β β
β 200 units disappeared! β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
// Bank account race condition code
#include <stdio.h>
#include <pthread.h>
int balance = 1000;
void* withdraw(void* arg) {
int amount = *(int*)arg;
int temp = balance;
// Context switch may occur here
temp = temp - amount;
balance = temp;
return NULL;
}
void* deposit(void* arg) {
int amount = *(int*)arg;
int temp = balance;
// Context switch may occur here
temp = temp + amount;
balance = temp;
return NULL;
}
int main() {
pthread_t t1, t2;
int withdraw_amount = 200;
int deposit_amount = 500;
pthread_create(&t1, NULL, withdraw, &withdraw_amount);
pthread_create(&t2, NULL, deposit, &deposit_amount);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Final balance: %d\n", balance);
// Expected: 1300, Actual: 800 or 1500 or 1300
return 0;
}
2. Critical Section Problem¶
Critical Section Definition¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Critical Section Concept β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Critical Section β
β = Code region that accesses shared resources β
β = Region where only one process should execute at a timeβ
β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Process Structure β β
β β β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β Entry Section β β β
β β β - Request permission to enter β β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β β β
β β βΌ β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β Critical Section β β β
β β β - Code accessing shared resource β β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β β β
β β βΌ β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β Exit Section β β β
β β β - Signal critical section exit β β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β β β
β β βΌ β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β Remainder Section β β β
β β β - Code not using shared resource β β β
β β βββββββββββββββββββββββββββββββββββββββββββ β β
β β β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Code Structure¶
// General critical section structure
while (true) {
// Entry Section
// Acquire permission to enter critical section
// ===== Critical Section =====
// Code accessing shared resources
counter++;
// ==========================================
// Exit Section
// Signal critical section completion
// Remainder Section
// Code not using shared resources
}
3. Critical Section Solution Requirements¶
Three Essential Requirements¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Three Requirements for Critical Section β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Mutual Exclusion β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β When one process is in the critical section, β β
β β no other process can enter β β
β β β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ β β
β β β β β β
β β β P1: βββββ Critical Section βββββ β β β
β β β P2: βββwaitingββββΆβ β β β β
β β β β β β β β
β β β ββββββββββββββ β β β
β β β β β β
β β ββββββββββββββββββββββββββββββββββββββββββββββββ β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Progress β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β If the critical section is empty and processes β β
β β want to enter, a decision must be made on which β β
β β process can enter, and this decision cannot be β β
β β postponed indefinitely β β
β β β β
β β β No indefinite denial of entry β β
β β β Processes in remainder section cannot participateβ β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 3. Bounded Waiting β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β After a process requests entry to critical sectionβ β
β β there is a limit on the number of times other β β
β β processes can enter β β
β β β β
β β β Prevent starvation β β
β β β Guarantee eventual entry β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Violation Examples¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Violation Examples β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Mutual Exclusion Violation: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β P1 and P2 are both in critical section β β
β β β Race condition occurs β β
β β β β
β β P1: ββββββββββββββββββββ β β
β β P2: ββββββββββββββββββββ β Simultaneous! β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Progress Violation: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β Critical section is empty but no one can enter β β
β β β β
β β P1: waiting βββββββββββββββββΆ β β
β β P2: waiting βββββββββββββββββΆ β β
β β Critical section: [empty] β Both cannot enter! β β
β β β β
β β Example: Incorrectly used turn variable β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 3. Bounded Waiting Violation: β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β P1 keeps entering critical section while P2 waitsβ β
β β forever β β
β β β β
β β P1: CS β CS β CS β ... β β
β β P2: waiting βββββββββββββββββββββββββΆ (starvation)β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
4. Peterson's Solution¶
Algorithm Description¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Peterson's Solution β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Software solution for mutual exclusion between two β
β processes β
β β
β Shared variables: β
β β’ flag[2]: Each process's intention to enter β
β β’ turn: Whose turn it is β
β β
β Core idea: β
β β’ Indicate desire to enter (flag[i] = true) β
β β’ Yield to the other (turn = j) β
β β’ Wait if other wants to enter and it's their turn β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Implementation Code¶
#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>
// Shared variables
volatile bool flag[2] = {false, false};
volatile int turn = 0;
int shared_counter = 0;
void* process_0(void* arg) {
for (int i = 0; i < 1000000; i++) {
// Entry Section
flag[0] = true; // Indicate intention to enter
turn = 1; // Yield to the other
while (flag[1] && turn == 1) {
// Busy Waiting
// Wait if other is in critical section and it's their turn
}
// Critical Section
shared_counter++;
// Exit Section
flag[0] = false; // Exit critical section
// Remainder Section
}
return NULL;
}
void* process_1(void* arg) {
for (int i = 0; i < 1000000; i++) {
// Entry Section
flag[1] = true; // Indicate intention to enter
turn = 0; // Yield to the other
while (flag[0] && turn == 0) {
// Busy waiting
}
// Critical Section
shared_counter++;
// Exit Section
flag[1] = false;
// Remainder Section
}
return NULL;
}
int main() {
pthread_t t0, t1;
pthread_create(&t0, NULL, process_0, NULL);
pthread_create(&t1, NULL, process_1, NULL);
pthread_join(t0, NULL);
pthread_join(t1, NULL);
printf("Counter: %d\n", shared_counter); // 2000000
return 0;
}
Correctness Proof¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Peterson's Solution Correctness β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Mutual Exclusion β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β For P0 to be in critical section: β β
β β flag[1] = false OR turn = 0 β β
β β β β
β β For P1 to be in critical section: β β
β β flag[0] = false OR turn = 1 β β
β β β β
β β For both to be in critical section: β β
β β turn = 0 AND turn = 1 (impossible!) β β
β β β β
β β β Mutual exclusion guaranteed β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 2. Progress β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β If only P0 wants to enter: β β
β β flag[0] = true, turn = 1, flag[1] = false β β
β β while condition: flag[1](false) && turn==1 β β
β β β Exit while loop, can enter β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
β 3. Bounded Waiting β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β If P0 is waiting and P1 finishes critical section:β β
β β For P1 to re-enter, must set turn = 0 β β
β β β P0 enters (since turn == 0, P0 has priority) β β
β β β β
β β Entry guaranteed after at most 1 wait β β
β βββββββββββββββββββββββββββββββββββββββββββββββββββββ β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Peterson's Solution Limitations¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Peterson's Solution Limitations β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β 1. Only applicable to two processes β
β β Extension to n processes becomes complex β
β β
β 2. Busy Waiting β
β β Wastes CPU time β
β β Also called spinlock β
β β
β 3. Not guaranteed to work on modern CPUs β
β β Compiler/CPU may reorder instructions β
β β Memory barriers required β
β β
β 4. Performance issues β
β β Cache coherence overhead on multicore systems β
β β
β In modern systems: β
β β’ Hardware support (atomic instructions) β
β β’ OS-provided synchronization tools (mutex, semaphore) β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
5. Hardware Support¶
Test-and-Set (TAS)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Test-and-Set β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Hardware instruction executed atomically: β
β 1. Read current value β
β 2. Set to new value (usually true) β
β β
β Pseudocode: β
β ``` β
β bool test_and_set(bool *target) { β
β bool rv = *target; // Read current value β
β *target = true; // Set to true β
β return rv; // Return previous value β
β } β
β // Entire operation is atomic (non-interruptible) β
β ``` β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Mutual Exclusion Using TAS¶
#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>
#include <stdatomic.h>
// Atomic boolean lock
atomic_bool lock = false;
int shared_counter = 0;
// test_and_set implementation (actually a hardware instruction)
bool test_and_set(atomic_bool *target) {
// C11 atomic: equivalent to atomic_exchange
return atomic_exchange(target, true);
}
void* critical_section(void* arg) {
for (int i = 0; i < 1000000; i++) {
// Entry section: Attempt to acquire lock
while (test_and_set(&lock)) {
// Busy waiting (spinning)
// If lock is already true, keep waiting
}
// Critical section
shared_counter++;
// Exit section: Release lock
lock = false;
}
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, critical_section, NULL);
pthread_create(&t2, NULL, critical_section, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Counter: %d\n", shared_counter); // 2000000
return 0;
}
Compare-and-Swap (CAS)¶
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
β Compare-and-Swap (CAS) β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ€
β β
β Hardware instruction executed atomically: β
β 1. Compare current value with expected value β
β 2. If equal, replace with new value β
β 3. Return previous value β
β β
β Pseudocode: β
β ``` β
β bool compare_and_swap(int *word, int expected, int new_val) { β
β int temp = *word; β
β if (temp == expected) { β
β *word = new_val; β
β return true; β
β } β
β return false; β
β } β
β // Entire operation is atomic β
β ``` β
β β
β x86: CMPXCHG instruction β
β ARM: LDREX/STREX instruction combination β
β β
βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ
Mutual Exclusion Using CAS¶
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>
atomic_int lock = 0; // 0: available, 1: in use
int shared_counter = 0;
void* critical_section(void* arg) {
for (int i = 0; i < 1000000; i++) {
// Entry section: Attempt to acquire lock using CAS
int expected = 0;
while (!atomic_compare_exchange_weak(&lock, &expected, 1)) {
// If CAS fails, expected is updated with current lock value
expected = 0; // Reset to 0 and retry
// Busy waiting
}
// Critical section
shared_counter++;
// Exit section: Release lock
atomic_store(&lock, 0);
}
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, critical_section, NULL);
pthread_create(&t2, NULL, critical_section, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Counter: %d\n", shared_counter); // 2000000
return 0;
}
Lock-Free Counter Using CAS¶
#include <stdio.h>
#include <pthread.h>
#include <stdatomic.h>
atomic_int counter = 0;
void* increment(void* arg) {
for (int i = 0; i < 1000000; i++) {
int old_val, new_val;
do {
old_val = atomic_load(&counter);
new_val = old_val + 1;
} while (!atomic_compare_exchange_weak(&counter, &old_val, new_val));
// Repeat until CAS succeeds
}
return NULL;
}
int main() {
pthread_t t1, t2;
pthread_create(&t1, NULL, increment, NULL);
pthread_create(&t2, NULL, increment, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
printf("Counter: %d\n", counter); // 2000000
return 0;
}
Hardware Instruction Comparison¶
ββββββββββββββββββββ¬ββββββββββββββββββββββββββ¬ββββββββββββββββββββββββββ
β Feature β Test-and-Set β Compare-and-Swap β
ββββββββββββββββββββΌββββββββββββββββββββββββββΌββββββββββββββββββββββββββ€
β Return value β Previous value β Success/failure + currentβ
ββββββββββββββββββββΌββββββββββββββββββββββββββΌββββββββββββββββββββββββββ€
β Conditional β Not possible (always β Possible (change only β
β modification β sets) β if matches) β
ββββββββββββββββββββΌββββββββββββββββββββββββββΌββββββββββββββββββββββββββ€
β Usage β Spinlocks β Lock-free algorithms β
ββββββββββββββββββββΌββββββββββββββββββββββββββΌββββββββββββββββββββββββββ€
β ABA problem β Not applicable β Can occur β
ββββββββββββββββββββΌββββββββββββββββββββββββββΌββββββββββββββββββββββββββ€
β Complexity β Simple β Slightly more complex β
ββββββββββββββββββββ΄ββββββββββββββββββββββββββ΄ββββββββββββββββββββββββββ
ABA problem:
Value changes from A β B β A, but CAS cannot detect the change
Solution: Add version number or use double-word CAS
6. Practice Problems¶
Problem 1: Identifying Race Conditions¶
Find and explain where a race condition can occur in the following code.
int balance = 1000;
void transfer(int from, int to, int amount) {
if (balance >= amount) {
balance = balance - amount;
// ... transfer processing ...
}
}
Show Answer
**Race condition location:** A race condition can occur between `if (balance >= amount)` and `balance = balance - amount` **Scenario:** - Balance: 1000, two threads each trying to transfer 700Thread 1: if (1000 >= 700) β true
Thread 2: if (1000 >= 700) β true (not yet decreased)
Thread 1: balance = 1000 - 700 = 300
Thread 2: balance = 1000 - 700 = 300 (incorrect operation!)
Problem 2: Critical Section Requirements¶
Which of the following is NOT a requirement for solving the critical section problem?
A. Mutual Exclusion B. Progress C. Bounded Waiting D. Fairness
Show Answer
**Answer: D. Fairness** Three essential requirements for critical section problem: 1. Mutual Exclusion - only one at a time 2. Progress - no indefinite waiting 3. Bounded Waiting - guaranteed entry within finite attempts Fairness is desirable but not an essential requirement.Problem 3: Peterson's Solution Analysis¶
Explain why two processes cannot simultaneously enter the critical section in Peterson's Solution.
Show Answer
**Core logic:** For P0 to be in the critical section: - `flag[1] == false` OR `turn == 0` For P1 to be in the critical section: - `flag[0] == false` OR `turn == 1` For both processes to enter simultaneously, both conditions must be true. However: - For both to enter, `flag[0] == true` AND `flag[1] == true` - Therefore the second condition (turn) becomes decisive - `turn` can only be 0 or 1 - `turn == 0 AND turn == 1` is impossible! Therefore, at most one process can enter the critical section.Problem 4: TAS Implementation¶
Implement a lock using Test-and-Set that satisfies the following requirements:
- lock(): Acquire lock
- unlock(): Release lock
- Safe for use by multiple threads
Show Answer
#include <stdatomic.h>
#include <stdbool.h>
typedef struct {
atomic_bool locked;
} spinlock_t;
void spinlock_init(spinlock_t *lock) {
atomic_store(&lock->locked, false);
}
void lock(spinlock_t *lock) {
while (atomic_exchange(&lock->locked, true)) {
// Spin (busy waiting)
// Optional: yield CPU
// sched_yield();
}
}
void unlock(spinlock_t *lock) {
atomic_store(&lock->locked, false);
}
// Usage example:
spinlock_t my_lock;
spinlock_init(&my_lock);
lock(&my_lock);
// Critical section
unlock(&my_lock);
Problem 5: Busy Waiting Problems¶
Explain the problems with busy waiting and suggest solutions.
Show Answer
**Problems with busy waiting:** 1. **CPU time waste** - Consumes CPU cycles even while waiting - Takes away time that other processes could use 2. **Priority inversion** - High priority process spins - Cannot proceed because low priority process holds the lock 3. **Power consumption** - Battery drain on mobile/embedded systems **Solutions:** 1. **Blocking locks** - Transition process to sleep state while waiting - Wake up when lock is released - Example: mutex, semaphore 2. **Hybrid approach** - Spin for a short time, then block - Linux futex, Java synchronized 3. **Using yield** - Yield to other threads instead of spinning - Call `sched_yield()`Next Steps¶
- 08_Synchronization_Tools.md - Mutex, semaphore, monitor