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

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

中圖分類(lèi)號(hào)：TP316 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

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

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

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

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

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

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

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

typedef ?sem_t ?semaphore;

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

由于進(jìn)程和線程的概念差異性，本方法是在用戶(hù)空間多任務(wù)層次實(shí)現(xiàn)了可調(diào)試運(yùn)行的信號(hào)量和PV原語(yǔ)，和傳統(tǒng)的信號(hào)量的定義仍有一定的差異，如何封裝類(lèi)似管程的高級(jí)同步機(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)程同步問(wèn)題的難點(diǎn)研究與實(shí)現(xiàn)[J].電腦知識(shí)與技術(shù)，2017，13（13）：38-39.

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

收稿日期：2022-05-08

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

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