并发专题(四) 锁——硬核实现一个简单的锁
锁(Lock)
之前章节我们讲过并发带来的一个基本问题——共享数据。出现这个问题的原因与指令执行的原子性有关(具体有关原子性的概念可以参照之前讲过的共享数据问题的哪一章节)。显然，单纯从指令的原子性上去避免共享数据问题有很大的难度，因为这个需要依赖于我们的硬件系统，需要硬件系统支持。
既然如此，那么应该选用哪种方法既不依赖于硬件，还可以让我们的代码原子性的去运行呢。我们可以从软件层面借助于一种数据结构去实现。这个数据结构便是锁。
锁是对于临界区的一种实现，锁本质上是一个数据结构。在编程中使用它，你可以像使用变量一样去使用。锁为程序员们提供了细粒度的并发控制。之前的章节我们讲过，线程是由程序员创建，由操作系统调度的。换言之，我们创建了线程之后交给了操作系统我们就丢失了对线程的控制权。锁这样的一个数据结构能够在线程调度方面帮助程序员们“曲线救国”。
如何去实现一个锁
既然锁是对于临界区的一种实现，那么锁就应该具备临界区的基本要求。可以这么讲，任何锁都具备互斥性，这是临界区的基本要求。那么什么是互斥性？互斥性就是在涉及到对共享的变量进行操作的代码时，我们必须保证只有一个线程在操作，而且这个线程必须执行完毕临界区内的所有代码才可以让出临界区交给下一个线程处理。
锁的实现不仅仅只是软件层面的实现，当然仅靠软件(编写代码)去实现锁也可以，但是这样实现的锁不是一个最佳的锁。如果想要实现一个表现良好的锁一定程度上还需要依赖于硬件系统。所以，一个表现良好的锁是软硬结合去实现的。
如何去评价锁
我们说到表现良好的锁，何为表现良好，怎么去评价。换言之，一个表现的锁体现在哪些方面上。
- 互斥性：最基本的条件，一个锁是否可以阻止多个线程进入临界区。
- 公平性：当锁可用时，是否每个线程有公平的机会去抢到锁，是否保障每个线程都有机会进入临界区。
- 性能：锁应用于高并发的场景，然而并发的初衷是为了提高效率，如果使用锁带来了很大的开销，那就类似于舍本逐末，买椟还珠了。
实现一个锁
正如上图所示，当一个线程获得锁之后，他可以执行临界区中的代码。而没有获得锁的线程只能排队，直到获取到锁才可以执行临界区的代码。这样的设计保障了良好的互斥性。那么应该如何去实现呢。
我们可以用一个变量(flag)来标志锁是否被某个线程占用。
-
当第一个线程进入临界区后，它要把这个标志位设为1。
-
当一个线程想要进入临界区时，它首先要检查这个标志位是否1。如果是1那么证明锁被某个线程占用，所以它要等待锁。
-
当线程执行完临界区的代码时，它要将标志位设为0，释放锁的的所有权，以便其他线程使用。
typedef struct lock_t {int flag;} lockt_t;
void init(lock_t *mutex) {
mutex->flag = 0; /* 初始状态为0 代表锁未被任何线程持有*/
}
void lock(lock_t *mutex) {
/* 自旋等待 */
while (mutex->flag != 0); // spin-wait
mutex->flag = 1;
}
void unlock(lock_t *mutex) {
mutex->flag = 0;
}
/* thread code */
static lock_t mutex;
static int counter = 10;
{
init(&mutex);
}
void decrement() {
/* 尝试进入临界区 */
mutex->lock();
/* 进入临界区 */
counter++;
/* 临界区代码执行完毕，释放锁 */
mutex->unlock();
/* 退出临界区 */
}
这样实现的锁有问题吗？，我们可以测试一下。
static lock_t mutex;
static int counter = 0;
const static int LOOP_CNT = 10000;
void decrement() {
counter--;
}
void increment() {
counter++;
}
void *threadI(void *args) {
printf("thread %s\n", (char*)args);
int i;
for (i = 0; i < LOOP_CNT; ++i) {
lock(&mutex);
increment();
unlock(&mutex);
}
return NULL;
}
void *threadD(void *args) {
printf("thread %s\n", (char*)args);
int i;
for (i = 0; i < LOOP_CNT; ++i) {
lock(&mutex);
decrement();
unlock(&mutex);
}
return NULL;
}
int main() {
pthread_t th1,th2;
init(&mutex);
pthread_create(&th1, NULL, threadI, "threadI");
pthread_create(&th2, NULL, threadD, "threadD");
pthread_join(th1, NULL);
pthread_join(th2, NULL);
printf("counter = %d\n", counter);
return 0;
}
结果出现了点小意外。
虽然这种状况出现的概率很小，但是出现即意味着我们在代码设计上有问题？那么问题出在了哪里呢。
问题便是，我们的锁也是一个共享的变量，在并发场景下同样会出现共享变量问题。也就是说我们对锁进行操作的代码在CPU看来同样不具备原子性。在我们实现锁的代码中，在对flag标识为进行赋值时，如果操作系统调度中断，那么很有可能出现两个线程同时将flag设置为1，同时拥有锁的现象。显然这连基本的互斥性都无法满足，那么这将是一个bad lock。那么应该怎么做，这就不得不依赖我们的硬件原语了。
test-and-set
test-and-set是一种硬件原语。这种硬件原语能够保障指令的原子性。在SPARC上，这个指令叫做ldstub(load/store unsigned byte) 加载保存无符号字节。在x86平台上，是xchg(atomic exchange, 原子交换指令)
因为这是一个硬件方面的原语，我们只能以C代码的形式来定义一下这个硬件原语做了什么
int test_and_set(int *oldptr, int new) {
int old = *oldptr;
*oldptr = new;
return old;
}
我们用test-and-set这个硬件语言去重新实现一下我们的锁
void lock(lock_t *mutex) {
/* 这段代码可以保证flag设置的原子性 */
while (test_and_set(&mutex->flag, 1) == 1); // spin-lock
}
void unlock(lock_t *mutex) {
mutex->flag = 0;
}
自旋锁
我们通过上述C语言代码实现了一个简单的锁，其实这种锁还有一个名字——自旋锁。这种锁的实现简单，实现思路也非常的清晰明了，但是这个锁是一个表现良好的锁吗？
在互斥性上，自旋锁能够做到良好的互斥性。但是从开销方面来看，这个锁并不是一个表现良好的锁。为什么这么说呢？因为自旋锁并没有真正的让其他线程去等待，用一个更为确切的词语说，自旋锁的策略是让其他线程阻塞。
事实上，上述临界区代码的执行过程中，没有获得锁的线程同样会获得操作系统分给它的CPU时间片。只不过它阻塞在lock的while循环上，这种操作有点浪费CPU的资源，因为它在这段时间内什么都没做，只是在不断的循环，直至把CPU时间片耗光，然后等待操作系统将CPU的使用权分配给其他线程，我们也称这种等待为有忙等待。