🔒 Custom Semaphore Implementation

🧠 Problem Statement

The goal is to implement a custom semaphore that:

1. Initializes with the maximum number of permits (which is also the initial available permits).
2. Allows threads to acquire a permit, blocking them if no permits are available.
3. Allows threads to release a permit, making it available for others.

❗ Constraints

1. Thread Safety: Must handle concurrent access to permits safely
2. Blocking Behavior: Threads must block when no permits are available
3. Permit Management: Must maintain accurate count of available permits
4. Maximum Limit: Cannot exceed the initial maximum number of permits
5. Notification: Must properly notify waiting threads when permits become available
6. Resource Cleanup: Should handle thread interruption gracefully

📥 Input / Output

Input:

• Maximum number of permits during initialization
• Multiple threads calling acquire() and release() methods
• Thread interruption requests

Output:

• Controlled access to permits based on availability
• Threads blocked when no permits available
• Proper permit counting and distribution

💡 Intuition About Solving This Problem

A semaphore controls access to a limited set of resources. Each thread that wants to access the resource must acquire a permit. If no permits are available, the thread waits. When done, the thread releases the permit.

The key insight is using a counter to track available permits and synchronization primitives to ensure thread safety. When permits are exhausted, threads wait on a condition variable until permits become available again.

🚀 Steps to Take to Solve

1. Design the data structure: Maintain permit count and maximum limit
2. Implement initialization: Set initial permits and validate input
3. Add thread synchronization: Use synchronized blocks for thread safety
4. Implement acquire logic: Block threads when no permits available
5. Implement release logic: Increment permits and notify waiting threads
6. Handle edge cases: Prevent permit overflow and handle interruption

⚠️ Edge Cases to Consider

1. Permit overflow: Prevent releasing more permits than maximum
2. Negative permits: Ensure permit count never goes below zero
3. Thread interruption: Handle InterruptedException properly
4. Spurious wakeups: Use while loop to check permit availability
5. Concurrent releases: Handle multiple threads releasing simultaneously
6. Initialization errors: Validate maximum permits parameter

💻 Code (with comments)

public class MySemaphore {
    private int permits;              // Current available permits
    private final int maxPermits;     // Maximum number of permits allowed
    private final Object lock = new Object(); // Synchronization lock

    public MySemaphore(int maxPermits) {
        if (maxPermits <= 0) {
            throw new IllegalArgumentException("Permits must be greater than zero.");
        }
        this.maxPermits = maxPermits;
        this.permits = maxPermits;    // Initialize with all permits available
    }

    public void acquire() throws InterruptedException {
        synchronized (lock) {
            // Wait until permits become available
            while (permits == 0) {
                lock.wait();
            }
            permits--; // Consume one permit
        }
    }

    public void release() {
        synchronized (lock) {
            // Only increment if we haven't reached maximum
            if (permits < maxPermits) {
                permits++; // Make one permit available
                lock.notify(); // Wake up one waiting thread
            }
        }
    }

    public int availablePermits() {
        synchronized (lock) {
            return permits; // Return current available permits
        }
    }
}

🔍 Dry Run Example

Scenario: Semaphore with 3 permits, 5 threads trying to acquire

Initial State:

• Available permits: 3
• Maximum permits: 3
• 5 threads waiting to acquire

Step 1: Thread 1 acquires permit

• Check: permits > 0 → true (permits = 3)
• Decrement permits to 2
• Thread 1 continues

Step 2: Thread 2 acquires permit

• Check: permits > 0 → true (permits = 2)
• Decrement permits to 1
• Thread 2 continues

Step 3: Thread 3 acquires permit

• Check: permits > 0 → true (permits = 1)
• Decrement permits to 0
• Thread 3 continues

Step 4: Thread 4 tries to acquire permit

• Check: permits > 0 → false (permits = 0)
• Thread 4 blocks and waits

Step 5: Thread 5 tries to acquire permit

• Check: permits > 0 → false (permits = 0)
• Thread 5 blocks and waits

Step 6: Thread 1 releases permit

• Check: permits < maxPermits → true (permits = 0 < 3)
• Increment permits to 1
• Notify waiting threads

Step 7: Thread 4 wakes up and acquires permit

• Check: permits > 0 → true (permits = 1)
• Decrement permits to 0
• Thread 4 continues

Result: Only 3 threads can have permits simultaneously, others wait until permits become available.

⏱️ Time Complexity / Space Complexity

Time Complexity:

• Acquire: O(1) - constant time to check and consume permit
• Release: O(1) - constant time to increment permit and notify
• Wait time: O(1) - constant time to block/unblock threads

Space Complexity:

• Permit storage: O(1) - constant space for permit count
• Lock overhead: O(1) - constant space for synchronization object
• Thread management: O(1) - constant space regardless of number of threads

---

🔑 Key Concepts

• Synchronization: Ensures thread safety when accessing permits.
• Acquire/Release: Threads block when no permits are available and are notified when permits are released.
• Fixed Permits: The semaphore limits the number of threads that can access the shared resource concurrently.

---

🧪 Usage Example

public class SemaphoreExample {
    public static void main(String[] args) throws InterruptedException {
        MySemaphore semaphore = new MySemaphore(3);

        for (int i = 0; i < 5; i++) {
            final int threadId = i;
            new Thread(() -> {
                try {
                    semaphore.acquire();
                    System.out.println("Thread " + threadId + " acquired a permit.");
                    Thread.sleep(1000);
                    semaphore.release();
                    System.out.println("Thread " + threadId + " released a permit.");
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }).start();
        }
    }
}