【数据结构与算法】(9)基础数据结构 之 阻塞队列的单锁实现、双锁实现详细代码示例讲解

目录

    • 2.8 阻塞队列
      • 1) 单锁实现
      • 2) 双锁实现

在这里插入图片描述

2.8 阻塞队列

之前的队列在很多场景下都不能很好地工作,例如

  1. 大部分场景要求分离向队列放入(生产者)、从队列拿出(消费者)两个角色、它们得由不同的线程来担当,而之前的实现根本没有考虑线程安全问题
  2. 队列为空,那么在之前的实现里会返回 null,如果就是硬要拿到一个元素呢?只能不断循环尝试
  3. 队列为满,那么再之前的实现里会返回 false,如果就是硬要塞入一个元素呢?只能不断循环尝试

因此我们需要解决的问题有

  1. 用锁保证线程安全
  2. 用条件变量让等待非空线程等待不满线程进入等待状态,而不是不断循环尝试,让 CPU 空转

有同学对线程安全还没有足够的认识,下面举一个反例,两个线程都要执行入队操作(几乎在同一时刻)

public class TestThreadUnsafe {
    private final String[] array = new String[10];
    private int tail = 0;

    public void offer(String e) {
        array[tail] = e;
        tail++;
    }

    @Override
    public String toString() {
        return Arrays.toString(array);
    }

    public static void main(String[] args) {
        TestThreadUnsafe queue = new TestThreadUnsafe();
        new Thread(()-> queue.offer("e1"), "t1").start();
        new Thread(()-> queue.offer("e2"), "t2").start();
    }
}

执行的时间序列如下,假设初始状态 tail = 0,在执行过程中由于 CPU 在两个线程之间切换,造成了指令交错

线程1线程2说明
array[tail]=e1线程1 向 tail 位置加入 e1 这个元素,但还没来得及执行 tail++
array[tail]=e2线程2 向 tail 位置加入 e2 这个元素,覆盖掉了 e1
tail++tail 自增为1
tail++tail 自增为2
最后状态 tail 为 2,数组为 [e2, null, null …]

糟糕的是,由于指令交错的顺序不同,得到的结果不止以上一种,宏观上造成混乱的效果

1) 单锁实现

Java 中要防止代码段交错执行,需要使用锁,有两种选择

  • synchronized 代码块,属于关键字级别提供锁保护,功能少
  • ReentrantLock 类,功能丰富

以 ReentrantLock 为例

ReentrantLock lock = new ReentrantLock();

public void offer(String e) {
    lock.lockInterruptibly();
    try {
        array[tail] = e;
        tail++;
    } finally {
        lock.unlock();
    }
}

只要两个线程执行上段代码时,锁对象是同一个,就能保证 try 块内的代码的执行不会出现指令交错现象,即执行顺序只可能是下面两种情况之一

线程1线程2说明
lock.lockInterruptibly()t1对锁对象上锁
array[tail]=e1
lock.lockInterruptibly()即使 CPU 切换到线程2,但由于t1已经对该对象上锁,因此线程2卡在这儿进不去
tail++切换回线程1 执行后续代码
lock.unlock()线程1 解锁
array[tail]=e2线程2 此时才能获得锁,执行它的代码
tail++
  • 另一种情况是线程2 先获得锁,线程1 被挡在外面
  • 要明白保护的本质,本例中是保护的是 tail 位置读写的安全

事情还没有完,上面的例子是队列还没有放满的情况,考虑下面的代码(这回锁同时保护了 tail 和 size 的读写安全)

ReentrantLock lock = new ReentrantLock();
int size = 0;

public void offer(String e) {
    lock.lockInterruptibly();
    try {
        if(isFull()) {
            // 满了怎么办?
        }
        array[tail] = e;
        tail++;
        
        size++;
    } finally {
        lock.unlock();
    }
}

private boolean isFull() {
    return size == array.length;
}

之前是返回 false 表示添加失败,前面分析过想达到这么一种效果:

  • 在队列满时,不是立刻返回,而是当前线程进入等待
  • 什么时候队列不满了,再唤醒这个等待的线程,从上次的代码处继续向下运行

ReentrantLock 可以配合条件变量来实现,代码进化为

ReentrantLock lock = new ReentrantLock();
Condition tailWaits = lock.newCondition(); // 条件变量
int size = 0;

public void offer(String e) {
    lock.lockInterruptibly();
    try {
        while (isFull()) {
            tailWaits.await();	// 当队列满时, 当前线程进入 tailWaits 等待
        }
        array[tail] = e;
        tail++;
        
        size++;
    } finally {
        lock.unlock();
    }
}

private boolean isFull() {
    return size == array.length;
}
  • 条件变量底层也是个队列,用来存储这些需要等待的线程,当队列满了,就会将 offer 线程加入条件队列,并暂时释放锁
  • 将来我们的队列如果不满了(由 poll 线程那边得知)可以调用 tailWaits.signal() 来唤醒 tailWaits 中首个等待的线程,被唤醒的线程会再次抢到锁,从上次 await 处继续向下运行

思考为何要用 while 而不是 if,设队列容量是 3

操作前offer(4)offer(5)poll()操作后
[1 2 3]队列满,进入tailWaits 等待[1 2 3]
[1 2 3]取走 1,队列不满,唤醒线程[2 3]
[2 3]抢先获得锁,发现不满,放入 5[2 3 5]
[2 3 5]从上次等待处直接向下执行[2 3 5 ?]

关键点:

  • 从 tailWaits 中唤醒的线程,会与新来的 offer 的线程争抢锁,谁能抢到是不一定的,如果后者先抢到,就会导致条件又发生变化
  • 这种情况称之为虚假唤醒,唤醒后应该重新检查条件,看是不是得重新进入等待

最后的实现代码

/**
 * 单锁实现
 * @param <E> 元素类型
 */
public class BlockingQueue1<E> implements BlockingQueue<E> {
    private final E[] array;
    private int head = 0;
    private int tail = 0;
    private int size = 0; // 元素个数

    @SuppressWarnings("all")
    public BlockingQueue1(int capacity) {
        array = (E[]) new Object[capacity];
    }

    ReentrantLock lock = new ReentrantLock();
    Condition tailWaits = lock.newCondition();
    Condition headWaits = lock.newCondition();

    @Override
    public void offer(E e) throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (isFull()) {
                tailWaits.await();
            }
            array[tail] = e;
            if (++tail == array.length) {
                tail = 0;
            }
            size++;
            headWaits.signal();
        } finally {
            lock.unlock();
        }
    }

    @Override
    public void offer(E e, long timeout) throws InterruptedException {
        lock.lockInterruptibly();
        try {
            long t = TimeUnit.MILLISECONDS.toNanos(timeout);
            while (isFull()) {
                if (t <= 0) {
                    return;
                }
                t = tailWaits.awaitNanos(t);
            }
            array[tail] = e;
            if (++tail == array.length) {
                tail = 0;
            }
            size++;
            headWaits.signal();
        } finally {
            lock.unlock();
        }
    }

    @Override
    public E poll() throws InterruptedException {
        lock.lockInterruptibly();
        try {
            while (isEmpty()) {
                headWaits.await();
            }
            E e = array[head];
            array[head] = null; // help GC
            if (++head == array.length) {
                head = 0;
            }
            size--;
            tailWaits.signal();
            return e;
        } finally {
            lock.unlock();
        }
    }

    private boolean isEmpty() {
        return size == 0;
    }

    private boolean isFull() {
        return size == array.length;
    }
}
  • public void offer(E e, long timeout) throws InterruptedException 是带超时的版本,可以只等待一段时间,而不是永久等下去,类似的 poll 也可以做带超时的版本,这个留给大家了

注意

  • JDK 中 BlockingQueue 接口的方法命名与我的示例有些差异
    • 方法 offer(E e) 是非阻塞的实现,阻塞实现方法为 put(E e)
    • 方法 poll() 是非阻塞的实现,阻塞实现方法为 take()

2) 双锁实现

单锁的缺点在于:

  • 生产和消费几乎是不冲突的,唯一冲突的是生产者和消费者它们有可能同时修改 size
  • 冲突的主要是生产者之间:多个 offer 线程修改 tail
  • 冲突的还有消费者之间:多个 poll 线程修改 head

如果希望进一步提高性能,可以用两把锁

  • 一把锁保护 tail
  • 另一把锁保护 head
ReentrantLock headLock = new ReentrantLock();  // 保护 head 的锁
Condition headWaits = headLock.newCondition(); // 队列空时,需要等待的线程集合

ReentrantLock tailLock = new ReentrantLock();  // 保护 tail 的锁
Condition tailWaits = tailLock.newCondition(); // 队列满时,需要等待的线程集合

先看看 offer 方法的初步实现

@Override
public void offer(E e) throws InterruptedException {
    tailLock.lockInterruptibly();
    try {
        // 队列满等待
        while (isFull()) {
            tailWaits.await();
        }
        
        // 不满则入队
        array[tail] = e;
        if (++tail == array.length) {
            tail = 0;
        }
        
        // 修改 size (有问题)
        size++;
        
    } finally {
        tailLock.unlock();
    }
}

上面代码的缺点是 size 并不受 tailLock 保护,tailLock 与 headLock 是两把不同的锁,并不能实现互斥的效果。因此,size 需要用下面的代码保证原子性

AtomicInteger size = new AtomicInteger(0);	   // 保护 size 的原子变量

size.getAndIncrement(); // 自增
size.getAndDecrement(); // 自减

代码修改为

@Override
public void offer(E e) throws InterruptedException {
    tailLock.lockInterruptibly();
    try {
        // 队列满等待
        while (isFull()) {
            tailWaits.await();
        }
        
        // 不满则入队
        array[tail] = e;
        if (++tail == array.length) {
            tail = 0;
        }
        
        // 修改 size
        size.getAndIncrement();
        
    } finally {
        tailLock.unlock();
    }
}

对称地,可以写出 poll 方法

@Override
public E poll() throws InterruptedException {
    E e;
    headLock.lockInterruptibly();
    try {
        // 队列空等待
        while (isEmpty()) {
            headWaits.await();
        }
        
        // 不空则出队
        e = array[head];
        if (++head == array.length) {
            head = 0;
        }
        
        // 修改 size
        size.getAndDecrement();
        
    } finally {
        headLock.unlock();
    }
    return e;
}

下面来看一个难题,就是如何通知 headWaits 和 tailWaits 中等待的线程,比如 poll 方法拿走一个元素,通知 tailWaits:我拿走一个,不满了噢,你们可以放了,因此代码改为

@Override
public E poll() throws InterruptedException {
    E e;
    headLock.lockInterruptibly();
    try {
        // 队列空等待
        while (isEmpty()) {
            headWaits.await();
        }
        
        // 不空则出队
        e = array[head];
        if (++head == array.length) {
            head = 0;
        }
        
        // 修改 size
        size.getAndDecrement();
        
        // 通知 tailWaits 不满(有问题)
        tailWaits.signal();
        
    } finally {
        headLock.unlock();
    }
    return e;
}

问题在于要使用这些条件变量的 await(), signal() 等方法需要先获得与之关联的锁,上面的代码若直接运行会出现以下错误

java.lang.IllegalMonitorStateException

那有同学说,加上锁不就行了吗,于是写出了下面的代码

在这里插入图片描述

发现什么问题了?两把锁这么嵌套使用,非常容易出现死锁,如下所示

在这里插入图片描述

因此得避免嵌套,两段加锁的代码变成了下面平级的样子

在这里插入图片描述

性能还可以进一步提升

  1. 代码调整后 offer 并没有同时获取 tailLock 和 headLock 两把锁,因此两次加锁之间会有空隙,这个空隙内可能有其它的 offer 线程添加了更多的元素,那么这些线程都要执行 signal(),通知 poll 线程队列非空吗?

    • 每次调用 signal() 都需要这些 offer 线程先获得 headLock 锁,成本较高,要想法减少 offer 线程获得 headLock 锁的次数
    • 可以加一个条件:当 offer 增加前队列为空,即从 0 变化到不空,才由此 offer 线程来通知 headWaits,其它情况不归它管
  2. 队列从 0 变化到不空,会唤醒一个等待的 poll 线程,这个线程被唤醒后,肯定能拿到 headLock 锁,因此它具备了唤醒 headWaits 上其它 poll 线程的先决条件。如果检查出此时有其它 offer 线程新增了元素(不空,但不是从0变化而来),那么不妨由此 poll 线程来唤醒其它 poll 线程

这个技巧被称之为级联通知(cascading notifies),类似的原因

  1. 在 poll 时队列从满变化到不满,才由此 poll 线程来唤醒一个等待的 offer 线程,目的也是为了减少 poll 线程对 tailLock 上锁次数,剩下等待的 offer 线程由这个 offer 线程间接唤醒

最终的代码为

public class BlockingQueue2<E> implements BlockingQueue<E> {

    private final E[] array;
    private int head = 0;
    private int tail = 0;
    private final AtomicInteger size = new AtomicInteger(0);
    ReentrantLock headLock = new ReentrantLock();
    Condition headWaits = headLock.newCondition();
    ReentrantLock tailLock = new ReentrantLock();
    Condition tailWaits = tailLock.newCondition();

    public BlockingQueue2(int capacity) {
        this.array = (E[]) new Object[capacity];
    }

    @Override
    public void offer(E e) throws InterruptedException {
        int c;
        tailLock.lockInterruptibly();
        try {
            while (isFull()) {
                tailWaits.await();
            }
            array[tail] = e;
            if (++tail == array.length) {
                tail = 0;
            }            
            c = size.getAndIncrement();
            // a. 队列不满, 但不是从满->不满, 由此offer线程唤醒其它offer线程
            if (c + 1 < array.length) {
                tailWaits.signal();
            }
        } finally {
            tailLock.unlock();
        }
        // b. 从0->不空, 由此offer线程唤醒等待的poll线程
        if (c == 0) {
            headLock.lock();
            try {
                headWaits.signal();
            } finally {
                headLock.unlock();
            }
        }
    }

    @Override
    public E poll() throws InterruptedException {
        E e;
        int c;
        headLock.lockInterruptibly();
        try {
            while (isEmpty()) {
                headWaits.await(); 
            }
            e = array[head]; 
            if (++head == array.length) {
                head = 0;
            }
            c = size.getAndDecrement();
            // b. 队列不空, 但不是从0变化到不空,由此poll线程通知其它poll线程
            if (c > 1) {
                headWaits.signal();
            }
        } finally {
            headLock.unlock();
        }
        // a. 从满->不满, 由此poll线程唤醒等待的offer线程
        if (c == array.length) {
            tailLock.lock();
            try {
                tailWaits.signal();
            } finally {
                tailLock.unlock();
            }
        }
        return e;
    }

    private boolean isEmpty() {
        return size.get() == 0;
    }

    private boolean isFull() {
        return size.get() == array.length;
    }

}

双锁实现的非常精巧,据说作者 Doug Lea 花了一年的时间才完善了此段代码

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/370814.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用绿联私有云Docker搭建自动化实时网页监控工具,实现降价提醒/RSS监控等

使用绿联私有云Docker搭建自动化实时网页监控工具&#xff0c;实现降价提醒/RSS监控等 哈喽小伙伴们好&#xff0c;我是Stark-C~ 之前老是有小伙伴们在评论区说我分享的Docker容器都是通过Docker run命令部署的&#xff0c;能不能照顾下像绿联私有云这种新势力NAS的新手用户&…

C# CAD界面-自定义工具栏(三)

运行环境 vs2022 c# cad2016 调试成功 一、引用 二、开发代码进行详细的说明 初始化与获取AutoCAD核心对象&#xff1a; Database db HostApplicationServices.WorkingDatabase;&#xff1a;这行代码获取当前工作中的AutoCAD数据库对象。在AutoCAD中&#xff0c;所有图形数…

【Git】01 Git介绍与安装

文章目录 一、版本控制系统二、Git三、Windows安装Git3.1 下载Git3.2 安装3.3 检查 四、Linux安装Git4.1 YUM安装4.2 源码安装 五、配置Git5.1 配置用户名和邮箱5.2 配置级别5.3 查看配置 六、总结 一、版本控制系统 版本控制系统&#xff0c;Version Control System&#xff…

【消息队列】kafka整理

kafka整理 整理kafka基本知识供回顾。

基于NSGA-II的深度迁移学习

深度迁移学习 迁移学习是一种机器学习技术&#xff0c;它允许一个预训练的模型被用作起点&#xff0c;在此基础上进行微调以适应新的任务或数据。其核心思想是利用从一个任务中学到的知识来帮助解决另一个相关的任务&#xff0c;即使这两个任务的数据分布不完全相同。这种方法…

vulnhub靶场之Thales

一.环境搭建 1.靶场描述 Description : Open your eyes and change your perspective includes 2 flags:user.txt and root.txt. Telegram: machineboy141 (for any hint) This works better with VIrtualBox rathe than VMware 2.靶场地址 https://www.vulnhub.com/entry/t…

年假作业3.0

1、选择题 BCDAA 2、填空题 15,27 15 11,10,13,12 3、改错题 1.缺少了要使用的命名空间&#xff0c;应在加上#include <iostream>的下一行添加using namespace std&#xff0c;void main(){}报错&#xff0c;C语言中main函数必须返回int改为&#xff1a;int main(…

海康IPC摄像机接入国标平台,发现一直不在线(离线)的处理方式

目 录 一、问题 二、问题分析 &#xff08;一&#xff09;常见设备离线问题的原因 &#xff08;二&#xff09;原因分析 三、问题查处 &#xff08;一&#xff09;设备端排查故障&#xff08;设备端自查&#xff09; 1、检查GB28181参数配置是否有误 2、…

vulhub中Apache APISIX Dashboard API权限绕过导致RCE(CVE-2021-45232)

Apache APISIX是一个动态、实时、高性能API网关&#xff0c;而Apache APISIX Dashboard是一个配套的前端面板。 Apache APISIX Dashboard 2.10.1版本前存在两个API/apisix/admin/migrate/export和/apisix/admin/migrate/import&#xff0c;他们没有经过droplet框架的权限验证&…

电动汽车充放电V2G模型(matlab代码)

目录 1 主要内容 1.1 模型背景 1.2 目标函数 1.3 约束条件 2 部分代码 3 效果图 4 下载链接 1 主要内容 本程序主要建立电动汽车充放电V2G模型&#xff0c;采用粒子群算法&#xff0c;在保证电动汽车用户出行需求的前提下&#xff0c;为了使工作区域电动汽车尽可能多的消…

PyTorch 2.2 中文官方教程(十四)

参数化教程 原文&#xff1a; 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 作者&#xff1a;Mario Lezcano 注意 点击这里下载完整示例代码 在本教程中&#xff0c;您将学习如何实现并使用此模式来对模型进行约束。这样做就像编写自己的nn.Module一样容易。 对深…

c#矩阵行列式计算//线程同步

using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;namespace 实现矩阵行列式计算 {internal class Program{static void Main(string[] args){//定义矩阵Console.WriteLine("矩阵是&#xff1a;&quo…

五、MyBatis 高级扩展

本章概要 Mapper 批量映射优化插件和分页插件 PageHelper 插件机制和 PageHelper 插件介绍PageHelper 插件使用 逆向工程和 MybatisX 插件 ORM 思维介绍逆向工程逆向工程插件 MyBatisX 使用 5.1 Mapper 批量映射优化 需求 Mapper 配置文件很多时&#xff0c;在全局配置文件…

【INTEL(ALTERA)】带有浮点单元 (FPU) Nios® V/g 处理器在 英特尔® Cyclone10 GX 设备中执行不正确的浮点运算

说明 由于 英特尔 Quartus Prime Pro Edition 软件版本 23.3 存在一个问题&#xff0c;当使用 Nios V/g 处理器并在 英特尔 Cyclone 10 GX 设备中启用 FPU 时&#xff0c;浮点运算无法按预期进行。 Nios V/g 处理器 – 启用浮点单元 解决方法 请勿在 英特尔 CycloneNios 10 G…

《Python 网络爬虫简易速速上手小册》第1章:Python 网络爬虫基础(2024 最新版)

文章目录 1.1 网络爬虫简介1.1.1 重点基础知识讲解1.1.2 重点案例&#xff1a;社交媒体数据分析1.1.3 拓展案例1&#xff1a;电商网站价格监控1.1.4 拓展案例2&#xff1a;新闻聚合服务 1.2 网络爬虫的工作原理1.2.1 重点基础知识讲解1.2.2 重点案例&#xff1a;股票市场数据采…

fastjson 导致的OOM

fastjson 导致的OOM 示例代码 public static void main(String[] args) throws Exception {try {List<Integer> list JSONObject.parseArray("[2023,2024", Integer.class);}catch (Exception e){System.err.println("error");}System.out.println…

Qos--优先级映射关系

precedence字段 根据RFC791定义,IP报文头 ToS(Type of Service)域由 8个比特组成,其中 3个比特的Precedence字段标识了 IP报文的优先级,Precedence在报文中的位置如图1所示。 比特0~2表示Precedence字段,代表报文传输的 8个优先级,按照优先级从高到低顺序取值为7、6、…

word表格文字上下居中怎么设置?简单教程分享!

“我在使用Word编辑表格时&#xff0c;想让文字上下居中对齐&#xff0c;但是不知道应该怎么操作&#xff0c;请问大家有什么比较简单实用的操作方法吗&#xff1f;” 在使用Word时&#xff0c;为了提高文档的视觉效果和可读性&#xff0c;很多用户会选择将表格文字上下居中&am…

华为突然官宣:新版鸿蒙系统,正式发布

华为&#xff0c;一家始终引领科技创新潮流的全球性企业&#xff0c;近日再次引发行业震动——全新HarmonyOS NEXT&#xff0c;被誉为“纯血版鸿蒙”的操作系统正式官宣。这是华为在操作系统领域迈出的坚实且具有突破性的一步&#xff0c;标志着华为正逐步摆脱对安卓生态系统的…

HTTP学习

HTTP学习 HTTP 协议是 Hyper Text Transfer Protocol&#xff08;超文本传输协议&#xff09;的缩写&#xff0c;是用于从万维网&#xff08; WWW:World Wide Web &#xff09;服务器传输超文本到本地浏览器的传送协议。 HTTP 是一个基于 TCP/IP 通信协议来传递数据&#xff…