Concurrent access to groups of objects

I'm trying to develop an application that consists of a pool of threads, using a work-stealing algorithm to concurrently execute tasks.

These tasks

• access a predefined set of objects;
• must "atomicly" acquire read/write permissions on all objects it accesses before actually running;
• upon finishing (and are guaranteed to eventually finish) release the objects they acquire.

One possible way to to solve this problem is to have each thread pick up a task at a time, then try to lock each of the objects using a predefined order. If at least one fails release all the locks, and proceed with another task.

This method however increases the probability of starvation of tasks with big object dependencies, and may even incur in live locks.

Is there another method to acquire a set of locks while maximizing concurrency? (without a glob开发者_运维知识库al lock) Or perhaps change the system in a way that it is no longer required? If so, any good papers about it?

ps: As thiton answered, this is a generalized version of the "dining philosophers" problem. I am looking for non-centralized solutions, in particular algorithms that fare well in high load (addition and deletion of tasks).

Ordering resources is a valid approach. Another straightforward aproach that comes to mind is to introduce a shared arbiter holding information about resource availability. Tasks would lock all the resources they need through the arbiter in a single atomic step "acquire(r1, r2, ..., rn)" and release them similarly with "release(r1, r2, ..., rn)".

If an "acquire" request A can be satisfied, the arbiter will make sure no other task may acquire any of the resources held by A until A releases them back.

The arbiter may use several strategies to satisfy incoming requests:

1. Reject request that can't be immediately satisfied - tasks will have to re-try. This opens the door to live-locks and starvation.
2. Keep all incoming requests in a queue and serving them in FIFO manner as resources needed for the request at head become available.
3. Keep all unsatisfied requests in a list (without blocking their demanded resources) and iterate through them (perhaps with a priority for older requests) each time some resources get released, to find a request that can be satisfied.

Your problem is called the Dining Philosophers. You should find any amount of literature you need under this keyword :-).

If a task tries to lock objects only to fail at some point, it's possible that another task will fail to lock an object because the first task owns it at the time.

I think I would use a global lock when trying to acquire the locks initially and maybe also when releasing them all finally.

I'd worry about maximum concurrency when a simple solution proves to be inadequate in practice.