Classical Java synchronization problem (care to give it a try?)

Question

I'm trying to solve a Java synchronization problem. The case is as follows:

There are class Persons and they want to be paired. So I have a class Coupling that does the pairing. When a person walks in to the Coupling and there is no one waiting for her, she starts to wait. And waits until someone comes along or she gets bored and leaves (predifines timer goes off).

If she walks in and finds someone waiting for her, they are immediately coupled and they exchange phone numbers and go their separate ways. (Continue execution with the other's information.)

The same person can't leave with two people.

I promise that this is not a university exercise I'm trying to cheat in. :) I just havn't done this stuff in a while and I'm a bit rusty at it.

This is something I came with up at first, so the Thread is trying to set the Person, and if this doesn't work it'll get false as return value. Then the thread gets the waiter. For obvious reasons, this will not work (another thread might come between the calls) and how would I signal the waiting thread to go on.

Here's the code I mentioned:

public class Coupling {
    private static volatile Person waitingPerson = null;

    public static synchronized Integer getWaitingPerson() {
        Integer temp = waitingPerson;
        waitingPerson = null;
        return temp;
    }

    public static synchronized Boolean setWaitingPerson(Integer waitingPerson) {
        if (waitingPerson == null){
            syncro.waitingPerson = waitingPerson;
            return new Boolean(true);
        }
        else
            return new Boolean(false);
}

Answer 1

If you really just want to get into this stuff and this is your example problem, try to get a copy of Java Concurrency in Practice, and find out for yourself. Its a great book.

Answer 2

Okay, I'll mangle your problem a little bit and propose a solution, then you'll tell me if you're satisfied :-)

First, have you considered making the "pairing" operation asynchronous? It would work pretty much like this:

1. A Person who wants to be paired, leaves a notification at a Coupling thread;
2. When a second person leaves a "free" notification, the Coupling thread notifies the two people.

How would that work in code? Well, you'd need two things:

1. A lock that supports accumulated permits (a semaphore!);
2. A thread safe data structure (well, just in case. It really doesn'd need to be thread safe)

So, every time a Person wants to be paired, it notifies the Coupling thread, that adds the Person to its "free people" list and releases one permit from the semaphore. The Coupling thread, on the other hand continuously try to acquire semaphore permits, two at a time. Since a permit is only released when a Person leaves a notification, having two permits means that two people want to be paired.

Well, less talk, more code. Here's the Coupling thread class:

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.Semaphore;

public class Coupling implements Runnable {
    private BlockingQueue<Person> peopleQueue;

    private Semaphore semaphore;

    public Coupling() {
        this.peopleQueue = new LinkedBlockingQueue<Person>();
        this.semaphore = new Semaphore(0);
    }

    @Override
    public void run() {
        while(true) {
            // Process incoming "free" events

            try {
                // Acquire permits for two people
                this.semaphore.acquire(2);

                Person pA = this.peopleQueue.poll();
                Person pB = this.peopleQueue.poll();

                pA.notifyPairing(pB);
                pB.notifyPairing(pA);
            } catch (InterruptedException e) {  // This shouldn't really happen..?
                break;
            }
        }
    }

    /**
     * Invoked to notify that a Person is waiting for a coupling
     * @param person
     */
    public void notifyFreePerson(Person person) {
        this.peopleQueue.offer(person);
        this.semaphore.release(1);
    }
}

And the Person class:

public class Person {
    public void notifyPairing(Person other) {
        System.out.printf("I've been paired with %s!\n)", other);
    }
}