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

关键词：

【中文标题】通过锁定在 Java 中实现线程安全的 ArrayList【英文标题】：Implement a thread-safe ArrayList in Java by locking 【发布时间】：2018-03-08 07:07:12 【问题描述】：

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

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 和listlock 的所有锁[j]。 对于 remove(int i)，线程需要获取所有锁 [j] for j >= i 和 listlock。 对于add()，线程需要获取listlock。 对于insert()，线程需要获取锁[i]。

我的问题是：

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

【问题讨论】：

List list = Collections.synchronizedList(new ArrayList()); 呢？ 那个存在，就叫Vector。 我认为这是一个练习，而不是一个简单的练习，因为 JDK 中有内置的并发集合。 @DwB 感谢您提供的信息。其实我从Vector或者synchronizedList的源码中发现，synchronized关键字是用来保证线程安全的。以 get() 为例，线程 A 想要调用 get(0)，而线程 B 想要调用 get(1)，使用 synchronized 将只允许一个线程调用 get() 函数，即使两个线程正在尝试读取数据不同的位置。如果线程正在访问不同的插槽，我想做的是同时执行此操作。 这绝不是合理的。您不能合理地限制列表上的同步规模，因为有多种方法可以访问列表中的给定元素（迭代器、枚举器、按索引访问），并且将列表增加一个元素可能会导致完全重建数组（即分配新数组，复制旧元素，转储旧数组）。 【参考方案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，是否唯一）：每个线程都会获得全局读锁，然后是ith 读锁，然后读取位置，没有人会等待。 同样的情况，有额外的线程尝试update([index =] i, element)：如果没有相等的is，没有人会等待。否则，只有写入的线程或读取冲突位置的线程会等待。 一个线程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>在释放锁之后！ 那么t_a 就能获得全局写锁并正常进行。

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

你说你只需要这五个操作，但如果你想要一个迭代器，它可以检查是否通过其他方式（不是迭代器本身）改变了某些东西，就像标准类一样。

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

如果我遗漏了什么，请告诉我。可能有很多极端案例。 :)

【讨论】：

线程安全在Java中实现单例模式的有效方法？ [复制]

】线程安全在Java中实现单例模式的有效方法？[复制]【英文标题】：ThreadSafeEfficientwaytoimplementsingletonpatterninJava?[duplicate]【发布时间】：2011-05-2719:42:06【问题描述】：可能重复：EfficientwaytoimplementsingletonpatterninJava我正在阅读这个Be... 查看详情

如何在 Swift 中实现线程安全的 HashTable (PhoneBook) 数据结构？

】如何在Swift中实现线程安全的HashTable(PhoneBook)数据结构？【英文标题】：HowtoimplementaThreadSafeHashTable(PhoneBook)DataStructureinSwift?【发布时间】：2018-08-1214:32:48【问题描述】：我正在尝试实现一个线程安全的电话簿对象。电话簿应该... 查看详情

java示例代码_使用Glassfish 2.1在JPA中实现悲观锁定

java示例代码_使用Glassfish 2.1在JPA中实现悲观锁定 查看详情

java示例代码_如何在Java中实现安全的静态登录凭据系统

java示例代码_如何在Java中实现安全的静态登录凭据系统 查看详情

在 Oracle 中实现乐观锁定

】在Oracle中实现乐观锁定【英文标题】：ImplementingOptimisticLockinginOracle【发布时间】：2016-12-0623:40:23【问题描述】：我对Oracle中的锁定主题感到困惑。根据我的研究，您可以使用FORUPDATENOWAIT/WAIT锁定行。我想以这种方式实现我的锁... 查看详情

java示例代码_在Java中实现基于UDP的线程服务器

java示例代码_在Java中实现基于UDP的线程服务器 查看详情

如何在java中实现跨线程的通讯

一般而言，如果没有干预的话，线程在启动之后会一直运行到结束，但有时候我们又需要很多线程来共同完成一个任务，这就牵扯到线程间的通讯。如何让两个线程先后执行？Thread.join方法privatestaticvoiddemo2(){ThreadA=newThread(newRunnab... 查看详情

java中实现多线程继承thread类与实现runnable接口的区别

Java中线程的创建有两种方式：  1．  通过继承Thread类，重写Thread的run()方法，将线程运行的逻辑放在其中  2．  通过实现Runnable接口，实例化Thread类  在实际应用中，我们经常用到多线程，如... 查看详情

boost中实现线程安全

博客转载自: http://www.cnblogs.com/lvdongjie/p/4447142.html1boost原子变量和线程#include<boost/thread.hpp>usingnamespaceboost;usingnamespacestd;mutexio_mu;//定认全局互斥变量/**模板类:线程安全的计数器，不可拷贝*/template<typ 查看详情

netty系列之:在netty中实现线程和cpu绑定

...。使用这个库你可以将线程绑定到特定的CPU或者CPU核上，通过减少线程在CPU之间的切换，从而提升线程执行的效率。虽然netty已经够优秀了，但是谁不想更加优秀一点呢？于是一个想法产生了，那就是能 查看详情

在 C++ 中实现 C++ 线程库

】在C++中实现C++线程库【英文标题】：ImplementingaC++threadingLibraryinc++【发布时间】：2009-02-1106:29:26【问题描述】：我是一名java程序员，但目前正在使用c++语言。与java不同，c++没有定义任何线程实用程序。在C++中实现多线程应用程... 查看详情

如何在Java中实现多个线程来下载单个表数据？

】如何在Java中实现多个线程来下载单个表数据？【英文标题】：HowtoimplementseveralthreadsinJavafordownloadingasingletabledata?【发布时间】：2012-01-0916:15:07【问题描述】：如何实现多个线程的多个/相同连接，以便快速下载单个大表数据。... 查看详情

如何在Java中实现多个线程来下载单个表数据？

】如何在Java中实现多个线程来下载单个表数据？【英文标题】：HowtoimplementseveralthreadsinJavafordownloadingasingletabledata?【发布时间】：2012-01-0916:15:07【问题描述】：如何实现多个线程的多个/相同连接，以便快速下载单个大表数据。... 查看详情

java示例代码_在Java中实现多线程池

java示例代码_在Java中实现多线程池 查看详情

使用redis的分布式java锁

通过优锐课的java学习分享中，了解有关分布式锁定以及如何在项目中实现它的更多信息！什么是分布式锁定？在多线程程序中，不同的线程可能需要访问相同的资源。但是，允许所有线程同时访问资源可能导致争用情况，错误... 查看详情

Waterline ORM 线程在设计上是安全的吗？

...己的内存，不与其他集群共享。如果你有一些关键部分要锁定，你 查看详情

如何在 C# 中实现 Base64 URL 安全编码？

】如何在C#中实现Base64URL安全编码？【英文标题】：HowtoachieveBase64URLsafeencodinginC#?【发布时间】：2014-12-0819:52:09【问题描述】：我想在C#中实现Base64URL安全编码。在Java中，我们有一个通用的Codec库，它为我提供了一个URL安全编码字... 查看详情

OpenMP：如何在任务中实现线程本地对象？

...or;但是，有问题的容器不提供随机访问迭代器。因此，我通过this***answer中描述的任务使用解决方法：for(std::map<A,B>::iter 查看详情