You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Cheung Lo <ch...@yahoo.co.uk> on 2003/07/30 10:59:59 UTC
Proposal for a Timeout Affected Priority Queue
Proposal for a Timeout Affected Priority Queue
Currently available open source queues fall into 2 categories: FIFO/LIFO and
priority-sorted. These are fine, so long as the supply of resources to
process the queue jobs exceed demand over the time period of interest. When
this is true, all the jobs are processed in a timely fashion.
In my last project however, the above assumption could not be made. The
jobs had an initial priority but during busy periods, the continous
insertion of higher priority jobs implied that lower priority jobs did not
get done. This pattern occured in another previous project as well. In an
insurance office, during periods of low-normal activity, answering customer
calls had higher priority over policy administration. However, admin could
only be delayed for a limited period. If this period timed out, the
priority of policy admin increased so that resources were diverted away from
new customer calls. In other circumstances, jobs that time out may be
binned instead.
I have implemented a generic solution to a self managing Timeout Affected
Priority (TAP) Queue. There are 3 core classes: TapQueue, TapObject and
TapConsumer. Whenever a consumer pops the next next job, the queue checks
for any priority timeouts and, if necessary, re-prioritizes the queue before
returning the next job. Internally, the TapQueue uses a modified version of
org.apache.commons.collections.BinaryHeap.
I would like to propose the adoption of the TapQueue into the collections
packages but need feedback on the following issues:
1. Has anyone else had a need for a timeout affected priority queue?
2. If so, what additional requirements did you have that is not already
described?
3. How do I submit a draft of the classes - do I attach a zip file or paste
into the body of an email?
4. Who do I send it to?
Cheung Lo
London, UK
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] Proposal for a Timeout Affected Priority Queue
Posted by Stephen Colebourne <sc...@btopenworld.com>.
0. Please prefix emails by topic, eg.[collections]
> 1. Has anyone else had a need for a timeout affected priority queue?
I haven't had a need for such a class, other may have.
> 3. How do I submit a draft of the classes - do I attach a zip file or
paste
> into the body of an email?
Either a zip attachment, or a link to the zip on another server
> 4. Who do I send it to?
The link/zip should be to this list.
Stephen
----- Original Message -----
From: "Cheung Lo" <ch...@yahoo.co.uk>
To: <co...@jakarta.apache.org>
Sent: Wednesday, July 30, 2003 9:59 AM
Subject: Proposal for a Timeout Affected Priority Queue
> Proposal for a Timeout Affected Priority Queue
>
> Currently available open source queues fall into 2 categories: FIFO/LIFO
and
> priority-sorted. These are fine, so long as the supply of resources to
> process the queue jobs exceed demand over the time period of interest.
When
> this is true, all the jobs are processed in a timely fashion.
>
> In my last project however, the above assumption could not be made. The
> jobs had an initial priority but during busy periods, the continous
> insertion of higher priority jobs implied that lower priority jobs did not
> get done. This pattern occured in another previous project as well. In
an
> insurance office, during periods of low-normal activity, answering
customer
> calls had higher priority over policy administration. However, admin
could
> only be delayed for a limited period. If this period timed out, the
> priority of policy admin increased so that resources were diverted away
from
> new customer calls. In other circumstances, jobs that time out may be
> binned instead.
>
> I have implemented a generic solution to a self managing Timeout Affected
> Priority (TAP) Queue. There are 3 core classes: TapQueue, TapObject and
> TapConsumer. Whenever a consumer pops the next next job, the queue checks
> for any priority timeouts and, if necessary, re-prioritizes the queue
before
> returning the next job. Internally, the TapQueue uses a modified version
of
> org.apache.commons.collections.BinaryHeap.
>
> I would like to propose the adoption of the TapQueue into the collections
> packages but need feedback on the following issues:
>
> 1. Has anyone else had a need for a timeout affected priority queue?
> 2. If so, what additional requirements did you have that is not already
> described?
> 3. How do I submit a draft of the classes - do I attach a zip file or
paste
> into the body of an email?
> 4. Who do I send it to?
>
> Cheung Lo
> London, UK
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
> For additional commands, e-mail: commons-dev-help@jakarta.apache.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
RE: [collections] Proposal for a Timeout Affected Priority Queue
Posted by Cheung Lo <ch...@yahoo.co.uk>.
Thanks for the pointers Neil & Stephen. Any further help greatly
appreciated.
I have attached a 15k zip file holding 8 java files. I have not included
any Apache licensing comments - I will do this later if I this is what I am
supposed to do - greenness showing :-).
The classes have been placed, for the time being, separately in the package
org.apache.commons.collections.xq (eXotic Queues). The classes fall into 4
groups:
TapObject - an interface
TapObjectAdapter - a simple implementation of TapObject
NOTE1: the tap() method is meant to be over-ridden to do any arbitrarily
complex priority upgrade, including setting the next timeout.
TapConsumer - an interface
TapConsumerAdapter - a simple implementation of TapConsumer
XBinaryHeap - a copy/paste of BinaryHeap
TapBinaryHeap - a subclass of XBinaryHeap
TapQueue - the clever bit :-)
NOTE2: I need to extend BinaryHeap. Unfortunately, this is marked as final.
I have just copied over the code to XBinaryHeap (eXtendable BinaryHeap).
You can do a text search for "Cheung" to see all the modifications. How do
I ask for an amendment?
NOTE3: I have over-ridden the 4 percolate methods and added 2 more to allow
bubbling up at any arbitrary index.
NOTE4: TapBinaryHeap really needs to be an inner class of TapQueue. I have
pulled it out for the time being so it is more clear.
TapTest - has a main() method to demonstrate how it all works.
NOTE5: I will write Ant/JUnit files later.
Internally, TapQueue has 2 TapBinaryHeaps. A priority max heap and a
timeout min heap.
Everytime a TapObject is inserted into the TapQueue, the same object is
inserted into both the priority and timeout heaps. Those objects with the
earliest timeouts will bubble to the top of the timeout heap. When, a
timeout occurs the guilty object is popped from the timeout heap. The
object has a reference to its' index on the priority heap. The new
percolateUpMaxHeap(int index) method is called to bubble the object to the
top of the priority heap where it too is popped - keeping both heaps
synched. The tap() method of the object is called and, if necessary,
re-inserted into the TapQueue where it will bubble up to its' new positions.
Everytime a free TapConsumer registers itself with the TapQueue, the queue
will, if necessary, re-order itself. The highest priority TapObject will
then be popped. The object has a reference to its' index on the timeout
heap. The new percolateUpMinHeap(int index) method is called to bubble the
object to the top of the timeout heap where it too is popped - keeping both
heaps synched. The consumer is given the object and de-registered.
Each bubble up/down operation takes place in log(n) time. Re-ordering only
happens when necessary. If too much re-ordering take place, then the
TapQueue operates in nlog(n) time but if this happens, the system is
seriously under-resourced and no amount of re-prioritising will help.
I have tested the classes and the logic works OK. I do have some problems
when running it multi-threaded mode and haven't worked out what's wrong yet.
The problems are commented in TapConsumerAdapter.service() and
TapTest.main().
Cheung Lo
London, UK
-----Original Message-----
From: Neil O'Toole [mailto:neilotoole@users.sourceforge.net]
Sent: 30 July 2003 23:06
To: Jakarta Commons Developers List
Subject: Re: [collections] Proposal for a Timeout Affected Priority
Queue
--- Cheung Lo <ch...@yahoo.co.uk> wrote:
> Proposal for a Timeout Affected Priority Queue
> I would like to propose the adoption of the TapQueue into the
> collections
> packages but need feedback on the following issues:
>
> 1. Has anyone else had a need for a timeout affected priority queue?
> 2. If so, what additional requirements did you have that is not
> already
> described?
> 3. How do I submit a draft of the classes - do I attach a zip file
> or paste
> into the body of an email?
> 4. Who do I send it to?
1. Yup, i hacked together a duct-tape and espresso solution for a
situation like this a few years ago. I remember at the time not being
very happy with it, and since I don't have access to that proprietary
code, I can thankfully forget i had anything to do with it. I would
very much like to see a first-class implementation in [collections].
2. Your description appears to suggest that the implementation only
bumps up the priority when the (single) timeout occurs. What might be
preferable is to have multiple timeout points (or some other aging
scheme).
Here's an example. Let's say you had a priority scheme 0->9 (9
highest), and in comes a policy admin job (as from your example). This
might get priority 1 (as opposed to a customer call, which might
initially have priority 6). Rather than waiting until the absolute
timeout occurs (say after 14 days) and then bumping the policy job
priority up to 9, it would be useful if after 2 days the policy job
gets bumped up to priority 2, then 2 days later to priority 3, etc.
Likewise I'd like my customer calls (which initially start at priority
6) to get bumped up to priority 7 after six hours, then to priority 8,
which would be the maximum priority for customer calls.
With this scheme policy jobs would gradually rise in priority, rather
than waiting until the deadline when the policy job would then become
absolute top priority (this does sound like my normal working pattern
though!).
To implement this there must be some way of associating an object (or
class of objects) with a particular (configurable) prioritizing scheme.
All sorts of things pop into my head ;) I'd really like to see what
you've come up with, and since i will probably have some OSS dev time
available fairly shortly, I'd be more than happy to lend you a hand
with development if needed.
3&4. As stephen said, a zip or a link. If the package is large (>100K?)
then you won't be able to mail it to the list anyway, so you would be
better off with a link.
- Neil
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org
Re: [collections] Proposal for a Timeout Affected Priority Queue
Posted by Neil O'Toole <ne...@users.sourceforge.net>.
--- Cheung Lo <ch...@yahoo.co.uk> wrote:
> Proposal for a Timeout Affected Priority Queue
> I would like to propose the adoption of the TapQueue into the
> collections
> packages but need feedback on the following issues:
>
> 1. Has anyone else had a need for a timeout affected priority queue?
> 2. If so, what additional requirements did you have that is not
> already
> described?
> 3. How do I submit a draft of the classes - do I attach a zip file
> or paste
> into the body of an email?
> 4. Who do I send it to?
1. Yup, i hacked together a duct-tape and espresso solution for a
situation like this a few years ago. I remember at the time not being
very happy with it, and since I don't have access to that proprietary
code, I can thankfully forget i had anything to do with it. I would
very much like to see a first-class implementation in [collections].
2. Your description appears to suggest that the implementation only
bumps up the priority when the (single) timeout occurs. What might be
preferable is to have multiple timeout points (or some other aging
scheme).
Here's an example. Let's say you had a priority scheme 0->9 (9
highest), and in comes a policy admin job (as from your example). This
might get priority 1 (as opposed to a customer call, which might
initially have priority 6). Rather than waiting until the absolute
timeout occurs (say after 14 days) and then bumping the policy job
priority up to 9, it would be useful if after 2 days the policy job
gets bumped up to priority 2, then 2 days later to priority 3, etc.
Likewise I'd like my customer calls (which initially start at priority
6) to get bumped up to priority 7 after six hours, then to priority 8,
which would be the maximum priority for customer calls.
With this scheme policy jobs would gradually rise in priority, rather
than waiting until the deadline when the policy job would then become
absolute top priority (this does sound like my normal working pattern
though!).
To implement this there must be some way of associating an object (or
class of objects) with a particular (configurable) prioritizing scheme.
All sorts of things pop into my head ;) I'd really like to see what
you've come up with, and since i will probably have some OSS dev time
available fairly shortly, I'd be more than happy to lend you a hand
with development if needed.
3&4. As stephen said, a zip or a link. If the package is large (>100K?)
then you won't be able to mail it to the list anyway, so you would be
better off with a link.
- Neil
---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org