Synchronization Blocks and Lock Selection

First Iteration: Single Elevator

In the initial implementation, no explicit synchronized blocks were used. A BlockingQueue served as the container for passenger requests shared between threads. This container inherently ensures thread safety and blocks when empty, preventing busy-waiting, thus eliminating the need for custom synchronization.

Second Iteration: Multiple Elevators and Output Synchronization

With multiple elevators, concurrent output operations could lead to non-sequential timestamps. The provided TimableOutput.println method is not atomic. If multiple elevators call it simultaneously without synchronization, the output order might not reflect the actual event sequence, resulting in timestamps that are not strictly non-decreasing.

To resolve this, a synchronized wrapper method was created:

public static synchronized long println(String message) {
    return TimableOutput.println(message);
}

Elevators use this synchronized println method instead of the raw output function.

Third Iteration: Custom Waitlist with ReentrantLock

In this iteration, elevators have different accessible floors. A centralized scheduling strategy was employed where all elevators compete for requests from a shared waitlist. A simple BlockingQueue was no longer suitable because the request at the head might not be serviceable by all elevators.

Inspired by the locking mechanism in ArrayBlockingQueue, a custom waitlist class was implemented using a ReentrantLock. Synchronization was managed manual rather than with the synchronized keyword.

private final ReentrantLock accessLock = new ReentrantLock();

public void addRequest(PassengerRequest req) {
    accessLock.lock();
    try {
        // Critical section: Modify waitlist
        requestSet.add(req);
    } finally {
        accessLock.unlock();
    }
}

public PassengerRequest getRequestForElevator(Elevator e) {
    accessLock.lock();
    try {
        // Critical section: Search for a suitable request
        for (PassengerRequest req : requestSet) {
            if (e.canService(req)) {
                requestSet.remove(req);
                return req;
            }
        }
        return null;
    } finally {
        accessLock.unlock();
    }
}

The lock() and unlock() calls define the critical section, ensuring only one thread can modify or read the shared waitlist at a time.

Scheduler Design

The scheduler's role was consistent across all three iterations. Its primary responsibilities were:

1. Receiving requests from the input thread and placing them into the shared waitlist.
2. Notifying (waking up) waiting elevators when new requests arrive.
3. Issuing shutdown commands to elevators after all requests are processed and input has ended, preventing indefinite waiting.

Interaction between the scheduler and elevators was facilitated by a Semaphore. Elevators used this semaphore to signal the completion of requests, allowing the scheduler to track progress and issue the final shutdown signal.

In retrospect, the scheduler's design had some redundancy. Its role in distributing requests was minimal due to the free-for-all competition strategy, and it did not provide a clean abstraction for easily switching to different scheduling algorithms like a dispatcher-based model.

System Architecture and Extensibility in the Final Iteration

The final architecture comprised several key classes: Elevator, FloorWaitlist, RequestHandler, and InputThread.

The focus was on functional correctness over performance optimization. The free-competition strategy performed adequately under random test data.

Good Extensibility: The elevator entity was designed using inheritance. Extending from a single elevator type to multiple specialized types (e.g., with different speed, capacity, or accessible floors) was straightforward. A new elevator type could be created by extending an abstract base class and overriding specific methods, such as those for splitting transfer requests.

Limited Extensibility: The architecture was tightly coupled with the free-competition scheduling strategy. Implementing alternative strategies, such as a centralized dispatcher that assigns requests to specific elevators, would require significant refactoring of the waitlist and elevator interaction logic.

Bugs and Resolutions

First Iteration Bugs

1. CPU Time Limit Exceeded (CTLE) due to Polling in LOOK Algorithm

• Cause: The LOOK algorithm's turn condition was flawed. If the waitlist was empty in both directions, the elevator would repeatedly change direction, causing a busy-wait loop.
• Fix: Added a condition to make the elevator block and wait (releasing CPU) when the waitlist was completely empty, instead of turning.

2. Run Time Limit Exceeded (RTLE) due to Indefinite Waiting

• Cause: A consequence of the first bug's fix. After blocking, the elevator was not properly notified when a new request arrived.
• Fix: Ensured the scheduler correctly notified all waiting elevators upon receiving a new request.

3. Wrong Answer (WA) due to Incorrect Door Timing Calculation

• Cause: An optimization aimed at minimizing door open/close time ("quantum doors") used System.currentTimeMillis() to record the open time. However, there was a gap between recording the timestamp and printing the "OPEN" message. If the thread was interrupted here, the printed time could be later than the recorded time, leading to a calculated sleep time that was too short, resulting in a door cycle of less than 0.4s.
• Fix: Used the timestamp returned by the synchronized println method itself, which is atomic with the output.

  // Fixed approach
  lastOpenTime = println("OPEN-" + currentFloor);
  // ... handle passenger boarding ...
  long timeToSleep = 400 - (println("CLOSE-" + currentFloor) - lastOpenTime);
  if (timeToSleep > 0) {
      sleep(timeToSleep);
  }
  

Third Iteration Bug

CPU Time Limit Exceeded (CTLE) due to Request Cycling

• Cause: With the old BlockingQueue waitlist, if an elevator picked up a request it couldn't service, it would re-insert it at the end. With only one request in the system, all elevators would cyclically pick up and re-insert the same request, causing infinite polling.
• Fix: Replaced the FIFO BlockingQueue with a random-access collection (HashSet) and implemented manual locking via ReentrantLock. This allowed elevators to efficiently search the entire waitlist for a serviceable request without disturbing the order for others.

Strategies for Identifying Bugs in Others' Code

Testing combined black-box methods with manually crafted edge cases.

• Manual Test Cases: Derived from edge cases discovered during self-testing, such as high-load scenarios, request patterns that stress specific elevator behaviors, or timing-sensitive sequences.
• Black-box Testing: Utilized existing test harnesses from peers too run a large volume of random inputs. Running multiple concurrent instances of a program under test increased the probability of exposing thread-safety issues like race conditions or deadlocks, though reproducibility remained challenging. The key difference from testing in the first unit was the necessity to account for concurrancy and timing, requiring tests that create high-pressure, concurrent scenarios to have a chance of triggering intermittent multithreading bugs.