首頁  >  文章  >  Java  >  Java實作cas指令的無鎖程式設計的實例

Java實作cas指令的無鎖程式設計的實例

黄舟
黄舟原創
2017-09-15 11:07:211520瀏覽

這篇文章主要介紹了Java語言中cas指令的無鎖定程式實作實例,具有一定參考價值,需要的朋友可以了解下。

最開始接觸到相關的內容應該是從volatile關鍵字開始的吧,知道它可以保證變數的可見性,而且利用它可以實現讀與寫的原子操作。 。 。但是要實現一些複合的操作volatile就無能為力了。 。 。最典型的代表是遞增和遞減的操作。 。 。 。

我們知道,在並發的環境下,要實現資料的一致性,最簡單的方式就是加鎖,保證在同一時刻只有一個執行緒可以對資料進行操作。 。 。 。例如一個計數器,我們可以用如下的方式來實現:


public class Counter {
  private volatile int a = 0;
  public synchronized int incrAndGet(int number) {
    this.a += number;
    return a;
  } 
  public synchronized int get() {
    return a;
  }
}

我們對操作都用synchronized關鍵字進行修飾,並保證對屬性a的同步存取。 。 。這樣子確實可以保證在並發環境下a的一致性,但是由於使用了鎖,鎖的開銷,線程的調度等等會使得程式的伸縮性受到了限制,於是就有了很多無鎖的實現方式。 。 。 。

其實這些無鎖的方法都利用了處理器所提供的一些CAS(compare and switch)指令,這個CAS到底乾了啥事情呢,可以用下面這個方法來說明CAS所代表的語意:


public synchronized int compareAndSwap(int expect, int newValue) {
    int old = this.a;
    if (old == expect) {
      this.a = newValue;
    }
    return old;
  }

好吧,透過程式碼應該對CAS語意的標書很清楚了吧,好像現在大多數的處理器都實作了原子的CAS指令了吧。 。
好啦,那麼接下來來看看在java中CAS都用在了什麼地方了吧,首先來看AtomicInteger類型吧,這個是並發庫裡面提供的一個類型:


#
private volatile int value;

這個是內部定義的屬性吧,用來保存值,由於是volatile類型的,所以可以保證執行緒之間的可見性以及讀寫的原子性。 。 。
那麼接下來來看看幾個比較常用的方法:


public final int addAndGet(int delta) {
  for (;;) {
    int current = get();
    int next = current + delta;
    if (compareAndSet(current, next))
      return next;
  }
}

這個方法的作用是在目前值的基礎上加上delta,這裡可以看到整個方法中並沒有加鎖,這程式碼其實就算是java中實作無鎖定計數器的方法,這裡compareAndSet方法的定義如下:


public final boolean compareAndSet(int expect, int update) {
  return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

由於呼叫了unsafe的方法,所以這個就無能為力了,其實應該可以猜到JVM呼叫了處理器本身的CAS指令來實現原子的操作。 。 。

基本上AtomicInteger類型的重要方法都是採用無鎖的方式實現的。 。因此在並發環境下,用這種類型能有更好的性能。 。 。
上面算是搞定了在java中實現無鎖的計數器,接下來來看看如何實現無鎖棧,直接貼代碼了,代碼是從《JAVA並發編程實戰》中模仿下來的:


package concurrenttest;
import java.util.concurrent.atomic.AtomicReference;
public class ConcurrentStack<e> {
  AtomicReference<node<e>> top = new AtomicReference<node<e>>();
  public void push(E item) {
    Node<e> newHead = new Node<e>(item);
    Node<e> oldHead;
    while (true) {
      oldHead = top.get();
      newHead.next = oldHead;
      if (top.compareAndSet(oldHead, newHead)) {
        return;
      }
    }
  }
  public E pop() {
    while (true) {
      Node<e> oldHead = top.get();
      if (oldHead == null) {
        return null;
      }
      Node<e> newHead = oldHead.next;
      if (top.compareAndSet(oldHead, newHead)) {
        return oldHead.item;
      }
    }
  }
  private static class Node<e> {
    public final E item;
    public Node<e> next;
     
    public Node(E item) {
      this.item = item;
    }
  }
}

好啦,上面的程式碼就算是實作了一個無鎖的棧,簡單吧。 。 。在並發環境中,無鎖定的資料結構伸縮性能夠比用鎖好得多。 。 。
在提到無鎖定程式設計的時候,就不得不提到無鎖定佇列,其實在concurrent函式庫中已經提供了無鎖定佇列的實作:ConcurrentLinkedQueue,我們來看看它的重要的方法實作吧:


public boolean offer(E e) {
  checkNotNull(e);
  final Node<e> newNode = new Node<e>(e);
  for (Node<e> t = tail, p = t;;) {
    Node<e> q = p.next;
    if (q == null) {
      // p is last node
      if (p.casNext(null, newNode)) {
        // Successful CAS is the linearization point
        // for e to become an element of this queue,
        // and for newNode to become "live".
        if (p != t) // hop two nodes at a time
          casTail(t, newNode); // Failure is OK.
        return true;
      }
      // Lost CAS race to another thread; re-read next
    }
    else if (p == q)
      // We have fallen off list. If tail is unchanged, it
      // will also be off-list, in which case we need to
      // jump to head, from which all live nodes are always
      // reachable. Else the new tail is a better bet.
      p = (t != (t = tail)) ? t : head;
    else
      // Check for tail updates after two hops.
      p = (p != t && t != (t = tail)) ? t : q;
  }
}

這個方法用於在佇列的尾部添加元素,這裡可以看到沒有加鎖,對於具體的無鎖演算法,採用的是Michael-Scott提出的非阻塞鍊錶連結演算法。 。 。具體是怎麼樣子的,可以到《JAVA並發程式設計實戰》去看吧,有比較詳細的介紹。

另外對於其他方法,其實都是採用無鎖的方式實現的。

最後,在實際的程式設計中,在並發環境中最好還是採用這些無鎖的實現,畢竟它的伸縮性更好。

總結

#

以上是Java實作cas指令的無鎖程式設計的實例的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn