可調(diào)試的信號量PV原語快速實現(xiàn)方法

摘要：為解決操作系統(tǒng)原理教材中同步互斥經(jīng)典算法驗證問題，提出了一種線程級可調(diào)試的信號量PV原語快速代碼實現(xiàn)方法。利用該方法對經(jīng)典的簡單生產(chǎn)者－消費者同步問題的偽代碼算法進行了C語言編程演示。通過演示說明了該方法代碼短小且可在多種操作系統(tǒng)下調(diào)試運行。

關(guān)鍵詞：信號量；PV原語；同步；互斥；生產(chǎn)者－消費者問題

中圖分類號：TP316 ? ? ?文獻標識碼：A

文章編號：1009-3044（2022）31-0090-03

1 概述

操作系統(tǒng)是計算機系統(tǒng)的核心和靈魂，進程是操作系統(tǒng)中最基本最重要的概念[1]。進程實現(xiàn)了并發(fā)多任務，多任務的同步互斥問題是操作系統(tǒng)原理課程的難點，對應用軟件多任務設(shè)計具有指導意義。信號量（semaphore） 是荷蘭計算機科學家Dijkstra在1965年提出的同步工具，是一種變量類型，有兩個分量：一個是信號量的值，另一個是信號量隊列。該類變量僅能由同步原語PV對其進行操作，PV原語具有原子性。信號量是操作系統(tǒng)實現(xiàn)進程同步的經(jīng)典機制，也是操作系統(tǒng)類課程中的最常用的同步機制[1-2]。PV原語的算法邏輯簡單，但是能夠靈活控制任務狀態(tài)的變化，廣泛應用在解決多任務速度匹配和資源調(diào)度問題中。尤其是對生產(chǎn)者－消費者問題、理發(fā)師問題都有基于信號量和PV原語的成熟解決算法。

在操作系統(tǒng)類課程中基于信號量和PV原語解決經(jīng)典同步問題時，不能直接進行簡潔代碼演示，只能使用偽代碼進行算法表述，結(jié)果由推理獲得。由于偽代碼沒有明確標準，讀者只能遵循經(jīng)典教材的使用范例，但經(jīng)典教材的風格也不統(tǒng)一。如在南大版費翔林和北大版陳向群的教材中信號量使用的是P操作和V操作，而在同樣廣泛使用的西電版湯小丹的教材中信號量使用的是Wait操作和Signal操作[3] 。由于相同問題可能會有不同版本的偽代碼描述，偽代碼不能直接運行輸出結(jié)果，容易導致算法難以理解。

目前操作系統(tǒng)原理教學中逐步引入了多任務實驗，實現(xiàn)方法有基于Java線程類方法、Linux+SystemV信號量方法[4]、基于Windows API的進程方法[5]。這些方法雖然能夠?qū)崿F(xiàn)多任務的同步與互斥，但涉及了較多的編程新概念，代碼冗長，需要較復雜的編程環(huán)境支持。大量非關(guān)鍵的概念和函數(shù)，不利于突出信號量和PV原語的作用。C語言作為普通高校程序設(shè)計基礎(chǔ)的必修課，同時也是操作系統(tǒng)實現(xiàn)的主要語言，具有很好的跨平臺特性，基于C語言標準庫提供可調(diào)試運行的信號量和PV原語具有一定的意義。

2 實現(xiàn)方法

現(xiàn)代操作系統(tǒng)中引入了線程概念。線程是輕量級的進程，是操作系統(tǒng)的可被調(diào)度和分派的基本單位。多線程環(huán)境中進程可以分為兩部分：資源集合和線程集合。由于同一進程中的多線程會競爭處理器資源，或運行中出現(xiàn)等待輸入輸出事件，故線程狀態(tài)也有運行態(tài)、就緒態(tài)、等待和終止態(tài)。經(jīng)典進程同步問題就可以轉(zhuǎn)換為線程同步問題，解決進程同步問題的基于PV原語算法可以在線程同步問題中來模擬實現(xiàn)。

線程實現(xiàn)方法分為內(nèi)核級線程，如Windows 2003；用戶級線程，如POSIX中的Pthread庫、Java線程庫；混合式線程，如Solaris 。內(nèi)核級線程需要內(nèi)核調(diào)試環(huán)境，配置非常復雜。用戶級線程在用戶應用程序中可以被編程管理，只需要普通的應用程序編程環(huán)境。用戶級線程庫在多種編程語言環(huán)境中有相關(guān)庫或類支持，如C語言、Java語言、C#語言等。C語言作為操作系統(tǒng)和系統(tǒng)庫的主要實現(xiàn)語言，在編制相關(guān)的多任務同步演示程序上具有一定的優(yōu)勢。由于多任務同步演示環(huán)境需要考慮在Windows平臺和Unix平臺上的實現(xiàn)，需要注意消除兩種系統(tǒng)中實現(xiàn)源代碼的差異性。雖然Java語言、C#語言本身具有跨平臺的實現(xiàn)，但是集成開發(fā)編程環(huán)境龐大（一般大于1GB） ，不如純粹的GNU C語言開發(fā)環(huán)境簡潔，集成GNU C編譯器的DEV C++集成開發(fā)環(huán)境安裝包只有50MB左右。

POSIX（Portable Operating System Interface，縮寫為POSIX） 翻譯為可移植操作系統(tǒng)接口，是IEEE為要在各種UNIX操作系統(tǒng)上運行軟件，而定義API的一系列互相關(guān)聯(lián)的標準的總稱。Pthread庫是實現(xiàn)了POSIX線程規(guī)范的一套API，POSIX的信號量API可以和Pthread協(xié)同工作。Pthread庫一般用于Unix-like POSIX 系統(tǒng)，如Linux、Solaris，在Microsoft Windows上也有實現(xiàn)，具有源代碼級的可移植性。由于Pthread庫可在用戶空間實現(xiàn)，在通用操作系統(tǒng)上均能夠比較方便獲得。因此可以采用一定的封裝技術(shù)，在通用操作系統(tǒng)上實現(xiàn)信號量和PV原語。

具體方法是使用線程實現(xiàn)多任務，利用Pthread提供的sem_t信號量實現(xiàn)傳統(tǒng)的信號量，sem_t信號量的操作模擬為PV原語。為了減少類型和函數(shù)名稱的差異帶來的誤解，引入自定義數(shù)據(jù)類型和宏定義進行封裝。使用C語言自定義類型將Pthread庫中的sem_t類型修改為semaphore類型，使用宏定義機制將sem_wait函數(shù)模擬P操作，sem_post函數(shù)模擬V操作，sem_init函數(shù)對信號量進行初始化。

#define ?P（S） ?（sem_wait（S））

#define ?V（S） ?（sem_post（S））

typedef ?sem_t ?semaphore;

經(jīng)過基本封裝后，PV原語變成兩個普通的C語言函數(shù)，可以直接使用。信號量semaphore 變成一種自定義數(shù)據(jù)類型，利用Pthread多線程替代進程模擬多任務。

sem_t是Pthread庫中的自定義union數(shù)據(jù)類型，通過源代碼分析實際為一個整數(shù)，和經(jīng)典的信號量定義相似。由于具體實現(xiàn)中，sem_t變量不能直接賦值，需要通過函數(shù)sem_init進行賦值，信號量的初始值為sem_init中的第3個參數(shù)。sem_wait 是Pthread庫中的一個函數(shù)，功能和經(jīng)典的P操作定義相似，在線程中被定義為一個原子操作，它的作用是從信號量的值減1，但它會先等待該信號量為一個非零值才開始做減法。sem_post是Pthread庫中的一個函數(shù)，功能和經(jīng)典的V操作定義相似，在線程中被定義為一個原子操作，它的作用是信號量的值加1。這兩個函數(shù)都是用sem_t 型參數(shù)。C語言中宏定義機制能夠為變量或者函數(shù)取別名，通過把sem_t轉(zhuǎn)換為semaphore，把sem_wait轉(zhuǎn)換為P操作，把sem_post轉(zhuǎn)換為V操作，能夠提高代碼的可閱讀性。

3 算法轉(zhuǎn)換與應用

PV原語是解決經(jīng)典多任務同步問題的有效工具，下面結(jié)合經(jīng)典的簡單生產(chǎn)者—消費者同步問題將偽代碼進行可調(diào)試運行代碼轉(zhuǎn)換。簡單生產(chǎn)者－消費者問題是生產(chǎn)者－消費者問題的特例，即只共享單個緩沖區(qū)，不需要使用緩沖區(qū)互斥操作。典型的簡單生產(chǎn)者－消費者問題偽代碼解法如圖1所示[1]。該問題解法利用信號量和PV原語實現(xiàn)同步。Producer表示生產(chǎn)者任務，Consumer表示消費者任務，兩個任務共用一個緩沖區(qū)。生產(chǎn)者和消費者是并發(fā)執(zhí)行，兩個任務的同步邏輯是緩沖區(qū)為空時消費者需要等待生產(chǎn)者，緩沖區(qū)滿時生產(chǎn)者需要等待消費者。

在上述偽代碼的解法中，編號①的部分進行緩沖區(qū)B和信號量的初始化，此處empty的值為1，full的初值為0。編號②部分由cobegin和coend組成，表示包裹的代碼任務將并發(fā)執(zhí)行，此處說明建立了producer和consumer任務。編號③部分producer是生產(chǎn)者任務實現(xiàn)代碼，PV原語用于實現(xiàn)對緩沖區(qū)B的同步。編號④部分consumer是消費者任務實現(xiàn)代碼，PV原語用于實現(xiàn)對緩沖區(qū)B的同步。信號量empty和full的初值和P操作的順序都有嚴格規(guī)定，但是偽代碼不能直觀看出由于初值和順序調(diào)整引起的執(zhí)行結(jié)果變化。利用Pthread和封裝的信號量PV原語，對應C語言代碼如下圖2所示。為了方便對比說明，將實現(xiàn)代碼進行了重新編排。

圖2的左上①部分描述了如何構(gòu)造PV原語，基于C語言的宏定義有利于得到和偽代碼一致的描述。圖2的右上部分②完成信號量的初始化和任務的創(chuàng)建，信號量的初始值通過特定函數(shù)進行設(shè)置，任務創(chuàng)建后與主進程一起運行。其中pthread_create函數(shù)功能是創(chuàng)建線程并立即參與調(diào)度，pthread_join用來等待一個特定線程的結(jié)束，sem_init實現(xiàn)對信號量值的初始化。圖2的下半部分③ producer描述了生產(chǎn)者的算法實現(xiàn)，循環(huán)執(zhí)行P操作實現(xiàn)等待緩沖區(qū)為空，生產(chǎn)產(chǎn)品，然后通知消費者消費；圖2下半部分④ consumer描述了消費者的算法實現(xiàn)，循環(huán)執(zhí)行等待緩沖區(qū)有產(chǎn)品，消費產(chǎn)品，通知生產(chǎn)者生產(chǎn)。其中關(guān)鍵的P操作V操作位置、empty和full信號量的初值和偽代碼描述一致。代碼中添加的sleep函數(shù)用于模擬生產(chǎn)者和消費者執(zhí)行時間不一致，同時sleep函數(shù)調(diào)用會主動觸發(fā)任務進入阻塞狀態(tài)，便于更好體現(xiàn)線程調(diào)度的作用。使用有限次數(shù)for循環(huán)代替無限while循環(huán)是為了觀察分析輸出結(jié)果。

該問題解決方法的代碼長度可控制到50行，與偽代碼有較好的對應關(guān)系，并可以靈活修改。在Ubuntu Linux 14+GCC 4.2環(huán)境下和Windows 7/8/10 + Dev Cpp V5.0 開發(fā)環(huán)境均能夠正常運行。輸出結(jié)果如圖3所示為交替輸出生產(chǎn)和消費值。在代碼中生產(chǎn)者的任務執(zhí)行時間和消費者任務執(zhí)行時間雖然不一致，但是通過合理地使用信號量和PV原語，仍然實現(xiàn)了生產(chǎn)—消費同步約束邏輯，即緩沖區(qū)空時才能執(zhí)行生產(chǎn)任務，緩沖區(qū)滿時才能執(zhí)行消費任務，結(jié)果符合生產(chǎn)者—消費者問題信號量同步算法的預期。

由于本方法是由C語言程序?qū)崿F(xiàn)，可以通過修改源代碼方式對信號量設(shè)置不同的初值，以及修改PV原語的位置能夠獲得多種輸出，通過信號量和PV原語算法進行推導解釋。比如對同步信號量full如果初值設(shè)置為1，empty初值也設(shè)置為0，表示緩沖區(qū)任務開始時緩沖區(qū)已經(jīng)滿的情況。由于是單緩沖情形，生產(chǎn)者任務在緩沖區(qū)滿的情況下應該不能運行，而消費者任務應該可以運行，所以預期運行結(jié)果應該是消費者任務先運行，但是消費任務輸出應該為0。基于信號量PV操作的同步算法，只需要修改圖1源程序中行36和行37，修改后代碼如圖4所示。

信號量值修改后運行結(jié)果如圖5所示，其中消費者任務先運行而緩沖區(qū)初始值為0，所以輸出為消費0，而本程序是只設(shè)計運行四次，所以沒有消費4輸出。符合同步算法預期結(jié)果，能夠直觀反映出信號量PV原語在同步機制中的作用。

綜上所述，本方法中信號量和PV原語與偽代碼中的信號量和PV原語基本一致，教材中基于信號量和PV原語實現(xiàn)的同步互斥問題算法偽代碼能夠快速轉(zhuǎn)換為可運行的C語言代碼。類似的一些教材中基于信號量的wait操作和signal操作表示的等待喚醒偽代碼，也能夠使用本方法進行C語言轉(zhuǎn)換。為了便于驗證和使用源代碼，已經(jīng)在Gitee網(wǎng)站（碼云）上建立代碼倉庫網(wǎng)址是https：//gitee.com/wayxingwork/pcdemo。

4 結(jié)束語

通過把Pthread庫中的信號量和相關(guān)操作進行友好封裝，實現(xiàn)了多操作系統(tǒng)平臺下對經(jīng)典進程同步互斥問題的可調(diào)試編程，便于學習者理解掌握多任務同步互斥算法知識。同時，具體實現(xiàn)方法考慮了開發(fā)環(huán)境和代碼獲取等因素，方便在線開放課程教學和課堂演示。

操作系統(tǒng)原理作為計算機專業(yè)基礎(chǔ)課程，教學課時一般為48學時，主要采用講授法進行理論教學。在應用型本科和高職高專層次教學過程中，經(jīng)常出現(xiàn)教學效果不佳等問題。改進的方法主要是教師優(yōu)化教學模式[6]和教學方法[7]，或者是創(chuàng)新理論推導公式[8]等方法，以及大量的典型習題訓練。通過對經(jīng)典問題提供可對照可調(diào)試的代碼解決方法也是一個改進的途徑。

由于進程和線程的概念差異性，本方法是在用戶空間多任務層次實現(xiàn)了可調(diào)試運行的信號量和PV原語，和傳統(tǒng)的信號量的定義仍有一定的差異，如何封裝類似管程的高級同步機制，后續(xù)需進行相關(guān)方面探索研究。

參考文獻：

[1] 費翔林，駱斌.操作系統(tǒng)教程[M].5版.北京：高等教育出版社，2014.

[2] 陳向群，楊芙清.操作系統(tǒng)教程[M].2版.北京：北京大學出版社，2006.

[3] 湯小丹，梁紅兵，哲鳳屏.計算機操作系統(tǒng)[M].3版.西安：西安電子科技大學出版社，2007.

[4] 費翔林，李敏，葉保留.Linux操作系統(tǒng)實驗教程[M].北京：高等教育出版社，2009.

[5] 金海東，徐云龍.“操作系統(tǒng)”課程中進程同步互斥教學研究[J].計算機教育，2009（14）：60-62.

[6] 李欣.計算機操作系統(tǒng)課程中PBL教學模式的應用研究[J].信息技術(shù)與信息化，2016（11）：123-124.

[7] 王秋芬，王永新.基于OBE的操作系統(tǒng)原理課程教學方法改革與實踐[J].教育教學論壇，2019（12）：167-168.

[8] 魯力，韓潔，徐琴.PV操作解決進程同步問題的難點研究與實現(xiàn)[J].電腦知識與技術(shù)，2017，13（13）：38-39.

【通聯(lián)編輯：謝媛媛】

收稿日期：2022-05-08

基金項目：廣東科技學院校級科研項目（項目編號：GKY-2021KYZDK-13）

作者簡介：魏星（1972—） ，男，重慶人，高級工程師，碩士，研究方向為測控技術(shù)。