The Gateway to Computer Science Excellence
+2 votes
391 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 by Boss (28.7k points)
edited by | 391 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
asked Nov 6, 2017 in Operating System by Parshu gate Active (3.1k points) | 177 views
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
198,314 comments
105,011 users