无锁模式的Vector

时间:2022-09-01 14:44:09

这两天学习无锁的并发模式,发现相比于传统的 同步加锁相比,有两点好处
1.无锁 模式 相比于 传统的 同步加锁  提高了性能

2.无锁模式 是天然的死锁免疫

下来介绍无锁的Vector--- LockFreeVector

它的结构是:

private final AtomicReferenceArray<AtomicReferenceArray<E>> buckets;

从这里我们可以看到,它的内部是采用的是 无锁的引用数组, 数组嵌套数组

相当于一个二维数组,它的大小可以动态的进行扩展,

为了更有序的读写数组,定义了一个Descriptor的静态内部类。它的作用是使用CAS操作写入新数据。

它定义了

private static final int FIRST_BUCKET_SIZE = 8;

/**
* number of buckets. 30 will allow 8*(2^30-1) elements
*/
private static final int N_BUCKET = 30;
FIRST_BUCKET_SIZE:为第一个数组的长度

N_BUCKET 整个二维数组最大可扩转至30

每次的扩展是成倍的增加,即:第一个数组长度为8,第二个为8<<1,第三个为8<<2 ......第30个为 8<<29

贡献源码:

/*
* Copyright (c) 2007 IBM Corporation
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/ package main.java.org.amino.ds.lockfree; import java.util.AbstractList;
import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicReferenceArray; /**
* It is a thread safe and lock-free vector.
* This class implement algorithm from:<br>
*
* Lock-free Dynamically Resizable Arrays <br>
*
* Damian Dechev, Peter Pirkelbauer, and Bjarne Stroustrup<br>
* Texas A&M University College Station, TX 77843-3112<br>
* {dechev, peter.pirkelbauer}@tamu.edu, bs@cs.tamu.edu
*
*
* @author Zhi Gan
*
* @param <E> type of element in the vector
*
*/
public class LockFreeVector<E> extends AbstractList<E> {
private static final boolean debug = false;
/**
* Size of the first bucket. sizeof(bucket[i+1])=2*sizeof(bucket[i])
*/
private static final int FIRST_BUCKET_SIZE = 8; /**
* number of buckets. 30 will allow 8*(2^30-1) elements
*/
private static final int N_BUCKET = 30; /**
* We will have at most N_BUCKET number of buckets. And we have
* sizeof(buckets.get(i))=FIRST_BUCKET_SIZE**(i+1)
*/
private final AtomicReferenceArray<AtomicReferenceArray<E>> buckets; /**
* @author ganzhi
*
* @param <E>
*/
static class WriteDescriptor<E> {
public E oldV;
public E newV;
public AtomicReferenceArray<E> addr;
public int addr_ind; /**
* Creating a new descriptor.
*
* @param addr Operation address
* @param addr_ind Index of address
* @param oldV old operand
* @param newV new operand
*/
public WriteDescriptor(AtomicReferenceArray<E> addr, int addr_ind,
E oldV, E newV) {
this.addr = addr;
this.addr_ind = addr_ind;
this.oldV = oldV;
this.newV = newV;
} /**
* set newV.
*/
public void doIt() {
addr.compareAndSet(addr_ind, oldV, newV);
}
} /**
* @author ganzhi
*
* @param <E>
*/
static class Descriptor<E> {
public int size;
volatile WriteDescriptor<E> writeop; /**
* Create a new descriptor.
*
* @param size Size of the vector
* @param writeop Executor write operation
*/
public Descriptor(int size, WriteDescriptor<E> writeop) {
this.size = size;
this.writeop = writeop;
} /**
*
*/
public void completeWrite() {
WriteDescriptor<E> tmpOp = writeop;
if (tmpOp != null) {
tmpOp.doIt();
writeop = null; // this is safe since all write to writeop use
// null as r_value.
}
}
} private AtomicReference<Descriptor<E>> descriptor;
private static final int zeroNumFirst = Integer
.numberOfLeadingZeros(FIRST_BUCKET_SIZE);; /**
* Constructor.
*/
public LockFreeVector() {
buckets = new AtomicReferenceArray<AtomicReferenceArray<E>>(N_BUCKET);
buckets.set(0, new AtomicReferenceArray<E>(FIRST_BUCKET_SIZE));
descriptor = new AtomicReference<Descriptor<E>>(new Descriptor<E>(0,
null));
} /**
* add e at the end of vector.
*
* @param e
* element added
*/
public void push_back(E e) {
Descriptor<E> desc;
Descriptor<E> newd;
do {
desc = descriptor.get();
desc.completeWrite();
//desc.size Vector 本身的大小
//FIRST_BUCKET_SIZE 第一个一位数组的大小
int pos = desc.size + FIRST_BUCKET_SIZE;
int zeroNumPos = Integer.numberOfLeadingZeros(pos); // 取出pos 的前导领
//zeroNumFirst 为FIRST_BUCKET_SIZE 的前导领
int bucketInd = zeroNumFirst - zeroNumPos; //哪个一位数组
//判断这个一维数组是否已经启用
if (buckets.get(bucketInd) == null) {
//newLen 一维数组的长度
int newLen = 2 * buckets.get(bucketInd - 1).length();
if (debug)
System.out.println("New Length is:" + newLen);
buckets.compareAndSet(bucketInd, null,
new AtomicReferenceArray<E>(newLen));
} int idx = (0x80000000>>>zeroNumPos) ^ pos; //在这个一位数组中,我在哪个位置
newd = new Descriptor<E>(desc.size + 1, new WriteDescriptor<E>(
buckets.get(bucketInd), idx, null, e));
} while (!descriptor.compareAndSet(desc, newd));
descriptor.get().completeWrite();
} /**
* Remove the last element in the vector.
*
* @return element removed
*/
public E pop_back() {
Descriptor<E> desc;
Descriptor<E> newd;
E elem;
do {
desc = descriptor.get();
desc.completeWrite(); int pos = desc.size + FIRST_BUCKET_SIZE - 1;
int bucketInd = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
- Integer.numberOfLeadingZeros(pos);
int idx = Integer.highestOneBit(pos) ^ pos;
elem = buckets.get(bucketInd).get(idx);
newd = new Descriptor<E>(desc.size - 1, null);
} while (!descriptor.compareAndSet(desc, newd)); return elem;
} /**
* Get element with the index.
*
* @param index
* index
* @return element with the index
*/
@Override
public E get(int index) {
int pos = index + FIRST_BUCKET_SIZE;
int zeroNumPos = Integer.numberOfLeadingZeros(pos);
int bucketInd = zeroNumFirst - zeroNumPos;
int idx = (0x80000000>>>zeroNumPos) ^ pos;
return buckets.get(bucketInd).get(idx);
} /**
* Set the element with index to e.
*
* @param index
* index of element to be reset
* @param e
* element to set
*/
/**
* {@inheritDoc}
*/
public E set(int index, E e) {
int pos = index + FIRST_BUCKET_SIZE;
int bucketInd = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
- Integer.numberOfLeadingZeros(pos);
int idx = Integer.highestOneBit(pos) ^ pos;
AtomicReferenceArray<E> bucket = buckets.get(bucketInd);
while (true) {
E oldV = bucket.get(idx);
if (bucket.compareAndSet(idx, oldV, e))
return oldV;
}
} /**
* reserve more space.
*
* @param newSize
* new size be reserved
*/
public void reserve(int newSize) {
int size = descriptor.get().size;
int pos = size + FIRST_BUCKET_SIZE - 1;
int i = Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
- Integer.numberOfLeadingZeros(pos);
if (i < 1)
i = 1; int initialSize = buckets.get(i - 1).length();
while (i < Integer.numberOfLeadingZeros(FIRST_BUCKET_SIZE)
- Integer.numberOfLeadingZeros(newSize + FIRST_BUCKET_SIZE - 1)) {
i++;
initialSize *= FIRST_BUCKET_SIZE;
buckets.compareAndSet(i, null, new AtomicReferenceArray<E>(
initialSize));
}
} /**
* size of vector.
*
* @return size of vector
*/
public int size() {
return descriptor.get().size;
} /**
* {@inheritDoc}
*/
@Override
public boolean add(E object) {
push_back(object);
return true;
}
}

参考:http://www.shaoqun.com/a/197387.aspx

源码部分,我只着重写了push_back这个方法的注释。

无锁模式的Vector的更多相关文章

  1. CAS实现无锁模式

    用多线程实现一个数字的自增长到1000000,分别用无锁模式和锁模式来实现代码. 1.使用ReentrantLock. package test; import java.util.concurren ...

  2. CAS无锁模式

    一.java内存模型:JMM 在内存模型当中定义一个主内存,所有声明的实例变量都存在于主内存当中,主内存的数据会共享给所有线程,每一个线程有一个块工作内存,工作内存当中主内存数据的副本当更新数据时,会 ...

  3. CAS无锁机制原理

    原子类 java.util.concurrent.atomic包:原子类的小工具包,支持在单个变量上解除锁的线程安全编程 原子变量类相当于一种泛化的 volatile 变量,能够支持原子的和有条件的读 ...

  4. 无锁版以时间为GUID的方法

    之前的博客 将时间作为GUID的方法 中,我使用了锁.我在实际的使用中,错将锁的释放放在了if语句中,这纯粹是我的失误,导致了很严重的错误.因此我在想是否有无锁的将时间作为GUID的方式,答案是使用I ...

  5. 【实战Java高并发程序设计6】挑战无锁算法:无锁的Vector实现

    [实战Java高并发程序设计 1]Java中的指针:Unsafe类 [实战Java高并发程序设计 2]无锁的对象引用:AtomicReference [实战Java高并发程序设计 3]带有时间戳的对象 ...

  6. &lbrack;转&rsqb;透过 Linux 内核看无锁编程

    非阻塞型同步 (Non-blocking Synchronization) 简介 如何正确有效的保护共享数据是编写并行程序必须面临的一个难题,通常的手段就是同步.同步可分为阻塞型同步(Blocking ...

  7. 非阻塞同步算法与CAS&lpar;Compare and Swap&rpar;无锁算法

    锁(lock)的代价 锁是用来做并发最简单的方式,当然其代价也是最高的.内核态的锁的时候需要操作系统进行一次上下文切换,加锁.释放锁会导致比较多的上下文切换和调度延时,等待锁的线程会被挂起直至锁释放. ...

  8. 无锁编程以及CAS

    无锁编程 / lock-free / 非阻塞同步 无锁编程,即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步(Non-blocking Sy ...

  9. 实现无锁的栈与队列&lpar;5&rpar;:Hazard Pointer

    两年多以前随手写了点与 lock free 相关的笔记:1,2,3,4,质量都不是很高其实(读者见谅),但两年来陆陆续续竟也有些阅读量了(可见剑走偏锋的技巧是多容易吸引眼球).笔记当中在解决内存释放和 ...

随机推荐

  1. 如何在网页标题栏加入logo图标?

    标题栏: <link rel="icon" href="ico地址" type="image/x-icon">收藏夹:<l ...

  2. Winform下richtextbox截图实现

    #region 根据richtextbox创建GDI+ private void DrawGDI(RichTextBox rich,Panel panl,PictureBox p2) { rich.U ...

  3. ArrayList、LinkedList、Vector的区别

    Arraylist和Vector是采用数组方式存储数据,此数组元素数大于实际存储的数据以便增加插入元素,都允许直接序号索引元素,但是插入数据要涉及到数组元素移动等内存操作,所以插入数据慢,查找有下标, ...

  4. &lpar;window&comma;parent&comma;opener&comma;top&rpar;&period;location&period;reload方法汇总

    今天在火狐浏览器上碰到个bug,调用parent.location.reload()时只刷新子页面,没有整个浏览器刷新,谷歌上没有问题,网上搜了一下 改成parent.location.reload( ...

  5. 阿里云RDS SQL Server 2008 R2 使用本地SQL备份文件还原全过程

    最近公司准备全面转向阿里云,写了好几个方案,最终决定购买一台ECS和一台RDS搭配使用.开始对阿里的RDS产品陌生,加上公司的数据库文件近20G,诸多担心,生怕产品买来了不能用,给公司造成损失.后来联 ...

  6. api-gateway实践(10)新服务网关 - OpenID Connect

    网关指南: https://help.aliyun.com/document_detail/29487.html?spm=5176.doc48835.6.550.23Oqbl 网关控制台: https ...

  7. ado&period;net的简单数据库操作(三)——简单增删改查的实际应用

    果然,在犯困的时候就该写写博客,写博客就不困了,哈哈! 上篇我记录了自己的SqlHelper的开发过程,今天记录一下如何使用这个sqlhelper书写一个具有简单增删改查的小实例啦. 实例描述:在数据 ...

  8. Mcafee&lpar;麦咖啡&rpar; 无法升级的解决办法&lpar;威流验证&rpar;

    McAfee时会遇到更新失败的情况.为了解决这个问题,你需要做如下设置:1.“运行”>“dcomcnfg.exe”2.双击“组件服务>计算机>我的电脑”3.展开“DCOM配置”,打开 ...

  9. Gym 100247C&Tab;Victor&&num;39&semi;s Research(有多少区间之和为S)

    https://vjudge.net/problem/Gym-100247C 题意: 给出一串数,求有多少个区间的和正好等于S. 思路:计算处前缀和,并且用map维护一下每个前缀和出现的次数.这样接下 ...

  10. 让Label等控件支持HTML格式的代码? 使用NSAttributedString&colon;

    > 如何让Label等控件支持HTML格式的代码? 使用NSAttributedString: NSString *htmlString = @"<div>Tate< ...