02 - Concurrency & Race Conditions (The Hackathon B Core)

Juspay Hackathon Part B focuses heavily on your ability to manually trace thread interleavings and identify race conditions.

1. What is a Race Condition?

A race condition occurs when two or more threads access shared data concurrently, and at least one thread modifies it. Because thread scheduling is non-deterministic (you don't know which thread will run when), the final outcome depends on the specific timing (interleaving) of instructions.

The "Check-Then-Act" Flaw

The most common race condition is assuming a variable hasn't changed between checking its state and acting on it.

if (node.isLocked == false) {      // 1. CHECK
    // ... thread context switch here ...
    node.isLocked = true;          // 2. ACT
}

This block is NOT ATOMIC. The hardware executes it as multiple assembly instructions.

2. Race Conditions in "Tree of Space"

Here are the exact scenarios you need to recite in the interview.

Scenario A: Same-Node Locking (Lost Mutual Exclusion)

Setup: Thread 1 calls lock(India, uid=5), Thread 2 calls lock(India, uid=7).

Time	Thread 1	Thread 2	State of `India.isLocked`
T1	Reads `isLocked == false`		`false`
T2	(Context switch)	Reads `isLocked == false`	`false`
T3	Writes `isLocked = true`		`true` (Locked by uid 5)
T4	Returns `true` (Success)	Writes `isLocked = true`	`true` (Overwritten by uid 7)
T5		Returns `true` (Success)	`true`

Result: Both threads return true. The mutual exclusion invariant is violated.

Scenario B: Shared Ancestor Counter Mutation (Lost Update)

Setup: Thread 1 calls lock(China) and Thread 2 calls lock(India). They share the ancestor Asia. Both must increment Asia.lockedDescendantsCount.

Incrementing (count++) is a Read-Modify-Write operation:

Load count from memory into CPU register.
Add 1 to register.
Store register back to memory.

Time	Thread 1	Thread 2	Memory `Asia.count`
T1	Read `count` -> 0		0
T2		Read `count` -> 0	0
T3	Add 1 -> (Reg = 1)		0
T4	Store Reg -> Memory (1)		1
T5		Add 1 -> (Reg = 1)	1
T6		Store Reg -> Memory (1)	1

Result: The counter should be 2, but it is 1. The state of the tree is permanently corrupted.

3. Deadlocks

A Deadlock happens when two or more threads are blocked forever, waiting for each other to release a lock.

The Four Necessary Conditions (Coffman Conditions)

For a deadlock to occur, ALL FOUR of these must be true simultaneously:

Mutual Exclusion: Resources (locks) cannot be shared. Only one thread can use a resource at a time.
Hold and Wait: A thread holds at least one resource and is waiting to acquire additional resources held by other threads.
No Preemption: A resource cannot be forcibly taken from a thread; the thread must release it voluntarily.
Circular Wait: A closed chain of threads exists, where Thread A waits for B, B waits for C, and C waits for A.

Deadlock Prevention in Trees

To prevent deadlocks, you must break at least one of the four conditions. The most practical one to break is Circular Wait.

Lock Ordering Strategy: Always acquire locks in a globally consistent order. In a tree, the natural order is either strictly Leaf-to-Root or strictly Root-to-Leaf.

Example: Thread 1 wants to lock China and Asia. Thread 2 wants to lock India and Asia. If Thread 1 locks China -> Asia, and Thread 2 locks India -> Asia. They will never deadlock because they both lock children before locking the parent. They will naturally serialize at Asia.

4. Livelock & Starvation

Livelock: Threads are actively executing and changing states in response to each other, but no actual progress is made. (Analogy: Two people walking in a hallway, both side-stepping into the same direction repeatedly to avoid each other).
Starvation: A thread is perpetually denied the resources it needs to make progress.
- Cause: A poorly designed scheduling algorithm, or a Reader-Writer lock where continuous Readers prevent a Writer from ever acquiring the lock (Writer Starvation).

02-concurrency-and-race-conditions.md