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

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

中圖分類號：TP316 ? ? ?文獻(xiàn)標(biāo)識碼：A

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

1 概述

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

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

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

2 實(shí)現(xiàn)方法

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

線程實(shí)現(xiàn)方法分為內(nèi)核級線程，如Windows 2003；用戶級線程，如POSIX中的Pthread庫、Java線程庫；混合式線程，如Solaris 。內(nèi)核級線程需要內(nèi)核調(diào)試環(huán)境，配置非常復(fù)雜。用戶級線程在用戶應(yīng)用程序中可以被編程管理，只需要普通的應(yīng)用程序編程環(huán)境。用戶級線程庫在多種編程語言環(huán)境中有相關(guān)庫或類支持，如C語言、Java語言、C#語言等。C語言作為操作系統(tǒng)和系統(tǒng)庫的主要實(shí)現(xiàn)語言，在編制相關(guān)的多任務(wù)同步演示程序上具有一定的優(yōu)勢。由于多任務(wù)同步演示環(huán)境需要考慮在Windows平臺和Unix平臺上的實(shí)現(xiàn)，需要注意消除兩種系統(tǒng)中實(shí)現(xiàn)源代碼的差異性。雖然Java語言、C#語言本身具有跨平臺的實(shí)現(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)上運(yùn)行軟件，而定義API的一系列互相關(guān)聯(lián)的標(biāo)準(zhǔn)的總稱。Pthread庫是實(shí)現(xiàn)了POSIX線程規(guī)范的一套API，POSIX的信號量API可以和Pthread協(xié)同工作。Pthread庫一般用于Unix-like POSIX 系統(tǒng)，如Linux、Solaris，在Microsoft Windows上也有實(shí)現(xiàn)，具有源代碼級的可移植性。由于Pthread庫可在用戶空間實(shí)現(xiàn)，在通用操作系統(tǒng)上均能夠比較方便獲得。因此可以采用一定的封裝技術(shù)，在通用操作系統(tǒng)上實(shí)現(xiàn)信號量和PV原語。

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

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

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

typedef ?sem_t ?semaphore;

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

收稿日期：2022-05-08

基金項(xiàng)目：廣東科技學(xué)院校級科研項(xiàng)目（項(xiàng)目編號：GKY-2021KYZDK-13）

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