Re: A quota based lock
On 8/8/2011 3:46 PM, Robert Klemme wrote:
On 08.08.2011 20:57, markspace wrote:
On 8/8/2011 11:39 AM, Knute Johnson wrote:
No priority scheme will ever be truly fair. I'll bet you could get
pretty close without being too complicated. I'll think about it some
more.
A simple priority system might involve multiple queues, where the high
priority queues are serviced X times more than the lower ones.
E.g., two queues. Queue A gets 10 jobs executed for each 1 job that
queue B gets executed. But because queue B is always guaranteed to be
serviced eventually, there is no starvation.
This is a simple step up from round-robin service (which is what Eric
proposed). There are many algorithms existing. Check out any text on OSs
and job scheduling.
Another idea would be to take the time a task has access to the
resource, sum up per task category and for the next task pick the first
one from the category which is furthest below its specified share
(percentage). Basically your approach measures executions and this
approach measures actual resource usage time.
Yes, all these disciplines are plausible. My main piece of advice
is KISS: Begin with the simplest possible solution, and elaborate it
only when there's solid evidence it won't suffice.
Sometimes the evidence can be gathered in advance: If you know
things about arrival rates and hold times and latency requirements, you
may be able to do a calculation that shows simple FIFO won't hack it.
More often, given the inherent complexity and "brittleness" of software
systems, you'll need to implement first and measure afterwards to learn
about a solution's shortcomings. This can lead to discarding the first
solution -- but, hey: It was the simplest one you could imagine, so you
probably didn't expend inordinate effort on it, right? Much cheaper to
jettison a simple approach than a complicated one.
KISS.
--
Eric Sosman
esosman@ieee-dot-org.invalid