java - java - 从引用中窃取位

Question

如何从地址中窃取 2 个 MSB 来执行原子操作？我正在尝试做一个单词 CAS

一个例子

public class Node
{
    long key;
    long value;
    Node lchild; // format is flag1,flag2,address
    Node rchild; // format is flag1,flag2,address
}

public void createNode()
{
    Node n1 = new Node(); //this should create a node with format 0,0,address1
}

public void setFlag1(Node n1)
{
    Now the new address should be in format 1,0,address1
}

public void setFlag2(Node n1)
{
    Now the new address should be in format 0,1,address1
}

AtomicReference如果我只需要一个额外的标志，可以使用。 AtomicStampedReference可以使用，但效率不高，因为它创建了一个包含时间戳和参考的额外框。

C 语言中的一个类似问题在从指针中窃取位时进行了讨论

score 4 · Accepted Answer

您可能可以使用 sun.misc.Unsafe 来实现它

http://www.docjar.com/docs/api/sun/misc/Unsafe.html

除其他外，它有许多compareAndSwap方法可以处理任何对象中的任意二进制数据。

话虽如此，如果您正在实现二叉搜索树，我建议您查看不可变的持久数据结构。这些优点包括：

由于不可变性，它们根据定义是线程安全的
他们不需要锁
一旦你开始做更复杂的事情（例如，子树的快照），进行结构共享的能力将是一个巨大的性能胜利——基本上你避免了获取防御性副本的需要。

score 3 · Accepted Answer

如果不实现您自己的支持此类操作并正确处理标志位的 JVM，这是不可能的，例如在进行 GC 时（此时需要识别所有引用并且移动收集器需要更改它们）。即使这样，这也违反了 Java 的设计原则，其中不包括显式取消引用或指针算法（我会计算引用中的更改位并屏蔽它们以进行取消引用）。

相反，我建议您创建一个新的混合 Edge 类型的标志和节点：

public class Node {
    long key;
    long value;
    Child lchild; // child = node reference + flags
    Child rchild;
}

// this is the edge type which should also be used to reference the root node with flags
public class Child {
    Node child;
    BitSet flags;

    public Child(Node node) {
        this.child = node;
        this.flags = new BitSet(2); // we initialize the flags with 00
    }
    public void setFlag(int index) {
        this.flags.set(index); // index would be 0 or 1 here for the two flags
    }
    public boolean isFlagSet(int index) {
        return this.flags.get(index); // index would be 0 or 1 here for the two flags
    }
}

score 1 · Accepted Answer

复制Maurice Herlihy 和 Nir Shavit所著《多处理器编程的艺术》第 215 页的摘录：

如 Pragma 9.8.1 中详细描述的，AtomicMarkableReference 对象封装了对 T 类型对象的引用和布尔标记。这些字段可以一起或单独进行原子更新。我们将每个节点的下一个字段设为 AtomicMarkableReference。线程 A 通过在节点的下一个字段中设置标记位来逻辑删除 currA，并与执行 add() 或 remove() 的其他线程共享物理删除：当每个线程遍历列表时，它通过物理删除（使用compareAndSet()) 它遇到的任何标记节点。换句话说，执行 add() 和 remove() 的线程不会遍历标记的节点，它们会在继续之前删除它们。contains() 方法与 LazyList 算法中保持一致，遍历所有节点，无论它们是否被标记，

score 0 · Accepted Answer

要从可用于对象引用变量的那些中提取位，需要创建您自己的 JVM。

您首先必须确保这些位未被实际使用（例如，当 JVM 总是在 16 字节边界上对齐对象时，通过获取引用中的低位位）。但是一些 JVM 使用 32 位引用的所有位。

接下来，您必须在每次加载引用时注入代码以在访问关联对象之前清除这些位。

然后你必须对垃圾收集器做同样的事情。

score 0 · Accepted Answer

对于在 Java 中工作，我能给你的最好建议是在数组索引而不是地址上进行位操作，因为 Java 不公开地址。

score -1 · Accepted Answer

不允许从引用中窃取位，但有一种解决方法：您可以使用 AtomicStampedReference，它允许您进行比较和交换以原子更新引用和整数。您可以将整数用作状态，也可以根据需要从整数的 MSB 中窃取位。你可以在java中对整数进行位运算，这很酷：

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

我最终编写了一个 java 程序，我从 AtomicStampedReference 的整数中窃取了 2 位并将它们用作状态位，并将整数的剩余 30 位用作计数器以防止 ABA 问题。

java - java - 从引用中窃取位

6 回答 6

Related

Reference