semaphore (信號)

Semaphore原理與操作說明

作者/王宜倫

[發表日期：2012/5/5]

甚麼是semaphore (信號)

Semaphore是Edsger W. Dijkstra於1960年代末期所設計的一種程式設計架構。Semaphore是一個variable (變數)或是abstract data type (抽象資料型別)，提供平行運算環境中，控制多個process (程序)或thread(執行緒)存取共享資源的能力，Semaphore可以用於紀錄某一特定資源剩下多少數目可使用；process或thread透過semaphore可以安全的使用共享資源，若特定資源已使用完時，會需要等待資源被釋放。雖然semaphore在防止deadlock或race condition方面是一個很有用的工具，但是程式使用semaphore運作上並無法保證一定不會遇到這些問題。

Semaphore包含兩種：binary semaphore(二進位信號)和counting semaphore(計數信號)。

一、binary semaphore(二進位信號)

binary semaphore值只能是0或1，在邏輯上相當於一個mutex(互斥鎖)。mutex使用上與binary semaphore具有相同功能，但是，mutex主要設計是防止兩個process同時間執行相同的一段code或存取同一資料，而binary semaphore設計上則是限制同時間存取同一資源；很多應用上mutex具有owner(擁有者)的概念，只有鎖住mutex的process，才具有解鎖的權限；相對的，semaphore並無此限制。

二、counting semaphore(計數信號)

counting semaphore值依據semaphore.h的SEM_VALUE_MAX (semvmx)定義。也有作業系統稱作general semaphore。

Semaphore的運作原理

Edsger W. Dijkstra的模型與鐵路操作有關：假設某段鐵路是單線的，因此，一次只允許一列火車通過；semaphore用於協調同步通過該軌道的火車，火車在進入單一軌道之前必須等待信號燈變為允許通行的狀態，火車進入軌道後，必須改變信號燈狀態，防止其他火車進入該軌道；火車離開這段軌道時，必須再次更改信號燈的狀態，以便允許其他火車進入軌道。

或是類似圖書館的研究室使用，假設有10間研究室(SEM_VALUE_MAX=10)，若學生要使用研究室便需要向櫃檯申請，櫃檯會記錄有多少間研究室使用中，若10間研究室都被申請使用後，且仍有學生要申請使用，該學生必須等待有其他學生離開，空出研究室後，才能進入使用，該櫃檯就扮演semaphore的角色。

在電腦系統中，信號燈(semaphore)以整數來表示，可用兩種操作行為來說明：

一、V operation：V()會將semaphore的值加1，signal函數或是sem_post()。
二、P operation：P()會將semaphore的值減1，wait函數或是sem_wait()。

P和V的意義來自荷蘭文(Edsger W. Dijkstr為荷蘭人)，V代表verhogen，其意思是增加，P代表portmanteau prolaag，其意思是嘗試減小。在P operation中，semaphore在減小之前必須為正，確保semaphore值不為負，並且比該值減小之前小1；在P和V operation中，必須在沒有干擾的情況下進行運算，亦即每個P或V operation必須具備atomic operation特性，該operation是不可分割的(all or nothing behavior)。

從semaphore概念上來說，counting semaphore為一個非負整數計數器，通常用來協調process或thread對共享資源的存取。semaphore value可用來表示可用資源的數目，可在初始化時將semaphore value設為可用資源的數目，然後，在使用資源時減1，在釋放資源時加1；若為負數時，表示資源不足，要存取共享資源的process或thread會被阻擋(block)，需要等待semaphore value變為正整數時，才可存取共享資源。實務上，也可將semaphore初始值設為1，使用該資源時加1，釋放資源時減1，若無法再加1時(signal或post回傳-1)，表示已無資源可使用，程式需針對此錯誤進行處理；部分作業系統當使用超過最大值時(SEM_VALUE_MAX)會發生overflow(溢位)，變為負數，表示資源不足。

由於semaphore並無強制由同一個process或thread來獲取和釋放，因此semaphore可用於非同步事件通知；同時，由於semaphore包含狀態，因此可以非同步方式使用，而不用像條件變數那樣要求獲取mutex。但是，semaphore的效率不如mutex。

Semaphore可以是無名稱的(unnamed)或是有名稱的(named)，unnamed semaphore可供單一process或不同process使用，依據初始化時設定決定，named semaphore則在不同process間同步共享資源。

Semaphore的使用

此章節以POSIX semaphore來說明semaphore的初始化、V operation、P operation與結束。關於POSIX semaphore的特性說明如下：

• POSIX semaphore是標準的counting semaphore，使用sem_post()執行V opeation，sem_wait()執行P operation。


• POSIX semaphore的最大值於limits.h中所定義，如下：
  #define _POSIX_SEM_VALUE_MAX 32767
  define中所定義的最大值32767為POSIX標準規範的值，亦即實際各種作業平台的semaphore最大值至少需為32767才符合POSIX規範；實際最大值可由sysconf()所設定：
  long sem_value_max = sysconf(_SC_SEM_VALUE_MAX);
  目前實際程式測試，各種主要作業系統的SEM_VALUE_MAX如下：
  Windows 2008 : 2,147,483,647
  RHEL 5.0 : 2,147,483,647
  CentOS : 2,147,483,647
  Solaris 10 : 2,147,483,647
  HP-UX 11iv3 : 2,147,483,647
  IBM AIX 6.1 : 32,767


• 一個semaphore並非被單一thread所擁有，亦即一個thread對semaphore執行sem_wait()時，另一thread可以執行sem_post()。但是作業系統在實作時，同一時間點僅能執行其中一個指令，以維持semaphore的一致性。


• 當建立一semaphore時，須設定semaphore的初始值，且初始值須符合：0 ? initial value ? SEM_VALUE_MAX


• Semaphore動作執行成功會回傳0，失敗會回傳 -1，並可將error number存放在errno，C的function perror(const char* string)可將errno的值存放在一字串，可將字串再列印到stderr。


• sem_trywait(sem_t* sem)不會block呼叫的thread：
  • 若semaphore value大於0，會將semaphore減1，立即完成此動作並回傳。
  • 若semaphore value小於等於0，會立即回傳錯誤EAGAIN，說明semaphore value非大於0。

一、Semaphore操作函數

後續說明sem_init()、sem_post()、sem_wait()、sem_trywait()與sem_destroy()使用方式。

• sem_init()：初始化semaphore
  
  語法：
  int sem_init(sem_t *sem, int pshared, unsigned int value);
  
  #include 
  sem_t sem;
  int pshared;
  int rc;
  int value;
  pshared =0;
  value =1;
  rc = sem_init(&sem, pshared, value);
  
  說明：
  (1)第一個參數為semaphore的位址，第二個參數為設定semaphore是否可讓不同process使用，第三個參數為semaphore初始值。
  (2)pshared的值為0，不能在process之間共用semaphore，僅能供process的所有thread使用；如果pshared的值不為0，則可以在process之間共用信號。
  (3)初始的semaphore值為1。
  (4)多個thread決不能初始化同一個semaphore。
  (5)不得對其他thread正在使用的semaphore重新初始化。
  
  sem_init()成功完成後會回傳0，若回傳值為-1則表示執行發生錯誤，如果出現下任一情況，該函數將失敗並回傳對應值：
  -EINVAL：參數值超過了SEM_VALUE_MAX。
  -ENOSPC：始化semaphore所需的資源已經用完，到達semaphore的SEM_NSEMS_MAX限制。
  -ENOSYS：系統不支援sem_init()函數。
  -EPERM：process缺少初始化semaphore所需的權限。


• sem_post()：增加semaphore值(加1)
  
  語法：
  int sem_post(sem_t *sem);
  
  #include 
  sem_t sem;
  int rc;
  rc = sem_post(&sem);
  
  sem_post()成功完成後會回傳0，若回傳值為 -1則表示執行發生錯誤，如果出現下任一情況，該函數將失敗並回傳對應值：
  -EINVAL：未對應到有效的semaphore。
  -ENOSYS：系統不支援sem_post()函數。


• sem_wait()：減少semaphore值(減1)
  
  語法：
  int sem_wait(sem_t *sem);
  
  #include 
  sem_t sem;
  int rc;
  rc = sem_wait(&sem);
  
  sem_wait()成功完成後會回傳0，若回傳值為 -1則表示執行發生錯誤，如果出現下任一情況，該函數將失敗並回傳對應值：
  -EINVAL：未對應到有效的semaphore。
  -ENOSYS：系統不支援sem_wait()函數。


• sem_trywait()：嘗試減少semaphore值(減1)
  
  語法：
  int sem_trywait(sem_t *sem);
  
  #include 
  sem_t sem;
  int rc;
  rc = sem_trywait(&sem);
  
  sem_trywait()成功完成後會回傳0，若回傳值為 -1則表示執行發生錯誤，且不會block呼叫的thread，如果出現下任一情況，該函數將失敗並回傳對應值：
  -EINVAL：未對應到有效的semaphore。
  -ENOSYS：系統不支援sem_post()函數。
  -EINTR：此函數被semaphore中斷。
  -EAGAIN：semaphore值小於或等於0，無可用的semaphore。


• sem_destroy()：銷毀semaphore
  
  語法：
  int sem_destroy(sem_t *sem);
  
  #include 
  sem_t sem;
  int rc;
  rc = sem_destroy(&sem);
  
  sem_destroy()成功完成後會回傳0，若回傳值為 -1則表示執行發生錯誤，如果出現下任一情況，該函數將失敗並回傳對應值：
  -EINVAL：未對應到有效的semaphore。
  -EBUSY：仍有process或thread被阻塞(blocked)在該semaphore。

二、範例程式

下列C範例程式可於不同系統計算SEM_VALUE_MAX的值。
/*semaphore.c*/
/*count SEM_VALUE_MAX*/
/*gcc -lpthread -lrt semaphore.c */

#include 
#include 
#include 
#include 

int main (int argc, char *argv[])
{
int value;
int rc = 0;
sem_t test_semaphore;
sem_init(&test_semaphore, 0, 1);
sem_getvalue(&test_semaphore, &value);
printf("The value of semaphore is %d\n", value);
while(rc == 0 & (value < 2147483647 & value > 0) )
{
rc = sem_post(&test_semaphore);
sem_getvalue(&test_semaphore, &value);
}

printf("sem_post returns %d\n", rc);
printf("The value of semaphore is %d\n", value);
rc = sem_post(&test_semaphore);
sem_getvalue(&test_semaphore, &value);
printf("sem_post returns %d\n", rc);
printf("The value of semaphore is %d\n", value);
}

參考文獻

http://compgroups.net/comp.unix.solaris/value-of-POSIX_SEM_VALUE_MAX
http://www.ibm.com/developerworks/cn/linux/l-ipc2lin2.html
http://www.cs.gmu.edu/~rcarver/ModernMultithreading/LectureNotes/Chapter3NotesPthreads.pdf
http://en.wikipedia.org/wiki/Semaphore_(programming)
http://www.5dlinux.com/article/6/2010/linux_38554.html
http://bugs.python.org/file12391/explore_sem_value_max.c