Background
悲观锁和乐观并发控制机制
悲观锁是一种悲观思想,它总认为最坏的情况可能会出现,它认为数据很可能会被其他人所修改,不管读还是写,悲观锁在执行操作之前都先上锁。
对读对写都需要加锁导致性能低,所以悲观锁用的机会不多。但是在多写的情况下,还是有机会使用悲观锁的,因为乐观并发控制机制遇到写不一致的情况下会一直重试,会浪费更多的时间。
乐观并发控制机制的思想与悲观锁的思想相反,它总认为资源和数据不会被别人所修改,所以读取不会上锁,但是乐观并发控制机制在进行写入操作的时候会判断当前数据是否被修改过。
乐观并发控制机制的实现方案主要包含CAS和版本号机制。乐观并发控制机制适用于多读的场景,可以提高吞吐量。
CAS
CAS即Compare And Swap(比较与交换),是一种有名的无锁算法。即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步。CAS涉及三个关系:指向内存一块区域的指针V、旧值A和将要写入的新值B。
总结来说:
- CAS 算法:会执行一个原子操作
- 在这个原子操作中,先检查当前value是否等于current,如果相等,则意味着value没被其他线程修改过,更新并返回true。如果不相等,compareAndSet则会返回false,然后循环继续尝试更新。
CAS实现的乐观并发控制会带来潜在的ABA问题。
CAS 的权衡
在轻度到中度的争用情况下,非阻塞算法的性能会超越阻塞算法,因为 CAS 的多数时间都在第一次尝试时就成功,而发生争用时的开销也不涉及线程挂起和上下文切换,只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多(这句话肯定是真的,因为没有争用的锁涉及 CAS 加上额外的处理),而争用的 CAS 比争用的锁获取涉及更短的延迟。
在高度争用的情况下(即有多个线程不断争用一个内存位置的时候),基于锁的算法开始提供比非阻塞算法更好的吞吐率,因为当线程阻塞时,它就会停止争用,耐心地等候轮到自己,从而避免了进一步争用。但是,这么高的争用程度并不常见,因为多数时候,线程会把线程本地的计算与争用共享数据的操作分开,从而给其他线程使用共享数据的机会。
版本号机制
版本号机制是通过一个版本号version来实现版本控制。
自旋锁(Spin Lock)
之前介绍的CAS就是自旋锁的一种具体实现。同一时刻只能有一个线程获取到锁,没有获取到锁的线程通常有两种处理方式:
- 一直循环等待判断该资源是否已经释放锁,这种锁叫做自旋锁,它不用将线程阻塞起来(NON-BLOCKING);
- 把自己阻塞起来,等待重新调度请求,这种是互斥锁。
自旋锁的原理比较简单,如果持有锁的线程能在短时间内释放锁资源,那么那些等待竞争锁的线程就不需要做内核态和用户态之间的切换进入阻塞状态,它们只需要等一等(自旋),等到持有锁的线程释放锁之后即可获取,这样就避免了用户进程和内核切换的消耗。
但是如果长时间上锁的话,自旋锁会非常耗费性能,它阻止了其他线程的运行和调度。线程持有锁的时间越长,则持有该锁的线程将被OS调度程序中断的风险越大。如果发生中断情况,那么其他线程将保持旋转状态(反复尝试获取锁),而持有该锁的线程并不打算释放锁,这样导致的是结果是无限期推迟,直到持有锁的线程可以完成并释放它为止。
解决上面这种情况一个很好的方式是给自旋锁设定一个自旋时间,等时间一到立即释放自旋锁。自旋锁的目的是占着CPU资源不进行释放,等到获取锁立即进行处理。
信号量 Semaphore
信号量是 Edsger Dijkstra 发明的数据结构,在解决多种同步问题时很有用。其本质是一个整数,并关联两个操作:
- 申请
acquire
(也称为 wait
、decrement
或 P
操作)
- 释放
release
(也称 signal
、increment
或 V
操作)
acquire
操作将信号量减 1,
- 如果结果值为负则线程阻塞,且直到其他线程进行了信号量累加为正数才能恢复。
- 如结果为正数,线程则继续执行。
release
操作将信号量加 1,如存在被阻塞的线程,此时他们中的一个线程将解除阻塞。
Go 运行时提供的runtime_SemacquireMutex
和runtime_Semrelease
函数可用来实现sync.RWMutex
互斥锁。
...