信號量介紹

信號量的基本內(nèi)容

• 信號量是一個(gè)提供對臨界區(qū)的互斥訪問的抽象的數(shù)據(jù)類型
• 每個(gè)信號量都有一個(gè)等待隊(duì)列
• 信號量是支持P和V操作的整數(shù)
• P(semaphore)：整數(shù)減一伞矩，如果信號量關(guān)著則阻塞
• V(semaphore)：整數(shù)加一流椒，允許另外一個(gè)線程進(jìn)入
  如果有線程在等待隊(duì)列中董饰，則將其Unblock。如果沒有線程在等待，則信號量會“記住”這個(gè)空位的存在哥牍。
• 信號量的安全性能：信號量的值永遠(yuǎn)大于等于0

信號量的分類

• 互斥信號量（二元信號量）

保證對臨界區(qū)的互斥訪問，只提供對資源的單一的訪問途徑

• 計(jì)數(shù)信號量（一般信號量）

用很多可用的單位資源表示一個(gè)資源喝检，或者說一個(gè)允許多種非同步化的并發(fā)的訪問嗅辣。（也就是多個(gè)線程可以同時(shí)訪問）（同時(shí)訪問數(shù)的上限用count定義）

信號量的語義

• 一種假想：

void P(int *semaphore) {
    while (*semaphore <= 0);
    *semaphore--;
}
void V(int *semaphore) {
    *semaphore++;
}

上述實(shí)現(xiàn)的操作必須是原子，但忙等其實(shí)很耗資源蛇耀，所以實(shí)際信號量的實(shí)現(xiàn)并不是這樣辩诞。

實(shí)際信號量是如下的結(jié)構(gòu)：

struct Semaphore {
    int value;
    Queue q;
};

也就是有一個(gè)等待隊(duì)列。mutex信號量其實(shí)很lock很像纺涤，僅僅是語義不一樣译暂。

使用信號量可能存在的問題

問題一：死鎖
先看下面一段代碼：
S = 1; Q = 1;
P0：P(S); P(Q); V(S); V(Q);
P1：P(Q); P(S); V(Q); V(S);
這種情況下，如果P0先搶到了S撩炊，P1先搶到了Q外永，則兩個(gè)線程會陷入死鎖。

經(jīng)典的同步問題——讀者寫者問題

• 問題描述：
  • 一個(gè)對象被多個(gè)線程共享
  • 有一些線程只讀拧咳，有一些線程只寫
  • 我們允許同時(shí)有多個(gè)讀者伯顶，但同時(shí)只能有一個(gè)寫者
• 用信號量解決這個(gè)問題：
• 嘗試一：

  Semaphore w_or_r = 1;
  Reader {
      P(w_or_r);
      read;
      V(w_or_r);
  }
  Writer {
      P(w_or_r);
      write;
      V(w_or_r);
  }
  

  但這是不可行的，讀者和寫者的角色沒有區(qū)分開骆膝。讀者和讀者之間也是互斥的祭衩，并不能滿足多個(gè)讀者同時(shí)讀的要求。
• 嘗試二

  Semaphore w_or_r = 1;
  int readcount; //record readers
  Reader {
      readercount ++;
      if(readcount == 1) {
          P(w_or_r);   //lock out writers
      }
      read;
      readcount--;
      if(readcount == 0) {
          V(w_or_r); //up for grabs
      }
      Writer {
          P(w_or_r);    //lock out readers
          write
          V(w_or_r);  //up for grabs
      }
  }
  

  但這樣又存在一個(gè)問題：readcount是所有的讀者的共享變量阅签。假設(shè)所有的讀者都在readcount++;后被調(diào)度下CPU掐暮，則讀者無法搶到鎖。
• 真實(shí)的做法（給readcount也加上鎖）：
  使用三個(gè)變量readcount mutex w_or_r

  int readcount = 0; 
  Semaphore mutex = 1;
  Semaphore w_or_r = 1;
  Writer {
      P(w_or_r);
      write;
      V(w_or_r);
  }    
  Reader {
      P(mutex);
      readcount++;
      if(readcount == 1)
          P(w_or_r);
      V(mutex);
      Read;
      P(mutex);
      readcount--;
      if(readcount == 0)
          V(w_or_r);
      V(mutex);
  }
  

  這種做法就是讓第一個(gè)讀者作為所有讀者的代表去搶讀寫鎖政钟，但一個(gè)寫者只能自己搶鎖路克。所以會造成寫者的饑餓樟结。假想一直有讀者，則寫者就一直得不到鎖精算。

由此我們引出了第二個(gè)問題：饑餓
如何寫出一個(gè)不會出現(xiàn)饑餓問題的解法呢瓢宦？

回顧信號量

• 信號量可以被用來解決一些傳統(tǒng)的同步問題
• 但信號量有一些缺陷：
  • 它們本質(zhì)上是共享變量，可以在程序的任何地方使用
  • 在共享變量和信號量之間其實(shí)沒有什么邏輯聯(lián)系
  • 既可以用作臨界區(qū)（互斥機(jī)制）又可以用于協(xié)調(diào)（schedulling）
  • 沒有辦法控制和保證正確的使用
• 有的時(shí)候很難使用灰羽，而且易于出錯(cuò)驮履。