Design a Parking Lot - Multi Threaded

Design a concurrent parking system with thread-safe operations and fair allocation.

What is the Parking Lot - Multithreaded Problem?

Design a multi-threaded parking lot system that handles concurrent vehicle entries and exits from multiple gates. The system must ensure thread-safe operations, prevent deadlocks, implement fair allocation mechanisms, and maintain real-time availability updates across all threads.

In this problem, you’ll design a system that handles concurrent access patterns, synchronization primitives, and ensures data consistency across multiple threads operating simultaneously.

Problem Overview

Design a parking lot system that supports multiple entry and exit gates operating concurrently, with thread-safe spot assignment, fair queuing, and real-time availability tracking.

Core Requirements

Functional Requirements:

Concurrent Access: Support multiple entry and exit gates (2-4 gates) operating simultaneously.
Thread-Safe Operations: Parking spot assignment and release must be atomic to prevent race conditions.
Deadlock Prevention: Prevent deadlocks when multiple threads compete for the same spot or resources.
Fair Allocation: Implement fair queuing to ensure requests are processed in arrival order (first-come-first-served).
Real-Time Availability: Maintain consistent view of spot availability across all threads using atomic operations.
Transaction Management: Ensure parking operations are transactional (all-or-nothing) to maintain data integrity.
Vehicle Types: Support motorcycles, cars, and trucks with appropriate spot size matching.
Vehicle Lookup: Track vehicles by license plate number across all parking spots.
Fee Calculation: Calculate parking fees based on duration when vehicles exit.
High Throughput: Optimize for high throughput with minimal contention between threads.

Non-Functional Requirements:

Thread Safety: All concurrent operations must be thread-safe using appropriate synchronization mechanisms (locks, semaphores, atomic operations, thread-safe collections).
Deadlock Prevention: Implement consistent lock ordering, timeout mechanisms, or tryLock() with timeouts.
Fair Allocation: Use fair locks, fair semaphores, or queue-based mechanisms for equitable processing.
Performance: Optimize for high throughput by minimizing lock contention, using fine-grained locking, and reducing critical section duration.
Consistency: Real-time availability updates must be consistent across all threads using atomic operations.
Scalability: System should scale to handle increasing numbers of vehicles and gates without significant performance degradation.

What’s Expected?

1. System Architecture

The system coordinates between multiple gates, the parking lot manager, and individual parking spots, all operating concurrently.

2. Key Classes to Design

classDiagram
    class ParkingLot {
        -List~ParkingFloor~ floors
        -Map~String,Ticket~ activeTickets
        -Semaphore entrySemaphore
        +parkVehicle(Vehicle, String) Ticket
        +unparkVehicle(String, String) double
    }
    
    class ParkingSpot {
        -SpotType type
        -SpotStatus status
        -ReentrantLock lock
        +tryPark(Vehicle, long) boolean
        +unpark() boolean
    }
    
    class EntranceGate {
        -ParkingLot parkingLot
        +enterVehicle(Vehicle) Ticket
    }
    
    class Vehicle {
        -String licensePlate
        -VehicleType type
    }
    
    class Ticket {
        -Vehicle vehicle
        -ParkingSpot spot
        -LocalDateTime entryTime
    }

    ParkingLot --> ParkingSpot
    EntranceGate --> ParkingLot
    Ticket --> Vehicle
    Ticket --> ParkingSpot

System Flow

Concurrent Entry Flow

Key Design Challenges

1. Thread-Safe Spot Assignment

Multiple vehicles arriving simultaneously might both see the same spot as available, leading to double-booking.

Solution: Use fine-grained locking with a fair ReentrantLock on each parking spot. Use tryLock() with timeout to prevent indefinite blocking. Combine with a fair semaphore to limit concurrent entry operations and ensure fair queuing.

2. Deadlock Prevention

Multiple threads acquiring locks in different orders can lead to deadlocks.

Solution: Implement consistent lock ordering (Semaphore → Spot Lock → System Lock). Use timeout mechanisms with tryLock() and tryAcquire() to avoid indefinite blocking. Release locks in reverse order of acquisition.

3. Fair Allocation

Without fair queuing, some threads might starve while others get repeated access.

Solution: Use fair locks and semaphores that maintain FIFO queues. Fair ReentrantLock and fair Semaphore ensure threads acquire locks in request order, preventing starvation and ensuring equitable access.

4. Real-Time Availability Consistency

All threads must see consistent availability counts without blocking reads.

Solution: Use atomic operations (AtomicInteger) for availability counters. Atomic operations provide lock-free reads while ensuring thread-safe updates. Combine with thread-safe collections (ConcurrentHashMap) for ticket storage.

What You’ll Learn

By solving this problem, you’ll master:

✅ Concurrency Control - Thread-safe operations using locks, semaphores, and atomic operations.
✅ Deadlock Prevention - Strategies to avoid circular wait conditions.
✅ Fair Allocation - Implementing equitable resource access mechanisms.
✅ Performance Optimization - Fine-grained locking and minimizing contention.
✅ Transaction Management - Ensuring all-or-nothing operations for data integrity.

View Complete Solution & Practice

Ready to see the full implementation? Open the interactive playground to access:

🎯 Step-by-step guidance through the 8-step LLD approach
📊 Interactive UML builder to visualize your design
💻 Complete Code Solutions in Python, Java, C++, TypeScript, JavaScript, C#
🤖 AI-powered review of your design and code

🚀 View Solution in Playground

After mastering Parking Lot - Multithreaded, try these similar problems:

Parking Lot (Tutorial) - Basic parking lot without concurrency.
Elevator System - Multiple Lifts - Concurrent request handling.
Task Scheduler - Resource scheduling and concurrency.