互斥锁,自旋锁与自适应自旋锁 - CSDN博客
互斥锁,自旋锁与自适应自旋锁
线程安全与锁的优化
从 实现原理上来讲，Mutex属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程(线程A和线程B)，它们分别运行在Core0和 Core1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁，而此时这个锁正被线程B所持有，那么线程A就会被阻塞 (blocking)，Core0 会在此时进行上下文切换(Context Switch)将线程A置于等待队列中，此时Core0就可以运行其他的任务(例如另一个线程C)而不必进行忙等待。而Spin lock则不然，它属于busy-waiting类型的锁，如果线程A是使用pthread_spin_lock操作去请求锁，那么线程A就会一直在 Core0上进行忙等待并不停的进行锁请求，直到得到这个锁为止。
(1) 如果是多核处理器，如果预计线程等待锁的时间较长，至少比两次线程上下文切换的时间要长，建议使用互斥量。
(2) 如果是单核处理器，一般建议不要使用自旋锁。因为，在同一时间只有一个线程是处在运行状态，那如果运行线程发现无法获取锁，只能等待解锁，但因为自身不挂起，所以那个获取到锁的线程没有办法进入运行状态，只能等到运行线程把操作系统分给它的时间片用完，才能有机会被调度。这种情况下使用自旋锁的代价很高。
自旋锁与互斥锁有点类似，只是自旋锁不会引起调用者立即睡眠，如果自旋锁已经被别的执行单元保持，调用者不放弃处理器的执行时间， 进行忙循环(自旋)， 看是否该自旋锁的保持者已经释放了锁，”自旋”一词就是因此而得名。(JDK1.6以后默认开启了自旋锁)
自旋的次数默认是10次。
有些不足之处：
1、自旋锁一直占用CPU，他在未获得锁的情况下，一直运行－－自旋，所以占用着CPU，如果不能在很短的时 间内获得锁，这无疑会使CPU效率降低。
2、在用自旋锁时有可能造成死锁，当递归调用时有可能造成死锁，调用有些其他函数也可能造成死锁，如 copy_to_user()、copy_from_user()、kmalloc()等。
因此我们要慎重使用自旋锁，自旋锁只有在内核可抢占式或SMP的情况下才真正需要，在单CPU且不可抢占式的内核下，自旋锁的操作为空操作。自旋锁适用于锁使用者保持锁时间比较短的情况下。
如果是多核处理器，如果预计线程等待锁的时间很短，短到比线程两次上下文切换时间要少的情况下，使用自旋锁是划算的。
自适应的自旋锁
JDK1.6中引入了自适应的自旋锁。 自适应意味着自旋的时间不再是固定的， 而是由前一次在同一个锁上的自旋时间以及锁拥有者的状态来决定。如果在同一个锁对象上, 自旋等待刚好成功获得锁， 并且在持有锁的线程在运行中， 那么虚拟机就会认为这次自旋也是很有可能获得锁， 进而它将允许自旋等待相对更长的时间。
不足与使用场景与自旋锁相同。
参考书籍: 《深入理解Java虚拟机》
本文已收录于以下专栏：
相关文章推荐
很多时候，当一个进程为了等待mutex而刚刚进入睡眠的时候，mutex已经被释放了，如果能在第一时间感知mutex被释放那是再好不过的了，解决该问题的方式就是用自旋忙等而不是阻塞等待，是这样吗？
java字旋锁
我们知道线程同步是并行编程中非常重要的手段，其中最典型的就是用pthreads提供的锁机制（lock）来对多个线程之间共享的临界区进行保护。我们知道pthreads也提供了多种锁的机制如：互斥锁、自旋...
一、原子操作
所谓原子操作，就是该操作绝不会在执行完毕前被任何其他任务或事件打断，也就说，它的最小的执行单位，不可能有比它更小的执行单位，因此这里的原子实际是使用了物理学里的物质微...
http://blog.csdn.net/kyokowl/article/details/6294341
POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一...
http://blog.csdn.net/kyokowl/article/details/6294341POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。...
自旋锁(Spin lock)自旋锁与互斥锁有点类似，只是自旋锁不会引起调用者睡眠，如果自旋锁已经被别的执行单元保持，调用者就一直循环在那里看是 否该自旋锁的保持者已经释放了锁，&自旋&一词就是因此而得...
POSIX threads(简称Pthreads)是在多核平台上进行并行编程的一套常用的API。线程同步(Thread Synchronization)是并行编程中非常重要的通讯手段，其中最典型的应用...
为什么需要内核锁?
多核处理器下，会存在多个进程处于内核态的情况，而在内核态下，进程是可以访问所有内核数据的，因此要对共享数据进行保护，即互斥处理
有哪些内核锁机制?
他的最新文章
讲师：吴岸城
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)01背包，完全背包，多重背包问题详细介绍以及源代码实现 - CSDN博客
01背包，完全背包，多重背包问题详细介绍以及源代码实现
部分内容转载自：/tanky-woo/archive//121803.html
背包的基本模型就是给你一个容量为V的背包
在一定的限制条件下放进最多(最少?)价值的东西
一般常用动态规划，存在以前状态向当前状态的一个转换，先求出之前状态的最优解，然后根据之前的状态得到现在状态的最优解。
常见的有三种限制条件。
01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
比较三个题目，会发现不同点在于每种背包的数量，01背包是每种只有一件，完全背包是每种无限件，而多重背包是每种有限件。
01背包问题
题目&来自hihocoder 01背包
01背包（ZeroOnePack）: 有N件物品和一个容量为V的背包。（每种物品均只有一件）第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
把这个过程理解下：在前i件物品放进容量v的背包时，
它有两种情况：
第一种是第i件不放进去，这时所得价值为:f[i-1][v]
第二种是第i件放进去，这时所得价值为：f[i-1][v-c[i]]+w[i]
（第二种是什么意思？就是如果第i件放进去，那么在容量v-c[i]里就要放进前i-1件物品）
最后比较第一种与第二种所得价值的大小，哪种相对大，f[i][v]的值就是哪种。
对于每一个物品，我们都有放进去与不放进去两种选择.
Java源代码如下：
import java.util.*;
public class Package01 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int weight = in.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
int[][] res = new int[n + 1][weight + 1];
for (int i = 1; i &=n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
for (int i = 1; i &=n; i++) {
res[i][0] = 0;
for (int j = 0; j &= j++) {
res[0][j] = 0;
for(int i=1;i&=n;i++) {
for (int k = 1; k &= k++) {
res[i][k] = res[i - 1][k];
if (w[i] &= k) {
if (v[i] + res[i-1][k - w[i]] & res[i-1][k])
res[i][k] = v[i] + res[i-1][k - w[i]];
System.out.println(res[n][weight]);
in.close();
我们想想看，能不能进行一下优化，其实我们并不需要保存每一层i的结果，我们只需要i-1的结果，那么我们可不可以优化成一维数组呢，要优化成一位数组也就意味着我们需要反向遍历，这样就可以保证每次更新的时候都用的是上一层的状态。
具体的原代码如下：
import java.util.*;
public class Package0102 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
int n = in.nextInt();
int weight = in.nextInt();
int[] v = new int[n + 1];
int[] w = new int[n + 1];
int[] res = new int[weight + 1];
for (int i = 1; i &=n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
for(int i=1;i&=n;i++) {
for (int k = k&=0; k--) {
if (w[i] &= k) {
if (v[i] + res[k - w[i]] & res[k])
res[k] = v[i] + res[k - w[i]];
System.out.println(res[weight]);
in.close();
题目：/problemset/problem/1043?sid=770394 hihocoder完全背包
完全背包(CompletePack): 有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
完全背包按其思路仍然可以用一个二维数组来写出：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0&=k*c[i]&=v}
同样可以转换成一维数组来表示：
伪代码如下：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-c[i]]+w[i]}
想必大家看出了和01背包的区别，这里的内循环是顺序的，而01背包是逆序的。
现在关键的是考虑：为何完全背包可以这么写？
在次我们先来回忆下，01背包逆序的原因？是为了是max中的两项是前一状态值，这就对了。
那么这里，我们顺序写，这里的max中的两项当然就是当前状态的值了，为何？
因为每种背包都是无限的。当我们把i从1到N循环时，f[v]表示容量为v在前i种背包时所得的价值，这里我们要添加的不是前一个背包，而是当前背包。所以我们要考虑的当然是当前状态。
对于二维数组，更新的时候为res[i][j-w[k]]
优化：对于完全背包，如果w[i]&=w[j]&&v[i]&=v[j]那么j就可以删掉了 优化是o(N*N)对于随机生成的值哟花比较明显
多重背包(MultiplePack): 有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可，因为对于第i种物品有n[i]+1种策略：取0件，取1件……取n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值，则有状态转移方程：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0&=k&=n[i]}
这里同样转换为01背包。
对于http://poj.org/problem?id=2392
有一头奶牛要上太空，他有很多种石头，每种石头的高度是hi，但是不能放到ai之上的高度，并且这种石头有ci个
将这些石头叠加起来，问能够达到的最高高度。
解题思路:首先对数据进行升序排序，这样才是一个标准的多重背包的问题。为什么要排序？因为只有这样才能得到最优解,如果一开始就是高的在前面，那么后面有低的却不能选到，就直接选高的去了。这样是不能达到最优解的。
具体代码如下：
import java.util.*;
public class SpaceElevator {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int len=40010;
while (in.hasNext()) {
int n=in.nextInt();
Node[] a=new Node[n];
for(int i=0;i&n;i++)
a[i]=new Node(in.nextInt(),in.nextInt(),in.nextInt());
Arrays.sort(a);
boolean[] dp=new boolean[len];
int res=0;
for(int i=0;i&n;i++)
int[] sum=new int[len];
for(int j=a[i].h;j&=a[i].a;j++)
if(!dp[j]&&dp[j-a[i].h]&&sum[j-a[i].h]&a[i].c) //首先如果高度j已经达到的话，那么就不需要继续计算了
sum[j]=sum[j-a[i].h]+1;
if(j&res) res=j;
System.out.println(res);
public static class Node implements Comparable&Node&
Node(int h,int a,int c)
public int compareTo(Node node) {
if(this.a&node.a) return 1;
else if(this.a&node.a) return -1;
总结：背包问题是很典型的动态规划问题，对于动态规划问题弄清楚转移方程，弄清楚相关的优化，每一层之间的关系，规划的流程。
本文已收录于以下专栏：
相关文章推荐
n,t,i,j,k:
f:array[0..00]
w,v:array[0..100...
上一篇讲的完全背包是指在所有物品件数无限多的情况下选择最值，现在引申出多重背包问题，即各物品个数均有限且不一定相同，求轙类情况下的最值。
国庆前去面了一下技术面，直接上机写题（15 min），另外还有些非常基础非常基础的数学题，比如追及问题之类（60 min）。
有两道上机题，时间15 min，其实只做一道就可以了，面试官让我...
背包问题可以用递归方法和动态规划方法，递归代码简洁，方便理解，不过由于重复计算，效率较低，DP方法将前面的计算结果保存到二维数组中，效率较高，值得推荐。
1. 01背包（ZeroOnePack）: ...
Problem Description
急！灾区的食物依然短缺！
为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装...
有n 种不同的物品，每个物品有两个属性，size 体积，value 价值，现在给一个容量为 w 的背包，问最多可带走多少价值的物品。
        int f[w+1];   //...
给定M（1&=M&=200）以及长度为M的四个数组，分别记为Pairs、Multi、Low、Up，你需要构造一个长度为M的数组Table（其中Low[i]&=Table[i]&=...
0 / 1背包问题 - 动态规划（C++实现）flyfish以下代码在VC++2013下编译通过#include &stdafx.h&
N件物品，没见有重量Wi，价值Vi；选其中几件放入容量为M的背包中，求最大价值。——经典背包问题
背包问题分三类：1.01背包：每件物品仅一件，可以不将背包装满（要么取0件要么1件）
        ...
01背包是指每件物品有且只有一件，而完全背包则是每件物品件数无限，求装入背包所对应的最值。
完全背包也有公式，在01背包公式的基础上加以改动。
完全背包公式：dp [ j ] =min/max( dp...
他的最新文章
讲师：吴岸城
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)Java锁之自旋锁详解
投稿：junjie
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了Java锁之自旋锁详解,本文是系列文章的第一篇,请持续关注脚本之家java栏目,需要的朋友可以参考下
锁作为并发共享数据，保证一致性的工具，在JAVA平台有多种实现(如 synchronized 和 ReentrantLock等等 ) 。这些已经写好提供的锁为我们开发提供了便利，但是锁的具体性质以及类型却很少被提及。本系列文章将分析JAVA下常见的锁名称以及特性，为大家答疑解惑。
自旋锁是采用让当前线程不停地的在循环体内执行实现的，当循环的条件被其他线程改变时 才能进入临界区。如下
public class SpinLock {
& private AtomicReference&Thread& sign =new AtomicReference&&();
& public void lock(){
&&& Thread current = Thread.currentThread();
&&& while(!sign .compareAndSet(null, current)){
& public void unlock (){
&&& Thread current = Thread.currentThread();
&&& sign .compareAndSet(current, null);
使用了CAS原子操作，lock函数将owner设置为当前线程，并且预测原来的值为空。unlock函数将owner设置为null，并且预测值为当前线程。
当有第二个线程调用lock操作时由于owner值不为空，导致循环一直被执行，直至第一个线程调用unlock函数将owner设置为null，第二个线程才能进入临界区。
由于自旋锁只是将当前线程不停地执行循环体，不进行线程状态的改变，所以响应速度更快。但当线程数不停增加时，性能下降明显，因为每个线程都需要执行，占用CPU时间。如果线程竞争不激烈，并且保持锁的时间段。适合使用自旋锁。
注：该例子为非公平锁，获得锁的先后顺序，不会按照进入lock的先后顺序进行。
2.自旋锁的其他种类
上文我们讲到了自旋锁，在自旋锁中 另有三种常见的锁形式:TicketLock ，CLHlock 和MCSlock
Ticket锁主要解决的是访问顺序的问题，主要的问题是在多核cpu上:
package com.alipay.titan.dcc.dal.
import java.util.concurrent.atomic.AtomicI
public class TicketLock {
&&& private AtomicInteger&&&&&&&&&&&&&&&&&&&& serviceNum = new AtomicInteger();
&&& private AtomicInteger&&&&&&&&&&&&&&&&&&&& ticketNum& = new AtomicInteger();
&&& private static final ThreadLocal&Integer& LOCAL&&&&& = new ThreadLocal&Integer&();
&&& public void lock() {
&&&&&&& int myticket = ticketNum.getAndIncrement();
&&&&&&& LOCAL.set(myticket);
&&&&&&& while (myticket != serviceNum.get()) {
&&& public void unlock() {
&&&&&&& int myticket = LOCAL.get();
&&&&&&& pareAndSet(myticket, myticket + 1);
每次都要查询一个serviceNum 服务号，影响性能（必须要到主内存读取，并阻止其他cpu修改）。
CLHLock 和MCSLock 则是两种类型相似的公平锁，采用链表的形式进行排序。
import java.util.concurrent.atomic.AtomicReferenceFieldU
public class CLHLock {
&&& public static class CLHNode {
&&&&&&& private volatile boolean isLocked =
&&& @SuppressWarnings("unused")
&&& private volatile CLHNode&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&& private static final ThreadLocal&CLHNode&&&&&&&&&&&&&&&&&&&&&&&&&& LOCAL&& = new ThreadLocal&CLHNode&();
&&& private static final AtomicReferenceFieldUpdater&CLHLock, CLHNode& UPDATER = AtomicReferenceFieldUpdater.newUpdater(CLHLock.class,
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CLHNode.class, "tail");
&&& public void lock() {
&&&&&&& CLHNode node = new CLHNode();
&&&&&&& LOCAL.set(node);
&&&&&&& CLHNode preNode = UPDATER.getAndSet(this, node);
&&&&&&& if (preNode != null) {
&&&&&&&&&&& while (preNode.isLocked) {
&&&&&&&&&&& }
&&&&&&&&&&& preNode =
&&&&&&&&&&& LOCAL.set(node);
&&& public void unlock() {
&&&&&&& CLHNode node = LOCAL.get();
&&&&&&& if (!pareAndSet(this, node, null)) {
&&&&&&&&&&& node.isLocked =
&&&&&&& node =
CLHlock是不停的查询前驱变量， 导致不适合在NUMA 架构下使用（在这种结构下，每个线程分布在不同的物理内存区域）
MCSLock则是对本地变量的节点进行循环。不存在CLHlock 的问题。
import java.util.concurrent.atomic.AtomicReferenceFieldU
public class MCSLock {
&&& public static class MCSNode {
&&&&&&& volatile MCSN
&&&&&&& volatile boolean isLocked =
&&& private static final ThreadLocal&MCSNode&&&&&&&&&&&&&&&&&&&&&&&&&& NODE&&& = new ThreadLocal&MCSNode&();
&&& @SuppressWarnings("unused")
&&& private volatile MCSNode&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
&&& private static final AtomicReferenceFieldUpdater&MCSLock, MCSNode& UPDATER = AtomicReferenceFieldUpdater.newUpdater(MCSLock.class,
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& MCSNode.class, "queue");
&&& public void lock() {
&&&&&&& MCSNode currentNode = new MCSNode();
&&&&&&& NODE.set(currentNode);
&&&&&&& MCSNode preNode = UPDATER.getAndSet(this, currentNode);
&&&&&&& if (preNode != null) {
&&&&&&&&&&& preNode.next = currentN
&&&&&&&&&&& while (currentNode.isLocked) {
&&&&&&&&&&& }
&&& public void unlock() {
&&&&&&& MCSNode currentNode = NODE.get();
&&&&&&& if (currentNode.next == null) {
&&&&&&&&&&& if (pareAndSet(this, currentNode, null)) {
&&&&&&&&&&& } else {
&&&&&&&&&&&&&&& while (currentNode.next == null) {
&&&&&&&&&&&&&&& }
&&&&&&&&&&& }
&&&&&&& } else {
&&&&&&&&&&& currentNode.next.isLocked =
&&&&&&&&&&& currentNode.next =
从代码上 看，CLH 要比 MCS 更简单，
CLH 的队列是隐式的队列，没有真实的后继结点属性。
MCS 的队列是显式的队列，有真实的后继结点属性。
JUC ReentrantLock 默认内部使用的锁 即是 CLH锁（有很多改进的地方，将自旋锁换成了阻塞锁等等）。
（全文完）
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具