自旋锁、互斥锁、信号量、读写锁、递归锁、乐观锁、悲观锁(一)

我们知道 每个操作系统都有这样一些锁，各个锁之间好像可以互相转换，但概念上又总是模棱两可。下面从Linux系统对这些锁的实现方式下手，谈一下这些锁之间的联系。

原子性:一条汇编指令的执行过程中是原子性的，cpu不可能将一条汇编语言执行一半，然后去执行别的汇编指令。这称为原子性，及，一条汇编语言就是cpu最小的执行时间单位，不可以分割，执行的时候不可暂停。因此，实现单一变量的原子读写操作是容易的，只要保证读写操作只对应一条汇编语言即可。

但是，很多情况下要求对复杂的变量操作也具有原子性，这就需要锁了。于是线程A在执行函数f的之前先对一个整形变量是不是大于1，大于1就继续执行函数f(临界区),否则就休眠一会儿之后再次判断该整形变量是否大于1。这样，如果执行f函数的时候别的线程B也想来执行函数f,就会因为该整形变量等于0而执行循环判断，而卡在f函数外面，知道线程A执行完函数f.
伪代码如下:

	int i = 1;
start: 
    if (i > 0){
   	  i = 0
   	 	f()
   	  i = 1
   }else {
   	 	goto start:
   }

这场景好像两个人都想到同一个取款机下取钱，A先进入，然后把门锁了，B想进入只能不断观察A是否开锁出来。
但是上面这段程序的问题就在先要读取变量i，再判断变量i是否大于0，这至少是两条汇编指令，不具有原子性。(假如锁大于0时按照这个时序:A读取锁->B读取锁->B判断锁为大于1->A判断锁为大于1，这就造成AB同事执行函数f的情况，一个取款机有两个人同时取钱的情况)
因此，一种解决方案是汇编指令系统提供了一条汇编指令xchg，相当于将读取锁变量和判断锁变量合并执行，保证了读取和判断的原子性。
实际上，在单核CPU上和多核CPU上，锁操作的难易是大有不同的。
单核cpu上，统一时间只有一个执行流，只要在进入临界区f()之前关掉中断，那么f()的执行流就不会被操作系统分片机制所打断。因此，单核CPU下只要在临界区前后控制好中断，就很容易实现锁机制。
但是,多核CPU下，只有内存地址是共享的，各个CPU核心都有自己的寄存器，和中断处理寄存器，这个时候关中断也只能保证该执行流不被自己所在的cpu核心的时间片机制打断，而无法保证不被其它cpu核心的执行流同时执行函数f()。
因此，多核CPU情况下，进入临界区f()之前除了关中断，还要使用内存变量作为锁变量并且要锁定总线。锁定总线保证了同一时间内只有一个执行流能访问内存。

自旋锁 上面的情况中，不断判断锁变量是否大于1，大于1就进入临界区并置锁为0，否则就一直判断锁是否大于1，并且不会让出所处cpu核心的时间片，相当于忙等状态。这就是自旋锁的实现。自旋锁是实现其它各种锁的基础。

值得一提的是，单核CPU的自旋锁没有机会忙等，因为关中断之后就只有一条执行流,不可能有锁被别的执行流占用的情况。

信号量

信号量的数据结构

typedef struct sem_t{
spinlock_t spin_lock//上文提到第自旋锁
int count;//信号量值，初始值为1
}sem_t;

加锁：

/**获取信号量*/
void seam_wait(sem_t *seam){
	sema->spin_lock.lock();
	start:
	if(sema->count>0）{
		sema->count--;
		sema->spin_lock.unlock();//信号量获取成功
		return;
	}else{
		put_thread_to_waitlist(sema);//将本线程放等待唤醒列表
		sema->spin_lock.unlock();
		schedule();//让时间片调度器调度时间片，相当于让出时间片，睡眠，下次时间片切回来之后从下一行开始执行
		goto start;
		
	}
}

释放信号量

void seam_singnal(sem_t *sema){
	sema->spin_lock.lock();
	sema->count++;
	wakeup_waitlist(sema);//将其它等待该信号的线程设为就绪态(唤醒)
	sema->spin_lock.unlock();//让出时间片
}

可以看到，信号量用自旋锁来保护对信号量值的操作。当信号量值初始为1的时候，这个就是pthread库里面的互斥锁。

读写锁 读写锁要求有线程在写的时候，其它线程不能读也不能写，有线程在读的时候，其它线程可以读，但不能写。即:单写多读。读写锁基本上可以说是自旋锁或者信号量的变种。下面以信号量来实现读写锁.假设允许100个线程同时读。

读写锁基本结构

#define RW_LOCK_BIAS 100
 typedef struct sem_t{
 spinlock_t spin_lock//上文提到第自旋锁
 int count;//信号量值，初始值为RW_LOCK_BIAS
  }sem_t;
 
 /**获取读锁*/
 void read_lock(seam * seam){
 	seam->spin_lock.lock();
 	start:
 	if(seam->count<=0){//获取失败
 		enter_waitList();//本线程进入等待列表
 		seam->spin_lock.unlock();
 		schedue();//CPU调度，时间片让给其它线程,下次从下一行开始读
 		goto start:
 	}else {
 	    //读锁加锁成功
	 	seam->count--;
	 	seam->spin_lock.unlock();
	 	return;
 	}
 }
 /**获取写锁*/
 void write_lock(seam *seam){
	 seam->spin_lock.lock();
	 start:
	 if(seam->count<=RW_LOCK_BIAS){//有线程在读，加锁失败
	 	enter_waitlist();
	 	seam->spin_lock.lock()
	 	schedue();//CPU调度，时间片让给其它线程,下次从下一行开始读
	 }else {//写锁加锁成功
	 	seam->count -= RW_LOCK_BIAS;
	 	seam->spin_lock.unlock();
	 	return;
	 }
 
 }

以上是读锁和写锁利用信号量实现加锁的方法，在这里，
我们有自旋锁->信号量(互斥锁)->读写锁的进化关系。实际上，linux里面对读写锁的实现，直接才用了改造自旋锁的方法，但是本质上是大同异。
参考文字:
郑刚:《操作系统真响还原》
彭东:《瞧一瞧Linux:Linux的自旋锁和信号量如何实现》
下一篇介绍递归锁、乐观锁与悲观锁。