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??
|
