0

I have a priority queue (with synchronized access) of tasks. Each task has a time at which it is to be performed. When the task at the front of the queue is due to be performed, it should be popped from the queue, but not before since something could be added ahead of it in the queue. (i.e. with an earlier timestamp). Also the task could be removed from the Q before it is due to be performed.

This much I think I have (sudo code)

public synchronized task Q.get(){
    while Q.empty(){
        wait();
    }
    // queue is not empty
    if (Q.head.time.isBefore(now)){ // task at head of Q is due to be done
        return Q.pop();
    }else{
        // THIS IS WHERE IM STUCK ***
    }

At the point *:

I could write code to sleep until the time of the task at the head of the queue, then take it. The problem here would be that we have a lock on the Q and so no tasks can be added while we sleep?? Also if something would be added (though I'm not sure it can) at the head of the queue then the reader would sleep too long.

I also thought I could write code to wait() on the Q again, but after setting a timer (a separate thread owned by the queue purely to Q.notify at the time of the task at the head of the queue). The problem I see with this is that if something is placed at the head of the Q, we'd interrupt the timer and notify on Q then the reader would take the new head task, without checking it's time.

Any help would be really appreciated, thanks in advance. I'm fairly inexperienced with this, so please correct any wrong assumptions etc.

Edit. The reader class, simply loops, gets the next task by calling Q.get() and actions it.

Matt Pellegrini
  • 159
  • 1
  • 3
  • 11

2 Answers2

0

I dont know how your code works with this method, but you could

  1. return null in your else or
  2. add a loop that checks if the first Task should be executed by now.

The code for the second approach would like this:

public synchronized task Q.get(){
    while Q.empty(){
        wait();
    }
    // queue is not empty
    while (!Q.head.time.isBefore(now)){
        //instead of writing 100 you can calculate the time between now 
        //and the first scheduled task
        wait(100); 
    }
    return Q.pop();
}
Domysee
  • 12,718
  • 10
  • 53
  • 84
  • So returning null would mean the reader never stops. Say the next task is not scheduled for another minute, the reader would spend the entire minute checking the Q, receiving null, checking the Q... – Matt Pellegrini Dec 29 '13 at 00:50
  • The second part, i'm unsure on. If I sleep the reader thread, does it still hold the lock on the Q? If it does then whilst this will sleep the thread waking periodically until the task at the head of the Q is due, it won't allow something to be put at the head of the Q, since it holds the lock. If sleep releases the lock, this might work. – Matt Pellegrini Dec 29 '13 at 00:53
  • you are right about the second part, sleep will hold the lock while sleeping. However, you can change the sleep to wait, this method also takes a timeout. This allows you to calculate the time between now and the first scheduled task and simply wait. I edited the answer to reflect this. – Domysee Dec 29 '13 at 08:07
  • Thanks, I didn't know about this wait(time) method, that brings me a lot closer to a solution. My problem now is that while waiting for the task to be due, the Q can change, it might be empty when the reader is notified, or worse, there might have been something added to the Q due before the current next due task. I guess when both these things happen, I just need to notify the waiting reader. I'll try and work it out and accept this answer if all goes well. – Matt Pellegrini Dec 29 '13 at 10:06
0

There are lot of useful classes in java.util.concurrent package. Take a look at PriorityBlockingQueue :

http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html

You can run two threads - one thread that writes to the Queue and second one that is reading from the queue. It contains method take() which blocks until there is something in the queue - so you don't have to wait().

If the time is not before now you can just offer() the taken object back to the queue. If the ordering of your objects is based on the time it will be stored in correct position in the queue.

The ordering of your object can be defined with Comparator using this constructor :

http://docs.oracle.com/javase/6/docs/api/java/util/concurrent/PriorityBlockingQueue.html#PriorityBlockingQueue(int, java.util.Comparator)

If you don't know much about Comparable and Comparator interfaces take a look at :

Java : Comparable vs Comparator

This could be also interesting for you :

http://tutorials.jenkov.com/java-util-concurrent/delayqueue.html

Community
  • 1
  • 1
Viktor K.
  • 2,670
  • 2
  • 19
  • 30
  • I don't think I'm struggling with the concurrent access, I'm aware of the blockingQ but I think I've achieved it here anyway. If I offer the task back then the reader will hog the processor, check for the next task, take it, if it's not ready, offer it back, check the next task, take it..... The question is how can I sit tight until the next task is ready OR until something is put it at the head of the queue, while still allowing things to be inserted in the queue, i.e. not having a lock on the Q. – Matt Pellegrini Dec 29 '13 at 00:46
  • You haven't achieved what Blocking queue is doing. In blocking queue you have two threads that can read/write from/to the queue independently -> there is no common lock for read and write operations. Look ak this tutorial : http://tutorials.jenkov.com/java-util-concurrent/blockingqueue.html ... After you offer the object back to the queue, the reading thread can sleep for reasonable time (e.g object.time - now + 50 ms), so the processor can work on something else. – Viktor K. Dec 29 '13 at 11:24
  • Isn't this what synchronized achieves? I am new to this so I'm likely wrong. But surely synchronized means getting a lock on the Q object before continuing? If the reader sleeps, it may miss something being added to the head of the Q. – Matt Pellegrini Dec 29 '13 at 15:13
  • I would need to see the whole Queue class to claim this for sure. It is possible that your implementation is doing the right thing. However you can achieve what you need easily with blocking queue. If you want to compare here is the source code : http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/concurrent/PriorityBlockingQueue.java – Viktor K. Dec 29 '13 at 19:22