How can two threads be "in" a "synchronized" method

Question

I'm really a new at Java concurrency and I'm trying to implement the following specifications:

• We have a car park which has some park spots
• Each car is represented as a thread which endlessy change the car state from Driving - Parking. Each car has his own parking spot.
• When the car is in the parking state, it tries to park in a spot (no necessary his spot). If the spot is free then it parks else it will skip this parking phase and go back to drive.
• The car remains in the spot unless the owner of the spot want to park.

This is not the exact specification, but the only problem that I have is the following:

I'm not able to make the car skip the turn. If two cars pick the same spots, then one is parked and the other is waiting until the park is free. Which is not the bahvior that I want. My first idea was to simply synchronize the read and write to a variable occupied:

class Car implements Runnable {
    private CarState state = CarState.driving

    run {
        while(true) {
            switch(state) {
            case driving: 
                System.out.println(this + " driving.");
                state = parking;
                break;
            case parking: Spot s = CarPark.getRandomSpot();

                if(s.willingToPark(this)) {
                    System.out.println(s + " occupied. " + this 
                    + " skip park turn.");
                } else {
                    s.park(this);
                } 
                state = driving;
            }
        }

    }
}

class Spot {
    private boolean occupied = false;
    private Car owner = new Car(...);

    synchronized boolean willingToPark(Car c) {
        if(occupied) {
            return true;
        } else {
            occupied = true;
            return false;
    }

    synchronized void park(Car c) {
        System.out.println(c + " parking at " + this);
        //don't care how this is implemented, just keep in mind
        //that it will enter in a loop until the owner came back.
        occupied = false;
    }
}

If I run this with three cars, then I will end up in having car0 is parking at spot1, car1 is parking at spot0, car2 is waiting on spot0, because car1 is executing the synchronized block park(Car c). I don't get how is it possible that two cars can park in the same spot if the willingToPark is synchronized.

Thank you

Answer 1

I don't get how is it possible that two cars can park in the same spot if the willingToPark is synchronized.

It's actually simple. Car1 captures spot0 and starts waiting for owner in a loop inside park() method (you did not provide the code). While it is waiting, it owns monitor and does not allow anyone to call synchronized methods on spot0.
That is the reason why car2 hangs on willingToPark() method.

Answer 2

The problem is in the looping of park. Imagine this:

• Two threads both grab the same Spot, s.
• They both try to acquire the monitor lock on s; only one will succeed.
• The one that succeeds will cause park to spin, while still holding the lock.
• The other one patiently waits until the lock is released, so that it can try to acquire it.

There's nothing (short of killing the JVM) that will tell the thread that failed to park, to stop waiting on s. It'll wait until it can acquire the lock -- which will only happen once the first thread finishes the loop on park.

The solution is not to loop in park at all. Instead, the Car should unset the occupied flag, via a new method unpark(Car). This method must also be synchronized, for the sake of memory visibility across threads.

Now the data flow looks like:

• Two threads both grab the same Spot, s.
• They both try to acquire the monitor lock on s; only one will succeed.
• The one that succeeds sets occupied = true, and immediately returns and then releases the lock on s
• The other one acquires the lock on s, and sees that the spot is occupied.

Incidentally, you don't even need a synchronized method for this. You can use an AtomicBoolean's compareAndSet method, which lets you atomically check the AtomicBoolean's value, and only set it if its current value is what you expect it to be. Thus, return occupied.compareAndSet(false, true) means "atomically check the current value; if it's false, then set it to true and return true; if it's true, then keep it as it is, and return false." This kind of behavior is useful, but a bit more advanced.