Concurrency & Deadlock lab report

1. Title and aim

Concurrent Systems & Synchronization: Mutex Locks, Counting Semaphores, Deadlock Detection, Coffman Conditions, and the Dining Philosophers Problem. To investigate multi-threaded concurrent programming architectures, analyze synchronization mechanisms (mutexes, counting semaphores, atomic Compare-And-Swap), evaluate race conditions in shared memory critical sections, examine the four Coffman conditions for deadlocks, solve the Dining Philosophers Problem using Dijkstra's resource hierarchy partial order, track dynamic state dependencies using Resource Allocation Graphs (RAG) and cycle detection, verify the linear atomic synchronization scaling law S(N) = k_sync · N + S_0 = 4.0000 · N + 0.0000 operations across worker threads N ∈ [2, 14], and evaluate Dijkstra's Banker's Algorithm for deadlock avoidance.

2. Abstract

Seven benchmark trials were generated across worker thread concurrency levels N = 2 to N = 14 threads (total atomic synchronization operations S from 8 to 56 operations). An ordinary least-squares regression of atomic operations against thread count yielded an empirical scaling multiplier of 4.0000 operations/thread and an intercept of 0.0000 operations, demonstrating exact agreement with Dijkstra's resource hierarchy synchronization model S(N) = 4N (difference = 0.0000%). The empirical telemetry confirms that by breaking Coffman's circular wait condition through asymmetric lock ordering, each thread completes its critical section in strictly 4 atomic operations without deadlocks or starvation.

3. Apparatus and fixed settings

• Circular Dining Philosophers Multi-Threaded Engine: Coordinates N concurrent threads executing alternating thinking, resource acquisition, critical section eating, and lock release cycles.
• Resource Allocation Graph (RAG) Cycle Detector: Maintains directed request (T_i → R_j) and assignment (R_j → T_i) edges, executing Tarjan's strongly connected components algorithm to detect deadlocks.
• Atomic Compare-And-Swap (CAS) Mutex Unit: Implements hardware-accelerated mutual exclusion locks, counting semaphores, and condition variables with atomic memory bus guarantees.
• Dijkstra Resource Hierarchy Partial Order Enforcer: Enforces global linear ordering on lock acquisitions (lower index first) to eliminate the Coffman circular wait condition.
• Banker's Algorithm Safety State Validator: Evaluates Allocation, Max, Available, and Need matrices to verify safe execution sequences and prevent unsafe resource allocations.
• Concurrency Telemetry & Contention Profiler: Measures atomic operations, lock contention wait times, context switches, and validates ordinary least-squares regression against S(N) = 4N.
• Concurrency model: Multi-threaded shared memory process model with POSIX mutex locks.
• Resource allocation: N shared mutex forks arranged in a circular topology.
• Deadlock prevention policy: Dijkstra's asymmetric resource hierarchy (acquire lower fork index first).
• Thread concurrency levels tested: N ∈ [2, 4, 6, 8, 10, 12, 14] worker threads.
• Graph analysis: Dynamic Resource Allocation Graph (RAG) tracking request and assignment edges.

4. Theory and graph choice

In multi-core computing architectures, parallel execution of concurrent threads across shared memory is essential to maximize throughput across operating system kernels, high-performance database engines, distributed cloud microservices, and real-time game engines. However, concurrent non-deterministic thread interleavings introduce race conditions that corrupt shared memory states unless protected by synchronization primitives. In 1965, Edsger W. Dijkstra formulated the critical section problem and introduced the counting semaphore, establishing the mathematical foundations of mutual exclusion. Yet synchronization introduces a profound secondary vulnerability: Deadlock. In 1971, Edward G. Coffman Jr. proved that deadlocks manifest if and only if four conditions hold simultaneously: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. In Dijkstra's classic Dining Philosophers Problem, N concurrent processes contend for N shared resources; under symmetric acquisition policies, simultaneous requests generate circular wait, causing all threads to permanently deadlock. Dijkstra eliminated this circular dependency through Resource Hierarchy: enforcing a global partial ordering on lock acquisitions guarantees that at least one thread acquires both resources and progresses. In our standardized concurrent execution model, each philosopher thread executes exactly 4 atomic synchronization operations per cycle: two lock acquires (left and right forks) and two lock releases. Across N threads, the cumulative atomic operation count scales strictly as S(N) = 4.0000 · N operations. In this laboratory investigation, students benchmark atomic synchronization operations across concurrency levels N ∈ [2, 14], verify the linear scaling law S(N) = 4.0000 · N + 0.0000 via ordinary least-squares regression, explore Resource Allocation Graph cycle detection, evaluate Dijkstra's Banker's Algorithm safety vectors, and analyze lock contention and priority inversion dynamics.

The mathematical regression fits the linear model y = mx + b, where x = N represents worker thread count in threads, y = S represents total atomic synchronization operations, m represents the step multiplier k_sync, and b represents the baseline operation offset (theoretically S_0 = 0.0000 operations). The gradient has physical units operations/thread.

5. Method

1. Initialize the concurrent environment with N worker threads and N shared mutex locks across benchmark concurrency levels N ∈ [2, 4, 6, 8, 10, 12, 14]. Clear the Resource Allocation Graph edge set.
2. Set all N philosopher threads to Thinking state. Reset atomic operation counter S, lock contention timer, and context switch telemetry.
3. Simulate transition of thread i to Hungry state. Enforce Dijkstra's resource hierarchy: identify lower-numbered fork index min(i, (i+1)%N) and execute atomic mutex acquisition wait(fork_low), incrementing operation counter S by 1 and updating the RAG with assignment edge.
4. Identify higher-numbered fork index max(i, (i+1)%N) and execute atomic mutex acquisition wait(fork_high), incrementing operation counter S by 1. Transition thread i to Eating state (critical section).
5. Upon completing eating, execute atomic lock release signal(fork_low) and signal(fork_high), incrementing operation counter S by 2 (total 4 operations for thread i). Return thread to Thinking state and clear RAG edges.
6. Plot recorded atomic synchronization operations S(N) against thread count N. Perform ordinary least-squares regression to verify the theoretical slope k_sync = 4.0000 operations/thread, intercept S_0 = 0.0000, and correlation coefficient R² = 1.00000.

6. Observations and calculation table

All benchmark observations use strictly controlled memory buffers. Values are recorded deterministically from the algorithmic comparator register. Residuals are computed relative to the ordinary least-squares regression line.

Download the sample observations (CSV) ↓

7. Worked calculation for one observation

8. Graph, gradient and final calculation

Circular markers represent empirical benchmark observations. The solid line represents the ordinary least-squares asymptotic linear fit.

9. Uncertainty and comparison

Percentage difference = |estimate − theoretical value| / |theoretical value| × 100 = 0.0000%.

For n = 7 benchmark observations, Σresidual² = 0.00000; s² = Σresidual²/(n − 2). Gradient standard error = √[s²/Σ(x − x̄)²] = 9.4491e-08. Intercept standard error = √[s²(1/n + x̄²/Σ(x − x̄)²)] = 8.4515e-07.

Propagating the fit parameters yields a fit standard error of 9.4491e-08 operations/thread, with an ideal coefficient of determination R² = 1.000000.

In concurrent systems and distributed synchronization theory, the atomic operation count S(N) = k_sync · N + S_0 = 4.0000·N + 0.0000 operations across thread count N is an exact deterministic arithmetic invariant for the Dining Philosophers protocol. Unlike continuous physical instrumentation, there is no analog sensor noise, thermal drift, or calibration variance in counting discrete atomic lock acquisitions and semaphore signals. However, in physical multi-core processors and operating system kernels, wall-clock concurrency throughput and lock contention are heavily modulated by microarchitectural dynamics: (1) CPU cache coherence protocols and bus locking: atomic Compare-And-Swap (CAS) instructions force the CPU to lock cache lines or memory buses under the MESI/MOESI coherence protocol, incurring 40–100 clock cycles of interconnect latency per contended lock; (2) Operating system context switch and thread scheduling overhead: when a thread blocks on a contested mutex, the kernel transitions the thread from Running to Waiting and performs a full context switch (saving CPU registers, switching page tables), consuming 1–5 µs of CPU overhead; (3) Spinlock thresholding vs sleep-locks: hybrid mutexes spin briefly in user space for a few hundred cycles before sleeping, amortizing context-switch overhead for short critical sections; and (4) Priority inversion on shared synchronization objects: low-priority threads holding locks required by high-priority threads cause systemic stalling unless Priority Inheritance Protocols (PIP) are enabled. Ordinary least-squares linear regression of observed atomic operations against thread count N across instances from N = 2 to N = 14 threads yields an empirical scaling factor k_sync = 4.0000 operations/thread and baseline intercept S_0 = 0.0000 operations with zero residual variance (R² = 1.00000), verifying the linear synchronization complexity bound Θ(N) with mathematical certitude.

10. Result and discussion

The empirical benchmark observations provide rigorous quantitative verification of Concurrent Systems Theory, Synchronization Primitives, and Deadlock Dynamics. In multi-core computing architectures, non-deterministic thread interleavings create race conditions that corrupt shared mutable data unless protected by mutual exclusion. However, improper synchronization introduces a fatal failure mode: Deadlock. Edward G. Coffman Jr. proved in 1971 that deadlocks require four simultaneous conditions: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait. In Dijkstra's classic Dining Philosophers Problem, N threads compete for N shared mutex locks; under symmetric acquisition policies, simultaneous requests generate circular wait, causing all threads to permanently deadlock. Dijkstra eliminated this circular dependency through Resource Hierarchy: enforcing a global partial ordering on lock acquisitions guarantees that at least one thread acquires both resources and progresses. In our standardized concurrent execution model, each philosopher thread executes exactly 4 atomic synchronization operations per cycle: two lock acquires (left and right forks) and two lock releases. Across N threads, the cumulative atomic operation count scales strictly as S(N) = 4.0000 · N operations. Across all benchmark trials from N = 2 to N = 14 threads, the empirical regression slope m = 4.0000 operations/thread and baseline intercept b = 0.0000 confirm this invariant with zero residual variance (R² = 1.00000). Comparative analysis across concurrency paradigms highlights critical architectural trade-offs: Resource Allocation Graphs (RAG) detect deadlock cycles in O(|V| + |E|) time using Tarjan's strongly connected components. Dijkstra's Banker's Algorithm evaluates multi-instance resource matrices at runtime to guarantee safe state transitions. Finally, real-world operating system case studies—such as the 1997 Mars Pathfinder priority inversion incident—demonstrate the necessity of Priority Inheritance Protocols (PIP) to prevent low-priority threads from indefinitely stalling mission-critical high-priority tasks.

11. Precautions and limitations

• In multithreaded systems, always acquire multiple locks in a globally consistent canonical order (e.g., ascending address or resource ID) to prevent circular wait deadlocks.
• Avoid calling external or third-party code while holding a mutex, as unknown callbacks may attempt to acquire additional locks, introducing unexpected deadlock cycles.
• Implement lock timeouts (e.g. pthread_mutex_timedlock) where feasible so that failing to acquire a lock triggers recovery routines rather than permanent thread stalls.
• When using condition variables, always evaluate the waking condition inside a while loop (while (!condition) wait()) to guard against spurious wakeups.

The simulated benchmark environment models idealized POSIX mutex locks and fair round-robin thread scheduling where synchronization operations execute deterministically (S(N) = 4N operations). In physical multi-core server processors, concurrent performance is heavily modulated by CPU hardware cache coherence protocol traffic (MESI/MOESI cache line invalidation storms on contended lock variables), atomic memory bus lock overhead, OS scheduler quantum jitter, thread migration across NUMA nodes, and priority inversion overhead. In the concurrent Dining Philosophers synchronization benchmark across worker thread counts N in [2, 14] threads (where each thread process executes alternating thinking, resource contention, critical section eating, and fork release phases under Dijkstra's resource hierarchy lock-ordering policy), each philosopher thread requires exactly 2 shared mutual exclusion locks (forks) to proceed. In each completed dining cycle, every thread executes exactly 4 atomic synchronization primitives: (1) acquire lower-ordered fork wait(fork_low); (2) acquire higher-ordered fork wait(fork_high); (3) release lower-ordered fork signal(fork_low); and (4) release higher-ordered fork signal(fork_high). Because Dijkstra's asymmetric resource hierarchy eliminates the circular wait condition, all N threads complete their critical sections without deadlock or starvation. Across all benchmark concurrency levels N ∈ [2, 4, 6, 8, 10, 12, 14], the cumulative atomic operation count is strictly governed by the exact deterministic linear invariant S(N) = 4.0000 · N + 0.0000 operations. Plotting atomic operations against thread count N yields an ordinary least-squares regression slope k_sync = 4.0000 operations/thread and baseline intercept S_0 = 0.0000 operations with an ideal coefficient of determination R² = 1.000000.

12. Conclusion

This laboratory investigation quantitatively verified the atomic synchronization mechanics, resource hierarchy partial ordering, and deadlock prevention scaling of Concurrent Systems. Through systematic benchmarking across thread counts from N = 2 to 14 threads, we verified the empirical synchronization multiplier k_sync = 4.0000 operations/thread and baseline intercept S_0 = 0.0000 operations with an ideal R² = 1.00000. The investigation established the microarchitectural efficiency and theoretical necessity of breaking Coffman conditions, tracking resource allocation graphs, and implementing priority inheritance, proving why robust synchronization forms the computational bedrock of multi-core operating systems, high-performance database engines, and fault-tolerant distributed systems.