Lock Free实现队列中针对pop()方法的疑问

来源：5-12 无锁境之给面试官讲讲无锁编程(Lock-Free Programming)(下)

hllcve

2021-06-23

public T pop() {
    while (true) {
        int stamp = head.getStamp();
        Node<T> ref = head.getReference();
        if (ref.next == null) {
            return null;
        }
        var next = ref.next;
        head.compareAndSet(ref, next, stamp, stamp + 1);
        return ref.value;
    }
}

head.compareAndSet(ref, next, stamp, stamp + 1);，这行代码也有可能CAS失败，CAS失败说明有别的线程操作了已经把头节点换掉了，这时这个pop操作就失败了，那为什么不像push那样CAS成功后在进行return？

if (head.compareAndSet(ref, next, stamp, stamp + 1)) {
    return;
}

写回答

2回答

求老仙

2021-06-24

已采纳

诶，这是我提供的代码嘛

hllcve

非常感谢！

2021-08-03

共2条回复

求老仙

2021-07-14

仔细看了，不是我的笔误，真的写错了，代码已经提交：

    public T pop(){
        while (true) {
            int stamp = head.getStamp();
            Node<T> ref = head.getReference();
            if(ref.next == null) {
                return null;
            }
            var next = ref.next;
            if( head.compareAndSet(ref, next, stamp, stamp+1) ) {
                return ref.value;
            }
        }
    }

当然造成这个问题的原因深入反思是测试用例写错了，这是更新过的测试用例：

    @Test
    public void testMultiThreads() throws InterruptedException {
        var stack = new LockFreeStack<Integer>();
        var list = IntStream.range(0, 16)
                .mapToObj(i -> {
                    var t = new Thread(() -> {
                        System.out.println(Thread.currentThread().getId());
                        for (int j = 0; j < 100; j++) {
                            try {
                                stack.push(j);
                                Thread.sleep(1);
                                stack.push(j);
                                Thread.sleep(1);
                                stack.pop();
                                Thread.sleep(1);
                            } catch (InterruptedException e) {
                                e.printStackTrace();
                            }
                        }
                    });
                    t.start();
                    return t;
                }).collect(Collectors.toList());
            list.forEach(t -> {
                    System.out.println("wait join..");
                    try {
                        t.join();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                });
        Integer c = 0;
        while(stack.pop() != null) {
            c ++;
        }
        assertEquals(c+"", "1600");
    }

莫失聪聪3779259

原来这个地方真是错了，我说昨晚看这个地方看半天怎么没看懂，就想这个地方应该加个if。

2021-08-10

共1条回复

笑傲Java面试剖析大厂高频面试真题秒变offer收割机

深度剖析大厂面试高频真题，让你秒变offer收割机

1783 学习 · 314 问题

查看课程

相似问题

自旋锁是不是Lock Free?

回答 1

关于AQS中队列