通过锁定在Java中实现线程安全的ArrayList [英] Implement a thread-safe ArrayList in Java by locking

问题描述

我想写一个简单的线程安全数组列表，它支持:

I want to write a simple thread-safe arraylist which supports:

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

add(), remove(int i), insert(int i), update(int i), and get(int i)

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

One simple implementation is to add lock to the internal data structure(an object array for example), but it is not good enough because only one thread could access the list at a time.

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

Therefore my initial plan is to add lock to each data slot so that different threads could have access to elements in different indexes at the same time. The data structure will look like this:

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

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

The locking should work as follows if there is no need to do resize():

• 对于get(int i)，线程需要获取锁[i].
• 对于insert(int i)，线程需要获取j> = i的所有锁[j]和列表锁.
• 对于remove(int i)，线程需要获取j> = i的所有锁[j]和列表锁.
• 对于add()，线程需要获取列表锁.
• 对于insert()，线程需要获取锁[i].

我的问题是:

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

推荐答案

一种简单的方法是仅使用

A simple approach would be to just use a read-write lock ([Reentrant]ReadWriteLock), so many threads could read concurrently, but once someone gets the write lock, nobody else can access the list.

或者您可以做一些与您的想法类似的事情:每个插槽一个读写锁+一个全局(结构")读写锁+一个用于跟踪 j> = i的变量案例.所以:

Or you could do something somewhat similar to your idea: one read-write lock for each slot + a global ("structural") read-write lock + a variable to keep track of the j >= i cases. So:

• 要访问(读取或写入)任何内容，线程至少需要全局读取锁.
• 只有试图进行结构更改(更改大小的线程)的线程会获得全局写锁定，但只会设置 int ModifyingFrom 变量，以指示从此处开始的所有位置均被锁定"( j> = i 情况).设置 modifyingFrom 后，您进行降级(请参见文档)从写到读锁定，让其他人可以访问列表.
• 任何试图执行任何非结构性更改的线程，一旦持有全局读取锁，就会检查其要执行的操作是否与 modifyingFrom 的当前值冲突.如果存在冲突，请休眠直到设置 modifyingFrom 的线程完成并通知正在等待的每个人.此检查必须同步(仅在某些对象上使用 synchronized(obj))，以便在发生冲突的线程之前 obj.notify()不会发生结构更改线程调用 obj.wait()并永远休眠(持有全局读取锁！).:(
• 您应该具有 boolean structureChangeHappening = false 或将 modifyingFrom 设置为某些 x>< list size> (当没有结构变化发生时)(然后，您只需检查 i< modifiedFrom 到 get()或 update()).完成结构更改的线程将 modifyingFrom 设置回该值，并且在此处必须进行同步以通知等待的线程.
• 一个想要在已经发生结构更改的线程将等待，因为它需要全局写锁，并且至少一个线程具有全局读锁.实际上，它会一直等到根本没有人访问该列表.
• 如果有

• To access (read or write) anything, a thread needs at least the global read lock.
• Only threads trying to make structural changes (the ones that change the size) get the global write lock, but only to set an int modifyingFrom variable indicating all positions from there on are "locked" (the j >= i cases). After setting modifyingFrom, you downgrade (see docs) from write to read lock, letting others access the list.
• Any thread trying to do anything that isn't a structural change, once holding the global read lock, checks if what it wants to do conflicts with the current value of modifyingFrom. If there's a conflict, sleep until the thread who has set modifyingFrom finishes and notifies everybody who is waiting. This check must be synchronized (just use synchronized (obj) on some object) so the structure-changing thread doesn't happen to obj.notify() before the conflicting thread calls obj.wait() and sleeps forever (holding the global read lock!). :(
• You should either have a boolean structuralChangeHappening = false or set modifyingFrom to some x > <list size> when no structural changes are happening (then you can just check that i < modifyingFrom to get() or update()). A thread finishing a structural change sets modifyingFrom back to this value and here's where it has to synchronize to notify waiting threads.
• A thread wanting to make a structural change when one is already happening will wait because it needs the global write lock and at least one thread has the global read lock. In fact, it will wait until nobody is accessing the list at all.
• A thread allocating a new (bigger... or smaller, if you had a trimToSize() or something) array would hold the global write lock during the entire operation.

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

I was tempted to think the global read-write lock wasn't really necessary, but the last two points justify it.

一些示例情况:

• 一些线程尝试获取 get(i)(每个线程都带有 i ，无论是否唯一):每个线程都将获得全局读取锁，然后第 i 个读锁，然后读取位置，没有人会等待.
• 相同情况，其他线程尝试 update([index =] i，element)::如果没有相等的 i ，没有人会等待.否则，将仅等待写线程或读冲突位置的线程.
• 线程 t 启动 insert([index =] 5，element)，其他线程尝试 get(i):一旦 t 设置了 modifyingFrom = 5 并释放了全局写锁，所有读取的线程都将获得全局读锁，然后检查 modifyingFrom.那些 i<modifyFrom 只是获得插槽的(读取)锁；其他的则等待直到 insert(5)完成并通知，然后获得插槽的锁定.
• 一个线程启动一个 add()并需要分配一个新数组:一旦获得全局写锁，其他人就无法完成任何操作.
• 列表的大小为7，一个线程 t_a 调用 add(element)，另一个线程 t_g 调用 get([index =] 7):
  • 如果 t_a 碰巧首先获得了全局写锁，则会设置 modifyingFrom = 7 ，并在释放锁后，立即设置 t_g 获取全局读取锁，看到 index(= 7)> = ModifyingFrom 并休眠直到 t_a 完成并通知它.
  • 如果 t_g 首先获得全局读取锁定，则它将检查 7<ModifyingFrom ( modifyingFrom>< list size>(== 7)，在示例之前的第4点)，然后抛出异常，因为 7> =< list size> 释放锁定后！然后， t_a 可以获取全局写锁定并正常进行.
  • Some threads trying to get(i) (each with it's i, unique or not): each one would get the global read lock, then the ith read lock, then read the position, and nobody would wait at all.
  • The same case with additional threads trying to update([index =] i, element): if there are no equal is, nobody will wait. Otherwise, only the thread writing or the threads reading the conflicting position will wait.
  • A thread t starts an insert([index =] 5, element), and other threads try to get(i): Once t has set modifyingFrom = 5 and released the global write lock, all threads reading get the global read lock, then check modifyingFrom. Those with i < modifyingFrom just get the (read) lock of the slot; the others wait until the insert(5) finishes and notifies, then get the lock of the slot.
  • A thread starts an add() and needs to allocate a new array: Once it gets the global write lock, nobody else can do anything until it has finished.
  • The size of the list is 7, a thread t_a calls add(element) and another thread t_g calls get([index =] 7):
    • If t_a happens to get the global write lock first, it sets modifyingFrom = 7, and once it has released the lock, t_g gets the global read lock, sees that index (= 7) >= modifyingFrom and sleeps until t_a finishes and notifies it.
    • If t_g gets the global read lock first, it checks that 7 < modifyingFrom (modifyingFrom > <list size> (== 7), 4th point before the examples), then throws an exception because 7 >= <list size> after releasing the lock! Then t_a is able to get the global write lock and proceeds normally.

    记住对 modifyingFrom 的访问必须同步.

    Remembering that accesses to modifyingFrom must be synchronized.

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

    You said you want only that five operations, but if you wanted an iterator, it could check if something changed by other means (not the iterator itself), like standard classes do.

    现在，我不知道在什么条件下这会比其他方法更好.另外，请考虑在实际应用程序中可能需要更多限制，因为这只能确保一致性:如果尝试读取和写入相同的位置，则读取可能发生在写入之前或之后.也许有像 tryUpdate(int，E)这样的方法才有意义，该方法仅在调用该方法时没有发生冲突的结构变化或 tryUpdate(int，E，谓词< ArrayList>)，仅当列表处于满足谓词的状态(应该仔细定义它，以免引起死锁)时，它才能工作.

    Now, I don't know under which conditions exactly this would be better than other approaches. Also, consider that you may need more restrictions in a real application, because this should ensure only consistency: if you try to read and write the same position, the read can happen before or after the write. Maybe it would make sense to have methods like tryUpdate(int, E), that only does something if no conflicting structural changes are happening when the method is called, or tryUpdate(int, E, Predicate<ArrayList>), which only does its work if the list is in a state that satisfies the predicate (which should be defined carefully not to cause deadlocks).

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

    Please let me know if I missed something. There may be lots of corner cases. :)

    这篇关于通过锁定在Java中实现线程安全的ArrayList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！