semaphore整理

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multitasking operating system. (In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a concurrent system such as a multitasking operating system. (Wikipedia)

semaphore機制主要是用來控制有限個數的resource存取問題，

例如洗手間有3間，可是同時間有十個人要使用，

這時候就會需要synchronization(一間洗手間同一個時間只能有一個人使用，同時最多三個人使用)

大家排隊依序使用-> FIFO

semaphore S本身是一個變數(waiting count/available resource count)，只能透過P(wait)和V(signal)來操作，

S <= 0 代表waiting count，全部resource使用中

S > 0 代表閒置的resource count

P: get or wait for resource, decrement S, wait(after decrement, if S<0)
V: 來自Dutch verhogen(increase), release the resource, increment S, notify waiting(before increment, if S<0, 代表increment之前有等待)

binary semaphore (count = 1) 例如一條鐵軌區段只能有一輛火車在上面運行，和mutex非常相似，其中差異在 semaphore不限定同一個thread可以解除資源鎖定，而mutex通常要求lock unlock在同一個thread。

這樣的特性使得semaphore有signaling的功能，有文章分類成locking semaphore和signaling semaphore，locking semaphore加鎖P和釋放V在同一個thread ( http://nuttx.org/doku.php?id=wiki:howtos:signalling-semaphores )。對比的話，locking semaphore – mutex, signaling semaphore – condition variable

另外一個須注意的地方是在priorty-based scheduling下，semaphore可能會造成priority inversion(對於需要鎖定資源的synchronization primitive都會遇到同樣的問題)，其中一種解法是priority inheritance(對於mutex, locking semaphore)

semaphore的API在POSIX.1b有定義(sem_ 開頭，不在pthreads中)

其他: 參考 https://en.wikipedia.org/wiki/Semaphore_(programming)

producer-consumer problem:
producer – queue – consumer
需用到三個semaphore
一個用來通知producer queue有位置可以放東西
一個用來通知consumer queue有東西可以取
一個binary semaphore用來鎖定queue的存取

2021.2.20 補充

在linux kernel 2.6.39裡的semaphore實作，他的semaphore count總是 >=0的，跟上面的PV計算方式不同(上面的count < 0代表有等待)，linux kernel是用 count + wait_list 來判斷

void down(struct semaphore *sem)
{
  unsigned long flags;

  spin_lock_irqsave(&sem->lock, flags);
  if (likely(sem->count > 0))
    sem->count--;
  else
    __down(sem);
  spin_unlock_irqrestore(&sem->lock, flags);
}
void up(struct semaphore *sem)
{
  unsigned long flags;

  spin_lock_irqsave(&sem->lock, flags);
  if (likely(list_empty(&sem->wait_list)))
    sem->count++;
  else
    __up(sem);
  spin_unlock_irqrestore(&sem->lock, flags);
}