深入理解相互排斥锁的实现

在实际的软件编程中，常常会遇到资源的争用，比方以下的样例：

class Counter
{
private:
int value;
public:
Counter(int c) { value = c; }
int GetAndIncrement()
{
int temp = value;
//进入危急区
value = temp +1; //离开危急区
return value;
}
}

class Counter
{
     private:
        int value;
     public:
        Counter(int c) { value = c; }
        int GetAndIncrement()
        {
           int temp = value;      //进入危急区        
            value = temp +1;       //离开危急区
            return value;
        }
 }

这样的实如今单线程系统中可以正常工作，可是在多线程系统则有可能出错。比方有2个线程，初始状态value=0。第一个线程执行完第9行，这时temp=0。突然一个中断来了，切换到第二个线程执行了，第二个线程执行完第9行也是temp=0，然后执行第10行赋值value=1。然后回到第一个线程继续执行第10行对value进行写覆盖，结果value=1.而正确的情况应该是value=2了。
为什么会产生这种情况呢？这时由于两个线程同一时候对一个资源value进行争用产生了冲突。为了避免上述情况，我们能够将这两行置入临界区内：某个时刻内仅能被一个线程运行的代码段。从而实现相互排斥。对Counter类的添加对临界区的相互排斥訪问：

class Counter
{
private:
int value;
lock lock;
public:
Counter(int c) { value = c; }
int GetAndIncrement()
{
lock.lock();//获取锁
int temp = value;
//进入临界区
value = temp +1; //离开临界区
lock.unlock();//释放锁
return value;
}
}

 class Counter
 {
    private:
      int value;
      lock lock;
    public:
      Counter(int c) { value = c; }
      int GetAndIncrement()
      {
        lock.lock();//获取锁
         int temp = value; //进入临界区 
         value = temp +1; //离开临界区
         lock.unlock();//释放锁
         return value;
     }
 }

通过在程序中为了使用Lock域来保证对象的相互排斥特性，必须对称的调用lock()和unlock()。须要满足例如以下条件：
1. 一个临界区之和一个lock对关联。
2. 线程进入临界区前调用lock()。
3. 线程离开临界区后调用unlock().
编程的框架例如以下：
lock()
临界区
unlock()
打个不是十分妥帖的比喻，就像是有一个仓库资源，可是有多个人想去仓库做点事情。这时候仓库仅仅须要一把锁（锁多了纯粹是浪费^_^），初始状态仓库上的锁是打开的。每一个人进去之前先把锁锁住(避免别的人进来)，然后自己在仓库里捣弄，离开时再把仓库的锁打开，让别人能够进来。
接下来更加深入的是怎样实现相互排斥锁呢？也就是lock()和unlock()方法。

class Lock
{
public:
virtual void lock() = 0;
//进入临界区前
virtual void unlock() = 0;
//离开临界区后
}

class Lock
{
   public: 
     virtual void lock() = 0; //进入临界区前 
      virtual void unlock() = 0; //离开临界区后
}

相互排斥锁须要满足三个条件：
相互排斥 不同线程的临界区没有重叠
无死锁 假设一个线程正在尝试获得一个锁，那么总会成功地获得这个锁。若线程A调用lock()可是无法获得锁，则一定存在其它线程正在无穷次地运行临界区。
无饥饿 每个试图获得锁的线程终于都能成功。
首先看双线程的相互排斥，首先从两个存在不足(假设大家能不看后面的分析也能知道哪里不足就更厉害了^_^),但十分有趣的锁算法说起：
LockOne类
这个类有一个标志数组flag，继续来个比喻，这个flag就相当于一个旗帜。LockOne类遵循这种协议：
1. 假设线程想进入临界区，首先把自己的旗帜升起来(flag对应位置1)，表示感兴趣。然后等对方的旗帜降下来就能够进入临界区了。
2. 假设线程离开临界区，则把自己的旗帜降下来。

class LockOne: public Lock
{
private:
bool flag[2];
public:
void lock()
{
int i = ThreadID.get();
int j = 1-i;
flag[i] = true;
while(flag[j]);
}
void unlock()
{
int i = ThreadID.get();
flag[i] = false;
}

  class LockOne: public Lock
  {
       private:
         bool flag[2];
       public:
         void lock()
         {
            int i = ThreadID.get();
            int j = 1-i;
            flag[i] = true;
            while(flag[j]);
         }
         void unlock()
         {
            int i = ThreadID.get();
            flag[i] = false;
         }
 }

LockOne类的协议看起来挺朴实的，可是存在一个问题：当两个线程都把旗帜升起来，然后等待对方的旗帜降下来就会出现死锁的状态(两个线程都在那傻乎乎的等待对方的旗帜降下来，直到天荒地老:))

LockTwo类
观察LockOne类存在的问题，就是在两个线程同一时候升起旗帜的时候，须要有一个线程妥协吧，这样就须要指定一个牺牲品，因此LockTwo类横空出世。

class LockTwo: public Lock
{
private:
int victim;
public:
void lock()
{
int i = ThreadID.get();
victim = i; //让别人先走，临时牺牲自己
while(victim == i);
}
void unlock(){]
}

 class LockTwo: public Lock
 {
    private:
      int victim;
    public:
      void lock()
      {
         int i = ThreadID.get();
         victim = i;                  //让别人先走，临时牺牲自己
         while(victim == i);
      }
      void unlock(){]
 }

当两个线程进行竞争的时候，总有一个牺牲品（较晚对victim赋值的线程），因此能够避免死锁。可是，当没有竞争的时候就杯具了，假设仅仅有一个线程想进入临界区，那么牺牲品一直是自己，直到等待别人来替换自己才行。

Perterson锁
通过上面两个类能够发现，LockOne类适合没有竞争的场景，LockTwo类适合有竞争的场景。那么将LockOne类和LockTwo类结合起来，就能够构造出一种非常好的锁算法。该算法无疑是最简洁、最完美的双线程相互排斥算法，依照其发明者的名字被命名为“Peterson算法”。

class Peterson: public Lock
{
private:
bool flag[2];
int victim;
public:
void lock()
{
int i = ThreadID.get();
int j = 1-i;
flag[i] = true;
victim = i;
while(flag[j] && victim==i);
}
void unlock()
{
int i = ThreadID.get();
flag[i] = false;
}
}

class Peterson: public Lock
{
   private:
     bool flag[2];
     int victim;
   public:
     void lock()
     {
        int i = ThreadID.get();
        int j = 1-i;
        flag[i] = true;
        victim = i;
        while(flag[j] && victim==i);
      }
      void unlock()
      {
         int i = ThreadID.get();
         flag[i] = false;
      }
}

Perterson锁是满足相互排斥特性的。通过反证法来说明，假设两个线程都想进入临界区，可是都成功进入了。由于两个线程都想进入，则说明flag相应位均为1，然后由于都能lock()成功，说明victim均不是自己。这和victim是当中之中的一个矛盾。

可是，实际中线程不可能仅仅有2个，接下来须要看看支持n线程的相互排斥协议。

Barkey锁

有一种协议称为Bakery锁，是一种最简单也最为人们锁熟知的n线程锁算法。以下看看究竟是神马情况。思想非常easy，还是打个简单的比喻来说明器协议：
1. 每一个线程想进入临界区之前都会升起自己的旗帜，并得到一个序号。然后升起旗帜的线程中序号最小的线程才干进入临界区。
2. 每一个线程离开临界区的时候降下自己的旗帜。

class Bakery: public Lock
{
private:
bool flag[];
Label label[];
public:
Bakery (int n)
{
flag = new 
bool[n];
label = new Label[n];
for(int i=0; i<n; i++)
{
flag[i] = flase;
label[i] = 0;
}
void Lock()
{
int i = ThreadID.get();
flag[i] = true;
label[i] = max(label[0], ..., label[n-1]) +1;
while((exist k!=i)(flag[k] && (label[k],k)<<(label[i], i))
}
void unlock()
{
flag[TheadID.get()] = false;
}
}
}

class Bakery: public Lock
{
  private: 
    bool flag[];
    Label label[];
  public:
    Bakery (int n)
    {
      flag = new bool[n];
      label = new Label[n];
      for(int i=0; i<n; i++)
      {
        flag[i] = flase;
        label[i]  =  0;
      }
      void Lock()
      {
         int i = ThreadID.get();
         flag[i] = true;               
         label[i] = max(label[0], ..., label[n-1]) +1;
         while((exist k!=i)(flag[k] && (label[k],k)<<(label[i], i))
       }
       void unlock()
       {
          flag[TheadID.get()] = false;
       }
     }
}

首先，Barkey算法是无死锁的。由于正在等待的线程中（类似于全部升起旗帜flag的线程中），必然存在一个最小的序号label。该线程能够进入临界区。
其次，Barkey算法是先来先服务的。因此先来的线程，分到的label比較小。
最后，Barkey算法是相互排斥的。假设两个线程同一时候位于临界区，则两个线程都已经升起旗帜，同一时候label都是最小的，矛盾。
非常重要的点是要实现一个n线程的相互排斥锁，必须至少使用n个存储单元。由于若此刻有某个线程正在临界区内，而锁的状态却与一个没有线程在临界区或正在临界区的全局状态相符，则状态不一致。即每一个线程共同拥有2个状态，则n个线程共同拥有2^n个状态，共须要n个存储器记录全局状态。