摘要：操作系統(tǒng)中，進程同步和互斥問題以及與之相關的信號量機制是教學過程中的重點和難點問題。本文介紹了教學實踐中總結的有關如何用信號量機制解決進程同步與互斥問題的求解規(guī)律及教學經(jīng)驗，旨在提高教學效果，促進學生對操作系統(tǒng)基本原理的理解和掌握。最后針對本課程的特點，提出了操作系統(tǒng)今后的教學研究方向。

關鍵詞：操作系統(tǒng)；教學研究；進程；同步；互斥；信號量

中圖分類號：G642文獻標識碼：A文章編號：1009-3044(2009)04-0898-03

The Teaching Experience of Operating System Course

GE Yan， LIU Guo-zhu， DU Jun-wei， CAO Ling

(Institute of Information Science and Technology， Qingdao University of Science and Technology， Qingdao 266061， China)

Abstract: The process synchronization and process mutual exclusion and semaphore mechanism， which are emphases and difficulty in the Operating System course. This paper introduces some teaching experiences about how to imply the semaphore mechanism to solve process synchronization and process mutual exclusion problems， which are summed up in teaching practice. Those key contents would help university students to understand and master the keystone principle. Finally， according to the character of Operating System Course， the new teaching research direction is improved at the end of this paper.

Key words: Operating system; teaching research; process; synchronization; mutual exclusion; semaphore

1 引言

操作系統(tǒng)是計算機系統(tǒng)的核心和靈魂，是計算機系統(tǒng)必不可少的組成部分。操作系統(tǒng)作為計算機專業(yè)的核心課程，不但高校計算機相關專業(yè)學習必須學習，也是從事計算機應用人員必不可少的知識[1]。

操作系統(tǒng)課程的內(nèi)容是由計算機各種操作系統(tǒng)的組成結構、設計思想、方法和理論綜合而形成。該課程具有以下特點：內(nèi)容龐雜、知識點多、涉及面廣；概念抽象，不易理解；而且實踐性強。學生在學習過程中往往對于一些重要的知識點感到不易理解，難于掌握。因此，需要系統(tǒng)地總結操作系統(tǒng)中重要知識點的教學方法，以提高教學質(zhì)量。

進程的同步和互斥是操作系統(tǒng)對計算機系統(tǒng)進行管理的核心問題，是操作系統(tǒng)課程的核心知識點，是教學過程中的重點和難點問題，也是考研的重點內(nèi)容，因此學生能否很好地理解并掌握這些知識點是影響教學效果的關鍵。

本文針對進程同步與互斥問題探討操作系統(tǒng)課程的教學方法，總結教學實踐中的一些經(jīng)驗，旨在提高學生對用信號量機制實現(xiàn)進程同步與互斥問題的理解和把握。

2 進程同步與互斥

進程是并發(fā)執(zhí)行的程序在執(zhí)行過程中分配和管理資源的基本單位。并發(fā)執(zhí)行是為了增強計算機系統(tǒng)的處理能力和提高資源利用率所采取的一種同時操作技術。在不考慮資源共享的情況下，各進程的執(zhí)行是獨立的，執(zhí)行速度是異步的[2]。但是在計算機系統(tǒng)中，由于資源有限又導致了進程之間的資源競爭和共享。那么，在進程并發(fā)執(zhí)行過程中存在哪些制約呢？

并發(fā)進程所受的制約有兩種：直接制約和間接制約。

1) 直接制約，又稱協(xié)作關系：某些進程為完成同一任務需要分工協(xié)作等待來自其他進程的信息，這種相互制約的關系稱為進程同步。

2) 間接制約：進程間競爭共有資源——獨占分配到的部分或全部共享資源，這種相互制約的關系稱為互斥。

并發(fā)進程之間的同步和互斥關系如果處理不好就會產(chǎn)生死鎖。目前最有效的解決方法是信號量機制。

3 信號量機制

信號量機制是由荷蘭科學家E.W.Dijkstra提出的。他將交通管制中多種顏色的信號燈管理交通的方法引入操作系統(tǒng)，讓兩個或多個進程通過特殊變量進行交互。一個進程在某一特殊點上被迫停止執(zhí)行直到接收到一個對應的特殊變量值，通過特殊變量這一設施，任何復雜的進程交互要求都可得到滿足，這種特殊變量稱為信號量（semaphore）。為了通過信號量傳送信號，進程可以通過P、V兩個特殊的操作來發(fā)送和接收信號[1]。

在操作系統(tǒng)中，信號量有如下幾個特點：

1) 信號量必須置一次且只能置一次初值。

2) 信號量的初值不能為負數(shù)。

3) 信號量只能通過初始化和兩個標準的PV原語對其進行操作，沒有其他任何方法可以檢查和操作信號量。

4) PV原語是操作系統(tǒng)內(nèi)核中執(zhí)行時不可中斷的過程，不受進程調(diào)度的打斷。

5) P原語操作的功能：將信號量s減l；若s<0，則調(diào)用P(s)的進程被置成等待信號量s的狀態(tài)，然后轉進程調(diào)度；否則調(diào)用P(s)的進程繼續(xù)執(zhí)行。

6) V原語操作的功能：將信號量s加1；若s的值小于或等于0，則喚醒一個等待信號量s的進程，然后再返回原進程繼續(xù)執(zhí)行或轉進程調(diào)度；否則調(diào)用P(s)的進程繼續(xù)執(zhí)行。

4 用信號量機制實現(xiàn)互斥和同步的方法

用PV操作解決進程同步問題時首先應確定問題的類型。如果并發(fā)的進程間涉及到同一共享資源的使用，則為互斥關系；如果并發(fā)的進程間執(zhí)行順序必須遵守某一規(guī)則，則為同步關系。當然更多的問題中可能既有相互合作的關系，也有對共享資源的使用，使得進程間的制約關系更為復雜。

4.1 用信號量機制實現(xiàn)進程互斥

在進程互斥問題中，要為多個進程互斥訪問的臨界資源設置一個公用信號量mutex，該信號量與所有的并發(fā)進程有關。公用信號量的值反映了可用該公用資源的數(shù)量。

在單純的互斥問題中，在每個進程中將臨界區(qū)（進程中訪問臨界資源的那段程序代碼）置于P(mutex)和V(mutex)原語之間。其模型如下圖1所示。

圖1中，信號量與PV操作的作用如下：

1) P操作的作用：判斷是否能進入臨界區(qū)，申請資源；

2) V操作的作用：退出臨界區(qū)，釋放資源；

3) 信號量初值設置為臨界資源的可用個數(shù)。

4.2 用信號量機制實現(xiàn)進程同步

與進程互斥不同，進程同步時的信號量只與制約進程及被制約進程有關而不是與整組并發(fā)進程有關，所以稱之為私用信號量。

以兩個進程生產(chǎn)者和消費者共用同一個緩沖區(qū)發(fā)送和接收信息為例，介紹實現(xiàn)進程同步的模型。設置兩個私用信號量：

empty: 表示緩沖區(qū)是否為空，初值為1。

full: 表示緩沖區(qū)是否為滿，初值為0。

該問題算法描述如圖2所示。

圖2中，P操作的作用是接收信息，判斷是否可以執(zhí)行；V操作的作用是發(fā)送消息告知對方。同一個私用信號量的P操作應在接收信息的進程中，V操作應在發(fā)送信息的進程中，只有含有V操作的進程發(fā)送消息后，接收進程才能執(zhí)行。

4.3 用信號量機制實現(xiàn)復雜的進程同步與互斥問題

多個生產(chǎn)者和多個消費者問題是一個典型的既有進程同步又有互斥的混合問題，即：多個生產(chǎn)者，多個消費者，共享多個緩沖區(qū)。其中，生產(chǎn)者與消費者之間要同步，而且還必須互斥地訪問緩沖區(qū)[3]。以該問題的求解為例分析進程同步與互斥復雜問題的求解模型：

1) 定義三個信號量。

①公用信號量mutex：保證生產(chǎn)者進程和消費者進程之間的互斥，初值為1。

②私用信號量empty：表示緩沖區(qū)中的空單元個數(shù)，初值為n；

③私用信號量full：表示緩沖區(qū)中的非空單元個數(shù)，初值為0。

2) 算法描述如圖3。

用信號量機制實現(xiàn)進程同步與互斥的注意事項如下：

不論是求解進程同步還是互斥問題，在一組并發(fā)進程中，P、V原語都是成對出現(xiàn)的：

1) 互斥操作時，它們在同一進程中；

2) 同步操作時，它們處于不同進程。

3) 在同步和互斥的混合問題中，應先執(zhí)行用于同步信號量的P操作，然后再執(zhí)行互斥信號量的P操作。

5 用信號量機制實現(xiàn)進程互斥和同步的例子

下面以幾個典型的實例，介紹如何利用信號量和PV操作有效地解決進程同步與互斥問題。

問題的分析步驟如下：

1) 分析并發(fā)的進程間的制約關系：是互斥、同步還是互斥與同步的混合問題。這一步的分析判斷是至關重要的。

2) 設定信號量的個數(shù)、初值和意義。

3) 決定并發(fā)進程執(zhí)行過程中調(diào)用P、V操作原語的位置。

5.1 用信號量實現(xiàn)進程互斥的例子

五個哲學家吃通心粉問題是操作系統(tǒng)中經(jīng)典的進程互斥問題，如圖4所示。有五個哲學家圍坐在一個圓桌旁，桌中央有一盤通心粉，每人面前有一只空盤子，每兩人之間放一只叉子，每個哲學家的行為是思考，感到饑餓，然后吃通心粉。為了吃通心粉，每個哲學家必須拿到兩只叉子，并且每個人只能直接從自己的左邊或右邊去取叉子。

為了防止出現(xiàn)死鎖，要求奇數(shù)號的哲學家先取左手邊的叉子，偶數(shù)號的哲學家先取右手邊的叉子。

哲學家就餐問題的求解過程如下：

1) 把哲學家看做是進程，進程之間是互斥關系。每一把叉子是相鄰兩個哲學家共享的公用資源。哲學家編號i=0-4。

2) 為每一把叉子設置對應的公用信號量，其初始值為1，規(guī)定每個哲學家左右的叉子和哲學家的編號相同。

fork[i]: semaphore; i=0，1，2，3，4

fork[i]=1;

3) 算法描述如下：

Process Pi (i=0，1，2，3，4)

begin

思考；

if i mod 2==0 then//偶數(shù)號哲學家

{P(fork[(i+1)mod5]);//拿右手邊的叉子

P(fork[i]); //拿左手邊的叉子 吃通心粉;

V(fork[(i+1)mod5]); //放下右手邊的叉子

V(fork[i]); //放下左手邊的叉子

}

else//奇數(shù)號哲學家

{P(fork[i]);//拿左手邊的叉子

P(fork[(i+1)mod5]); //拿右手邊的叉子

吃通心粉;

V(fork[i]);//放下左手邊的叉子

V(fork[(i+1)mod5]); //放下右手邊的叉子

}

end

5.2 用信號量機制實現(xiàn)進程同步的例子

把并發(fā)進程的同步和互斥問題一般化，可抽象為一般模型：生產(chǎn)者和消費者問題。該問題可以具體劃分為以下四種情況。

①一個生產(chǎn)者、一個消費者共享一個緩沖區(qū)

②一個生產(chǎn)者、一個消費者共享多個緩沖區(qū)

③多個生產(chǎn)者、多個消費者共享一個緩沖區(qū)

④多個生產(chǎn)者、多個消費者共享多個緩沖區(qū)

深入分析生產(chǎn)者和消費者問題將有助于深刻理解如何解決程互斥與同步問題。下面以第二種情況（一個生產(chǎn)者，一個消費者共享多個緩沖區(qū)），介紹進程同步問題和進程典型的進程同步問題。該問題的求解過程如下：

1) 定義用于進程同步的私用信號量：

empty: 表示緩沖區(qū)是否為空，初值為n。full: 表示緩沖區(qū)是否為滿，初值為0。

2) 程序描述如圖5。

5.3 用信號量機制實現(xiàn)復雜的進程同步問題

復雜的生產(chǎn)者——消費者問題：

桌上有一只盤子，只能容納兩個水果，每次只能放入或取出一只水果。爸爸專向盤子中放蘋果（apple），媽媽專向盤子中放桔子（orange），一個兒子專等吃盤子中的桔子，一個女兒專等吃盤子中的蘋果。試用信號量和P、V操作來實現(xiàn)爸爸、媽媽、兒子和女兒之間的同步與互斥關系[4]。

解題思路：

1) 分析：該問題實質(zhì)上是兩個生產(chǎn)者和兩個消費者被連結到僅能放兩個個產(chǎn)品的緩沖區(qū)上。生產(chǎn)者需要指明是給哪個消費者的產(chǎn)品，而消費者取走產(chǎn)品后無需特別通知某個生產(chǎn)者，因為空出的緩沖區(qū)（盤子）可以由兩個生產(chǎn)者隨意爭奪。

2) 設置兩個公用信號量（plate， mutex）和兩個私用信號量（orange， apple）。

plate，控制盤子容納水果數(shù)目；初值為2。

mutex，控制對盤子的互斥訪問，初值為1。

orange表示盤子里有桔子，初值為0。

apple表示盤子里有蘋果，初值為0。

3) 算法描述如圖6。

在進程同步和互斥的混合問題中，一定要重點提醒學生，每個進程中各個P操作的次序是重要的：先檢查資源數(shù)目，再檢查是否互斥（否則可能死鎖）。讓學生思考為什么會產(chǎn)生死鎖，通過思考進一步理解進程的同步和互斥問題的求解方法。

6 總結

信號量機制是操作系統(tǒng)管理并發(fā)進程執(zhí)行的有效方法。用信號量機制解決進程同步與互斥問題是操作系統(tǒng)的重要知識點，是學生學習和理解其他相關知識點的前提和基礎，也是教師講解過程中應加以重視的環(huán)節(jié)。例如，進程間的消息緩沖通信機制中，需要利用信號量機制實現(xiàn)發(fā)送和接收過程的同步與互斥；文件系統(tǒng)中，也需要利用信號量機制實現(xiàn)讀寫控制。

本文著重介紹了在《操作系統(tǒng)》課程的教學過程中對用信號量解決進程同步與互斥問題這一核心知識點的教學體會。該教學方法經(jīng)過多年的教學實踐，已成為該課程的一個教學亮點。學生普遍感覺利用這些系統(tǒng)歸納總結出的求解思路、求解規(guī)律和求解方法．能夠比較熟練地解決這類問題，反映較好。

《操作系統(tǒng)》課程同其他計算機科學技術一樣，其技術也是日新月異，發(fā)展很快。因而對教學來說就要緊跟其發(fā)展，了解該學科的前沿信息。在教學過程中，充分把握好操作系統(tǒng)課程的特點，歸納出行之有效的教學方法，提高學生的學習興趣，充分提高學生的能力。

參考文獻：

[1] 孫鐘秀. 操作系統(tǒng)教程[M]. 3版. 北京：高等教育出版社， 2005.

[2] 湯子贏. 計算機操作系統(tǒng)[M]. 西安：西安電子科技大學出版社，2000.

[3] 張堯學. 計算機操作系統(tǒng)教程[M]. 北京：清華大學出版社， 2006.

[4] 史湘寧， 凌云翔. 操作系統(tǒng)典型題解析與實戰(zhàn)模擬[M]. 長沙：國防科技大學出版社， 2002.

葛艷（1975-），女，山東泰安人，副教授，主要從事計算機專業(yè)教學，智能控制理論與應用研究。