Traversing a list with hazard pointers
I'm working with Hazard pointer in order to implement a lock-free linked list in C. I couldn't find any example code other than vary basics queues and stacks. The problem is I need to traverse the list, so my question is if I can change the value of a hazard pointer once is assigned. For example:
t←Top
while(true) {
if t=null then
return null
*hp←t
if Top!=t then
continue
...
t←(t→next) //after this instruction pointer t will be still protected?
}
Finally I ended implementing my own version of Hazard Pointers (HP) according to the original paper. The answer to my question is NO, t is no longer safe to use. The reason is that, the way HP works, *hp is protecting the node being pointed by t when you declared it as a hazardous pointer, so when t moves to the next node, the HP mechanism keeps protecting the previous node. I have to reassign the new value to *hp before I can use it safely.
Also, in the example of the paper it is not explicit, but when you finish using a hazard pointer you have to release it. That means, return *hp to its original state (NULL). This way, if another thread wants to delete (retire) this node, it won't be seen as being used.
In my example above, I have to release *hp before leaving the method. Inside the loop it is not necessary because I am overwriting the same *hp position (*hp ← t), so the previous node is no longer protected.
You do not need hazard pointers when you are only traversing the list. Hazard happens when different threads are reading and writing from and to the same resource (In particular, hazard pointers are to overcome ABA problem, when a resource's value is changed to something and then back to its original value, which makes noticing the change difficult). With traversing, you are only reading, hence no need for hazard pointers.
By the way, it seems to me that you have to change if Top=t to if Top!=t , so that you can proceed with your code if there is no hazard. Note that continue returns to the beginning of the loop. Also, your whole code should be in a while(true) loop.
You can read more about hazard pointers here http://www.drdobbs.com/lock-free-data-structures-with-hazard-po/184401890 , or just by googling!
EDIT You need to provide the code for insert and delete functions. In short, the part of the code that you've mentioned ends up being an infinite loop after execution of t←(t→next) , since Top!=t will hold true afterwards. What you need to do instead of checking t against Top, is to check it against its previously captured value. Again, it depends on your implementation of other methods, but you probably want to implement something similar to Tim Harris algorithm, which uses a two phase deletion (1-marking and 2-freeing the node). Then, when you traverse the list, you need to check for marked nodes as well. There is also an implementation of a doubly linked list, with a find method which you can use as a base of your implementaion, in Fig 9 of http://www.research.ibm.com/people/m/michael/ieeetpds-2004.pdf. Hope this helps.
上一篇: 为什么thenCallRealMethod（）在这里失去了参数？
下一篇: 遍历具有危险指针的列表