Re: Locking objects in an array
On Thu, 14 May 2009, Daniel Pitts wrote:
Patricia Shanahan wrote:
Daniel Pitts wrote:
....
I was thinking more about not having explicit locks per object, but
instead having a "Lock Request" that puts its region into a specific data
structure. That Lock Request would block as long as the current region
intersects any region currently ahead of it in that data structure. Once
work is complete, that Lock Request can be removed from that
data-structure, unblocking other threads waiting for that region.
Won't that create unnecessary contention?
Assume all requests are for 2x2 squares, identified by lowest index in
each dimension.
Requests: (0,0) (1,1) (2,2).
The first and third requests do not overlap, and could run in parallel,
but (1,1) has to block until (0,0) is over, and (2,2) would block
because it overlaps (1,1) which is ahead of it.
Yes, I was thinking about that.
It might be possible to have a "blocking" lock mark itself as "waiting on
another". If the latest lock can move past the waiting lock successfully,
then it can preempt that waiting lock.
An alternative, depending on the OPs actual problem, would be collect the
list of regions (and jobs) that need to execute, and create an optimal
ordering of those jobs such that the most can execute at once.
This still may lead to a less than optimal solution if the jobs themselves
have varying time that can't be accounted for in the ordering process.
Funnily enough, i have exactly the same problem in something i'm working
on in my spare time at the moment. I'm writing a parallel JUnit runner,
which runs the tests in multiple threads (there are existing ways of doing
this, but they're all awful).
One of the features i want to add is the ability to control concurrency in
cases where tests can't safely run in parallel. For example, at work,
we're testing a system that has a 'publish' operation, where you can't
really run two publishes at the same time, so i want to be able to mark
tests as requiring exclusive use of the publishing operation, so the
runner won't try and run two at once.
I could do this with a normal locking mechanism, but that hurts
concurrency: if a publishing test is already running, then if another
thread picks up a second one, it will block, and so sit idle until the
first one finishes. As you observed, no good.
I could do it with a mechanism that scans the test queue and picks the
first test that doesn't need any currently-held locks. This avoids
blocking, avoids the contention problem Patricia described, but does lead
to a risk of starvation or at least queue-jumping - if i'm running a test
which uses publishing, the next one uses publishing and database copying
(another non-parallelisable operation), and there's one after that just
uses database copying, then this approach would run the third one, which
would then stop the second one from running when the first one finishes.
Currently, i lean towards a mechanism like your lock requests (the code
for which i will be examining in detail at a later date ...), which would
give me safety without starvation, at the expense of concurrency. In my
case, the great majority of tests don't need any exclusive access at all,
so there should always be some other test to run while one of the
publishing or database copying tests is blocked, and so the loss of some
concurrency should not be a big deal.
tom
--
Once, at a fair on the Heath, [Geoffrey Fletcher] overheard a man saying
that Hampstead wasn't thrilling enough. Fletcher reached over in the
darkness and stuck an ice lolly down the back of his shirt.