Locking objects in an array

[Daniel Pitts]

Daniel Pitts wrote:
....

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.

Patricia

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.

 

[Seamus MacRae]

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.

And now we're back at the scheduling problem that arose in another
thread recently.

 

[Roedy Green]

How should I design the code to achieve this?

what you need is a separate array of locking objects, one for each 2x2
region. The lock's purpose is to establish who has legit access. The
data objects are not locked.
--
Roedy Green Canadian Mind Products
http://mindprod.com

"It wasn’t the Exxon Valdez captain’s driving that caused the Alaskan oil spill. It was yours."
~ Greenpeace advertisement New York Times 1990-02-25

 

[Philipp]

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.

A bit more input about the problem I'm trying to solve. I'm thinking
about a parallel implementation of a kinetic Monte-Carlo method
(http://en.wikipedia.org/wiki/Kinetic_Monte_Carlo). So, I'm not
worried about starvation (big array, small regions, few threads). The
process which needs to be executed on each region is fast and probably
always of comparable calculation-length.
Reordoring of jobs must be taken with caution as the random order of
the locations is key to the physical correctness of the solution.
Biases are easily introduced by making wrong assumptions.

Any input about my non-blocking idea (see my previous post)? Is it any
good?

Phil
PS: I will be away for a week without internet access

 

[Tom Anderson]

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

 

[Daniel Pitts]

Sorry if this is a duplicate, news server problems.

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.

One thing to consider is the difference between Unit tests and
Integration tests (and the fuzzy line in between). Unit test, if your
code was written properly, will always be safe to run in parallel.
Integration tests rely on external resources that may be limited, so
they might not be parallelizable.

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.

With long running tasks, that might not be such a bad thing. An
unscheduled thread takes up very few resources (though not none)

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.

True, but your eventual goal is that all the tests run, at some point
that second test will get a chance to run.

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

My approach for your particular use case would probably be to have a
specialized queue which will return the next not-blocked test available.

It might not be perfect, but it probably gets you to 80% of your goal.
The queue "heuristic" can be improved without breaking the abstraction,
so the rest of your code needn't change. That would probably get you
that last 19%