System V Semaphore

在撰寫 Linux AP 時，System V semaphore 經常作為保護關鍵區域(critical section)或在不同 process 之間的同步(synchronization)之用。所謂 critical section 是指某程式碼段落對特定資源(可能是任何變數、檔案、驅動等等)做操作，而該資源若同時被不同程式(process)讀寫可能會有風險導致系統崩潰。好比 A process 正在寫入某 flash sector，此時 B process 正巧要讀取也要讀取同一個 flash sector，此時讀寫可能都會失敗，而導致系統不穩定。此類問題在多工作業系統中可能經常發生，因此需要使用一個機制來限制特定區域的存取。

為了解決上述情況，荷蘭電腦科學家 Edsger W. Dijkstra 發明了 semaphore (號誌)的概念，使用 P(荷蘭語 passeren, wait)操作取得 semaphore 與 V(荷蘭語 vrijgeven, signal) 操作釋放 semaphore，由此來控制 critical section 的進入量。

semaphore 可以區分為 counting semaphore(計數號誌) 與 binary semaphore(二位元號誌，等同 Mutex)，差別只在於初始化時 semaphore 的量為多少。binary semaphore 嚴謹的限制 critical section 同時間只能有一個 process 進入，反之 counting semaphore 則可允許 N 個 process 同時操作。大多數的情況 binary semaphore 足以應付程式的需要，因此下面的實作也以此為主。

Linux System Call

Linux Kernel 所提供關於 Semaphore 的 System Call:

int semget(key_t key, int nsems, int semflg);
int semctl(int semid, int semnum, int cmd, ...);
int semop(int semid, struct sembuf *sops, unsigned nsops);

這三個 function 在實作 semaphore 是不可或缺的，概略說明如下

int semget(key_t key, int nsems, int semflg) – 取得/建立號誌
key: semaphore 的鍵值，可以為任意整數，用以區別不同 semaphore
nsems: semaphore 的數量。注意，這與 counting semaphore 或 binary semaphore 無關，而是你要取得多少個 semaphore。
semflg: 權限與旗標的集合。旗標選為 IPC_CREATE 代表建立 semaphore，但號誌已存在時也不會返回錯誤訊息，而是直接取得該號誌。若想要在號誌已存在的情況下返回錯誤可與 IPC_EXCL 連用。
return: 執行成功取得一個正整數，該整數就是 semaphore ID。執行失敗返回 -1 並且設置 error number。

int semctl(int semid, int semnum, int cmd, …) – 設定號誌
semid: semaphore ID，也就是 semget() 的回傳值。
semnum: 要針對第幾個 semaphore 操作。如剛剛所敘述，一個 semaphore ID 可能包含數個 semaphore 在其中，故此參數是指定要對第幾個 semaphore 做設定。編號從 0 開始。
cmd: 針對 semaphore 做何種操作(命令)。命令有許多種，但較常使用的 command 只有 SETVAL GETVAL IPC_RMID
…: 第四個參數的需要與否取決於 cmd 的值為何，若需要時則是帶入指向 union semun 的指標。該聯合內容為

union semun {
    int              val;    /* Value for SETVAL */
    struct semid_ds *buf;    /* Buffer for IPC_STAT, IPC_SET */
    unsigned short  *array;  /* Array for GETALL, SETALL */
    struct seminfo  *__buf;  /* Buffer for IPC_INFO
                                (Linux-specific) */
};

return: 執行失敗返回 -1 並且設置 error number。執行成功根據不同 command 回傳正整數。

int semop(int semid, struct sembuf *sops, unsigned nsops) – 操作號誌
semid: semaphore ID，也就是 semget() 的回傳值。
sops: 傳入指向 sembuf 結構的指標或陣列。其結構為

unsigned short sem_num;  /* semaphore number */
short          sem_op;   /* semaphore operation */
short          sem_flg;  /* operation flags */

sem_num 代表要針對此 semaphore ID 中的第幾個 semaphore 做操作。
sem_op 大於 0 相當於執行 V 操作，將號誌量(semaphore value)釋放回此 semaphore。
小於 0 相當於執行 P 操作，自該 semaphore 中取得號誌量。若號誌量不足，預設將會持續等待，直到有可用的號誌量才會返回。
等於 0 則代表檢驗此 semaphore 的號誌量是否為零，等於零才會返回，不等於零預設會持續等待。
sem_flg 為控制旗標。一般常會使用 SEM_UNDO 來確保萬一在操作過程中程式因為突發狀況終止，可以還原此一操作。用意在避面 A，B 兩個 process 同時使用一個 semaphore 時，當 A 取得 semaphore 後被使用者強制中止後，B 將會發生餓死的情況(starving)。此外若不希望程式為了取得 semaphore 而等待，可以使用 IPC_NOWAIT 旗標。設置後若無法取得 semaphore 將直接返回錯誤。

nsops: 由於第二個參數 sops 可以 array 的方式傳入，此參數代表 sops array 總共有幾個元素。

實作

首先，若要使用 System V semaphore 核心必須要支援，一般 x86 PC Linux kernel 預設都會支援。但若要執行在嵌入式系統上，請注意核心的 config file 有沒有選上 CONFIG_SYSVIPC 選項。若使用 menuconfig 設定，此選項會出現於 General setup -> System V IPC。可以檢驗檔案系統上是否有 /proc/sysvipc/ 路徑存在，判斷系統是否支援 System V IPC。

假設我有兩個 process proc1 與 proc2 都需要操作同一個資源，其同時只能被一個 process 使用，因此操作該資源的程式段稱作 critical section。在進入 critical section 之前必須取得 semaphore 已確保沒有其他 process 正在操作。

由於可能會經長性的使用到 semaphore 的相關 system call，因此將其寫成簡單的函式當作 API 給 process 使用。

int init_semaphore(key_t key, int sem_val)
{
    int         sem_id;
    union semun sem_union;

    sem_id = semget(key, 1, 0666 | IPC_CREAT);

    if (sem_val >= 0) {
        sem_union.val = sem_val;

        if (semctl(sem_id, 0, SETVAL, sem_union) == -1) {
            return -1;
        }
    }

    return sem_id;
}

使用 key 值建立一個權限為 666 的信號，且若 sem_val 大於等於零則以此當作初始的信號量。

int del_semaphore(int sem_id)
{
    union semun sem_union;

    if (semctl(sem_id, 0, IPC_RMID, sem_union) == -1) {
        return -1;
    } else {
        return 0;
    }
}

刪除 sem_id 的號誌。這裡呼叫 semctl() 的第四個參數 sem_union 是可以省略的。

int semaphore_p(int sem_id)
{
    struct sembuf sem_b;

    sem_b.sem_num = 0;
    sem_b.sem_op = -1;
    sem_b.sem_flg = SEM_UNDO;
    if (semop(sem_id, &sem_b, 1) == -1) {
        fprintf(stderr, "semaphore_p failed\n");
        return -1;
    }
    return 0;
}

sem_op 的值為 -1 ，代表要取得信號量的意思。

int semaphore_v(int sem_id)
{
    struct sembuf sem_b;

    sem_b.sem_num = 0;
    sem_b.sem_op = 1;
    sem_b.sem_flg = SEM_UNDO;
    if (semop(sem_id, &sem_b, 1) == -1) {
        fprintf(stderr, "semaphore_v failed\n");
        return -1;
    }
    return 0;
}

sem_op 的值為 1 ，代表要釋放信號量的意思。

int main (int argc, char *argv[])
{
    int semid;

    printf("%s - get the semaphore\n", PROCESS_NAME);

    semid = init_semaphore(KEY_SEM_EXAMPLE, 1);
    if (semid == -1) {
        perror(PROCESS_NAME);
        exit(EXIT_FAILURE);
    }

    printf("%s - wait the semaphore\n", PROCESS_NAME);
    if (SEM_P(semid) != 0) {
        perror(PROCESS_NAME);
        exit(EXIT_FAILURE);
    }

    printf("%s - enter critical section\n", PROCESS_NAME);
    sleep(5);
    printf("%s - exit critical section\n", PROCESS_NAME);

    printf("%s - signal the semaphore\n", PROCESS_NAME);
    SEM_V(semid);

    sleep(10);

    printf("%s - destory the semaphore\n", PROCESS_NAME);
    if (del_semaphore(semid) != 0) {
        perror(PROCESS_NAME);
        exit(EXIT_FAILURE);
    }

    exit(EXIT_SUCCESS);
}

proc1 –
Line 14: 建立號誌，初始號誌量為 1 。
Line 21: 取得號誌。
Line 27: sleep(5) 假裝是執行 critical section 操作。
Line 31: 釋放號誌。
Line 36: 移除號誌。前面先 sleep(10) 是避免移除號誌時 proc2 還在使用而造成錯誤。

int main (int argc, char *argv[])
{
    int semid;

    sleep(1);

    printf("%s - get the semaphore\n", PROCESS_NAME);
    semid = init_semaphore(KEY_SEM_EXAMPLE, 0);
    if (semid == -1) {
        perror(PROCESS_NAME);
        exit(EXIT_FAILURE);
    }

    printf("%s - wait the semaphore\n", PROCESS_NAME);
    if (SEM_P(semid) != 0) {
        perror(PROCESS_NAME);
        exit(EXIT_FAILURE);
    }

    printf("%s - enter critical section\n", PROCESS_NAME);
    sleep(5);
    printf("%s - exit critical section\n", PROCESS_NAME);

    printf("%s - signal the semaphore\n", PROCESS_NAME);
    SEM_V(semid);

    exit(EXIT_SUCCESS);
}

proc2 –
Line 14: 取得號誌，第二個參數。
Line 21: 取得號誌。
Line 27: sleep(5) 假裝是執行 critical section 操作。
Line 31: 釋放號誌。
Line 36: 移除號誌。前面先 sleep(10) 是避免移除號誌時 proc2 還在使用而造成錯誤。
若是在 x86 PC 上執行，可以將 tarball 解開後直接執行 go.sh，script 會自動編譯與執行 proc1 與 proc2 顯示出結果：

felix@felix-Vostro-1450:~/sem$ ./go.sh 
proc1 - get the semaphore
proc1 - wait the semaphore
proc1 - enter critical section
proc2 - get the semaphore
proc2 - wait the semaphore
proc1 - exit critical section
proc1 - signal the semaphore
proc2 - enter critical section
proc2 - exit critical section
proc2 - signal the semaphore
proc1 - destory the semaphore
felix@felix-Vostro-1450:~/sem$

從結果中可看出，在 proc1 進入 critical section 後，proc2 必須要等待 proc1 離開 critical sector 且 signal semaphore 之後才可以再次進入。

附件

程式碼： felix-lin_sem.tar.bz2

一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Focus

Felix Lin's Exploration of Life

實作 System V Semaphore in Linux User Space

System V Semaphore

Linux System Call

實作

附件

延伸閱讀

27 則迴響於《實作 System V Semaphore in Linux User Space》

發佈留言取消回覆

System V Semaphore

Linux System Call

實作

附件

延伸閱讀

27 則迴響於《實作 System V Semaphore in Linux User Space》

發佈留言 取消回覆

發佈留言取消回覆