search
Log In
2 votes
532 views

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) ?

in Operating System
edited by
532 views
0
Have to tried to consider shared and exclusive locks on a DLL ?

I think 3 semaphores are sufficient as 4 pointers are modified in case of DLL.
0
Answer given is $1$.
2

Given Solution :

1
looks right !

They are not asking to prevent deadlock or starvation. I accounted these for this question as it is not given to do that.
0
Questions asks for min. semaphores such that given $3$ operations can be performed one at a time. right!
In a doubly linked list we have access to a node from $2$ sides. So, If we go from other side we can perform many together.
0
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.
0
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.
0
Not many up operations, if we use mutex then only 1 at a time will take the control.

Please log in or register to answer this question.

Related questions

1 vote
1 answer
2
0 votes
1 answer
3
0 votes
1 answer
4
...