[concurrency-interest] Proposal WeightedLinkedBoundedQueue

Tim Peierls tim at peierls.net
Fri Nov 24 12:48:20 EST 2006


If this is about resource control, couldn't you use a Semaphore to bound the
resource usage and any kind of thread-safe queue to provide the resource
ordering?

put(x) => sem.acquire(x.weight()); queue.put(x);
take() => x = queue.take(); sem.release(x.weight());

where sem is initialized with the resource bound.

--tim

On 11/24/06, Thierry Hanot <thanot at infovista.com> wrote:
>
>  Ok - but practically speaking how to you calculate the size/weight? We
> often talk informally about lightweight and heavyweight objects, but we
> don't actually have a simple means of quantifying that. Are you just working
> on the basis that if the user can define some notion of "weight" then this
> data structure can impose a weight limit?
>
>
>
> Yes because the weight depends a lot about the architecture of what you
> are doing.
>
> For instance if you use a queue to store task, the weight of the task can
> an estimation of the cost of the task ( refuse task if you want to be sure
> to guarantee the execution in a certain amount of time). If for a reason or
> another the task is also containing data used during the execution, then the
> weight can be an estimation of its size.
>
> In my case the queue contains data to be store in a database. Each data is
> referenced by a composite id and we have some other information about the
> impact of the data. To avoid to have for each event the 3 objects (the
> id,the data and the impacts). We have one event which is containing one id ,
> n data and one compacted impact list.
>
> Then the size of an event is not 1. And when we want to avoid using to
> much memory we need to use a weight estimation which instead of the count to
> bound the queue.
>
>
>
>
>
> It seems rather special purpose. If weight was memory-usage, and we had a
> way to measure that, then I could see use for this in some memory
> constrained contexts.
>
>
>
> I agree, it's a bit specific. But the queues are very useful to have some
> kind of "resource usage control".  The resource cannot be represented by the
> counts of objects in the queue or by the memory but can be of any kind (
> memory mostly but we can have network/cpu/disk …). And most of the
> applications need the resource control (except if you have unlimited
> resources)
>
>
>
> As it is I would think you could do this via a fairly simple wrapper, as
> you'll need to track the cumulative weight as objects are added/removed.
> You'll need stronger synchronization than provided by LinkedBlockingQueue
> unless the weight-limit is allowed to be violated - so adding the sync in
> the wrapper seems reasonable too.
>
>
>
> I was thinking of extending the LinkedBoundedQueue because we can
> generalize all the principle in this queue easily. But the locks and
> conditions are privateL.
>
> The main change in the code is:
>
> instead of using getAndIncrement(or decrement) we can use getAndAdd(+ or –
> element.weigth) and  test the not full no anymore with an equality on
> capacity but on >=.
>
> With this we can avoid any stronger synchronization ( even if we will
> probably notify a bit too much the notFull condition).
>
>
>
>
>
>
>
>
>
> Cheers,
>
> David Holmes
>
>
>
>
>
> Best regards,
>
> Thierry Hanot
>
>
>
> -----Original Message-----
> *From:* concurrency-interest-bounces at cs.oswego.edu [mailto:
> concurrency-interest-bounces at cs.oswego.edu]*On Behalf Of *Thierry Hanot
> *Sent:* Thursday, 23 November 2006 9:43 PM
> *To:* dholmes at ieee.org; concurrency-interest at cs.oswego.edu
> *Subject:* Re: [concurrency-interest] Proposal WeightedLinkedBoundedQueue
>
> The weight is defined by the end user using a small interface yes.
>
> I use the term weight but size is also relevant J
>
>
>
>
>
> *Thierry Hanot*
>   ------------------------------
>
> *From:* David Holmes [mailto:dcholmes at optusnet.com.au]
> *Sent:* jeudi 23 novembre 2006 01:26
> *To:* Thierry Hanot; concurrency-interest at cs.oswego.edu
> *Subject:* RE: [concurrency-interest] Proposal WeightedLinkedBoundedQueue
>
>
>
> How do you define and measure the "weight" of an object?
>
>
>
> David Holmes
>
> -----Original Message-----
> *From:* concurrency-interest-bounces at cs.oswego.edu [mailto:
> concurrency-interest-bounces at cs.oswego.edu]*On Behalf Of *Thierry Hanot
> *Sent:* Wednesday, 22 November 2006 10:18 PM
> *To:* concurrency-interest at cs.oswego.edu
> *Subject:* [concurrency-interest] Proposal WeightedLinkedBoundedQueue
>
>
>
> A small proposal for adding a new class in the concurrent package.
>
> All bounded collection are bounded to avoid to use to much memory.(At
> least in my case J).
>
> But the element put in those collections are often with different size.
>
> In my case  BoundedQueue is used as an event queue and we can have
> composite events which contains itself many events.
>
> What do you think about adding some bounded collection no more based on
> the count but on the sum of the weight of the object inside?
>
>
>
> After a quick look on the code of the LinkedBoundedQueue it seems pretty
> easy to do.
>
>
>
> Does somebody else can see the advantage of this kind of object and is
> there enough people interested to make it a part of the concurrent package?
>
>
>
> B.R
>
>
>
>
>
> *Thierry Hanot*
>
>
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at altair.cs.oswego.edu
> http://altair.cs.oswego.edu/mailman/listinfo/concurrency-interest
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/attachments/20061124/2b188fc9/attachment.html 


More information about the Concurrency-interest mailing list