How can I write a semaphore in Java which prioritizes previous successful applicants?

Question

I have a need for a single-permit semaphore object in my Java program where there is an additional acquire method which looks like this:

boolean tryAcquire(int id)

and behaves as follows: if the id has not been encountered before, then remember it and then just do whatever java.util.concurrent.Semaphore does. If the id has been encountered before and that encounter resulted in the lease of the permit then give this thread priority over all other threads who may be waiting for the permit. I'll also want an extra release method like:

void release(int id)

which does whatever the java.util.concurrent.Semaphore does, plus also "forgets" about the id.

I don't really know how to approach this, but here's the start of a possible implementation but I fear it's going nowhere:

public final class SemaphoreWithMemory {

    private final Semaphore semaphore = new Semaphore(1, true);
    private final Set<Integer> favoured = new ConcurrentSkipListSet<Integer>();

    public boolean tryAcquire() {
        return semaphore.tryAcquire();
    }

    public synchronized boolean tryAcquire(int id) {
        if (!favoured.contains(id)) {
            boolean gotIt = tryAcquire();
            if (gotIt) {
                favoured.add(id);
                return true;
            }
            else {
                return false;
            }
        }
        else {
            // what do I do here???
        }
    }

    public void release() {
        semaphore.release();
    }

    public synchronized void release(int id) {
        favoured.remove(id);
        semaphore.release();
    }

}

Answer 1

EDIT:
Did some experiment. Please see this answer for results.

In principle, Semaphore has a queue of threads internally, so like Andrew says if you make this queue a priority queue and poll from this queue to give out permits, it probably behaves the way you want. Note that you can't do this with tryAcquire because that way threads don't queue up. From what I see looks like you'd have to hack the AbstractQueuedSynchronizer class to do this.

I could also think of a probabilistic approach, like this:
(I'm not saying that the code below would be a good idea! Just brainstorming here. )

public class SemaphoreWithMemory {

    private final Semaphore semaphore = new Semaphore(1);
    private final Set<Integer> favoured = new ConcurrentSkipListSet<Integer>();
    private final ThreadLocal<Random> rng = //some good rng

    public boolean tryAcquire() {
        for(int i=0; i<8; i++){
            Thread.yield();
            // Tend to waste more time than tryAcquire(int id)
            // would waste.
            if(rng.get().nextDouble() < 0.3){
                return semaphore.tryAcquire();
            }
        }
        return semaphore.tryAcquire();
    }

    public boolean tryAcquire(int id) {
        if (!favoured.contains(id)) {
            boolean gotIt = semaphore.tryAcquire();
            if (gotIt) {
                favoured.add(id);
                return true;
            } else {
                return false;
            }
        } else {
            return tryAquire();
    }
}

Or have the "favoured" threads hang out a little bit longer like this:
EDIT: Turns out this was a very bad idea (with both fair and non-fair semaphore) (see my experiment for details.

    public boolean tryAcquire(int id) {
        if (!favoured.contains(id)) {
            boolean gotIt = semaphore.tryAcquire(5,TimeUnit.MILLISECONDS);
            if (gotIt) {
                favoured.add(id);
                return true;
            } else {
                return false;
            }
        } else {
            return tryAquire();
    }

I guess this way you can bias the way permits are issued, while it won't be fair. Though with this code you'd probably be wasting a lot of time performance wise...