⏱️ 8 min read

Concurrency in LLD

Concurrency shows up in LLD when multiple threads or requests access shared state simultaneously. A parking lot with 10 entry gates, a rate limiter handling 1000 requests/second, or a task scheduler with worker threads – all need synchronization to avoid corrupted state.

Why this matters: Interviewers ask “how would you handle concurrent access?” as a follow-up to almost every machine coding problem. Knowing when and where to add synchronization (without making everything sequential) is a senior-level skill.

Prerequisites

SOLID Principles – SRP helps isolate concurrent critical sections
Strategy Pattern – strategies themselves should be thread-safe or stateless

The Core Problem: Race Conditions

flowchart LR
    A["Thread A: read balance = 100"]:::client
    B["Thread B: read balance = 100"]:::data
    C["Thread A: deduct 80<br/>write balance = 20"]:::client
    D["Thread B: deduct 70<br/>write balance = 30"]:::data
    E["Expected: insufficient funds<br/>Actual: balance = 30 negative"]:::service

    A --> C
    B --> D
    C --> E
    D --> E

    classDef client fill:#4c3a5e,stroke:#818cf8,color:#e2e8f0
    classDef service fill:#1a3a2a,stroke:#4ade80,color:#e2e8f0
    classDef data fill:#3b3520,stroke:#fbbf24,color:#e2e8f0

Both threads read the same balance, both decide they can proceed, both write. The account goes negative. This is a check-then-act race condition.

Synchronization Primitives

// 1. Mutex (synchronized / ReentrantLock)
// Use when: exclusive access to shared mutable state
public class Wallet {
    private final Lock lock = new ReentrantLock();
    private long balanceCents;

    public void debit(long amountCents) {
        lock.lock();
        try {
            if (balanceCents < amountCents) {
                throw new InsufficientBalanceException(balanceCents, amountCents);
            }
            balanceCents -= amountCents;
        } finally {
            lock.unlock(); // ALWAYS in finally
        }
    }

    public void credit(long amountCents) {
        lock.lock();
        try {
            balanceCents += amountCents;
        } finally {
            lock.unlock();
        }
    }

    public long getBalance() {
        lock.lock();
        try {
            return balanceCents;
        } finally {
            lock.unlock();
        }
    }
}

// 2. ReadWriteLock
// Use when: many readers, few writers
public class ParkingLot {
    private final ReadWriteLock rwLock = new ReentrantReadWriteLock();
    private final List<Floor> floors;

    public int getAvailableSlots(VehicleType type) {
        rwLock.readLock().lock(); // Multiple threads can read simultaneously
        try {
            return floors.stream()
                .mapToInt(f -> f.countAvailable(type))
                .sum();
        } finally {
            rwLock.readLock().unlock();
        }
    }

    public Ticket park(Vehicle vehicle) {
        rwLock.writeLock().lock(); // Exclusive access for writes
        try {
            Slot slot = strategy.findSlot(floors, vehicle.getType());
            if (slot == null) throw new ParkingFullException();
            slot.occupy(vehicle);
            return new Ticket(vehicle, slot, Instant.now());
        } finally {
            rwLock.writeLock().unlock();
        }
    }
}

// 3. Atomic variables
// Use when: single variable needs atomic updates (counters, flags)
public class RateLimiter {
    private final AtomicInteger requestCount = new AtomicInteger(0);
    private final AtomicLong windowStart = new AtomicLong(System.currentTimeMillis());
    private final int maxRequests;
    private final long windowMillis;

    public boolean allowRequest() {
        long now = System.currentTimeMillis();
        long start = windowStart.get();
        if (now - start > windowMillis) {
            // New window -- reset
            if (windowStart.compareAndSet(start, now)) {
                requestCount.set(1);
                return true;
            }
        }
        return requestCount.incrementAndGet() <= maxRequests;
    }
}

import threading
from concurrent.futures import ThreadPoolExecutor

# 1. Lock (mutex)
class Wallet:
    def __init__(self, balance: int = 0):
        self._balance = balance
        self._lock = threading.Lock()

    def debit(self, amount: int):
        with self._lock:  # Context manager ensures unlock
            if self._balance < amount:
                raise InsufficientBalanceError(self._balance, amount)
            self._balance -= amount

    def credit(self, amount: int):
        with self._lock:
            self._balance += amount

    @property
    def balance(self) -> int:
        with self._lock:
            return self._balance

# 2. RLock (reentrant -- same thread can acquire multiple times)
class ParkingLot:
    def __init__(self):
        self._lock = threading.RLock()
        self._floors = []

    def park(self, vehicle) -> 'Ticket':
        with self._lock:
            slot = self._strategy.find_slot(self._floors, vehicle.type)
            if slot is None:
                raise ParkingFullError()
            slot.occupy(vehicle)
            return Ticket(vehicle, slot)

    def get_available(self, vehicle_type) -> int:
        with self._lock:
            return sum(f.count_available(vehicle_type) for f in self._floors)

# 3. Thread pool for parallel task execution
class TaskScheduler:
    def __init__(self, max_workers: int = 4):
        self._executor = ThreadPoolExecutor(max_workers=max_workers)
        self._tasks: list = []
        self._lock = threading.Lock()

    def submit(self, task: 'Task'):
        with self._lock:
            self._tasks.append(task)
        self._executor.submit(self._execute_task, task)

    def _execute_task(self, task):
        try:
            task.run()
        except Exception as e:
            task.mark_failed(str(e))

#include <mutex>
#include <shared_mutex>
#include <atomic>
#include <thread>

// 1. std::mutex
class Wallet {
    mutable mutex mtx_;
    long balanceCents_ = 0;
public:
    void debit(long amount) {
        lock_guard<mutex> lock(mtx_);
        if (balanceCents_ < amount)
            throw InsufficientBalanceException(balanceCents_, amount);
        balanceCents_ -= amount;
    }

    void credit(long amount) {
        lock_guard<mutex> lock(mtx_);
        balanceCents_ += amount;
    }

    long balance() const {
        lock_guard<mutex> lock(mtx_);
        return balanceCents_;
    }
};

// 2. shared_mutex (read-write lock)
class ParkingLot {
    mutable shared_mutex rwMutex_;
    vector<Floor> floors_;
public:
    int getAvailable(VehicleType type) const {
        shared_lock lock(rwMutex_);  // Multiple readers OK
        int count = 0;
        for (const auto& floor : floors_)
            count += floor.countAvailable(type);
        return count;
    }

    Ticket park(Vehicle* vehicle) {
        unique_lock lock(rwMutex_);  // Exclusive writer
        auto slot = strategy_->findSlot(floors_, vehicle->getType());
        if (!slot) throw ParkingFullException();
        slot->occupy(vehicle);
        return Ticket(vehicle, slot);
    }
};

// 3. Atomic for lock-free counters
class RateLimiter {
    atomic<int> count_{0};
    atomic<long long> windowStart_{0};
    int maxRequests_;
public:
    bool allowRequest() {
        auto now = chrono::steady_clock::now().time_since_epoch().count();
        int current = count_.fetch_add(1);
        return current < maxRequests_;
    }
};

Thread Pool Pattern

Thread pools reuse a fixed number of threads to process tasks, avoiding the overhead of creating/destroying threads for each request.

public class TaskScheduler {
    private final ExecutorService executor;
    private final BlockingQueue<ScheduledTask> taskQueue;
    private final Map<String, Future<?>> runningTasks = new ConcurrentHashMap<>();

    public TaskScheduler(int poolSize) {
        this.executor = Executors.newFixedThreadPool(poolSize);
        this.taskQueue = new LinkedBlockingQueue<>();
    }

    public String submit(Runnable task, String name) {
        String taskId = UUID.randomUUID().toString();
        Future<?> future = executor.submit(() -> {
            try {
                task.run();
            } catch (Exception e) {
                // Log failure, update task status
            } finally {
                runningTasks.remove(taskId);
            }
        });
        runningTasks.put(taskId, future);
        return taskId;
    }

    public boolean cancel(String taskId) {
        Future<?> future = runningTasks.get(taskId);
        if (future != null) {
            return future.cancel(true);
        }
        return false;
    }

    public void shutdown() {
        executor.shutdown();
        try {
            if (!executor.awaitTermination(30, TimeUnit.SECONDS)) {
                executor.shutdownNow();
            }
        } catch (InterruptedException e) {
            executor.shutdownNow();
        }
    }
}

from concurrent.futures import ThreadPoolExecutor, Future
import uuid

class TaskScheduler:
    def __init__(self, pool_size: int = 4):
        self._executor = ThreadPoolExecutor(max_workers=pool_size)
        self._running: dict[str, Future] = {}

    def submit(self, task: callable, name: str = "") -> str:
        task_id = str(uuid.uuid4())
        future = self._executor.submit(task)
        self._running[task_id] = future
        future.add_done_callback(lambda f: self._running.pop(task_id, None))
        return task_id

    def cancel(self, task_id: str) -> bool:
        future = self._running.get(task_id)
        if future:
            return future.cancel()
        return False

    def shutdown(self):
        self._executor.shutdown(wait=True)

#include <thread>
#include <queue>
#include <functional>
#include <condition_variable>

class ThreadPool {
    vector<thread> workers_;
    queue<function<void()>> tasks_;
    mutex queueMutex_;
    condition_variable condition_;
    bool stop_ = false;
public:
    explicit ThreadPool(size_t numThreads) {
        for (size_t i = 0; i < numThreads; ++i) {
            workers_.emplace_back([this] {
                while (true) {
                    function<void()> task;
                    {
                        unique_lock lock(queueMutex_);
                        condition_.wait(lock, [this] {
                            return stop_ || !tasks_.empty();
                        });
                        if (stop_ && tasks_.empty()) return;
                        task = std::move(tasks_.front());
                        tasks_.pop();
                    }
                    task();
                }
            });
        }
    }

    void submit(function<void()> task) {
        {
            lock_guard lock(queueMutex_);
            tasks_.push(std::move(task));
        }
        condition_.notify_one();
    }

    ~ThreadPool() {
        { lock_guard lock(queueMutex_); stop_ = true; }
        condition_.notify_all();
        for (auto& w : workers_) w.join();
    }
};

When to Use vs When to Avoid

Synchronization Tool	Use When	Avoid When
Mutex/Lock	Protecting shared mutable state	Read-heavy workloads (use RWLock)
ReadWriteLock	Many readers, few writers	Write-heavy (adds overhead vs plain mutex)
Atomic variables	Single counters or flags	Complex multi-field updates
Thread pool	Many short-lived tasks	Few long-running tasks (dedicated threads better)
ConcurrentHashMap	Shared map with concurrent access	Single-threaded context

Common Pitfalls

Pitfall	Consequence	Prevention
Forgetting to unlock	Deadlock	Use try-finally or lock_guard/with statement
Locking too broadly	Poor performance (everything serial)	Lock only the critical section
Locking too narrowly	Race condition between lock regions	Ensure check-then-act is atomic
Lock ordering violation	Deadlock	Always acquire locks in the same order
Holding locks during I/O	Blocks all other threads	Do I/O outside the lock

Interview Questions

“Where would you add synchronization in your design?” – Identify the shared mutable state: the slot allocation map, the wallet balance, the task queue. Those are your critical sections.
“Mutex vs ReadWriteLock?” – If 90% of operations are reads (checking available slots), RWLock lets readers proceed in parallel. If writes are frequent, plain mutex is simpler and often faster.
“How do you avoid deadlocks?” – Lock ordering (always acquire locks in the same order), timeouts (tryLock with timeout), and minimizing lock scope (hold locks for the shortest time possible).
“What about lock-free data structures?” – ConcurrentHashMap, AtomicInteger, CAS operations. Use them for simple counters and flags. For complex state, locks are clearer and less error-prone.
“In the interview, should you write thread-safe code?” – Only if the problem explicitly mentions concurrent access. Don’t add locks preemptively. Mention it as an improvement: “If this were multi-threaded, I’d add a lock here.”