воскресенье, 24 июня 2012 г.

binary tree for multithread access

Task
I need some binary tree structure for concurrent access from multiple threads where some threads do searching and some other perform insert/delete operations. This structure must work both in kernel and user mode

Solutions
Lets add some sync primitive to each tree node -  it is going to be SRWLock in user mode and EX_PUSH_LOCK in kernel mode. It`s clear that reader can acquire shared lock while writer will use exclusive one. Bcs order of locks always have to be the same - we need tree structure with top-down rebalancing (I hope this is right assumption). So lets see which kinds of trees allow such operations
  1. weight-balanced tree. Drawbacks: need to use floating point, so in kernel mode we must care about FPU context saving/restoring
  2. classical B-tree. I think there may be a problem with granularity - when node contains a big number of keys and we need to lock it exclusively - all search operations will be blocked from this node till the lowest level of its children
  3. red-black tree. Looks like it is a good candidate but sadly I cannot find implementation in plain C with top-down rebalancing :-(
Do I miss something important ?

    2 комментария:

    1. Win8 has RTL_RB tree implementation that may be of use :)

      ОтветитьУдалить
    2. No
      1) Implementation of avl inside ntdll don`t have fain grained synchronization within each node
      2) avl trees uses bottop-top pass for rebalancing. This is no-no - you will acquire locks in opposite order with simple searching and end up with dealock

      ОтветитьУдалить