w**n 发帖数: 122 | 1 concurrency非常不熟
求大牛们指点,这个应该怎么写
//bow |
g*******s 发帖数: 2963 | |
s********r 发帖数: 403 | 3 non-blocking algorithm 禁止使用 lock 或 mutex,
只能使用 atomic operation, 比如 compare-and-swap (CAS)
哪个公司出的题? |
w**n 发帖数: 122 | 4 glassdoor上LinkedIn的题
大牛能指点下吗?
我goog到这个,但是没太看懂
http://stackoverflow.com/questions/1645326/non-blocking-thread-
【在 s********r 的大作中提到】 : non-blocking algorithm 禁止使用 lock 或 mutex, : 只能使用 atomic operation, 比如 compare-and-swap (CAS) : 哪个公司出的题?
|
n*****u 发帖数: 465 | 5 这个不太容易写, 应该用 tight loop 加上原子操作 CAS 啥的, 确认可以安全写或读,
一个writer 会容易点, 多个就烦了.
【在 w**n 的大作中提到】 : concurrency非常不熟 : 求大牛们指点,这个应该怎么写 : //bow
|
s********r 发帖数: 403 | 6 大牛不敢。
我只是写过一些简单的 non-blocking algorithm。
这些 non-blocking 算法是 Multiple-Thread Multiple Data 的编程模式,用于多核
系统,但其执行效率与体系结构,尤其是 cache 结构相关。还牵涉到 memory
consistent model。在c++11 中,很多 atomic operation 是为这个准备的。
下面的 code 仅仅代表一个思路上的描述:
void enq(Node *queue, T val)
{
Node * node = new node(val);
node->next = NULL;
Node * tail = NULL, *last = NULL;
for (;;)
{
tail = queue->gettail(); //atomic get
last = tail->next;
if (tail == queue->gettail()) //Are we still there?
{
if (NULL == last)
{
if (NULL == compare_and_swap(&tail->next, NULL, node))
{
queue->settail(node);
break; //succeed
}
}
else
{
queue->settail(last); //Other threads preempt us
}
}
}
}
non-blocking algorithm 细节上非常 tricky,还有什么ABA problem。很多算法在业
界还处于试验阶段。据说某些牛级的 Professor, 在发表文章后,经过一段时间依然被
发现算法有bug.
【在 w**n 的大作中提到】 : glassdoor上LinkedIn的题 : 大牛能指点下吗? : 我goog到这个,但是没太看懂 : http://stackoverflow.com/questions/1645326/non-blocking-thread-
|
w**n 发帖数: 122 | 7 你这个跟我goog到的那个很象。
但是我没看太懂
这个CAS是做什么的呢?
if (NULL == compare_and_swap(&tail->next, NULL, node))
如果tail->next是NULL(就说明没有别的thread来改过),然后就把tail->next置成node
? 是这意思吗?
【在 s********r 的大作中提到】 : 大牛不敢。 : 我只是写过一些简单的 non-blocking algorithm。 : 这些 non-blocking 算法是 Multiple-Thread Multiple Data 的编程模式,用于多核 : 系统,但其执行效率与体系结构,尤其是 cache 结构相关。还牵涉到 memory : consistent model。在c++11 中,很多 atomic operation 是为这个准备的。 : 下面的 code 仅仅代表一个思路上的描述: : void enq(Node *queue, T val) : { : Node * node = new node(val); : node->next = NULL;
|
s********r 发帖数: 403 | 8 基本上是这个意思,
CAS 返回本内存地址的 old value, 如果是 NULL,证明当前thread 操作得手
这个是个 atomic, 没有条件判断的先后
node
【在 w**n 的大作中提到】 : 你这个跟我goog到的那个很象。 : 但是我没看太懂 : 这个CAS是做什么的呢? : if (NULL == compare_and_swap(&tail->next, NULL, node)) : 如果tail->next是NULL(就说明没有别的thread来改过),然后就把tail->next置成node : ? 是这意思吗?
|
p*****3 发帖数: 488 | 9 这是哪个贱人出的题目... 太偏了
这个出题的人就是存心不让人过 |
w**n 发帖数: 122 | 10 glassdoor上linkedin这道题出现过很多很多次
估计是他们题库里的?
【在 p*****3 的大作中提到】 : 这是哪个贱人出的题目... 太偏了 : 这个出题的人就是存心不让人过
|
m****i 发帖数: 650 | |
p*****3 发帖数: 488 | 12 queue->settail(node);
Race condition here?? When other thread is reading tail?? |
s********r 发帖数: 403 | 13 That one needs to be an atomic operation,
as the queue->gettail()
【在 p*****3 的大作中提到】 : queue->settail(node); : Race condition here?? When other thread is reading tail??
|