Your OS has a set of queues, each of which is protected by a lock. To enqueue or dequeue an item, a thread must hold the lock associated to the queue.
You need to implement an atomic transfer routine that dequeues an item from one queue and enqueues it on another. The transfer must appear to occur atomically.
This is your first attempt:
void transfer(Queue *q1, Queue *q2) {
Item thing; /* the thing being transferred */
q1->lock.Acquire(); thing = q1->Dequeue(); if (thing != NULL){
q2->lock.Acquire(); q2->Enqueue(thing); q2->lock.Release();
} q1->lock.Release()
You may assume that q1 and q2 never refer to the same queue. Also, assume that you have a function Queue::Address that takes a queue and returns, as an unsigned integer, its address in memory.
a. Explain how using this implementation of transfer leads to deadlock; b. Write a modified version of transfer that avoids deadlock and does the transfer atomically; c. If the transfer does not need to be atomic, how might you change your solution to achieve a higher degree of concurrency? Justify how your modification increases concurrency.