Java - Как реализовать разбиение бит по ссылкам

Question

Когда речь заходит об алгоритмах блокировки свободных или ожидающих данных структур, некоторые алгоритмы украдут 2 младших значащих бита из указателя, поскольку они не используются, и используют их как статус бит (например, если узел логически удален или что-то еще). Я понял, что в java, я бы просто использовал AtomicStampedReference вместо того, чтобы красть бит. Однако я понял, что единственный способ решить проблему ABA в java - использовать AtomicStampedReference, чтобы отслеживать, был ли изменен узел или нет.

ПРИМЕЧАНИЕ: Если your'e не уверен, что проблема ABA есть, википедия дает прекрасный пример, объясняющий, как плохо все портится, на него: https://en.wikipedia.org/wiki/ABA_problem

Примечание: Причина, я говорю единственный способ решить проблема ABA является использование AtomicStampedReference основано на этом посту: http://tutorials.jenkov.com/java-util-concurrent/atomicstampedreference.html#atomicstampedreference-and-the-a-b-a-problem

Так, так как я не могу использовать целое число в атомной штампованной ссылке отслеживать такие вещи, как логическое удаление больше, есть способ, которым я может украсть неиспользуемые биты в самой ссылке? Я пытался получить доступ к «небезопасный» пакет, чтобы сделать эту задачу по телефону:

import sun.misc.Unsafe; 

Но когда я делаю это, я получаю следующее сообщение об ошибке из Eclipse:

Ограничение доступа: Тип небезопасный не доступен из-за ограничения на требуемую библиотеку C: \ Program Files \ Java \ jre1.8.0_40 \ lib \ rt.jar

У кого-нибудь есть идеи? Если вам любопытно, что я пытаюсь сделать, я пытаюсь реализовать поточный безопасный блокирующий хэш-файл в Java как школьный проект. И мне нужно использовать 2 бита LSB, чтобы различать 3 разных типа узлов: узел данных (00), выделенный узел данных (01) или узел массива (10)

EDIT: Следует упомянуть, Мне нужно, чтобы 2 бита состояния находились внутри атомной ссылки. Причина, по которой мне это нужно, - это то, что я буду выполнять операции сравнения и свопинга, и мне нужно сравнить и сменить, если узел данных (00) будет помечен (01) или преобразован в arrayNode (10). Первоначально я использовал целое число в AtomicStampedReference для этого, но я больше не могу этого делать, поскольку AtomicStampedReference следует зарезервировать для предотвращения проблем, вызванных ABA.

Answer 1

Хорошо, так что невозможно украсть биты из ссылок на Java, но я закончил красть биты от ссылки с меткой с меткой. Я украл 2 бита MSB из целочисленного штампа, который будет использоваться в качестве бит состояния, и я использовал оставшиеся 30 бит в целых числах в качестве счетчика.Я могу сделать это, так как Java позволяет выполнять битовые операции над целыми числами:

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

я реализовал и проверил это в моем Java параллельного кода HashMap. Это решает проблему ABA и позволяет мне отслеживать, указывает ли ссылка на узел, отмеченный узел или arraynode.

Благодарим вас за тип_outcast за то, что вы сделали предложение о краже битов из целого числа AtomicStampedReference!

EDIT Я думаю, что я выложу функции, которые я написал, чтобы использовать нижние 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; 
} 

Answer 2

AFAIK, нет возможности украсть эти 2 бита в Java.

Тем не менее, при написании структур данных без блокировки в Java проблема с ABA обычно решается просто не путем повторного использования объектов. Каждый раз, когда вы меняете ссылку на атом, вы устанавливаете его на новый объект и просто бросаете старый. Сборщик мусора гарантирует, что новый объект не будет создан по тому же адресу, что и старый, до тех пор, пока он не станет безопасным, и не вызовет проблем с ABA.

Для таких вещей, как маркировка узлов, вы можете иметь опорную точку атома в промежуточном классе-оболочке, который просто содержит ссылку на ваш узел. Затем CAS с новой оболочкой с другим конкретным типом, чтобы изменить знак. (например, DataNodeWrapper -> MarkedNodeWrapper). Снова, каждый раз, когда вы меняете атомную ссылку, бросайте старую обертку, чтобы она не вызывала у вас никакого горя.