数据结构与算法——Java实现 31.阻塞队列

                        —— 24.10.8

一、问题提出

目前队列存在的问题

1.很多场景要求分离生产者、消费者两个角色、它们需要由不同的线程来担当，而之前的实现根本没有考虑线程安全问题

2.poll方法，队列为空，那么在之前的实现里会返回null，如果就是硬要拿到一个元素呢?以现在的实现只能不断循环尝试

3.offer方法，队列为满，那么在之前的实现里会返回false，如果就是硬要塞入一个元素呢?以现在的实现只能不断循环尝试

4.指令交错，多个线程会造成混乱效果

二、解决方法

 为解决线程不安全问题，需要给线程加锁，使线程局部阻塞

用条件变量让 poll 或 offer 线程进入等待 状态，而不是不断循环尝试，让CPU空转

三、单锁实现

Java中两种锁的选择

① synchronized：关键字，功能少

② ReentrantLock：可重入锁，功能丰富

lock() 加锁

unlock() 解锁

lockInterruptibly() 加锁（可在阻塞时打断，提前唤醒）

offer方法实现

if判断

问题

从 tailWaits 中唤醒的线程，会与新来的 offer 的线程争抢锁，谁能抢到是不一定的，如果后者先抢到，就会导致条件又发生变化

这种情况称之为虚假唤醒，唤醒后应该重新检查条件，看是不是得重新进入等待

    public void offer(String e) throws InterruptedException {// 加锁，可重入锁阻塞时可打断方法（可被强制唤醒）lock.lockInterruptibly();try {// 判断是否为满if (isFull()){// 队列满时，使offer线程阻塞,直到poll线程取走后，有位置时再恢复运行// tail.signal() 唤醒线程tailWaits.await();}array[tail] = e;if (++tail == array.length){tail = 0;}size++;}finally {// 解锁lock.unlock();}}
import java.util.Arrays;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;public class TestThreadUnsafe {private final String[] array = new String[10];// 尾指针private int tail = 0;// 元素个数private int size = 0;// 创建一个可重入锁对象ReentrantLock lock = new ReentrantLock();// 条件变量对象（集合线程）Condition tailWaits = lock.newCondition();public void offer(String e) throws InterruptedException {// 加锁，可重入锁阻塞时可打断方法（可被强制唤醒）lock.lockInterruptibly();try {// 判断是否为满if (isFull()){// 队列满时，使offer线程阻塞,直到poll线程取走后，有位置时再恢复运行// tail.signal() 唤醒线程tailWaits.await();}array[tail] = e;if (++tail == array.length){tail = 0;}size++;}finally {// 解锁lock.unlock();}}public void poll(String e) throws InterruptedException {}@Overridepublic String toString() {return Arrays.toString(array);}private boolean isFull(){return size == array.length;}private boolean isEmpty(){return size == 0;}public static void main(String[] args) throws InterruptedException{TestThreadUnsafe queue = new TestThreadUnsafe();for (int i = 0; i < 10; i++) {queue.offer("e"+i);}new Thread(()->{try {System.out.println(Thread.currentThread().getName()+"添加元素之前");queue.offer("e10");System.out.println(Thread.currentThread().getName()+"添加元素成功");} catch (InterruptedException e) {throw new RuntimeException(e);}},"t1").start();new Thread(()->{System.out.println("开始唤醒");try{queue.lock.lockInterruptibly();queue.tailWaits.signal();} catch (InterruptedException e) {throw new RuntimeException(e);}finally {queue.lock.unlock();}},"t2").start();}
}

while判断 

解决了虚假唤醒的问题

    @Overridepublic void offer(E e) throws InterruptedException {    // poll 等待队列非空lock.lockInterruptibly();try{while (isFull()){// 放在条件变量等待tailWaits.await();}array[tail] = e;if (++tail == array.length){tail = 0;}size++;// 唤醒等待线程headWaits.signal();}finally {lock.unlock();}}
import java.util.Arrays;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;public class BlockingQueue1<E> implements BlockingQueue<E> {private final E[] array;private int head;private int tail;private int size;// 根据容量创造一个数组public BlockingQueue1(int capacity) {array = (E[]) new Object[capacity];}// 加可重入锁private ReentrantLock lock = new ReentrantLock();// 配合poll方法条件变量，在队列头部删除private Condition headWaits = lock.newCondition();// 配合offer方法条件变量，在队列尾部加入private Condition tailWaits = lock.newCondition();// 判空private boolean isEmpty(){return head == tail;}// 判满private boolean isFull(){return size == array.length;}@Overridepublic String toString() {return "array=" + Arrays.toString(array);}@Overridepublic void offer(E e) throws InterruptedException {    // poll 等待队列非空lock.lockInterruptibly();try{while (isFull()){// 放在条件变量等待tailWaits.await();}array[tail] = e;if (++tail == array.length){tail = 0;}size++;// 唤醒等待线程headWaits.signal();}finally {lock.unlock();}}@Overridepublic boolean offer(E e, long timeout) throws InterruptedException {lock.lockInterruptibly();try{// 将毫秒时间转换为纳秒时间long t = TimeUnit.MILLISECONDS.toNanos(timeout);while (isFull()){if (t<=0){return false;}// 最多等待多少纳秒tailWaits.awaitNanos(t);}array[tail] = e;if (++tail == array.length){tail = 0;}size++;// 唤醒等待线程headWaits.signal();return true;}finally {lock.unlock();}}@Overridepublic E poll() throws InterruptedException {lock.lockInterruptibly();try {while (isEmpty()){headWaits.await();}E e = array[head];array[head] = null;if (++head == array.length){head = 0;}size--;tailWaits.signal();return e;}finally {lock.unlock();}}
}

 main函数

public class TestBlockingQueue1 {public static void main(String[] args) throws InterruptedException {BlockingQueue1<String> queue = new BlockingQueue1<>(3);Thread t1 = new Thread(() -> {try {System.out.println(System.currentTimeMillis()+" begin ");queue.offer("任务1");System.out.println(queue);queue.offer("任务2");System.out.println(queue);queue.offer("任务3");System.out.println(queue);queue.offer("任务4",5000);System.out.println(queue);System.out.println(System.currentTimeMillis() + " end ");} catch (InterruptedException e) {throw new RuntimeException(e);}},"生产者");t1.start();Thread.sleep(2000);queue.poll();}
}

 

四、双锁实现

单锁问题：

单锁实现的缺陷：两个线程用了同一把锁，一个执行时，另一个就需阻塞，而offer方法添加元素和poll方法取走元素使用了同一把锁，这样两个线程不能同时执行，两方法相互阻塞

解决方法：

offer方法主要操作尾指针，poll方法主要操作头指针，将offer方法和poll方法分别添加一个锁，用两把锁分别保护头指针和尾指针，从而分别保护offer和poll两个方法

代码实现

import java.util.Arrays;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;public class BlockingQueue2<E> implements BlockingQueue<E> {private final E[] array;private int head;private int tail;private int size;// tailLock给offer方法入队用,Condition分别创建两个等待的条件变量private ReentrantLock tailLock = new ReentrantLock();private Condition notEmpty = tailLock.newCondition();// headLock给poll方法出队用private ReentrantLock headLock = new ReentrantLock();private Condition notFull = headLock.newCondition();public BlockingQueue2(int capacity) {this.array = (E[]) new Object[capacity];}// 判空private boolean isEmpty(){return size == 0;}// 判满private boolean isFull(){return size == array.length;}@Overridepublic String toString() {return "array=" + Arrays.toString(array);}@Overridepublic void offer(E e) throws InterruptedException {// 加锁tailLock.lockInterruptibly();try{while (isFull()) {notEmpty.await();}array[tail] = e;if (++tail == array.length) {tail = 0;}size++;}finally {tailLock.unlock();}}@Overridepublic boolean offer(E e, long timeout) throws InterruptedException {return false;}@Overridepublic E poll() throws InterruptedException {// 加锁headLock.lockInterruptibly();try{while (isEmpty()){notEmpty.await();}E e = array[head];array[head] = null;if (++head == array.length) {head = 0;}size--;return e;}finally {headLock.unlock();}}public static void main(String[] args) throws InterruptedException {BlockingQueue2<String> queue = new BlockingQueue2<>(3);queue.offer("任务1");new Thread(()->{try {queue.offer("任务2");} catch (InterruptedException e) {throw new RuntimeException(e);}},"offer").start();new Thread(()->{try {System.out.println(queue.poll());} catch (InterruptedException e) {throw new RuntimeException(e);}},"poll").start();}
}

size自增/自减问题

size的自增自减不能保障安全，size自增自减在多个线程同时执行时可能遇到冲突

解决方法

用原子变量AtomicInteger类型保证安全

getAndIncrement 自增方法，能保证线程安全

getAndDecrement 自减方法，能保证线程安全

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

构建MySQL健康检查Web应用

构建MySQL健康检查Web应用

构建MySQL健康检查Web应用 在这里将探讨如何将MySQL健康检查功能转换为一个功能完整的Web应用。这个应用允许用户通过简单的Web界面执行MySQL健康检查&#xff0c;并查看详细的结果。我们将逐步介绍代码实现、改进过程以及如何设置和运行这个应用。 1. MySQL健康检查类 首先…
阅读更多...
codetop标签双指针题目大全解析(二)，双指针刷穿地心！！！！！

codetop标签双指针题目大全解析(二)，双指针刷穿地心！！！！！

复习比学习更重要&#xff0c;如果忘了就跟没学是一样的 1.和为k的子数组2.统计[优美子数组]3.区间列表的交集4.将x减到0的最小操作5.替换子串得到平衡字符串6.划分字母区间7.分隔链表8.通过删除字母匹配到字典里最长单词9.寻找目标值-二维数组10.至多包含两个不同字符的最长子…
阅读更多...
麒麟系统串口配置篇

麒麟系统串口配置篇

麒麟系统串口配置篇 1.配置串口驱动&#xff08;编译/动态加载串口&#xff09; 解压文件夹,然后在解压后的文件夹所在目录&#xff0c;右键选择打开终端&#xff0c;依次执行以下命令&#xff1a; 以麒麟系统下的CH341串口驱动为例&#xff0c;解压CH341SER_LINUX.zip sudo…
阅读更多...
2024_10_8 系统进展

2024_10_8 系统进展

改进位置 发现是label_api里藏了我需要改进的东西 settings.py 数据库 我这边电脑上使用的是windows 192 vue.config.js 陈家强是这样设置的 module.exports {publicPath: process.env.NODE_ENV production? /: /,assetsDir: static,// css: {// extract: false// },…
阅读更多...
【C++ 11】for 基于范围的循环

【C++ 11】for 基于范围的循环

文章目录 【 1. 基本用法 】【 2. for 新格式的应用 】2.1 for 遍历字符串2.2 for 遍历列表2.3 for 遍历的同时修改元素 问题背景 C 11标准之前&#xff08;C 98/03 标准&#xff09;&#xff0c;如果要用 for 循环语句遍历一个数组或者容器&#xff0c;只能套用如下结构&#…
阅读更多...
“我养你啊“英语怎么说？别说成I raise you!成人学英语到蓝天广场附近

“我养你啊“英语怎么说？别说成I raise you!成人学英语到蓝天广场附近

“我养你啊”这句经典台词出自周星驰自导自演的电影《喜剧之王》。在这部电影中&#xff0c;周星驰饰演的尹天仇对张柏芝饰演的柳飘飘说出了这句深情而动人的台词。这句台词出现在柳飘飘即将离去之时&#xff0c;尹天仇鼓起勇气&#xff0c;用它作为对柳飘飘个人困境的承诺&…
阅读更多...
VIP与MPIO，备胎管理谁更强

VIP与MPIO，备胎管理谁更强

我爱上班&#xff0c;风雨无阻 大家每天去上班&#xff0c;不可能只有一条路线 可以地铁、也可以开车或公交 万一地铁停运或车子限行&#xff0c;至少还有其他线路选择 企业级存储也是如此 关键业务的存储访问一般有多条路径 网络或单个存储设备故障后 访问路径会自动切换…
阅读更多...
集合框架05：List接口使用、List实现类、ArrayList使用

集合框架05：List接口使用、List实现类、ArrayList使用

视频链接&#xff1a;13.11 ArrayList使用_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1zD4y1Q7Fw?p11&vd_sourceb5775c3a4ea16a5306db9c7c1c1486b5 1.List接口使用代码举例 package com.yundait.Demo01;import java.util.ArrayList; import java.util.List;pu…
阅读更多...
轻松掌握IP代理服务器设置方法，网络冲浪更自如

轻松掌握IP代理服务器设置方法，网络冲浪更自如

在数字化时代&#xff0c;互联网就像是一片浩瀚的海洋&#xff0c;而IP代理服务器就如同我们在这片海洋中航行的指南针。通过使用代理IP&#xff0c;我们可以更方便地访问全球网络资源&#xff0c;提升网络安全性。本文将为您详细介绍IP代理服务器的设置方法&#xff0c;让您在…
阅读更多...
指针——指针数组、数组指针

指针——指针数组、数组指针

&#xff08;一&#xff09;指针数组 1、本质&#xff1a;指针数组的本质任然是数组 2、基本格式&#xff1a;int* arr[5] 3、应用&#xff1a;如尝试使用指针来模拟二维数组 先来看代码 #include<stdio.h> //指针数组——模拟实现二维数组 int main() {int a[5] {…
阅读更多...
本科毕业论文不会写怎么办，论文查重显示80%多

本科毕业论文不会写怎么办，论文查重显示80%多

如果本科毕业论文不会写且查重显示 80% 多&#xff0c;可以从以下几个方面着手解决&#xff1a; 一、调整心态&#xff0c;正视问题 首先&#xff0c;不要惊慌和焦虑。高重复率并不意味着无法挽救&#xff0c;要相信自己有能力解决这个问题。把它看作是一个学习和提升的机会&a…
阅读更多...
Matlab实现海鸥优化算法优化回声状态网络模型 （SOA-ESN）（附源码）

Matlab实现海鸥优化算法优化回声状态网络模型 （SOA-ESN）（附源码）

目录 1.内容介绍 2部分代码 3.实验结果 4.内容获取 1内容介绍 海鸥优化算法&#xff08;Seagull Optimization Algorithm, SOA&#xff09;是一种受海鸥觅食和飞行行为启发的群体智能优化算法。SOA通过模拟海鸥在空中搜寻食物、聚集和分散的行为模式&#xff0c;来探索和开发…
阅读更多...
Leecode刷题之路第13天之罗马数字转整数

Leecode刷题之路第13天之罗马数字转整数

题目出处 13-罗马数字转整数-题目出处 题目描述 个人解法 思路&#xff1a; todo 代码示例&#xff1a;&#xff08;Java&#xff09; todo复杂度分析 todo 官方解法 13-罗马数字转整数-官方解法 方法1&#xff1a;模拟 思路&#xff1a; 代码示例&#xff1a;&#xff0…
阅读更多...
ctf.bugku - game1

ctf.bugku - game1

题目来源&#xff1a; game1 - Bugku CTF 访问页面&#xff0c;让玩游戏 得到100分&#xff0c;没拿到flag 查看页面源码&#xff0c; GET请求带有 score、IP、sign 三个参数&#xff0c;最后的flag 应该跟分数有关&#xff1b; 给了score一个99999分数&#xff0c; sign 为 …
阅读更多...
dotnet7==windows ZIP方式安装和web demo和打包

dotnet7==windows ZIP方式安装和web demo和打包

下载ZIP Download .NET 7.0 (Linux, macOS, and Windows) 解压 创建项目 mkdir MyWebApp cd MyWebApp "C:\Users\90816\Downloads\dotnet-sdk-7.0.317-win-x64\dotnet.exe" new webapp -n MyWebApp 运行项目 "C:\Users\90816\Downloads\dotnet-sdk-7.0.317-…
阅读更多...
同城O2O系统源码与跑腿配送平台的架构设计与开发方案详解

同城O2O系统源码与跑腿配送平台的架构设计与开发方案详解

今天&#xff0c;笔者将与您一同深入探讨同城O2O系统的源码及跑腿配送平台的架构设计与开发方案&#xff0c;助力开发者和企业在这一领域的实践与探索。 一、O2O系统概述 在同城O2O模式中&#xff0c;用户可以通过手机应用或网页平台下单&#xff0c;而配送员则根据订单信息迅…
阅读更多...
QT 优化登录框

QT 优化登录框

作业 优化登录框&#xff1a; 当用户点击取消按钮&#xff0c;弹出问题对话框&#xff0c;询问是否要确定退出登录&#xff0c;并提供两个按钮&#xff0c;yes|No&#xff0c;如果用户点击的Yes&#xff0c;则关闭对话框&#xff0c;如果用户点击的No&#xff0c;则继续登录 …
阅读更多...
信息安全——应急响应

信息安全——应急响应

应急响应部分 1、提交攻击者的IP地址 简单过一遍apache日志&#xff0c;less /var/log/apache2/access.log.1 很明显的可以发现大量的扫描流量&#xff0c;如下&#xff1a; 大量的并发连接&#xff0c;且访问资源均返回404&#xff0c;且UA不正常&#xff0c;从这里可以得…
阅读更多...
【重学 MySQL】六十二、非空约束的使用

【重学 MySQL】六十二、非空约束的使用

【重学 MySQL】六十二、非空约束的使用 定义目的关键字特点作用创建非空约束删除非空约束注意事项 在MySQL中&#xff0c;非空约束&#xff08;NOT NULL Constraint&#xff09;是一种用于确保表中某列不允许为空值的数据库约束。 定义 非空约束&#xff08;NOT NULL Constra…
阅读更多...
Prometheus + Grafana 监控 MySQL 数据库

Prometheus + Grafana 监控 MySQL 数据库

文章目录 1、前置介绍2、搭建流程2.1、安装 Docker2.2、安装 MySQL2.3、安装 MySQL Exporter2.4、安装 Prometheus2.5、安装 Grafana 1、前置介绍 本次监控平台搭建&#xff0c;我使用2台阿里云服务器来完成本次的搭建部署操作&#xff0c;配置如下&#xff1a; 阿里云ECS1&am…
阅读更多...
最新文章

Copyright @ 2022~2023