Java

Question

当谈到无锁/无等待数据结构的算法时，一些算法会从指针中窃取 2 个最低有效位，因为它们没有被使用，并将它们用作状态位（比如如果一个节点是逻辑上删除或其他东西）。我认为在 java 中，我只使用 AtomicStampedReference 而不是窃取位。但是，我意识到解决 java 中的 ABA 问题的唯一方法是使用 AtomicStampedReference 来跟踪节点是否已更改。

注意：如果您不确定 ABA 问题是什么，维基百科给出了一个很好的例子来解释它把事情搞砸的程度： https://en.wikipedia.org/wiki/ABA_problem

注意：我说解决 ABA 问题的唯一方法是使用 AtomicStampedReference 的原因是基于此 post： http://tutorials.jenkov.com/java-util-concurrent/atomicstampedreference.html#atomicstampedreference-and-the-a-b-a-problem

所以，既然我不能再使用原子标记引用中的整数来跟踪逻辑删除之类的事情，有没有办法可以窃取引用本身中未使用的位？我试图通过调用访问 "unsafe" 包来完成此任务：

import sun.misc.Unsafe;

但是当我这样做时，我从 Eclipse 中收到以下错误：

访问限制：由于所需库 C:\Program Files\Java\jre1.8.0_40\lib\rt.jar

的限制，无法访问类型 Unsafe

有人有什么想法吗？如果您对我正在尝试做的事情感到好奇，我正在尝试将 java 中的线程安全无锁哈希映射作为一个学校项目来实现。我需要使用 2 个 LSB 位来区分 3 种不同的节点类型：数据节点 (00)、标记数据节点 (01) 或数组节点 (10)

编辑：我应该提一下，我需要将 2 个状态位放在原子引用中。我需要这个的原因是因为我将要进行比较和交换操作，如果数据节点 (00) 被标记为 (01) 或变成数组节点 (10)，我需要比较和交换失败。我最初为此使用了 AtomicStampedReference 中的整数，但我不能再这样做了，因为应该保留 AtomicStampedReference 以防止 ABA 引起的问题。

Answer 1

AFAIK，无法窃取 Java 中的那 2 位。

然而，在Java中编写无锁数据结构时，ABA问题通常只是通过不重用对象来解决。每次更改原子引用时，都会将其设置为一个新对象，然后将旧对象丢弃。垃圾收集器保证不会在与旧对象相同的地址创建新对象，直到这样做是安全的并且不会导致 ABA 问题。

对于节点标记之类的事情，您可以将原子引用指向中间包装器 class，它只包含对您的节点的引用。然后 CAS 到具有不同具体类型的新包装器以更改标记。（例如，DataNodeWrapper -> MarkedNodeWrapper）同样，每次更改原子引用时，将旧的包装器扔掉，这样它就不会给您带来任何 ABA 麻烦。

Answer 2

好的，所以不可能从 Java 中的引用中窃取位，但我最终从原子标记引用中窃取了位。我从整数标记中窃取了 2 个 MSB 位用作状态位，并将整数中剩余的 30 位用作计数器。我可以这样做，因为 java 允许您对整数进行位运算：

https://docs.oracle.com/javase/tutorial/java/nutsandbolts/op3.html

我在 java 并发哈希映射代码中实现并测试了它。这解决了 ABA 问题，并且仍然允许我跟踪引用是指向节点、标记节点还是数组节点。

感谢您type_outcast提出从 AtomicStampedReference 的整数中窃取位的建议！

编辑我想我会 post 我写的函数，使用整数的低 30 位作为计数器，高 2 位作为标志。这些函数将 AtomicStampedReference 的整数作为输入，输出取决于函数。希望对有类似情况的朋友有所帮助

//get the incremented counter without messing up the mask bits
//if already at highest value (2^30 - 1, or 1073741823, reset to 0)
private int custInc(int rawStamp){
    int markedBits = 0xC0000000 & rawStamp;
    if (getUnmarkedStamp(rawStamp) == 1073741823)
        return (0 | markedBits);
    else 
        return ((rawStamp + 1) | markedBits);
}

//get the stamp value without the marked bits
private int getUnmarkedStamp(int rawStamp){
    int stampMask = 0x3FFFFFFF;
    return stampMask & rawStamp;
}


//call this to determine if the AtomicStampedReference is pointing to an array node
//10XXXXX... indicates arrayNode;
//01XXXXX... indicates marked data node
//00XXXXX... indicates a normal data node
private boolean isStampArrayNode(int rawStamp){
    int isArrayNodeMask = 0xC0000000;
    if ((isArrayNodeMask & rawStamp) == 0x80000000)
        return true;
    else 
        return false;               
}

//call this to determine if the AtomicStampedReference is pointing to an marked data node
//10XXXXX... indicates arrayNode;
//01XXXXX... indicates marked data node
//00XXXXX... indicates a normal data node
private boolean isStampMarkedDataNode(int rawStamp){
    int isArrayNodeMask = 0xC0000000;
    if ((isArrayNodeMask & rawStamp) == 0x40000000)
        return true;
    else 
        return false;               
}

//call this to get what the raw stamp value if you are to mark it as a marked data node
//01XXXXX... indicates marked data node.ensure that this is returned
private int getStampMarkedAsDataNode(int rawStamp){
    return (rawStamp | 0x40000000) & 0x7FFFFFFF;
}

//call this to get what the raw stamp value if you are to mark it as an array node
//10XXXXX... indicates arrayNode;
private int getStampMarkedAsArrayNode(int rawStamp){
    return (rawStamp | 0x80000000) & 0xBFFFFFFF;
}

Java - 如何从引用中窃取位

Java - How to implement bit stealing from references

multithreading

lock-free

pointer-arithmetic