Re: A quota based lock
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.