更新时间:2023-10-24 07:59:28
一个简单的方法是使用 读写锁 ([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锁.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.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!). :(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.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
s,没有人会等.否则,只有写入或读取冲突位置的线程会等待.t
开始一个insert([index =] 5, element)
,其他线程尝试get(i)
code>: 一旦t
设置了modifyingFrom = 5
并释放了全局写锁,所有读取的线程都会得到全局读锁,然后检查modifyingFrom代码>.那些带有 i 只是获取槽的(读)锁;其他人等到 insert(5)
完成并通知,然后获取插槽的锁.
add()
并且需要分配一个新的数组:一旦它获得了全局写锁,在它完成之前没有人可以做任何事情.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
就可以拿到全局写锁,正常进行.
get(i)
(each with it's i
, unique or not): each one would get the global read lock, then the i
th read lock, then read the position, and nobody would wait at all.update([index =] i, element)
: if there are no equal i
s, nobody will wait. Otherwise, only the thread writing or the threads reading the conflicting position will wait.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.add()
and needs to allocate a new array: Once it gets the global write lock, nobody else can do anything until it has finished.t_a
calls add(element)
and another thread t_g
calls get([index =] 7)
:
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.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. :)