CODEWITHSUNDEEP
javamultithreading
OneMoreError
OneMoreError

Reputation: 7728

Implementing a Queue with access to only n threads - rest should be queued

In a recent interview, I was asked to implement a Queue that allow access to only four threads at once. any further threads requesting access should be queued, and they should be given access prioritised on the order in which they were queued. I came up with the following Queue implementation, but wan not able to come up with the multi threaded part of the code.

public class Queue<Item> implements Iterable<Item> {
    private int N;               // number of elements on queue
    private Node<Item> first;    // beginning of queue
    private Node<Item> last;     // end of queue

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    public Queue() {
        first = null;
        last  = null;
        N = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return N;     
    }

    public Item peek() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        return first.item;
    }

    public void enqueue(Item item) {
        Node<Item> oldlast = last;
        last = new Node<Item>();
        last.item = item;
        last.next = null;
        if (isEmpty()) first = last;
        else           oldlast.next = last;
        N++;
    }

    public Item dequeue() {
        if (isEmpty()) throw new NoSuchElementException("Queue underflow");
        Item item = first.item;
        first = first.next;
        N--;
        if (isEmpty()) last = null;
        return item;
    } 
}

How do you guarantee access to only n threads on the queue at a time ?

Also, please suggest some good reads, which have problems like these so that i can work on multithreading part of Java.

Upvotes: 1

Views: 78

Answers (2)

Amm Sokun
Amm Sokun

Reputation: 1298

Use a Semaphore. You can initilaze the Semaphore with number (permit) n and acquire to access the queue. Acquire will block if all permits are occupied.

http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Semaphore.html

A semaphore restricts the number of threads acquiring a resource. A thread already holding a resource can acquire it again. Thus a semaphore internally maintains the thread-identity.

In your scenario, each queue method should acquire the permit and release it at the end of the method.

Even if two rogue threads pass around the queue objects amongst them, semaphore helps maintain the permit by keeping track of thread-identity.

Upvotes: 2

Bohemian
Bohemian

Reputation: 425083

Being called by a thread means you have a reference to that thread via Thread.currentThread(). You can never prevent a thread from calling you, but you can prevent a thread from using the queue object by limiting the number of different Thread objects returned from this call to 4, and of course you'll need a threadsafe way of checking that.

Here's one way:

private Set<Thread> threads = new HashSet<>();

private synchronized void checkOk() {
    if (threads.size() < 4) {
        threads.add(Thread.currentThread());
    } else {
        if (!threads.contains(Thread.currentThread()))
            throw new IllegalStateException();
    }
}

then add a call to the method to each public method like this:

public Item peek() {
    checkOk();
    if (isEmpty()) throw new NoSuchElementException("Queue underflow");
    return first.item;
}

Upvotes: 0

Related Questions