在 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 和listlock 获取所有的锁[j].
• 对于remove(int i)，一个线程需要为j >= i 和listlock 获取所有的锁[j].
• 对于 add()，线程需要获取列表锁.
• 对于insert()，线程需要获取锁[i].

我的问题是:

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

推荐答案

一个简单的方法是使用 读写锁 ([Reentrant]ReadWriteLock)，这么多线程可以同时读取，但是一旦有人获得写锁，其他人无法访问该列表.

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 modifiedFrom 变量，指示从那里开始的所有位置都被锁定"(j >= i 情况).设置 modifyingFrom 后，您降级(参见 docs) 从写锁到读锁，让其他人访问列表.
• 任何试图做任何不是结构性变化的事情的线程，一旦持有全局读锁，就会检查它想做的事情是否与 modifyingFrom 的当前值冲突.如果有冲突，睡眠直到设置了 modifyingFrom 的线程完成并通知所有等待的人.此检查必须是同步的(只需在某个对象上使用 synchronized (obj))，因此在冲突线程之前，结构更改线程不会发生在 obj.notify() 上调用 obj.wait() 并永远休眠(持有全局读锁！).:(
• 你应该有一个 boolean structureChangeHappening = false 或者将 modifyingFrom 设置为一些 x ><list size> 当没有发生结构变化时(然后你可以检查 i 到 get() 或 update()).完成结构更改的线程将 modifyingFrom 设置回该值，这是它必须同步以通知等待线程的位置.
• 想要在结构更改已经发生时进行结构更改的线程将等待，因为它需要全局写锁并且至少有一个线程具有全局读锁.事实上，它会等到完全没有人访问该列表.
• 一个线程分配一个新的(更大...或更小，如果你有一个trimToSize() 或其他)数组将在整个操作期间保持全局write锁.

• 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) 的情况相同: 如果没有相等的 is，没有人会等.否则，只有写入或读取冲突位置的线程会等待.
• 一个线程t开始一个insert([index =] 5, element)，其他线程尝试get(i)code>: 一旦t设置了modifyingFrom = 5并释放了全局写锁，所有读取的线程都会得到全局读锁，然后检查modifyingFrom.那些带有 i 只是获取槽的(读)锁；其他人等到 insert(5) 完成并通知，然后获取插槽的锁.
• 一个线程启动了一个add()并且需要分配一个新的数组:一旦它获得了全局写锁，在它完成之前没有人可以做任何事情.
• 列表大小为7，一个线程t_a调用add(element)，另一个线程t_g调用get([index =] 7):
  • 如果t_a碰巧先拿到全局写锁，它设置modifyingFrom = 7，一旦释放锁，t_g获取全局读锁，看到 index (= 7) >= modifiedFrom 并休眠直到 t_a 完成并通知它.
  • 如果 t_g 首先获得全局读锁，它会检查 7 (modifyingFrom > (== 7), 示例前的第 4 点)，然后抛出异常，因为 7 >= ; 释放锁后！ 然后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,Predicate<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屋！