Semaphore原理與操作說明

作者/王宜倫

甚麼是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