Hi Adam,
Quoting Adam Hraska <[email protected]>:
Selected HT
===========
I would like to implement a HT based on (F) because it:
- is fully resizable
- has zero reader overhead
- does not have excessive space overhead
Unfortunately, HT (F) has blocking updates. However,
I thought of how to make updates lock-free even in the
face of resize() using techniques of (A), (C), (D).
First, bucket linked lists would use (A)'s lock-free
linked lists where contention for a node is resolved
locally by competing for its immediate neighbors
(ie predecessor or successor). Second, nodes would be
sorted as in (D) so that a bucket can be split/joined
by changing a single link (instead of a multiple zip/
unzip passes + waiting of (F)). Third, during resize
bucket heads would be moved to the new table lock-freely
one bucket head at a time as in (C).
What remains is to update the single split/join link
between buckets in a lock-free manner. To do this we
will mark the boundary node or head with additional
states. I assume all nodes will reside on a word-sized
address, so we can make use of the lower 2 bits in eg
the "next" node pointers. Details will be provided
with the implementation unless I find a mistake in
my logic before that ;-).
The resulting HT would have these properties:
+ fully resizable
+ zero overhead readers when not resizing
+ minimal space overhead
+ lock-free updates even during resize (ie we can update
the table from exception handlers ever during resize)
- indirection while resizing (have to check bucket
heads in both the old and the new table)
- MB for readers of buckets that are being split/joined
- resize will not be lock-free, ie if a resizing thread
is killed (but it won't be), updaters will not be able
to complete resizing on behalf of the resizing thread.
The table would however continue to function even
after such a failure but without the performance
benefit of a resize.
End
===
I still have to write which RCU algorithm to implement
in HelenOS and how to interface GPTH with a concurrent
HT.
Thanks for providing the above analysis. One can almost feel the
foundations for your thesis in it. Hopefully it is managable to
implement it in the rather short time you have. I guess the most
important property for us at this point, after the correctness
property, is the resizing property. For the use in the memory
mnagement, the HT needs to have non-blocking lookups too.
Have you already setup hosting for your branch? I would like to be
able to see what is brewing in it.
Jakub
----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.
_______________________________________________
HelenOS-devel mailing list
[email protected]
http://lists.modry.cz/cgi-bin/listinfo/helenos-devel
