java - 通过锁定在Java中实现线程安全的ArrayList

Question

我想写一个简单的线程安全的arraylist，它支持:

add()，remove(int i)，insert(int i)，update(int i)和get(int i)

一种简单的实现是向内部数据结构(例如，对象数组)添加锁，但这还不够好，因为一次只能有一个线程可以访问该列表。

因此，我最初的计划是向每个数据插槽添加锁，以使不同的线程可以同时访问不同索引中的元素。数据结构将如下所示:

class MyArrayList {
    Lock listlock;
    Lock[] locks;
    Object[] array;
}

如果不需要执行resize()，则锁定应按以下方式进行:

对于get(int i)的

，线程需要获取锁[i]。

对于insert(int i)的

，线程需要获取j> = i的所有锁[j]和列表锁。

用于remove(int i)，一个线程需要获取j> = i的所有锁[j]，并获取列表锁。

对于add()的

，线程需要获取列表锁。

对于insert()为

，线程需要获取锁[i]。

我的问题是:

在添加更多对象时调整大小时如何处理锁，我需要创建一个新的更大的数组来容纳所有对象。这很烦人，因为其他一些线程也可能等待释放锁

是否有更好的建议来实现这种线程安全的arraylist？

Answer 1

一种简单的方法是仅使用read-write lock([Reentrant]ReadWriteLock)，因此许多线程可以并发读取，但是一旦有人获得了写锁，其他任何人都无法访问该列表。

或者，您可以执行与您的想法类似的操作:每个插槽一个读写锁+一个全局(“结构”)读写锁+一个变量，以跟踪j >= i的情况。所以:

要访问(读取或写入)任何内容，线程至少需要全局读取锁。

只有试图进行结构更改(更改大小的线程)的线程才获得全局写锁定，但仅设置int modifyingFrom变量以指示此后的所有位置均被“锁定”(在j >= i情况下)。设置modifyingFrom后，您可以将写入(从docs)降级为读取锁定，让其他人访问该列表。

任何尝试执行非结构性更改的线程，一旦持有全局读取锁定，便会检查其要执行的操作是否与modifyingFrom的当前值冲突。如果存在冲突，请 hibernate 直到设置了modifyingFrom的线程完成并通知正在等待的每个人。此检查必须同步(仅在某些对象上使用synchronized (obj))，以便在冲突线程调用obj.notify()并永久 hibernate (持有全局读取锁!)之前，更改结构的线程不会发生在obj.wait()上。 :(

当没有结构上的变化时，您应该具有boolean structuralChangeHappening = false或将modifyingFrom设置为某些x > <list size>(然后您可以检查i < modifyingFrom是get()还是update())。完成结构更改的线程会将modifyingFrom设置回该值，这是它必须同步以通知正在等待的线程的地方。

一个想要在已经发生结构更改的线程将等待，因为它需要全局写锁，并且至少一个线程具有全局读锁。实际上，它将一直等到没有人完全访问该列表。

分配新数组(更大或更小，如果您有 trimToSize() 或其他)的线程将在整个操作期间保持全局写锁定。

我倾向于认为并不是真正需要全局读写锁，但是最后两点证明了这一点。

一些示例情况:

一些尝试尝试get(i)的线程(每个线程都具有i，是否唯一):每个线程都将获得全局读取锁定，然后将i读取锁定，然后读取位置，没有人会等待。

与尝试update([index =] i, element)的其他线程相同的情况:如果没有相等的i，则没有人会等待。否则，仅线程写入或线程读取冲突位置将等待。

线程t启动insert([index =] 5, element)，其他线程尝试get(i):t设置了modifyingFrom = 5并释放了全局写锁之后，所有读取的线程都获得了全局读锁，然后检查modifyingFrom。那些带有i < modifyingFrom的用户只会获得该插槽的(读)锁。其他的则等待insert(5)完成并通知，然后获得插槽的锁定。

线程启动add()并需要分配一个新的数组:一旦获得全局写锁，其他人就无法完成任何操作。

列表的大小为7，一个线程t_a调用add(element)，另一个线程t_g调用get([index =] 7):

如果t_a碰巧首先获得了全局写锁，它将设置modifyingFrom = 7，一旦释放该锁，t_g就会获得全局读锁，看到index (= 7) >= modifyingFrom并 hibernate ，直到t_a完成并通知它。

如果t_g首先获得了全局读取锁定，它将检查7 < modifyingFrom(modifyingFrom > <list size> (== 7)，示例之前的第4个点)，然后引发异常，因为释放锁定后的7 >= <list size> ! 然后t_a能够获取全局写锁定并正常进行。

请记住，对 modifyingFrom的访问必须同步。

您说过只需要这五个操作，但是如果您想要一个迭代器，它可以检查是否通过其他方式(而不是迭代器本身)更改了某些内容，就像标准类所做的那样。

现在，我不知道在什么条件下这比其他方法要好。另外，请考虑在实际应用程序中可能需要更多限制，因为这只能确保一致性:如果尝试读取和写入相同的位置，则读取可能发生在写入之前或之后。使用 tryUpdate(int, E)之类的方法仅在调用该方法时没有发生结构冲突的情况下才会执行某些操作，或者只有列表在满足谓词的状态下才进行操作的 tryUpdate(int, E, Predicate<ArrayList>)才有意义。仔细定义，以免造成死锁)。

如果我错过了什么，请告诉我。可能会有很多极端情况。 :)