关于 多核 多读一写 无锁链表，请教
其他很多cpu读链表，单独一个cpu修改链表, 赋值操作为原子操作。比如单向链表: a->c->NULL
负责修改的cpu插入b节点:
b->next = c;
smp_wb();//保证上面先执行
a->next = b;
其他的只读链表的cpu
cur = a;
cur = cur->next;
visit(cur); //可能为b
mp_read_barrier_depends();
cur = cur->next;//如果为b，是否一定为c
visit(cur);
请问， 这样有没有问题， 不知道链表可不可以看成是data dependency, 如果是，这样写，除非读不到b (a->next==c)，否则(a->next == b) b->next就一定是c。
多谢。
上面的代码是为了说明方便，实际上mp_read_barrier_depends() 定义为do{}while(0) ，读链表的操作为一个for循环
for(...)
visit(cur); 没有问题，据说那款有问题的cpu早已停产了。 插入应该没问题，删除怎么办？ 看起来好像没问题~ 本帖最后由 yiifburj 于 2014-08-23 14:38 编辑
mnipxh 发表于 2014-06-03 17:11 static/image/common/back.gif
插入应该没问题，删除怎么办？
删除等一会再释放内存。
一个办法是
void wmbdd_barrier(void *unused)
{
smp_mb();
}
smb_mb();
preempt_disable();
smp_call_function(wmbdd_barrier, NULL, 1);
preempt_enable();
然后再free, 正确性和可行性还不敢保证。 本帖最后由 leiweigan1 于 2014-07-16 08:53 编辑
回复 5# yiifburj
能具体点说明，无锁删除的方法吗？类似于rcu?
回复 6# leiweigan1
on_each_cpu应该有问题， 帖子已更改， 因为on_each_cpu先在其他cpu上执行， 再在本cpu上执行， 应该顺序掉过来。
双向或单项链表 a b c ， 删除b， 改变a->next和c->prev， 这样b就从链表上下来了， b指针指向不动， 然后smp_mb(); on_each_cpu(...);/* 不需要on_each_cpu, 因为本cpu已经有smp_mb()了， 可以去掉， 忘了那个函数的名字了， 见on_each_cpu的实现，*/ ， 本cpu加入smp_mb(); 表明 a， c里面的指针指向的更改此时此刻已经提交，其他cpu可见， 然后其他cpu执行smp_mb();表明其他cpu执行smp_mb之后的内存操作均在smp_mb后面完成， 这样其他cpu拿到的本cpu的数据就是更新之后的， b可以安全的free掉了。
只是推测， 还不敢保证， 另外可能有更简单的方法， rcu没有仔细研究过。 回复 7# yiifburj
以单项链表为例，a-》b-》c，删除b，a->next = c，这不是原子操作， 有可能在赋值a-》next的时候，c已经被删除了吧？
回复 8# leiweigan1
抱歉, 忘了来这里了, 这种方法只能同时一个人修改, 当同时多个人改的时候不能无锁, 但只是修改的人需要锁, 读的不需要.
页:
[1]