并发-锁type
status
date
slug
summary
tags
category
icon
password
Property
在源代码中加锁，放在临界区周围，保证临界区能够像单条原子指令一样执行
假设临界区像这样，典型的更新共享变量：
为了使用锁，给临界区增加了这样一些代码：
锁就是一个变量，因此需要声明一个某种类型的锁变量，才能使用。这个锁变量（简称锁）保存了锁在某一时刻的状态。它要么是可用的，表示没有线程持有锁，要么是被占用的，表示有一个线程持有锁，正处于临界区。我们也可以保存其他的信息，比如持有
锁的线程，或请求获取锁的线程队列，但这些信息会隐藏起来，锁的使用者不会发现。
调用
lock()尝试获取锁，如果没有其他线程持有锁（即它是可用的），该线程会获得锁，进入临界区。这个线程有时被称为锁的持有者（owner）。如果另外一个线程对相同的锁变量（mutex）调用lock()，因为锁被另一线程持有，该调用不会返回。这样，当持有锁的线程在临界区时，其他线程就无法进入临界区。锁的持有者一旦调用
unlock()，锁就变成可用了。如果没有其他等待线程（即没有其他线程调用过lock()并卡在那里），锁的状态就变成可用了。如果有等待线程（卡在lock()里），其中一个会（最终）注意到（或收到通知）锁状态的变化，获取该锁，进入临界区。锁为程序员提供了最小程度的调度控制。把线程视为程序员创建的实体，但是被操作系统调度，具体方式由操作系统选择。锁让程序员获得一些控制权。通过给临界区加锁，可以保证临界区内只有一个线程活跃，将原本由操作系统调度的混乱状态变得更为可控。
API
POSIX 库将锁称为互斥量（mutex），因为它被用来提供线程之间的互斥。即当一个线程在临界区，它能够阻止其他线程进入直到本线程离开临界区。最基本的一对函数是：
如果有一段代码是一个临界区，就需要通过锁来保护，以便像需要的那样运行：
所有锁必须正确初始化，以确保它们具有正确的值，并在锁和解锁被调用时按照需要工作。
有两种方法来初始化锁，一种方法是使用
PTHREAD_MUTEX_INITIALIZER：初始化的动态方法（即在运行时）是调用p
thread_mutex_init()：当用完锁时，还应该相应地调用
pthread_mutex_destroy()实现一个锁
评价一种锁实现的效果：
- 锁是否能完成它的基本任务，即提供互斥（mutual exclusion）
- 公平性，当锁可用时，是否每一个竞争线程有公平的机会抢到锁
- 使用锁之后增加的时间开销
控制中断
最早提供的互斥解决方案之一，就是在临界区关闭中断，这个方案是为单处理器系统开发的：
主要优点就是简单，
缺点很多：
- 首先，这种方法要求我们允许所有调用线程执行特权操作（打开关闭中断），即信任这种机制不会被滥用
- 这种方案不支持多处理器。如果多个线程运行在不同的CPU 上，每个线程都试图进入同一个临界区，关闭中断也没有作用。
- 关闭中断导致中断丢失，可能会导致严重的系统问题
- 效率低。与正常指令执行相比，现代CPU 对于关闭和打开中断的代码执行得较慢。
基于以上原因，只在很有限的情况下用关闭中断来实现互斥原语。例如，在某些情况下操作系统本身会采用屏蔽中断的方式，保证访问自己数据结构的原子性，或至少避免某些复杂的中断处理情况。这种用法是可行的，因为在操作系统内部不存在信任问题，它总是信任自己可以执行特权操作。
测试并设置指令(原子交换)
因为关闭中断的方法无法工作在多处理器上，所以系统设计者开始让硬件支持锁。
最简单的硬件支持是测试并设置指令（test-and-set instruction），也叫作原子交换（atomicexchange）。
用一个变量来标志锁是否被某些线程占用：
当第一个线程正处于临界区时，如果另一个线程调用
lock()，它会在while循环中自旋等待(spin-wait)，直到第一个线程调用unlock()清空标志。然后等待的线程会退出while循环，设置标志，执行临界区代码。遗憾的是，这段代码有两个问题：正确性和性能
通过适时的中断，很容易构造出两个线程都将标志设置为1，都能进入临界区的场景
性能问题主要是线程在等待已经被持有的锁时，采用了自旋等待不停地检查标志的值。自旋等待在等待其他线程释放锁的时候会浪费时间
自旋锁
上面的想法很好，但没有硬件的支持是无法实现的。幸运的是，一些系统提供了这一指令，支持基于这种概念创建简单的锁。这个更强大的指令有不同的名字：在SPARC上，这个指令叫ldstub（load/store unsigned byte，加载/保存无符号字节）；在x86 上，是xchg（atomic exchange，原子交换）指令。但它们基本上在不同的平台上做同样的事，通常称为测试并设置指令（test-and-set）。
关键是这些代码是原子地（atomically）执行。因为既可以测试旧值，又可以设置新值，所以把这条指令叫作“测试并设置”。这一条指令完全可以实现一个简单的自旋锁：
将测试（test 旧的锁值）和设置（set 新的值）合并为一个原子操作之后，保证了只有一个线程能获取锁。这就实现了一个有效的互斥原语！
- 正确性：自旋锁一次只允许一个线程进入临界区，因此是正确的锁
- 公平性：自旋锁不提供任何公平性保证。实际上，自旋的线程在竞争条件下可能会永远自旋。自旋锁没有公平性，可能会导致饿死。
- 性能
- 在单CPU 的情况下，性能开销相当大。假设一个线程持有锁进入临界区时被抢占。调度器可能会运行其他每一个线程（假设有N−1 个这种线程）。而其他线程都在竞争锁，都会在放弃CPU 之前，自旋一个时间片，浪费CPU 周期。
- 但是，在多CPU 上，自旋锁性能不错（如果线程数大致等于CPU 数）。假设线程A 在CPU 1，线程B 在CPU 2 竞争同一个锁。线程A（CPU 1）占有锁时，线程B竞争锁就会自旋（在CPU 2 上）。然而，临界区一般都很短，因此很快锁就可用，然后线程B 获得锁。自旋等待其他处理器上的锁，并没有浪费很多CPU 周期，因此效果不错。
比较并交换
某些系统提供了另一个硬件原语，即比较并交换指令（SPARC系统中是compare-and-swap，x86系统是compare-and-exchange）:
比较并交换的基本思路是检测ptr指向的值是否和expected 相等；如果是，更新ptr 所指的值为新值。否则，什么也不做。不论哪种情况，都返回该内存地址的实际值，让调用者能够知道执行是否成功。
有了比较并交换指令，就可以实现一个锁，类似于用测试并设置那样，只要用下面的代码替换
lock()函数：检查标志是否为0，如果是，原子地交换为1，从而获得锁。锁被持有时，竞争锁的线程会自旋
链接的加载和条件式存储指令
一些平台提供了实现临界区的一对指令。例如MIPS 架构中，链接的加载（load-linked）和条件式存储（store-conditional）可以用来配合使用，实现其他并发结构：
链接的加载指令和典型加载指令类似，都是从内存中取出值存入一个寄存器。关键区别来自条件式存储（store-conditional）指令，只有上一次加载的地址在期间都没有更新时，才会成功，（同时更新刚才链接的加载的地址的值）。成功时，条件存储返回1，并将ptr 指的值更新为value。失败时，返回0，并且不会更新值。
使用LL/SC 实现锁：
获取并增加
获取并增加（fetch-and-add）指令，它能原子地返回特定地址的旧值，并且让该值自增一
用获取并增加指令，实现一个ticket 锁
如果线程希望获取锁，首先对一个ticket 值执行一个原子的获取并相加指令。这个值作为该线程的“turn”（顺位，即myturn）。根据全局共享的lock->turn 变量，当某一个线程的（myturn== turn）时，则轮到这个线程进入临界区。unlock 则是增加turn，从而下一个等待线程可以进入临界区。
本方法能够保证所有线程都能抢到锁。只要一个线程获得了ticket值，它最终会被调度。之前的方法则不会保证。比如基于测试并设置的方法，一个线程有可能一直自旋，即使其他线程在获取和释放锁。
放弃CPU
如果临界区的线程发生上下文切换，其他线程只能一直自旋，等待被中断的（持有锁的）进程重新运行。有什么好办法？
第一种简单友好的方法就是，在要自旋的时候，放弃CPU。
考虑在单CPU 上运行两个线程。基于yield 的方法十分有效。一个线程调用
lock()，发现锁被占用时，让出CPU，另外一个线程运行，完成临界区。考虑许多线程（例如100 个）反复竞争一把锁的情况。在这种情况下，一个线程持有锁，在释放锁之前被抢占，其他99 个线程分别调用
lock()，发现锁被抢占，然后让出CPU。假定采用某种轮转调度程序，这99个线程会一直处于运行—让出这种模式，直到持有锁的线程再次运行。虽然比原来的浪费99个时间片的自旋方案要好，但这种方法仍然成本很高，上下文切换的成本是实实在在的，因此浪费很大。使用队列：休眠替代自旋
前面一些方法的真正问题是存在太多的偶然性。调度程序决定如何调度。如果调度不合理，线程或者一直自旋，或者立刻让出CPU。无论哪种方法，都可能造成浪费，也能防止饿死。
因此，必须显式地施加某种控制，决定锁释放时，谁能抢到锁。为了做到这一点，需要操作系统的更多支持，并需要一个队列来保存等待锁的线程。
简单起见，利用Solaris 提供的支持，它提供了两个调用：
park()能够让调用线程休眠，unpark(threadID)则会唤醒threadID标识的线程。可以用这两个调用来实现锁，让调用者在获取不到锁时睡眠，在锁可用时被唤醒。首先，将测试并设置和等待队列结合，实现了一个更高性能的锁。其次，通过队列来控制谁会获得锁，避免饿死。
guard 基本上起到了自旋锁的作用，围绕着flag 和队列操作。因此，这个方法并没有完全避免自旋等待。线程在获取锁或者释放锁时可能被中断，从而导致其他线程自旋等待。但是，这个自旋等待时间是很有限的（不是用户定义的临界区，只是在lock和unlock 代码中的几个指令），因此，这种方法也许是合理的。
在
lock()函数中，如果线程不能获取锁（它已被持有），线程会把自己加入队列（通过调用gettid()获得当前的线程ID），将guard 设置为0，然后让出CPU。当要唤醒另一个线程时，flag 并没有设置为0。线程被唤醒时，就像是从park()调用返回。但是，此时它没有持有guard，所以也不能将flag 设置为1。因此，直接把锁从释放的线程传递给下一个获得锁的线程，期间flag 不必设置为0。
决方案中的竞争条件，就在park()调用之前。如果不凑巧，一个线程将要park，假定它应该睡到锁可用时。这时切换到另一个线程（比如持有锁的线程），这可能会导致麻烦。比如，如果该线程随后释放了锁。接下来第一个线程的park 会永远睡下去（可能）。这种问题有时称为唤醒/等待竞争（wakeup/waiting race）。
Solaris 通过增加了第三个系统调用separk()来解决这一问题。通过setpark()，一个线程表明自己马上要park。如果刚好另一个线程被调度，并且调用了unpark，那么后续的park调用就会直接返回，而不是一直睡眠。lock()调用可以做一点小修改：
另外一种方案就是将guard 传入内核。在这种情况下，内核能够采取预防措施，保证原子地释放锁，把运行线程移出队列。
不同操作系统，不同实现
例如，Linux 提供了futex，它类似于Solaris 的接口，但提供了更多内核功能。具体来说，每个futex 都关联一个特定的物理内存位置，也有一个事先建好的内核队列。调用者通过futex 调用来睡眠或者唤醒。
具体来说，有两个调用。调用
futex_wait(address, expected)时，如果address 处的值等于expected，就会让调线程睡眠。否则，调用立刻返回。调用futex_wake(address)唤醒等待队列中的一个线程。基本上，它利用一个整数，同时记录锁是否被持有（整数的最高位），以及等待者的个数（整数的其余所有位）。因此，如果锁是负的，它就被持有（因为最高位被设置，该位决定了整数的符号）。这段代码的有趣之处还在于，它展示了如何优化常见的情况，即没有竞争时：只有一个线程获取和释放锁，所做的工作很少（获取锁时测试和设置的原子位运算，释放锁时原子的加法）。
两阶段锁
Linux 采用的是一种古老的锁方案，多年来不断被采用，可以追溯到20 世纪60 年代早期的Dahm 锁，现在也称为两阶段锁（two-phase lock）。两阶段锁意识到自旋可能很有用，尤其是在很快就要释放锁的场景。因此，两阶段锁的第一阶段会先自旋一段时间，希望它可以获取锁。
但是，如果第一个自旋阶段没有获得锁，第二阶段调用者会睡眠，直到锁可用。上文的Linux 锁就是这种锁，不过只自旋一次；更常见的方式是在循环中自旋固定的次数，然后使用futex 睡眠。
两阶段锁是又一个杂合（hybrid）方案的例子，即结合两种好想法得到更好的想法。当然，硬件环境、线程数、其他负载等这些因素，都会影响锁的效果。事情总是这样，让单个通用目标的锁，在所有可能的场景下都很好，这是巨大的挑战。