Picky host (lock?)

Question

I believe my problem can be considered regardless of used language but, to have some 'anchor', I'll describe it using the Java language.

Let's consider the following scenario: I have a class PickyHost extending Thread and an instance of it, pickyHostInst running. That class might look like this:

class PickyHost extends Thread {
    private ArrayList<Guest> guests;
    public void enter(Guest g) {
        // deal with g
    }
    private void pickGuests() {
        // ...
    }
    public void run() {
        // listen indefinitely
    }
}

Moreover, in the background, I have many Guest instances running (they also extend Thread class) and once in a while, some guest wants to invoke enter method on pickyHostInst with an argument g being itself. Now, I want PickyHost to be picky in the following sense:

Immediately after someone invokes enter method, it puts g at the end of guests list and forces g to wait for notification. Also (I think here lies the crux of the matter) it goes itself for a 5 seconds sleep and somehow allows (during these 5 seconds) other guests to invoke enter method (if so happens, then it forgets about how long it had to sleep and resets its alarm clock to sleep exactly 5 seconds again) - I'll call it a sensitive sleep.

As you can see, the total amount of time pickyHostInst sleeps can be huge if many guests arrive - like: A arrives, then after 4 seconds B arrives, then after another 4 seconds C arrives and so on. However, suppose there's been created a chain A, B, ..., G of guests and from the moment of arrival of G till 5 seconds later, no-one arrived. Then I want pickyHostInst to invoke pickGuests method which, using some algorithm, determines a subset S of {A, B, ..., G} of guests to notify that they can stop waiting and carry on doing what they normally do and moreover removes elements of S from guests list. Method pickGuests can take some time to accomplish and in the meantime some guest H might have arrived and invoked enter - then enter should proceed normally but pickGuests should ignore H and to the end of its last invocation deal with {A, B, ..., G} - not with {A, B, ..., G, H}. After finishing pickGuests, pickyHostInst should (here I have 2 ideas - implementing any of them will make me happy :)) either

1. fall again into 5 seconds of sensitive sleep after which, if no guest after H arrived, invoke pickGuests again, or
2. simultaneously serves guests via enter method as usual but invokes pickGuests only after max("a moment when last guest from S (from the last invocation) notifies pickyHostInst (like: the last "Thank you, Mr Host" from among S)", "a moment 5 seconds after the last (newest) guest invoked enter").

Finally, after a long introduction, my question - which tools do I need to accomplish such task? I'm unfortunately a bit lost among the richness of various locks and multithreading/locking mechanisms and can't discern which one fits to my problem (or which ones, combined somehow).

I'll greatly appreciate some code-sketches that would put me on the right track.

Answer 1

You can use a java.util.Timer object, which can be reset in the enter method. The timer task will run in its own thread and do the picking for you if it is not canceled before hand.

Note that the enter method will be running on one of the many Guest threads. This means that it should probably synchronized. The easiest way to do this is is to add the synchronized keyword to the method declaration in Java: public synchronized void enter(Guest g). This will ensure that only one guest can enter at a time. You can put the timer cancel/restart code in here.

The way java.util.Timer works it through the abstract java.util.TimerTask class. This is a type of Runnable that also has a method to cancel the task. My recommendation is to schedule a task that will pick guests after a 5000ms interval whenever a guest enters. If a task from the previous guest is running, cancel it first.

The enter method should acquire the guest's lock (using a synchronized block) and have the guest wait. The picking should call the notify() method on the guests you select. This will allow them to continue executing.

When you remove selected guests from your queue, be aware of the fact that Java collections are not thread-safe by default. You will have to use an external lock to ensure that no-one else is modifying your list when you add and remove guests. The Collections.synchronizedList(List) method provides a handy way to do this.

Here is a list of links that discuss the topics I have mentioned:

1. http://docs.oracle.com/javase/tutorial/essential/concurrency/ (excellent tutorial for beginners)
2. http://docs.oracle.com/javase/7/docs/api/java/util/Timer.html
3. http://docs.oracle.com/javase/7/docs/api/java/util/TimerTask.html
4. http://docs.oracle.com/javase/7/docs/api/java/util/Collections.html#synchronizedList%28java.util.List%29

Answer 2

I might do this like this. I'd try to avoid notify/notifyAll as you'll have to involve a flag because of spurious wakeups and that clutters the code quite a bit. CountDownLatch is a much better choice here IMO even though the name is a bit weird.

static final long five_sec = TimeUnit.SECOND.toNanos(5)
final Queue<Pair<Guest, CountDownLatch>> guests = new LinkedList<>();
long earliest = -1;

// Synchronizing on "this" is fine but using private lock 
// object is even better
final Object lock = new Object();


void enter(Guest g){
    Pair p = Pair.of(g, new CountDownLatch(1));
    synchronized(lock){
        guests.get().add(p);
        earliest = System.nanoTime() + five_sec;
    }
    p.second.await();
}

void pickGuests(){
    synchronized(lock){
        // pop a few guests from sofar and wake them
        Guest g = sofar.poll();
        if(g != null){
            g.second.countDown();
        }
    }

}

void run(){
    while(!Thread.currentThread().isInterrupted()){
        long sleepTime;
        synchronized(lock){
            if(System.nanoTime() > earliest){
                pickGuests();
            }
            sleepTime = earliest - System.nanoTime();
            sleepTime = sleepTime < five_sec ? five_sec : sleepTime;
        }
        Thread.sleep(sleepTime);
    }
}