在多线程环境中，为了实现线程安全的数组元素交换，我们会进行同步锁定。
// a is char array.
synchronized(a) {
char tmp = a[1];
a[1] = a[0];
a[0] = tmp;
}
是否有可能在上述情况下使用下面的 API，以便我们可以进行无锁数组元素交换？如果是，如何？
问问题
2804 次
6 回答
5
无论使用哪种 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);
希望这有点道理。
更新：
一些测试表明，除非您有大量线程同时访问数组（在普通硬件上超过 100 个），否则简单的同步（数组）{} 比复杂的同步工作得快得多。
于 2009-08-05T09:53:17.347 回答
1
// 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;
}
}
于 2016-05-19T13:40:40.700 回答
0
您将获得的最接近的是java.util.concurrent.atomic.AtomicReferenceArray，它提供基于 CAS 的操作，例如boolean compareAndSet(int i, E expect, E update). 虽然它没有swap(int pos1, int pos2)操作，所以你将不得不通过两次compareAndSet调用来模拟它。
于 2009-08-05T11:12:04.910 回答
0
“并发应用程序可伸缩性的主要威胁是独占资源锁。” - Java 并发实践。
我认为你需要一个锁，但正如其他人提到的那样，锁可能比现在更细化。
您可以使用像 java.util.concurrent.ConcurrentHashMap 这样的锁条带化。
于 2009-08-06T09:45:15.283 回答
0
正如其他人已经说过的那样，您提到的 API 只能用于设置单个对象的值，而不是数组。甚至同时用于两个对象，因此无论如何您都不会进行安全交换。
解决方案取决于您的具体情况。数组可以替换为其他数据结构吗？它的大小是否也同时发生变化？
如果必须使用数组，可以将其更改为保存可更新对象（不是原始类型也不是 a Char），并在交换的两者上同步。像这样的 S 数据结构可以工作：
public class CharValue {
public char c;
}
CharValue[] a = new CharValue[N];
请记住使用确定性同步顺序来避免死锁（http://en.wikipedia.org/wiki/Deadlock#Circular_wait_prevention）！您可以简单地遵循索引排序来避免它。
如果还应同时从集合中添加或删除项目，则可以使用 aMap代替，在Map.Entry'es 上同步交换并使用同步的 Map 实现。简单的List不会这样做，因为没有用于保留值的独立结构（或者您无权访问它们）。
于 2009-08-06T13:25:21.003 回答
-1
我不认为 AtomicReferenceFieldUpdater 是为了数组访问而设计的，即使是这样，它一次只提供一个引用的原子保证。AFAIK，java.util.concurrent.atomic 中的所有类一次只提供对一个引用的原子访问。为了将两个或多个引用更改为一个原子操作，您必须使用某种锁定。
于 2009-08-05T08:50:20.297 回答