鎖定自由數組元素交換

Question

在多線程環境中，爲了使線程安全的數組元素交換，我們將執行同步鎖定。

// a is char array. 
synchronized(a) { 
    char tmp = a[1]; 
    a[1] = a[0]; 
    a[0] = tmp; 
} 

是否有可能，我們可以利用下面的API的上述情況，這樣我們就可以有一個鎖定免費數組元素交換？如果是，如何？

http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.html#compareAndSet%28T,%20V,%20V%29

Answer 1

無論使用哪種API，您都無法在Java中實現線程安全和無鎖數組元素交換。

元素交換需要多個讀取和更新操作，需要以原子方式執行。爲了模擬你需要一個鎖的原子性。

編輯：

一種替代以鎖定自由算法可能是微鎖定：不是鎖定整個陣列有可能僅鎖定正在交換元件。

這種方法的價值完全值得懷疑。也就是說，如果需要交換元素的算法可以保證不同的線程能夠在陣列的不同部分上工作，那麼就不需要同步。

在相反的情況下，當不同的線程實際上可以嘗試交換重疊的元素時，線程執行順序將很重要。例如，如果一個線程試圖交換數組中的元素0和1，而另一個線程同時嘗試交換1和2，那麼結果將完全取決於執行順序，對於初始{'a'，'b'，'c '}您可以以{'b'，'c'，'a'}或{'c'，'a'，'b'}結束。因此你需要更復雜的同步。

這裏是字符數組的一個快速和骯髒的類，它實現微鎖：

import java.util.concurrent.atomic.AtomicIntegerArray; 

class SyncCharArray { 

    final private char array []; 
    final private AtomicIntegerArray locktable; 

    SyncCharArray (char array[]) 
    { 
     this.array = array; 

     // create a lock table the size of the array 
     // to track currently locked elements 
     this.locktable = new AtomicIntegerArray(array.length); 
     for (int i = 0;i<array.length;i++) unlock(i); 

    } 

    void swap (int idx1, int idx2) 
    { 
     // return if the same element 
     if (idx1==idx2) return; 

     // lock element with the smaller index first to avoid possible deadlock 
     lock(Math.min(idx1,idx2)); 
     lock(Math.max(idx1,idx2)); 

     char tmp = array[idx1]; 
     array [idx1] = array[idx2]; 
     unlock(idx1); 
     array[idx2] = tmp; 
     unlock(idx2); 

    } 

    private void lock (int idx) 
    { 
     // if required element is locked when wait ... 
     while (!locktable.compareAndSet(idx,0,1)) Thread.yield(); 
    } 

    private void unlock (int idx) 
    { 
     locktable.set(idx,0); 
    } 

} 

你需要創建SyncCharArray，然後把它傳遞給需要交換的所有主題：

char array [] = {'a','b','c','d','e','f'}; 
SyncCharArray sca = new SyncCharArray(array); 

// then pass sca to any threads that require swapping 
// then within a thread 

sca.swap(15,3); 

希望有一定道理。

UPDATE：

一些測試表明，除非你有訪問數組simulteniously（100+上運行的設施，工廠硬件）一個簡單的同步（陣列）的線程大量{}工作快得多比精巧的同步。

Answer 2

我不認爲AtomicReferenceFieldUpdater是爲數組訪問，即使它是，它只是提供了一次在一個參考原子的保證。 AFAIK中，java.util.concurrent.atomic中的所有類一次只能提供對一個引用的原子訪問權限。爲了將兩個或多個引用更改爲一個原子操作，您必須使用某種鎖定。

Answer 3

最接近你會得到的是java.util.concurrent.atomic.AtomicReferenceArray，它提供了基於CAS的操作，如boolean compareAndSet(int i, E expect, E update)。它沒有swap(int pos1, int pos2)操作，但您必須用兩個compareAndSet調用來模擬它。

Answer 4

「併發應用程序中可擴展性的主要威脅是獨佔資源鎖定。」 - 實踐中的Java併發。

我認爲你需要一個鎖，但正如其他人提到鎖可以比目前更細粒度。

您可以像java.util.concurrent.ConcurrentHashMap一樣使用鎖條。

Answer 5

您提到的API，如其他人所述，只能用於設置單個對象的值，而不是數組。即使對於兩個物體同時，也不會有安全的交換。

解決方案取決於您的具體情況。數組可以被另一個數據結構替換嗎？它是否也在同時變化？

如果您必須使用數組，則可以將其更改爲包含可更新對象（不是基元類型，也不是Char），並通過交換進行同步。像這樣的S路數據結構，將工作：

public class CharValue { 
    public char c; 
} 

CharValue[] a = new CharValue[N]; 

記得使用確定性的同步爲了不具有死鎖（http://en.wikipedia.org/wiki/Deadlock#Circular_wait_prevention）！你可以簡單地遵循索引排序來避免它。

如果還應該從集合中同時添加或刪除項目，您可以改用Map，同步Map.Entry的交換並使用同步的Map實現。一個簡單的List不會這樣做，因爲沒有保留值的隔離結構（或者您無權訪問它們）。

Answer 6

// lock-free swap array[i] and array[j] (assumes array contains not null elements only) 
    static <T> void swap(AtomicReferenceArray<T> array, int i, int j) { 
    while (true) { 
     T ai = array.getAndSet(i, null); 
     if (ai == null) continue; 
     T aj = array.getAndSet(j, null); 
     if (aj == null) { 
     array.set(i, ai); 
     continue; 
     } 
     array.set(i, aj); 
     array.set(j, ai); 
     break; 
    } 
    }