Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Eric Sosman Newsgroups: comp.lang.java.programmer Subject: Re: A quota based lock Date: Mon, 08 Aug 2011 07:58:51 -0400 Organization: A noiseless patient Spider Lines: 72 Message-ID: References: <83f81158-8aee-486d-a51b-c0f7dfdbb0da@h25g2000prf.googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Injection-Date: Mon, 8 Aug 2011 11:59:29 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="f8igmItKsWs6nM5YanFxAA"; logging-data="30685"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19PhqG7c9gdZIjY0JQIpH4Q" User-Agent: Mozilla/5.0 (Windows NT 5.1; rv:5.0) Gecko/20110624 Thunderbird/5.0 In-Reply-To: <83f81158-8aee-486d-a51b-c0f7dfdbb0da@h25g2000prf.googlegroups.com> Cancel-Lock: sha1:TQ9V9YunVbzkILc/Cz417eBfE/I= Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:6866 On 8/8/2011 3:13 AM, 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, at the > beginning, i use Lock api from jdk concurrent package, but i suffered > from serious job starvation, so i want to do something like this: >[...] > > 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%.(This rule > apply to other type of jobs as well). > > 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? Your requirements aren't entirely clear to me, but here are a couple of thoughts: If the locks are held for short durations (as most locks should be), this "quota" notion doesn't seem to make a lot of sense. If a worker takes the lock, does something critical for a microsecond, then drops it and goes about its business for a second, whatever problems you're having aren't really to do with the lock per se. So I guess you're thinking about a lock that proxies for an unshareable resource a worker will use for macroscopic time, and it's not truly the lock you want quotas for, but the resource behind it. If so, right away you can see you'll need a way to ensure that a worker will release the resource "soon" to give other workers a chance at it. If this property isn't inherent in your design, you'll need to include some kind of preemption mechanism, a way to wrest the resource from its holder involuntarily (possibly involving rollbacks or other kinds of recovery for the worker that got preempted). Lacking either preemption or a guarantee of timely release, you can't be sure that Worker A (20% quota) won't hold the resource for six solid months. This is the kind of problem an O/S' task scheduler solves: It doles out various unshareable resources (CPU cycles, RAM locations, I/O access, ...) to competing consumers. I'm not an expert on the various techniques used, but I don't think it's a "solved problem" (if it were, there wouldn't be so many different schedulers). That is, I don't think there's a one-size-fits-all sure-fire solution to your problem; you'll need to consider your goals and constraints in quite a bit of detail to arrive at a tolerable compromise, probably less than completely satisfactory. So, one thought is to give the problem to the O/S' scheduler! If the unshareable resource is something the O/S understands, maybe your workers should be separate "tasks" or "jobs" or whatever the O/S wants to call them. It could save you a lot of hard work if you can let an existing software component do the job for you. Failing that, I'd suggest keeping things as simple as possible. Start with an ordinary queue, with each worker joining the end of the queue when it wants the resource and then getting the resource when it reaches the front. If Worker A holds the resource (and eventually releases it), all the other workers will get a crack at it (if they want it) before A gets it again. Don't mess around with quotas or priorities or whatnot until and unless the simple solution is found wanting. If the simple solution doesn't work out, report back (with more detail) and I'm sure folks will suggest more sophisticated approaches. But for starters, KISS. -- Eric Sosman esosman@ieee-dot-org.invalid