Lists - Locks in optimistic contains()

[Andrey Brito]

Hello.

It seems the list has been too quite for too long, but maybe we can still try to create some interesting discussions.

So, while looking at the motivations for the lazy approach for lists, it mentions that in that "particular implementation" contains() acquire locks. Nevertheless, I cannot see a reason why the implementation of contains() (figure 9.13 in the book) needs to validate before checking. After all, if the item was there when it started, it does not matter if it was recently removed.

Is someone aware of a non-intuitive motivation for this?

Thank you.

[]'s

Andrey

[Vaarnan Drolia]

Could it be because of the definition of contains()?

"The contains(x) returns true if, and only if the set contains x."

--Vaarnan

--
You received this message because you are subscribed to the Google Groups "Art of Multiprocessor Programming" group.
To unsubscribe from this group and stop receiving emails from it, send an email to art-of-multiprocessor-...@googlegroups.com.
To post to this group, send email to art-of-multiproc...@googlegroups.com.
Visit this group at http://groups.google.com/group/art-of-multiprocessor-programming?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Andrey Brito]

Hi Vaarnan,

the point is that if the consistency model for the contains() is linearizability, then a result that was valid at any point during the execution of the method is a valid result.

And even by using the validation, between the time the observation was made (holding the lock) and the time of the actual return, many things can have changed anyway (e.g., the thread lost the processor and other thread removed the element). So, one cannot (realistically) expect something stronger than linearizability.

Good to see I am not alone in the group.

[]'s

Andrey

[Nitish Varshney]

Hi Andrey,

   As you have specified "result that was valid at any point during the execution of the method is a valid result" and problem with OptimisticList class contains method is it acquires locks. Combining both the points I can not see a reason why there is need of locks at all? After all item was there when it started, it does not matter if it was recently removed.


--
Nitish