Re: Locking objects in an array
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.
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.
--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>