常见锁相关

Linux 锁

• futex: 所有的futex同步操作都应该从用户空间开始，首先创建一个futex同步变量，也就是位于共享内存的一个整型计数器。当进程尝试持有锁或者要进入互斥区的时候，对futex执行"down"操作，即原子性的给futex同步变量减1。如果同步变量变为0，则没有竞争发生， 进程照常执行。如果同步变量是个负数，则意味着有竞争发生，需要调用futex系统调用的futex_wait操作休眠当前进程。sys_futex系统调用进入kernel mode进行处理 用来挂起或者唤醒进程来挂起或者唤醒进程，当然这部分工作也只能在内核态下完成。当进程释放锁或 者要离开互斥区的时候，对futex进行"up"操作，即原子性的给futex同步变量加1。如果同步变量由0变成1，则没有竞争发生，进程照常执行。如 果加之前同步变量是负数，则意味着有竞争发生，需要调用futex系统调用的futex_wake操作唤醒一个或者多个等待进程。这里的原子性加减通常是用CAS(Compare and Swap)完成的，与平台相关。可见: futex是从用户态开始，由用户态和核心态协调完成的。pthread_mutex_lock()是一个用户空间API，在C库中实现。在Linux上，它通常基于内核futex()系统调用。

  通常有两种处理方式：一种是没有获取到锁的线程就一直循环等待判断该资源是否已经释放锁，这种锁叫做自旋锁，它不用将线程阻塞起来(NON-BLOCKING)；还有一种处理方式就是把自己阻塞起来，等待重新调度请求，这种叫做互斥锁。两者各有利弊，已加锁时阻塞掉当前线程让出cpu资源可以去执行别的线程，通过减少cpu的浪费来提高效率，但是这个过程需要进行上下文切换，保存各寄存器状态需要花费时间，如果每个线程对于锁的占有时间很短，拥有锁之后会很快释放锁，那么自旋锁又更加高效，所以要根据具体情况具体使用。

• 互斥锁：在无法得到资源时，内核线程会进入睡眠阻塞状态，这需要陷入内核进行cpu上下文的切换。而自旋锁处于忙等待状态。因此，如果资源被占用的时间较长，使用互斥锁较好，因为可让CPU调度去做其它进程的工作。

• 自旋锁： 自旋锁的原理比较简单，如果持有锁的线程能在短时间内释放锁资源，那么那些等待竞争锁的线程就不需要做内核态和用户态之间的切换进入阻塞状态，它们只需要等一等(自旋)，等到持有锁的线程释放锁之后即可获取，这样就避免了用户进程和内核切换的消耗。因为自旋锁避免了操作系统进程调度和线程切换，所以自旋锁通常适用在时间比较短的情况下。由于这个原因，操作系统的内核经常使用自旋锁。但是，如果长时间上锁的话，自旋锁会非常耗费性能，它阻止了其他线程的运行和调度。线程持有锁的时间越长，则持有该锁的线程将被 OS(Operating System) 调度程序中断的风险越大。如果发生中断情况，那么其他线程将保持旋转状态(反复尝试获取锁)，而持有该锁的线程并不打算释放锁，这样导致的是结果是无限期推迟，直到持有锁的线程可以完成并释放它为止。解决上面这种情况一个很好的方式是给自旋锁设定一个自旋时间，等时间一到立即释放自旋锁。自旋锁的目的是占着CPU资源不进行释放，等到获取锁立即进行处理。但是如何去选择自旋时间呢？如果自旋执行时间太长，会有大量的线程处于自旋状态占用 CPU 资源，进而会影响整体系统的性能。因此自旋的周期选的额外重要！JDK在1.6 引入了适应性自旋锁，适应性自旋锁意味着自旋时间不是固定的了，而是由前一次在同一个锁上的自旋时间以及锁拥有的状态来决定，基本认为一个线程上下文切换的时间是最佳的一个时间。自旋锁只能用于多核cpu，如果是单核将无限制处于自旋状态。

  单cpu自旋锁：运行在临界区域代码时，不运行发生进程切换（即不能阻塞，相当于主动释放cpu），要独占cpu。
  多cpu自旋锁：运行在临界区域代码时，没加锁的cpu发生进程切换，加锁的不行。
  自旋锁是指当一个线程尝试获取某个锁时，如果该锁已被其他线程占用，就一直循环检测锁是否被释放，而不是进入线程挂起或睡眠状态。

  自旋锁和互斥锁区别： 自旋锁是一种互斥锁的实现方式而已，相比一般的互斥锁会在等待期间放弃cpu，自旋锁（spinlock）则是不断循环并测试锁的状态，这样就一直占着cpu。互斥锁：用于保护临界区，确保同一时间只有一个线程访问数据。对共享资源的访问，先对互斥量进行加锁，如果互斥量已经上锁，调用线程会阻塞，直到互斥量被解锁。在完成了对共享资源的访问后，要对互斥量进行解锁。

数据库锁

当程序中可能出现并发的情况时，我们就需要通过一定的手段来保证在并发情况下数据的准确性，通过这种手段保证了当用户和其他用户一起操作时，所得到的结果和他单独操作时的祷告的结果是一样的。这种手段就叫做并发控制。并发控制的目的是保证一个用户的工作不会对另一个用户的工作产生不合理的影响。没有做好并发控制，就可能导致脏读、幻读和不可重复读等问题。实现并发控制的主要手段大致可以分为乐观并发控制和悲观并发控制两种。

• 悲观锁：总是假设最坏的情况，每次去拿数据的时候都认为别人会修改，所以每次在拿数据的时候都会上锁，这样别人想拿这个数据就会阻塞直到它拿到锁（共享资源每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程）。传统的关系型数据库里边就用到了很多这种锁机制，比如行锁，表锁等，读锁，写锁等，都是在做操作之前先上锁。

  悲观锁主要分为共享锁或排他锁

  1. 共享锁【Shared lock】又称为读锁，简称S锁。顾名思义，共享锁就是多个事务对于同一数据可以共享一把锁，都能访问到数据，但是只能读不能修改。锁级别：Row Lock 行级别。
  2. 排他锁【Exclusive lock】又称为写锁、独占锁，简称X锁。顾名思义，排他锁就是不能与其他锁并存，如果一个事务获取了一个数据行的排他锁，其他事务就不能再获取该行的其他锁，包括共享锁和排他锁，但是获取排他锁的事务是可以对数据行读取和修改。数据库的增删改操作默认都会加排他锁，而查询不会加任何锁。锁级别：Row Lock 行级别。

• 乐观锁： 总是假设最好的情况，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，如果更新了这个数据，放弃操作，否则执行操作。可以使用版本号机制和CAS（compare and swap）（比较与交换）算法实现。乐观锁适用于多读的应用类型，这样可以提高吞吐量。乐观锁适用于多读的应用类型，这样可以提高吞吐量

  应用： 使用数据版本（Version）记录机制实现，这是乐观锁最常用的一种实现方式。何谓数据版本？即为数据增加一个版本标识，一般是通过为数据库表增加一个数字类型的 “version” 字段来实现。当读取数据时，将version字段的值一同读出，数据每更新一次，对此version值加一。当我们提交更新的时候，判断数据库表对应记录的当前版本信息与第一次取出来的version值进行比对，如果数据库表当前版本号与第一次取出来的version值相等，则予以更新，否则认为是过期数据。

• 表锁： 锁表，开销小，加锁快；不会出现死锁；锁定力度大，发生锁冲突概率高，并发度最低

• 行锁： 锁行，开销大，加锁慢；会出现死锁；锁定粒度小，发生锁冲突的概率低，并发度高。

死锁

• 概念：死锁是指在一组进程中的各个进程均占有不会释放的资源，但因互相申请被其它进程所占用不会释放的资源而处于的一种永久等待状态。

• 产生死锁的四个必要条件

  1.互斥性：线程对资源的占有是排他性的，一个资源只能被一个线程占有，直到释放。

  2.占用并保持：一个线程对请求被占有资源发生阻塞时，对已经获得的资源不释放。

  3.非抢占：一个线程在释放资源之前，其他的线程无法抢占占用。

  4.循环等待：发生死锁时，线程进入死循环，永久阻塞。

• 死锁的解除
  　　1.抢占资源，从一个或多个进程中抢占足够数量的资源，分配给死锁进程，以解除死锁状态。
  　　2.终止（或撤销）进程，终止（或撤销）系统中的一个或多个死锁进程，直至打破循环环路，使系统从死锁状态解脱出来。

• 产生死锁的原因
  1.竞争不可抢占性资源: p1已经打开F1，想去打开F2，p2已经打开F2，想去打开F1，但是F1和F2都是不可抢占的，这是发生死锁。
  2.竞争可消耗资源引起死锁: 进程间通信，如果顺序不当，会产生死锁，比如p1发消息m1给p2，p1接收p3的消息m3，p2接收p1的m1，发m2给p3，p3，以此类推，如果进程之间是先发信息的那么可以完成通信，但是如果是先接收信息就会产生死锁。
  3.进程推进顺序不当: 进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。

• 避免死锁的方法
  银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。
  　　在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。
  　　银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。

1.破坏“占用并保持”条件

想办法，让进程不要那么贪心，自己已经有了资源就不要去竞争那些不可抢占的资源。比如，让进程在申请资源时，一次性申请所有需要用到的资源，不要一次一次来申请，当申请的资源有一些没空，那就让线程等待。不过这个方法比较浪费资源，进程可能经常处于饥饿状态。还有一种方法是，要求进程在申请资源前，要释放自己拥有的资源。

2.破坏“不可抢占”条件

允许进程进行抢占，方法一：如果去抢资源，被拒绝，就释放自己的资源。方法二：操作系统允许抢，只要你优先级大，可以抢到。

3.破坏“循环等待”条件

将系统中的所有资源统一编号，进程可在任何时刻提出资源申请，但所有申请必须按照资源的编号顺序（升序）提出

• 死锁的检测
  1.每个进程、每个资源制定唯一编号
  2.设定一张资源分配表，记录各进程与占用资源之间的关系
  3.设置一张进程等待表，记录各进程与要申请资源之间的关系