我正在嘗試創建一個并發資料結構，它允許一個執行緒在另一個執行緒寫入它時從中輪詢隨機元素。
public class SomeList<E> extends CopyOnWriteArrayList<E> {
private final Random random = new Random();
public E pollRandom() {
if (size() == 0) {
throw new NoSuchElementException();
}
return remove(random.nextInt(size()));
}
}
我擔心的是：在極端情況下，例如，在執行緒 A 呼叫size()(in pollRandom()) 之后，執行緒 B 洗掉最后一個元素。不幸的是，隨機索引恰好是最后一個元素（已被洗掉）的索引。因此，remove()呼叫將拋出一個未捕獲的IndexOutOfBoundsException. 這是我沒想到的 -pollRandom()呼叫失敗，即使此串列中仍有元素。
所以我想問：我的擔心是真的嗎？也許我誤解了CopyOnWriteArrayList（或任何其他型別的并發串列）實際上是做什么的？如果我的擔憂是真實的，有沒有辦法解決問題？我不想添加synchronized到所有方法中，因為添加synchronized會使性能變得更糟。
如果有人愿意回答這個問題，我會很高興。我的英語不好，如果我的表達聽起來含糊或不禮貌，請告訴我，謝謝:)
PS：我知道CopyOnWriteArrayList所有可變操作都很慢，因為它每次都需要完整的副本，感謝@Boris the Spider。它可以是任何型別的并發串列。這里只是一個例子。
uj5u.com熱心網友回復：
COW 串列的作業原理如下：
- 它有一個相關欄位，即
Object[]，包含串列中的元素。 - 任何呼叫變異（所以
clear，add，addAll，remove，等等）將復制內部陣列，突變適用于復制，然后將其領域這一新的陣列。鑒于 java 的作業方式，“舊”陣列仍然存在，該欄位只是一個指標。 - 值得注意的是，任何迭代器（
for (Foo f : theCowList)是制作一個迭代器的一種方式）都復制了“指標”，這意味著任何現有的迭代器都會繼續運行。他們不會涵蓋您添加的任何內容。它們將涵蓋您洗掉的任何內容 - 由 cowList 制作的迭代器將遍歷所有元素，就像您制作迭代器時一樣，無論您之后執行任何更改。這就是 COWList 的“點”。如果您不需要該功能，則 COWList 不太可能是適合您的型別。
COWList 本質上是原子的，對于任何單個呼叫都是安全的。然而，你的操作是三個電話：size()然后indexOf和size()試。這里不能保證原子性。你的擔心是有道理的。
一般心態更新
您正在做的是所謂的“檢查然后行動”：您檢查物件的狀態（它是否為空？），然后您決定如何行動。
在并發領域這是錯誤的做法。正確的模型是先行動再檢查：假設天氣晴朗，執行行動，然后對無效狀態做出反應。這也意味著它需要的“行為”的一部分做檢查本質。如果沒有這樣的內部操作可用，則兩種模型都不起作用，這就是重點：在這種情況下，您必須找到一種方法來注入同步，否則該操作不可能在并發操作中安全地進行。示例：“如果元素不在串列中，則添加該元素”在普通 jane 中以并發方式是不可能的ArrayList。
處理并發時的第二個重要認識是，如果您想將并發檢查轉移到物件本身，那么與該物件進行互動的唯一安全方法就是單次呼叫。您正在撥打 3 個電話。不好。你只得到一個。
這是一個可以在這里作業的不同操作的示例：假設您有一個方法從串列中洗掉第一項，NSElemEx如果串列為空則拋出。
你的“風格”會這樣寫：
public E pollFirst() {
// This code is wrong! do not use!
if (isEmpty()) throw new NoSuchElementException();
return remove(0);
}
這是錯誤的 - 您混淆了 2 個電話。你只能得到一個。這是正確的方法：
public E pollFirst() {
try {
return remove(0);
} catch (ArrayIndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
注意我們首先是如何做的，假設天氣晴朗：我們只是洗掉第 0 個元素，一開始不知道是否有這樣的元素。如果失敗，我們對失敗做出反應（如果你呼叫remove(0)一個空的 COWList，一個 ArrayIndexOutOfBoundsException 出現，我們在這里做出反應）。
那么我們該怎么做呢？
不幸的答案是，不可能- COWList 沒有一個可以執行您想要的操作的呼叫，因此，您已經死在水中了。COWList承諾一定的并發安全性；要做到這一點，它有一個名為lock. 諸如remove(int index)獲取此鎖之類的操作將導致任何執行緒（例如）也呼叫remove凍結，直到第一個執行緒完成。
您不能使用此鎖。這會導致各種問題。我們只是停留在這一點上，我們需要首先回傳并糾正您犯下的一系列樣式錯誤。
優先組合而不是繼承
您已決定擴展 COWList。這意味著您是說物件的任何實體在所有方面都像 COWList 一樣，并在此基礎上提供其他功能。問題是， COWList 和你想要的不一致。特別是，為了符合“你是一個 COWList 與額外的螺栓”的想法，你需要復制它的鎖定行為：你抓取隨機元素的操作需要鎖定其他執行緒，因為 COWList 作為一個 impl 根本不不提供您需要在沒有鎖的情況下執行此操作的 API，但您實際上看不到鎖，這意味著您無法執行此操作。
The real problem, though, is that you really do not want to be 'a COWList with additional functionality'. That as a concept is rarely a good idea: COWList is already a complex beast, thus anything that is by definition 'a COWList with addons' is even more complicated. Forget COWList, what you want is much simpler: A datastructure to which you can add things concurrently and grab (concurrency-safe) random elements from it. That's all you want. Why bring COWList's rules into it? You're using COWlist here because it's convenient - most of the work is done for you. That's great, but, don't 'expose' that. Keep implementation details internalized. Thus, write it like so:
public class SomeList<E> extends AbstractList<E> {
private final CopyOnWriteArrayList<E> list = new CopyOnWriteArrayList<E>();
}
Here you just adopt the rules of List itself, but given that your type is named SomeList, I assume you intentionally want that. The mental 'load' of what AbstractList enforces is vastly simpler than what COWList enforces. Now you merely implement all methods you need to, usually as one-liners that just farm out the work to your COWList.
Now we're at least closer to doing it right: You can now make your own lock object or just define in the docs that all operations synchronize on the SomeList instance itself (which means you just add the synchronized keyword to every method - that's shorthand for wrapping the entire method body in synchronized (this) { body-goes-here }.
Sticking a field in a class and implementing many methods as one-liners that just invoke a similar method on said field is called composition, vs adding an extends clause and letting it serve as implementation for most of the methods you intend to expose, which is called inheritance. Prefer composition over inheritance.
Now that you're taking care of the synchronizing on your own, there is absolutely no need for COWList anymore. That inner list can just become a plain jane ArrayList. Much more efficient.
Efficiency
"Just synchronize on all the things" is a bit of a cop-out. synchronized (x) { ... } simply means that only one thread can be in such a block for any given x. Just 'blocking' threads is the easy way out. A really cool datastructure would do some or all of the work without holding the lock. Separately, 'remove item from the middle of a large arraylist' is a slow operation (because all elements that follow must be copied over to one slot earlier; arraylist fundamentally works as a continuous set of elements, hence why removing one in the middle is so pricey).
Thus, even the 'fixed' case of using composition over inheritance is quite inefficient: It uses locks (ouch), and removes elements from the middle of arraylists (double ouch).
Making concurrency-safe data structures that are still fast require three things:
[1] It is quite an artform. You need to come up with very creative ideas.
[2] It's trade-offs, so be sure to be very specific in what you data structure can and cannot do. You often end up with datastructures that take up (way) more space in memory in order to allow lock-free access. Also often seemingly simple operations such as 'how many elements are in you' are impossible to efficiently answer, so don't offer that functionality. There's a reason the java.util.concurrent package has so many classes in it: There is no god-class that can do it all and do it efficiently in both memory, CPU, and lock aspects.
[3] Be clear in the difference between 'trends' and 'guarantees'. For example, it's much easier to write a fast, efficient system that can give you (and remove) a random element from a humongous list of elements that 'trends towards' picking fairly from the bunch, vs. one that guarantees that it is exactly uniformly randomly chosen every time.
Part of the art is to know when you can make do with a trend instead of a guarantee, usually orders-of-magnitude speedups lie in such realizations.
Here are some ideas on how to make hypothetically really fast ones:
Do you add everything, and then you 'switch the mode' and never add another element again, instead only removing from there on out?
If that's the case, a much faster idea:
Have one object that is 'modal'. It starts out with just having an add method (and possibly addAll). Nothing else. Not even .get (don't add API you don't need, it only limits your flexibility when trying to optimize things!). It doesn't even promise concurrency-safe behaviour (calling add from 2 threads simultaneously will fail disastrously at times). When 'done', you call a build() method. This returns a new object that ONLY has poll() method that returns an arbitrary element in a concurrency-safe fashion.
If that's your API you can write it very efficiency and entirely lock free!
Your builder is just a really simple class that contains a plain jane arraylist and fills it:
class RandomPollerBuilder<E> {
private final ArrayList<E> data = new ArrayList<E>();
private boolean open = true;
public void add(E elem) {
if (!open) throw new IllegalStateException();
data.add(elem);
}
public RandomPoller<E> build() {
open = false;
data.trimToSize();
Collection.shuffle(data);
return new RandomPoller<E>(data);
}
}
隨機輪詢器看起來像：
public class RandomPoller<E> {
private final AtomicInteger pos;
private final List<E> input;
RandomPoller<E>(List<E> input) {
this.input = input;
this.pos = new AtomicInteger(input.size());
}
public E poll() {
int idx = pos.decrementAndGet();
if (idx >= 0) return input.get(idx);
pos.incrementAndGet();
throw new NoSuchElementException();
}
public int size() {
return Math.max(0, pos.get());
}
}
在這里，我們結合了大量屬性：
- 我們根本不洗掉。去除往往很慢，如果我們可以避免它，為什么不呢？
- 我們依賴 AtomicInteger，它為我們提供了一種在并發環境中以比鎖快得多的方式保證嚴格和完整排序的方法。
- 我們將實作減少到您真正需要的部分。每種方法寫起來都很痛苦。我包含了一個
size()方法來說明這一點：poll演算法的作業方式是它將 0 遞增到 -1 甚至更糟（如果多個執行緒同時嘗試poll()使用空輪詢器，則原子整數可以低于 -1，但最終它會回傳到 0，所以沒有“翻轉”我們的原子整數的風險，因為沒有系統會有 20 億個執行緒）。我們需要在我們的size()方法中防范這種情況。 - 這也意味著：如果你不是特別需要效率，那么不要理會這些，并制作全域鎖定資料結構。逃避很容易并且有效（只是效率不高）。測驗并發性是非常困難的（因為事情只是在正確的情況下可能會出錯，他們不能保證。在測驗中，您希望損壞的代碼實際上失敗，這就是問題所在。這實際上是不可能的！） - 所以不要除非您完全清楚自己在做什么并且確定需要它，否則不要去那里。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/401114.html