java – 这是(无锁)队列实现线程安全吗?

前端之家收集整理的这篇文章主要介绍了java – 这是(无锁)队列实现线程安全吗?前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
我试图在 Java中创建一个无锁队列的实现,主要用于个人学习.队列应该是一个通用的队列,允许任意数量的读者和/或作者同时进行.

你能否回顾一下,并提出任何改进/问题你找到?

谢谢.

  1. import java.util.concurrent.atomic.AtomicReference;
  2.  
  3. public class LockFreeQueue<T> {
  4. private static class Node<E> {
  5. E value;
  6. volatile Node<E> next;
  7.  
  8. Node(E value) {
  9. this.value = value;
  10. }
  11. }
  12.  
  13. private AtomicReference<Node<T>> head,tail;
  14.  
  15. public LockFreeQueue() {
  16. // have both head and tail point to a dummy node
  17. Node<T> dummyNode = new Node<T>(null);
  18. head = new AtomicReference<Node<T>>(dummyNode);
  19. tail = new AtomicReference<Node<T>>(dummyNode);
  20. }
  21.  
  22. /**
  23. * Puts an object at the end of the queue.
  24. */
  25. public void putObject(T value) {
  26. Node<T> newNode = new Node<T>(value);
  27. Node<T> prevTailNode = tail.getAndSet(newNode);
  28. prevTailNode.next = newNode;
  29. }
  30.  
  31. /**
  32. * Gets an object from the beginning of the queue. The object is removed
  33. * from the queue. If there are no objects in the queue,returns null.
  34. */
  35. public T getObject() {
  36. Node<T> headNode,valueNode;
  37.  
  38. // move head node to the next node using atomic semantics
  39. // as long as next node is not null
  40. do {
  41. headNode = head.get();
  42. valueNode = headNode.next;
  43. // try until the whole loop executes pseudo-atomically
  44. // (i.e. unaffected by modifications done by other threads)
  45. } while (valueNode != null && !head.compareAndSet(headNode,valueNode));
  46.  
  47. T value = (valueNode != null ? valueNode.value : null);
  48.  
  49. // release the value pointed to by head,keeping the head node dummy
  50. if (valueNode != null)
  51. valueNode.value = null;
  52.  
  53. return value;
  54. }

解决方法

代码不是线程安全的.考虑putObject(…):
  1. public void putObject(T value) {
  2. Node<T> newNode = new Node<T>(value);
  3. Node<T> prevTailNode = tail.getAndSet(newNode);
  4. prevTailNode.next = newNode;
  5. }

第二个语句在前一个节点的下一个指针设置之前添加新节点.这只发生在第三个声明中.因此,有一个窗口,其中下一个是null;即比赛条件.

即使你固定下来,还有一个比较阴险的问题.读取Node对象的下一个字段的线程不一定会看到第二个线程刚刚写入的值.这是Java内存模型的结果.在这种情况下,确保以下读取始终看到较早的书面值的方法是:

>声明为volatile,或
>在相同对象上的原始互斥体中进行读写操作.

编辑:在更详细地阅读getObject()和putObject()的代码时,我可以看到没有什么强制下一个的非空值在putObject中被刷新到内存,没有任何强制getObject从主内存中读取.所以getObject代码可以看到下一个错误的值,导致它在队列中真的有一个元素时返回null.

猜你在找的Java相关文章