请教一个多线程设计的面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教一个多线程设计的面试题

请教一个多线程设计的面试题# JobHunting - 待字闺中

w*e2013-11-19 08:11

1 楼

设计一个支持concurrency的BST，该BST是类似于AVL和RBT的balanced，也就是说有些
操作会rotation。
请问谁有大概的思路？

m*n2013-11-19 08:11

2 楼

critical section + AVL tree rotation.

w*e2013-11-19 08:11

3 楼

details？怎么在tree里加入lock，lock怎么工作，然后改进improve concurrency，等
等。

【在 m*******n 的大作中提到】

: critical section + AVL tree rotation.

s*u2013-11-19 08:11

4 楼

都这难度了啊。。。。

p*32013-11-19 08:11

5 楼

这个如果只是一般的插入和删除还好做，如果要rotate有可能一直rotate到root啊，整
个结构都可能改变。觉得rotate的话是肯定要锁住整个树，两个插入或删除不能同时发
生。如果读的话是不是可以用cpu支持的check and swap. 如果在确定iterate的子节点
发生变化的时候就retry,retry超过一定次数就lock整个树，就是在rotate的的时候刚
好正在travel那个rotate的节点的时候才可能miss一个数

【在 w*******e 的大作中提到】

: 设计一个支持concurrency的BST，该BST是类似于AVL和RBT的balanced，也就是说有些
: 操作会rotation。
: 请问谁有大概的思路？

p*22013-11-19 08:11

6 楼

这题是大牛研习的EPI里的吧？

【在 p*****3 的大作中提到】

:
: 这个如果只是一般的插入和删除还好做，如果要rotate有可能一直rotate到root啊，整
: 个结构都可能改变。觉得rotate的话是肯定要锁住整个树，两个插入或删除不能同时发
: 生。如果读的话是不是可以用cpu支持的check and swap. 如果在确定iterate的子节点
: 发生变化的时候就retry,retry超过一定次数就lock整个树，就是在rotate的的时候刚
: 好正在travel那个rotate的节点的时候才可能miss一个数

p*32013-11-19 08:11

7 楼

java的concurrentHashMap有点像啊，网上有篇paper :
http://www.cs.umanitoba.ca/~hacamero/Research/RBTreesKim.pdf

【在 p*****2 的大作中提到】

:
: 这题是大牛研习的EPI里的吧？

z*q2013-11-19 08:11

8 楼

用基本的读写锁思路行么？不一定是最优的，但应付面试够了吧

z*e2013-11-19 08:11

9 楼

就是用基本的读写锁
但是不会把整个bst对象给锁住
会把节点锁住，当然这里bst都是自己去实现
所以锁node就好了

【在 z**q 的大作中提到】

: 用基本的读写锁思路行么？不一定是最优的，但应付面试够了吧

f*42013-11-19 08:11

10 楼

锁node的话，树一大，并发一上去就别跑了 -_-
struct Node
{
Node *left, *right;
share_pointer data;
};
atomic root;
查找的时候，把当前root和data一块返回，对data的操作需要比较返回的
root和当前的atomic root；发现不一样，重新从atomic root查找。
新增或者删除的时候，每次都新建一个root，新树可以复用旧树未修改节点，更新
atomic root，旧树的未被新树使用的节点可以delay到下一次新增删除的时候删除。注
意退出的时候也需要清除这些节点。