Architecture problem: access-queue block

Question

There's a resource manager class. It helps us to access devices. But, of course, it should look for not to give access to one device for 2 processes at the same time.

At first I thought I wouldn't have any access queue. I thought there would be method like anyFree_devicename() that would return access handle if there is any free and NULL if no any. But, because of high concurrency for some devices, I've written accessQueue in every device.

Now, when you try to access device your pid (process id) is inserted into such accessQueue and you can ask for your turn using special method.

But, I found one problem: access Queues can block each other when you need few devicec in one command:

Device1 Device2
   1       2
   2       1

And both of them would be blocked.

inline bool API::Device::Device::ShallIUse(int pid)
{
if (amIFirst(pid)) return 1;   // if I'm first I can use it anyway
std::stack<int> tempStorage;    // we pass every element acessQ -> Temp 

while (acessQueue.front() != pid) // every process
{
    //we take process pointer to look into it's queue
    API::ProcessManager::Process* proc = API::ProcessManager::TaskManager::me->giveProcess(acessQueue.front());
    // list of devices this prosess needs now
    std::vector<API::Device::Device*>* dINeed = proc->topCommand()->devINeedPtr(); 
    // an dsee if there any process 
    for (int i = 0; i < (dINeed->size() - 1); i++)
    {
        if (!dINeed[i]->mIFirst())
        {
            while ( ! tempStorage.empty())
            {
                acessQueue.push(tempStorage.top());
                tempStorage.pop();
            }
            return 0;
        }
    }
    tempStorage.push(acessQueue.front());
    acessQueue.pop();
}
return 1;

I've written such algorithm some lime later but:

1. It ruing all layer-based architecture

2. Now It seems to work wrong.

3. That's crazy! We simply look-trough all commands in nearly all processes and tring to push some of commands up on the access Queue. It works really slow.

Answer 1

Your access queue is creating what is known as a dead-lock. Multiple clients become perpetually blocked because they are trying to take ownership of the same set of resources but in a different order.

You can avoid it by assigning a unique value to all your resources. Have the clients submit a list of desired resources to the resource manager. The resource manager's acquire method will sort the list by the resource number and then attempt to allocate that set of resources in order.

This will enforce a specific order for all acquisitions and you will never be able to deadlock.

Any given client will, of course, block until all the set of resources it needs are available.