可調試的信號量PV原語快速實現方法

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

關鍵詞：信號量；PV原語；同步；互斥；生產者－消費者問題

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

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

1 概述

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

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

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

2 實現方法

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

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

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

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

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

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

typedef ?sem_t ?semaphore;

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

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

3 算法轉換與應用

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

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

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

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

由于本方法是由C語言程序實現，可以通過修改源代碼方式對信號量設置不同的初值，以及修改PV原語的位置能夠獲得多種輸出，通過信號量和PV原語算法進行推導解釋。比如對同步信號量full如果初值設置為1，empty初值也設置為0，表示緩沖區任務開始時緩沖區已經滿的情況。由于是單緩沖情形，生產者任務在緩沖區滿的情況下應該不能運行，而消費者任務應該可以運行，所以預期運行結果應該是消費者任務先運行，但是消費任務輸出應該為0?；谛盘柫縋V操作的同步算法，只需要修改圖1源程序中行36和行37，修改后代碼如圖4所示。

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

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

4 結束語

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

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

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

參考文獻：

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

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

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

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

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

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

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

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

【通聯編輯：謝媛媛】

收稿日期：2022-05-08

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

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