锁&锁与指令原子操作的关系 & cas_Queue

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

锁

锁以及信号量对大部分人来说都是非常熟悉的，特别是常用的mutex。锁有很多种，互斥锁，自旋锁，读写锁，顺序锁，等等，这里就只介绍常见到的，

互斥锁

这个是最常用的，win32：CreateMutex-WaitForSingleObject-ReleaseMutex，linux的pthread_mutex_lock-pthread_mutex_unlock，c#的lock和Monitor，java的lock，这些都是互斥锁。互斥锁的作用大家都知道，是让一段代码同时只能有一个线程运行，

自旋锁

不常用，linux的pthread_spin系列函数就是自旋锁，（网上很多用原子操作写的自旋锁），作用和互斥锁大同小异。

信号量

win下的CreateSemaphore、OpenSemaphore、ReleaseSemaphore、WaitForSingleObject，linux也有同样的semaphore系列，还有c#的AutoResetEvent或者semaphore。这个用的也很多，信号两个状态，阻塞和通过，作用是保证多线程代码的业务顺序！

先唠一唠这些锁的原理，（为什么我把信号量也归结于锁？）

首先互斥锁，互斥锁实际上是由原子操作来实现的，

比如，当变量A为0的时候为非锁，为1的时候为锁，当第一个线程将变量A从0变为1（原子操作）成功的时候，就相当于获取锁成功了，另外的线程再次获取锁的时候发现A为1了，（或者说两个线程同时获取锁->原子操作，某一个会失败），表示获取锁失败，当第一个线程用完了，就释放锁，将A=0（原子操作）。

互斥锁的特点是，当锁获取失败了，当前代码上下文（线程）会休眠，并且把当前线程添加到这个内核维护的互斥锁的链表里，当后面的锁再次获取失败，也是将当前线程和执行信息放到这个链表里。当前占用的互斥锁的人用完了锁，内核会抽取互斥锁等待链表上的下一个线程开始唤醒继续执行，当内核链表上为空，就是没人抢锁了，就将锁状态设置为非锁，以次类推~

然后呢，我们讲自旋锁，自旋锁很简单，他和互斥锁大同小异，区别就是不休眠，当获取锁失败了，就一直while（获取），一直到成功，所以，自旋锁在大部分场景都是不适用的，因为获取锁的时间里，cpu一直是100%的！！

最后讲信号量，上面问为什么我将信号量也归结于锁这一类？

因为信号量也是原子操作来实现的！道理和互斥锁一样的，信号量也有一个链表，当等待信号的时候，系统也是把当前线程休眠，把线程和代码执行信息存储到这个信号量的链表里，当内核接受到信号的时候，就把这个信号量上的所有等待线程激活运行，这就是信号量！

原子操作

到底什么是原子操作？

百度百科所谓原子操作是指不会被线程调度机制打断的操作；这种操作一旦开始，就一直运行到结束，中间不会有任何 context switch （切换到另一个线程）。

所以，原子操作保证了多个线程对内存操作某个值得准确性！那么原子操作具体如何实现的？

首先是inter cpu，熟悉汇编的人都知道，inter指令集有个lock，如果某个指令集前面加个lock，那么在多核状态下，某个核执行到这个前面加lock的指令的时候，inter会让总线锁住，当这个核把这个指令执行完了，再开启总线！这是一种最最底层的锁！！

比如 lock cmpxchg dword ptr [rcx],edx cmpxchg这个指令就被加锁了！

inter指令参考可查阅http://www.intel.cn/content/www/cn/zh/processors/architectures-software-developer-manuals.html

来自IA-32券3：

HLT 指令(停止处理器)停止处理器直至接收到一个启用中断(比如 NMI 或 SMI，正常情况下这些都是开启的)、调试异常、BINIT#信号、INIT#信号或 RESET#信号。处理器产生一个特殊的总线周期以表明进入停止模式。硬件对这个信号的响应有好几个方面。前面板上的指示灯会打亮，产生一个记录诊断信息的 NMI 中断，调用复位初始化过程(注意 BINIT#引脚是在 Pentium Pro 处理器引入的)。如果停机过程中有非唤醒事件（比如 A20M#中断）未处理，它们将在唤醒停机事件处理之后的进行处理。

在修改内存操作时，使用 LOCK 前缀去调用加锁的读-修改-写操作(原子的)。这种机制用于多处理器系统中处理器之间进行可靠的通讯，具体描述如下：在 Pentium 和早期的 IA-32 处理器中，LOCK 前缀会使处理器执行当前指令时产生一个 LOCK#信号，这总是引起显式总线锁定出现。在 Pentium 4、Intel Xeon 和 P6 系列处理器中，加锁操作是由高速缓存锁或总线锁来处理。如果内存访问有高速缓存且只影响一个单独的高速缓存线，那么操作中就会调用高速缓存锁，而系统总线和系统内存中的实际内存区域不会被锁定。同时，这条总线上的其它 Pentium 4、Intel Xeon 或者 P6 系列处理器就回写所有的已修改数据并使它们的高速缓存失效，以保证系统内存的一致性。如果内存访问没有高速缓存且/ 或它跨越了高速缓存线的边界，那么这个处理器就会产生 LOCK#信号，并在锁定操作期间不会响应总线控制请求。

IA-32 处理器提供有一个 LOCK#信号，会在某些关键内存操作期间被自动激活，去锁定系统总线。当这个输出信号发出的时候，来自其它处理器或总线代理的总线控制请求将被阻塞。软件能够通过预先在指令前添加 LOCK 前缀来指定需要 LOCK 语义的其它场合。在 Intel386、Intel486、Pentium 处理器中，明确地对指令加锁会导致 LOCK#信号的产生。由硬件设计人员来保证系统硬件中 LOCK#信号的可用性，以控制处理器间的内IA-32 架构软件开发人员指南卷 3：系统编程指南170存访问。对于 Pentium 4、Intel Xeon 以及 P6 系列处理器，如果被访问的内存区域是在处理器内部进行高速缓存的，那么通常不发出 LOCK#信号；相反，加锁只应用于处理器的高速缓存（参见 7.1.4.LOCK 操作对处理器内部高速缓存的影响）。

可参考inter的 IA-32券3 第七章第一小节！

当然inter还有其他方式保证原子操作！

然后是ARM cpu, arm主要是靠两个指令来保证原子操作的，LDREX 和 STREX

LDREX
LDREX 可从内存加载数据。

如果物理地址有共享 TLB 属性，则 LDREX 会将该物理地址标记为由当前处理器独占访问，并且会清除该处理器对其他任何物理地址的任何独占访问标记。

否则，会标记：执行处理器已经标记了一个物理地址，但访问尚未完毕。

STREX
STREX 可在一定条件下向内存存储数据。条件具体如下：

如果物理地址没有共享 TLB 属性，且执行处理器有一个已标记但尚未访问完毕的物理地址，那么将会进行存储，清除该标记，并在Rd 中返回值 0。

如果物理地址没有共享 TLB 属性，且执行处理器也没有已标记但尚未访问完毕的物理地址，那么将不会进行存储，而会在Rd 中返回值 1。

如果物理地址有共享 TLB 属性，且已被标记为由执行处理器独占访问，那么将进行存储，清除该标记，并在Rd 中返回值 0。

如果物理地址有共享 TLB 属性，但没有标记为由执行处理器独占访问，那么不会进行存储，且会在Rd 中返回值 1。

参考：http://blog.csdn.net/duanlove/article/details/8212123

原子CAS操作

原子操作指令里，有原子加，原子减，cas到底是什么呢？

首先看一段代码，

bool compare_and_swap(int *accum, int *dest, int newval)
{
if (*accum == *dest) {
*dest = newval;
return true;
} else {
*accum = *dest;
return false;
}
}

cas即是Compare-and-swap，先比较再互换，即修改，意思就是，当reg等oldvalue的时候，将reg设置为newval，这段代码在非原子情况下（多线程）是没用的，但是如果这段代码是原子操作，那么他的威力就非常大，互斥锁就和这个cas有关，

上面我们也看到inter这个指令了，lock cmpxchg，cmpxchg作用就是cas这个函数的作用，比较并交换操作数，这就是cas原子操作，神奇吧，上面一个函数的作用，被inter一个指令搞定了，再cmpxchg前面加一个lock，那么这就是一个真正发挥威力的cas！

在win32内核中有个InterlockedCompareExchange函数，这个函数就是cas功能，在inter cpu上的实现就是这段指令=》lock cmpxchg！

linux下有__sync_bool_compare_and_swap 和 __sync_val_compare_and_swap 。

在dotnet下有 interlocked.compareexchange。java参考sun.misc.Unsafe类。

CAS操作，到底有什么威力？

如果要修改一个变量，在多线程下，应该要加锁，代码是这样的

int num = 0;
void add()
{
lock();
num = num + 123;
unlock();
}

但是如果不要锁，cas来操作？？

int num = 0;
void add()
{
int temp;
do
{
temp = num;
}
while (cas(num, temp, temp+123)==true)
}

我们看到用一个do while来无限判断cas的修改结果，如果修改完成，那就成功+1，如果cas没有修改成功，继续while，temp将获取最新的num，再次cas操作！

当一个线程的时候，num一个人操作，不会出现差错，当两个人的时候，某个人先进行cas原子操作，num+1，第二个线程拿着旧值去加操作，返现返回的就是false，于是重新复制temp获取最新的num，这就是cas的核心价值！无锁！

cas其实这也算一种锁，乐观锁！相同于自旋锁也循环！

贴下cas互斥锁的代码（自己写的），当然也可以去用原子+-来判断，反正都是原子操作~~

int i = 0;//0非锁，1锁住
//尝试获取锁，当cas返回失败，获取锁失败，返回true，获取锁成功获取失败就休眠，等待系统唤醒
bool lock()
{
return cas(i, 0, 1);
}
bool unlock()
{
return cas(i, 1, 0);
}

CAS无锁Queue

简单发下我写的cas环形队列，很简单的！

// .h#pragma once#ifndef _cas_queue
#define _cas_queue#ifndef C_BOOL
#define C_BOOLtypedef int cbool;
#define false 0
#define true 1#endif//
//typedef struct _cas_queue
//{
//int size;
//} cas_queue;#define QUEUE_SIZE 65536#ifdef __cplusplus
extern "C" {
#endif
/*
compare and swap： CAS(*ptr,outvalue,newvalue);
return bool
*/cbool compare_and_swap(void ** ptr,long outvalue,long newvalue);void cas_queue_init(int queue_size);void cas_queue_free();cbool cas_queue_try_enqueue(void * p);cbool cas_queue_try_dequeue(void ** p);#ifdef __cplusplus
}
#endif#endif//.c
#include "cas_queue.h"#ifdef _MSC_VER
#include <windows.h>
#else#endifvolatile unsigned long read_index = 0;
volatile unsigned long write_index = 0;long* read_index_p = &read_index;
long* write_index_p = &write_index;void** ring_queue_buffer_head;int ring_queue_size = QUEUE_SIZE;cbool is_load = 0;cbool compare_and_swap(void * ptr, long outvalue, long newvalue)
{
#ifdef _MSC_VER // vs
long return_outvalue = InterlockedCompareExchange(ptr, newvalue, outvalue);
return return_outvalue == outvalue;
/*InterlockedCompareExchange64 No success！！*/
//#ifndef _WIN64
////32 bit
//long return_outvalue = InterlockedCompareExchange(ptr, newvalue, outvalue);
//return return_outvalue == outvalue;
//#else
////64 bit
//long return_outvalue = InterlockedCompareExchange64(ptr, newvalue, outvalue);
//return return_outvalue == outvalue;
//#endif
#else
//linux
#endif}void cas_queue_init(int queue_size)
{
if (queue_size > 0)
ring_queue_size = queue_size;
int size = sizeof(void**)*ring_queue_size;
ring_queue_buffer_head = malloc(size);
memset(ring_queue_buffer_head, 0, size);
is_load = 1;
read_index = 0;
write_index = 0;
}void cas_queue_free()
{
is_load = 0;
free(ring_queue_buffer_head);
}cbool cas_queue_try_enqueue(void * p)
{
if (!is_load)
return false;
unsigned long index;
do
{
//queue full
if (read_index != write_index && read_index%ring_queue_size == write_index%ring_queue_size)
return false;
index = write_index;
} while (compare_and_swap(&write_index, index, index + 1) != true);
ring_queue_buffer_head[index%ring_queue_size] = p;return true;
}
cbool cas_queue_try_dequeue(void ** p)
{
if (!is_load)
return false;
unsigned long index;
do
{
//queue empty
if (read_index == write_index)
return false;
index = read_index;
} while (compare_and_swap(read_index_p, index, index + 1) != true);
*p = ring_queue_buffer_head[index%ring_queue_size];
return true;
}

具体我测试过，在4个线程情况下，80万个消息，同时入和出，出完只需要150毫秒左右！当然线程过多而且集火的话肯定会慢的。

这个demo不是很实用，看下篇：CAS原子锁高效自旋无锁的正确用法

锁&锁与指令原子操作的关系 & cas_Queue的更多相关文章

mysql表锁、行锁、索引之间暧昧的关系
MySQL的innodb存储引擎支持行级锁,innodb的行锁是通过给索引项加锁实现的,这就意味着只有通过索引条件检索数据时,innodb才使用行锁,否则使用表锁.根据当前的数据更新语句(UPDATE ...
mysql隔离级别与锁，接口并发响应速度的关系(2)
innoDB默认隔离级别 mysql> SELECT @@tx_isolation; +-----------------+ | @@tx_isolation | +-------------- ...
mysql隔离级别与锁，接口并发响应速度的关系(1)
默认隔离级别:可重复读原始数据 | id | name | addr | | nick | NULL | 事务1 事务2 start transaction start transaction ; ...
Java中的锁——锁的分类
Java中有各种各样的锁,例如公平锁.乐观锁等等,这篇文章主要介绍一下各种锁的分类. 按照其性质分类公平锁/非公平锁公平锁是指多个线程按照申请锁的顺序来获取锁. 非公平锁是指多个线程获取锁的顺序并 ...
Java多线程(一)——线程基础和锁锁锁
目录 Java多线程(一) 一.线程的定义二.Synchronize线程同步三.偏向锁.自旋锁.重量级锁四.volatile关键字五.Compare And Swap无锁自旋优化技术和ABA版 ...
单片机、CPU、指令集和操作系统的关系
郑重声明:转载自http://blog.csdn.net/zhongjin616/article/details/18765301 1> 首先讨论各种单片机与操作系统的关系说到单片机,大家第一 ...
CPU、内存、硬盘、指令之间的关系
我们都知道所有的程序最终都是一系列计算机能够识别的指令和数据,通过执行这些指令来控制整个计算机. 而CPU就是负责读取和解释执行这些指令的,CPU主要包括运算器.控制器和寄存器,控制器负责把指令.数据 ...
synchronized同一把锁锁不同代码
对于多线程,如果是计算密集型,多线程不一定优势:但如果是io密集型(因为速度慢),多线程多数情况下就有很大的优势了(但也不全是,因为当io已经满负荷运转下,即100%了,再增加线程,未必就会增加效率) ...
【Java虚拟机5】Java内存模型（硬件层面的并发优化基础知识--指令乱序问题）
前言其实之前大家都了解过volatile,它的第一个作用是保证内存可见,第二个作用是禁止指令重排序.今天系统学习下为什么CPU会指令重排. 存储器的层次结构图 1.CPU乱序执行指令的根源 CPU读 ...

随机推荐

Oracle Database Server 'TNS Listener'远程数据投毒漏洞（CVE-2012-1675）解决
环境:Windows 2008 R2 + Oracle 10.2.0.3 应用最新bundle patch后,扫描依然报出漏洞 Oracle Database Server 'TNS Listener ...
docker基础
docker1.映射主机目录到镜像: $ docker run -v /data:/mnt -i -t image-id bash移除:docker rm -v 2.停止所有的container,这样 ...
如何把TOMCAT 添加到服务中自动启动
1.配置系统参数: JAVA_HOME:C:\Program Files\Java\jdk1.8.0_51 //本机Jdk的安装路径,已配置相关Java应用的无需再配置. CATALINA_HOM ...
Character 比较注意先要转换成字符串类型
Character tmp = '/'; if("/".equals(tmp)){ System.out.print("error"); } if(" ...
Java学习笔记（一） java介绍
编程语言分为:编译型语言和解释型语言. 编译型语言需要经过特定编译器通过一次性编译,成为该特定平台硬件可执行的机器码,可脱离开发环境独立运行,运行效率较高,但是无法跨平台移植. 解释型语言需要经过特定 ...
bzoj3405：[Usaco2009 Open]Grazing2 移动牛棚
思路:首先因为要让距离尽量大,所以奶牛1一定在1号牛棚,奶牛n一定在s号牛棚,然后考虑dp. 因为总距离为s-1,然后要使长度为d的段数尽量多,那么剩下的一定就是d+1的段数,也就是s-(n-1)*d ...
[收藏转贴]struct探索·extern "C"含义探索 ·C++与C的混合编程·C 语言高效编程的几招
一.C/C++语言 struct深层探索 1.自然对界 struct是一种复合数据类型,其构成元素既可以是基本数据类型(如 int.long.float等)的变量,也可以是一些复合数据类型(如 arr ...
IOS中的单例设计模式
单例设计模式是IOS开发中一种很重要很常用的一种设计模式.它的设计原理是无论请求多少次,始终返回一个实例,也就是一个类只有一个实例.下面是苹果官方文档中关于单例模式的图片: 如图所示,左边的图是默认的 ...
OpenCV__type()返回的数字
OpenCV中的类型以宏定义的形式给出 type_c.h中片段 #define CV_CN_MAX 512 #define CV_CN_SHIFT 3 #define CV_DEPTH_MAX (1 ...
Universal-Image-Loader解析（二）——DisplayImageOptions的详细配置与简单的图片加载
在使用这个框架的时候,我们必须要配置一个DisplayImageOptions对象来作为ImageLoader.getInstance().displayImage()中的参数,所以很有必要讲解这个对 ...