Design a Parking Lot - Multi Threaded
What is the Parking Lot - Multithreaded Problem?
Section titled “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
Section titled “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
Section titled “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?
Section titled “What’s Expected?”1. System Architecture
Section titled “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
Section titled “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
Section titled “System Flow”Concurrent Entry Flow
Section titled “Concurrent Entry Flow”
Key Design Challenges
Section titled “Key Design Challenges”1. Thread-Safe Spot Assignment
Section titled “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
Section titled “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
Section titled “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
Section titled “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
Section titled “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
Section titled “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
Related Problems
Section titled “Related Problems”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.