google-code-prettify

2015年2月20日 星期五

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

沒有留言:

張貼留言