Locks锁

, , , ,

Locks provide some minimal amount of control over scheduling to programmers.

线程是程序员创建的，但是由OS安排执行的，怎么执行是OS说了算的，所以这回导致一些超出程序员预想的混乱。 而lock可以帮助程序员减少这些混乱 ，让程序稍微有一点可控制性。线程用的锁的名字是mutex, 它在线程之间提供了一种互斥锁

如果自己创建一个锁

创建一个锁可以很好理解锁是如何工作的。要想组建一个锁（需要OS和硬件支持），1.要想明白这个锁是干什么的（例子用互斥锁 mutual exclusion）,2.正确,，3.是公平，4.是性能

先设定一个最简单的锁的情况：

image-20190712102200391

假设CPU是单核的，一个进程在执行关键代码的时候不会被中断，就好像是获得了锁一样。

好处就是非常简单，坏处就比较多：

  1. 有的线程霸占CPU不释放锁
  2. 在多核CPU没用
  3. 关闭中断，中断就丢失了，比如硬盘完成了一个读操作，CPU就不知道去唤醒等待读操作的线程
  4. 没效率

为了在多核情况下有用，改进一下我们的锁，用一个全局的标志flag ，多核都能访问

image-20190712103103446

我们可以看到lock 函数里面有个test-and-set 操作，这个操作实际上是CPU自带的一个指令。

这个锁有两个问题：一个是正确性 另一个是性能问题

当两个线程同时看到flag=0的时候他们就同时把flag设置成1 以为自己获得了锁，性能问题和之前一样，一个线程获得锁，其他线程就干等，占着CPU资源干等

要解决正确性问题我们就求助硬件了，就要用到CPU的另一个指令就是xchg (x86), 它是一个原子性的test-and-set 操作，不允许两个线程同时执行，用C语言描述一下这个操作

image-20190712104215636

我们记住CPU里面它就是原子性操作，我们的锁就变成了下面的样子

image-20190712104329019

我们评估一下现在的锁，实现了目的互斥锁以及要求的正确，但是还是没解决公平和性能

没有获得锁的线程一直处于test-and-set 操作循环中，所以这种锁也叫spin lock 自旋锁。既然满足了正确性，但是总是要个先后嘛，这个锁要想在单核CPU上正确工作需要抢先调度策略preemptive scheduler

CPU还有一个指令是compare-and-swap

image-20190712104941718

用这个指令来实现锁其实和test-and-set 差别不大

image-20190712105014816

其他的指令还有fetch-and-add 以及 load-linked and store-conditional

都能用到上面自旋锁的实现上，但没本质改变

硬件解决了一部分问题 ，但是没全部解决，我出门从OS层面寻求帮助

我们假设OS有个yield()操作，线程自己放弃CPU，资源让给别的线程；线程有三个状态running, ready, blocked。

image-20190712110746099

yield 操作把线程从running 状态变成来了ready状态，当一个线程想要获得锁的时候发现锁已经被别人获取了，它就可以yield ，虽然也是在等待，但不是在CPU里干等，而是把CPU资源让出来。

这就解决了性能问题（其实还是有一点开销：比如100个线程1个获得锁其他99个都要执行一遍test-and-set来进行线程状态的转换。总体是赚了，哈哈哈）

剩下的就是公平问题了，如果有多个线程是ready 状态等,到时候先唤醒谁？从现实中找解决问题，那就是排队了就是术语中的队列Queue。好比某个饭馆火爆，已经没位置了，大家在外面排队，里面吃完一桌，外面队前面的进去一桌人。

image-20190712112240253

到这里我们实现了，当初设定互斥锁的目标。 在真实的情况中不同的操作系统有不同的支持和实现