通过锁定

Question

实现Java中的线程安全的ArrayList我想写它支持一个简单的线程安全的ArrayList：

的add（），删除（int i）以插入（int i）以，更新（INT I ）和get（int i）

一个简单的实现是向内部数据结构（例如对象数组）添加锁，但它不够好，因为一次只能有一个线程访问列表。

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

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

锁定应该工作如下如果没有必要做调整（）：

• 对于GET（int i）以，一个线程需要获取锁[i]中。
• 对于insert（int i），线程需要获取所有的锁[j]（对于j> = i）和listlock。
• 对于remove（int i），线程需要获取j> = i和listlock的所有锁[j]。
• 对于add（），线程需要获取listlock。
• 对于insert（），线程需要获取锁[i]。

我的问题是：

• 如何调整，而更多的对象添加和我需要建立一个新的更大的阵列来存储所有对象时处理的锁。这很烦人，因为一些其他线程也可能会等待锁被释放，
• 任何更好的建议来实现这样的线程安全的数组列表？

Answer 1

一个简单的方法是只使用一个read-write lock（[Reentrant]ReadWriteLock），这么多的线程可以同时读取，但一旦有人被写入锁，其他人可以访问列表。

或者您可以做一些与您的想法有点相似的事情：每个插槽一个读写锁+一个全局（“结构”）读写锁+一个变量来跟踪j >= i个案。所以：

• 要访问（读取或写入）任何内容，线程至少需要全局读取锁定。
• 只有尝试进行结构更改（更改大小的线程）的线程才会获得全局写入锁定，但仅设置一个int modifyingFrom变量，指示从此处开始的所有位置都已“锁定”（j >= i个案）。在设置modifyingFrom之后，您将降级（请参阅docs）从写入读取锁定，让他人访问列表。
• 任何线程都会尝试执行任何不是结构性更改的任何操作，一旦持有全局读取锁定，就会检查它是否与当前值modifyingFrom发生冲突。如果发生冲突，请一直睡到设置好modifyingFrom的线程结束并通知所有正在等待的人。此检查必须同步（仅在某些对象上使用synchronized (obj)），因此在冲突线程调用obj.wait()并永久休眠（保持全局读锁定！）之前，结构更改线程不会发生在obj.notify()之前。 :(
• 您应该有一个boolean structuralChangeHappening = false或设置modifyingFrom一些在没有结构性变化正在发生x > <list size>（那么你可以检查i < modifyingFrom到get()或update()）。线程完成了结构性的变化将modifyingFrom回到这个价值这里是它必须同步以通知等待线程的地方
• 当一个线程已经发生时，想要进行结构性更改的线程将等待，因为它需要全局写锁定，并且至少有一个线程具有全局读锁定。它将等待，直到没有人访问该列表。
• 一个线程分配一个新的（更大或更小，如果你有一个trimToSize()或什么）阵列将举行全球编写锁在整个操作期间。

我很想认为全球读写锁是不是真的有必要，但最后两点证明它。

一些示例情况：

• 有些线程试图get(i)（每个都有它i，独特与否）：每个人将获得全局读锁定，那么i个读锁，然后读这个位置，没有人会等待。
• 与额外的线程尝试update([index =] i, element)相同的情况：如果没有相等的i s，没有人会等待。否则，只有线程写入或读取冲突位置的线程才会等待。
• 线程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并睡觉，直到t_a完成并通知它。
  • 如果t_g首先获得全局读锁定，它会检查7 < modifyingFrom（modifyingFrom > <list size> (== 7)，示例前第4点），然后抛出一个异常，因为解除锁定后7 >= <list size>！ Then t_a能够获得全局写入锁定并正常进行。访问到modifyingFrom

缅怀必须同步。

你说你只需要这五个操作，但是如果你想要一个迭代器，它可以检查是否有其他方法改变（不是迭代器本身），像标准类一样。

现在，我不知道在哪种情况下这会比其他方法更好。另外，考虑到在真实应用程序中可能需要更多限制，因为这应该只确保一致性：如果您尝试读取和写入相同的位置，则读取可能发生在写入之前或之后。也许这是有道理的，有像tryUpdate(int, E)这样的方法，只有在调用方法时没有发生冲突的结构变化时才会执行某些操作，或者只有在列表处于满足谓词状态时才会执行其工作（tryUpdate(int, E, Predicate<ArrayList>)）被仔细地定义为不导致死锁）。

请让我知道，如果我错过了什么。可能会有很多角落案例。 :)