09.非ブロッキング同期

渋滞解消アルゴリズム
非ブロッキングアルゴリズムは,一次原子機械命令をラッチの代わりに使用して,同時アクセスにおけるデータの整合性を確保した.非ブロッキングアルゴリズムは、OSおよびJVMにおいて、スレッド、プロセススケジュールメカニズム、ゴミ回収メカニズム、およびロックおよび他の同時構造を実現するために広く使われている.

非ブロッキング同期方式と同期方式とを比較して、複数のスレッドが同じデータを競争している間にブロッキングが発生しないようにすることができ、(本質的には原子命令に基づくポーリングが安全である)ので、スケジュールのオーバーヘッドを低減するために、より細かい粒度のレベルで調整することができる.非ブロッキングアルゴリズムには,デッドロックなどの活性化問題は存在しない.

ロックの同期機構に基づいて使用されるのはシステムの反発量であり、ロックが解除される前に、このロックが必要とされるスレッドはすべて待ち続けなければならない(ブロックまたはスピン待ち).
CAS
比較と交換はプロセッサが提供する原子操作命令であり、メモリユニットアクセスの相互反発性を利用して、マルチプロセッサシステムでは依然として原子性を保証できます.すなわち同時に実行できないで、一つの命令周期が完成して、中断できません.このコマンドは同時に安全です.CASの機能は以下のコード表現を使用できます.

int compare_and_swap(int *word,int testval,int newval){
    int oldval;
    oldval = *word;
    if(oldval == testval){
        *word =newval;
    }
    return oldval;
}

CASは、更新動作を成功的に実行したいという楽観的な技術であり、他のスレッドが最近変数を更新したら検出できる.複数のスレッドがCASを使用して同じ変数を同時に更新する場合、一つのスレッドだけが実行に成功し、他のスレッドは失敗し、失敗したスレッドはブロックされず、更新されたと判断して、いくつかの回復動作を再試行または実行することができる.渋滞の原因にもなりません.デッドロックなどの活動的な問題にもなりません.
CASの性能
CASの性能はプロセッサの数によって大きく変化します.単一CPUのシステムでは、CASは通常、少ないクロック周期であり、プロセッサ間の同期が不要であるため、マルチCPUのシステムでは、プロセッサ間で同期制御が必要であるため、クロック周期が比較的多くなり、オーバーヘッドも比較的高いです.
経験的な法則:ほとんどのプロセッサでは、競合しないロック取得および解放された「高速コードパス」上のオーバーヘッドは、CASの約2倍である.
JVMのCASへのサポート
Java 5の前に、明確なコードを作成しないとCASは実行できません.Java 5は下の層に対するサポートを導入し、int、longおよび引用の上でCAS操作を公開し、jvmは彼らを下の層のハードウェアに集約して提供する最も効果的な方法を提供する.CAS対応プラットフォームでは、運転時に対応するマシンコマンドをコンパイルします.サポートしない場合はJVMはスピンロックを使用します.Java 5に導入された原子変数類は、CASを使用して、java.util.co ncurrentカバンの多くの種類にこれらの原子類を使用しています.Java 1.6のロック最適化技術では、ロックと軽量級ロックに使用されるCASアルゴリズムを偏向してロックの性能を最適化する.

原子変数クラスに基づいて非ブロッキングスタックを実現する

public class ConcurrentStack{
    AtomicReference> top = new AtomicReference<>();
    public void push(E e){
        Node newHead = new Node(e);
        Node oldHead;
        do{
            oldHead = top.get();
            newHead.next = oldHead;
        }while(!top.compareAndSet(oldHead,newHead));

    }

    public Node pop(){
        Node oldHead；
        Node newHead；
        do{
            oldHead= top.get();
            if(oldHead == null)
                return null;
            newHead = oldHead.next;
        while (!top.compareAndSet(oldHead,newHead));
        return oldHead.item;
        }
    }

    private class Node{
        public final E item;
        public Node next;
        public Node(E item){
            this.item = item;
        }
    }
}

compreAndSetの実現擬似コード:

public synchronized boolean compareAndSet(int expectVal,int newVal){
    return (expectVal == compareAndSwap(expectVal,newVal));
}

コンカレント・ステージは、コンカレント・セキュリティを保証します.compreAndSetは原子性と視認性を保証します.このクラスでは、唯一の共有変数の場合topは、スレッドがスタックの状態を変更する必要があるときに、compreAndSet方法を呼び出し、この方法はvolatile変数に書き込まれたものと同じ意味を持つ.
参考資料
[1]Java同時プログラミングの実戦