Semaphores:

Question

Assume that you have a semaphore associated with each item on a doubly linked list. 
Using No other synchronization primitive, What is the fewest number of semaphore that you must acquire for any operation (lookup, insert, delete) ?

Comments

This is what i was thinking. suppose we are reading from a node 4 and other thread comes and deletes node 3 then, we have to modify 2 pointers . But that can be done, if question says that there is no possibilty of deadlock and multithreading is there .

Since, it is not concerned about these problems, why not lock the complete list.

---

When complete list in locked using one semaphore, then it may be the case that all operations are performed from the side that performs UP on semaphore.

---

Not many up operations, if we use mutex then only 1 at a time will take the control.

Answer 1

1