Java的锁

首先回顾一下Java中的锁的一些特性。在面试时，我们常被问道Java的锁升级过程：
即一个锁的初始是不加锁的，而当只有一个线程来尝试获取这把锁的时候，它会变为偏向锁，（在锁对象头中存储线程id）这样可以对应的线程可以直接获得锁。
而当有更多线程（2个）尝试获取锁时，它会转变为一个轻量级锁，这里所谓的轻量级，是一种无线程挂起的锁，也就是自旋锁。最终，当自旋等到超过一定次数，或者此时有更多线程来进行竞争，锁会转变为互斥锁。所有等待的线程都会被挂起。

Golang Mutex

与Java相比，Golang的并非所有对象都可以被用来加锁，其对象没有Java那样的对象头信息。它通过一个叫Mutex的结构体实现代码的同步。

它的结构非常简单，state字段表示加锁状态，加锁和解锁就是通过原子操作改变state的值。sema则是一个信号量，表示等待队列。

其拥有两种工作模式：

正常模式

在该模式下，goroutine在尝试获得锁时，会首先进行自旋，在一定次数之后，如果仍获取失败，则会进入等待队列。当正在持有锁的goroutine释放锁后，并不会直接将锁传递给等待队列的第一个goroutine。而是第一个尝试获得锁的goroutine，也就是说：等待队列的第一个goroutine，需要和其他新来的goroutine竞争。而这种竞争，往往是新来的goroutine更有优势，它们正在持有CPU时间，而队列头部的goroutine才刚被唤醒，并且新来的可能数量更多。如果队列头部的goroutine获取失败，它并不会去到队列尾部，而是继续在头部等待。可以看出，在正常模式下的Mutex是一种非公平锁，在竞争少的情况下，拥有高吞吐量，但是它会导致goroutine饥饿。而当队列中的goroutine的等待时间超过1ms时，Mutex会转变为饥饿模式。

饥饿模式

在该模式下，所有新来的goroutine都不再会尝试直接进行锁的获取，而是直接到后面进行排队。当前正持有锁的goroutine释放锁之后，它会将锁直接传递给位于等待队列头部的goroutine。而当队列全部清空，或者有一个goroutine的等待时间小于1ms就获得了锁的时候，Mutex又会重新转变为正常模式。可以看到，饥饿模式下，Mutex为公平锁，所有新来的goroutine都会排队，相比正常模式吞吐量下降，但是优化了线程饥饿。

排队队列

再回头看Mutex的结构，其中信号量只是一个uint32值，那么是怎么实现goroutine的排队的呢？

在golang运行时中， 包含一个251大小的信号量表(semtable)，这个表存储的是平衡二叉树的根，而平衡树中每个节点都是一个sudog类型的对象，要使用一个信号量时 ，需要提供一个记录信号量数值的变量， 根据它的地址进行计算， 映射到sematable中的一颗平衡树上，找到对应的节点，就找到了该信号量的等待队列了。