Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #6924

Re: A quota based lock

Show all headers | View raw

On Mon, 8 Aug 2011, Robert Stark wrote:

> I want to write a lock to control access to a resource, there are 
> different kind of jobs using this resource, say job A,B,C, [...] My idea 
> is input a map of percentages you want to assign for each job, and 
> provide a simple lock api.
>
> Input A=>20, B=>70, C=>10 means A=>20%, B=>70%, C=>10% If there's no A 
> jobs pending on the lock, then its quota would be divided evenly to 
> other pending jobs that is B=>80%, C=>20%.

So there's a single resource, right? And at any time, only one thread can 
hold the lock on the resource? But you want to share the lock between the 
threads in a fair (or at least controlled) way over time? Do you want to 
be fair in terms of time for which the lock his held, or the number of 
lock acquisitions?

> Then i got stuck, the only way i can think about is to introduce an 
> extra dispatch thread and several queues, can someone give me some hint?

You will need a separate queue for each kind of thread. I don't think you 
need another thread to handle the dispatching.

When a thread tries to acquire the lock, if the lock is available, it 
takes it (of course). If the lock is not available, it joins the right 
queue.

When a thread releases the lock, if there are no threads waiting, it does 
nothing (of course). If there are threads waiting, it decides which of the 
kinds of thread should get the lock next, and hands the lock to the next 
thread in that queue.

The only problem is how you decide which kind of thread should get the 
lock next.

The easiest would be to keep counters for each kind of thread, counting 
how many times threads of that kind have acquired the lock (or how long in 
total they have held it for, if you prefer). You can then easily calculate 
the total number of acquisitions (or the total time of holding), and so 
the share of the lock which each kind of thread has had so far. At any 
point in time, you can compare that historical share to your desired 
share, and put the kinds of threads in order, from the most short-changed 
to the most overprivileged, and award the lock to a thread of the most 
needy kind which currently has threads waiting.

This approach will give you a fair apportionment over time.

However, it means that if a kind of thread does not make full use of its 
allowance at some point in time (perhaps because there are not many of 
that kind of thread running), then it effectively builds up a 'share 
credit' which will allow it to make greater demands on the resource later 
on. You might consider that unfair. You might not.

If you do consider it unfair, you could address it by decaying the share 
counts over time - it would be a simple use of timestamps and Math.exp() 
to apply an exponential decay immediately before updating the counters.

tom

-- 
One chants out between two worlds Fire - Walk With Me.

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Find similar

Thread

A quota based lock Robert Stark <panxiaozhong@gmail.com> - 2011-08-08 00:13 -0700
  Re: A quota based lock Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-08-08 07:58 -0400
    Re: A quota based lock Knute Johnson <september@knutejohnson.com> - 2011-08-08 09:48 -0700
      Re: A quota based lock markspace <-@.> - 2011-08-08 10:00 -0700
        Re: A quota based lock Knute Johnson <september@knutejohnson.com> - 2011-08-08 11:39 -0700
          Re: A quota based lock markspace <-@.> - 2011-08-08 11:57 -0700
            Re: A quota based lock Robert Klemme <shortcutter@googlemail.com> - 2011-08-08 21:46 +0200
              Re: A quota based lock Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-08-08 20:41 -0400
                Re: A quota based lock Robert Klemme <shortcutter@googlemail.com> - 2011-08-10 09:36 +0200
                Re: A quota based lock Robert Stark <panxiaozhong@gmail.com> - 2011-08-10 04:40 -0700
                Re: A quota based lock Robert Klemme <shortcutter@googlemail.com> - 2011-08-10 18:55 +0200
                Re: A quota based lock Martin Gregorie <martin@address-in-sig.invalid> - 2011-08-10 19:26 +0000
                Re: A quota based lock Patricia Shanahan <pats@acm.org> - 2011-08-10 12:37 -0700
                Re: A quota based lock Robert Stark <panxiaozhong@gmail.com> - 2011-08-10 18:30 -0700
                Re: A quota based lock markspace <-@.> - 2011-08-10 19:17 -0700
                Re: A quota based lock Robert Klemme <shortcutter@googlemail.com> - 2011-08-11 12:32 +0200
          Re: A quota based lock Tom Anderson <twic@urchin.earth.li> - 2011-08-09 21:00 +0100
  Re: A quota based lock markspace <-@.> - 2011-08-08 07:58 -0700
  Re: A quota based lock Tom Anderson <twic@urchin.earth.li> - 2011-08-09 21:45 +0100

csiph-web