“操作系統”課程中進程同步互斥教學研究

金海東　徐云龍

摘要:“操作系統”是計算機專業的核心課程之一。由于涉及的學科多、知識點多、課程內容難理解等,該課程的教與學一直是學科難點。成人教育學生普遍起點較低,對純理論性知識不太樂于接受。本文以該課程的一個核心知識點——進程同步與互斥為實例,探討如何從學習者的角度設計循序漸進的教學內容,并通過編寫程序驗證書本理論,提高成教學生的興趣和實踐能力。

關鍵詞:進程;同步;互斥;信號量;多線程

中圖分類號:G642 文獻標識碼:B

計算機專業中,“操作系統”課程非常重要。操作系統直接高效地管理著計算機的各種軟硬件資源,為用戶提供使用接口。操作系統是最復雜的系統軟件,涉及了程序設計語言、計算機系統結構/硬件、軟件設計、網絡、算法等。由于該課程內容多而雜,普通高校學生特別是成人教育學生學習比較困難。傳統教學方式下,只給學生講解操作系統原理,學生感到抽象、難懂,近些年來,很多高校加大實驗(實踐)教學力度,在講授理論的同時,加入操作系統內核代碼分析,如一些學校讓學生分析Linux內核。但這勢必加大教學工作量,教師無法在五六十學時內完成課程教學。

為了既讓學生深入掌握理論知識,又能通過編碼驗證理論,本文根據實際教學經驗,結合普通高校學生學習該課程的狀況,以進程同步互斥為例,從以下四個方面討論如何循序漸進地展開教學。

1 “進程同步與互斥”的引入

教學中,首先帶領學生回憶在DOS環境下的C語言編程,使學生明白什么是單道程序環境。然后就提高系統的利用率,提出了程序并發執行的載體——進程。程序并發執行時,涉及到相同資源會引起一些問題,但抽象的理論并不利于學生的深入理解,筆者設計了一個銀行存取款問題的案例:

某一銀行賬戶M,尚有存款100元;用戶P、Q同時對該賬戶進行操作,可能會導致數據不一致,操作過程如圖1所示:

① 時間T2>T1>T0;

② T0時刻,p0操作讀出Mp0=100;

③ T0時刻,q0操作讀出Mq0=100;

④ T1時刻,p1操作寫入數據:存款100,M=Mp0+ 100=200;Q未能獲得更新后的數據;

⑤ T2時刻,q1操作寫入數據:存款100,M=Mq0+ 100=200;

應該是300元的賬戶余額,由于操作的并發執行,造成只有200元余額。通過這一具體、直觀的例子,讓學生明白并發執行與順序執行有很多不一樣的地方,即并發環境中的共享資源,不能同時訪問,只可互斥訪問。然后帶領學生學習并發操作的Bernstein條件、臨界資源等知識。

2信號量描述

怎樣才能做到在某一時刻,只有一個進程訪問該資源呢,這就是臨界資源的管理方法。在介紹了部分不成熟的管理方案后,引入Dijkstra提出的信號量和P、V操作機制。

(1) 信號量定義

信號量是進程在某一特殊點上被迫停止執行直到接收到一個對應的特殊變量值。進程使用P、V兩個原語操作發送和接受信號,如信號沒有送到,進程被掛起,直到信號到達。

信號量按其用途可分為:用于進程互斥訪問臨界資源的公用信號量;用于進程同步時協調相互關系的私有信號量。

信號量按其取值可分為:整型信號量、可用資源數目的記錄型信號量。

(2)P、V操作定義描述

信號量結構中需要一個整型計數和一個等待對象。

P操作表示現行進程向系統申請資源,將信號量值減1,如結果小于0,則調用進程被置成等待信號量的狀態。

V操作表示現行進程釋放該類資源,信號量值加1,系統可用資源數也增加一個,如果s.value≤0,等待隊列中有等待進程,則喚醒其中一個。

信號量定義,PV操作算法C語言描述如下:

typedef struct {

int value; //信號量值

QueueType waitQueue; //等待隊列

} semaphore;

void P(semaphore s){

--s.value;

if (s.value<0){

阻塞調用進程;

進程進入等待隊列s. waitQueue;

}

}

void V(semaphores){

++s.value;

if(s.value<=0){

從等待隊列s. waitQueue中取出一個進程;

將該進程入就緒隊列;

}

}

(3) 關于信號量與PV操作的幾個結論

結論1:若信號量s為正值,則該值等于在封鎖進程之前對信號量s可施行的P操作數,亦等于s所代表的實際還可以使用的物理資源數。

結論2:若信號量s為負值,則其絕對值等于排列在該信號量s隊列中等待的進程個數,亦等于對信號量s實施P操作而被封鎖起來并進入信號量s隊列的進程數。

結論3:PV操作一定要成對使用。

(4) 進程中信號量操作模型

通過對臨界區訪問過程的分析,信號量機制中P原語相當于進入臨界區操作,V原語相當于退出臨界區操作。用P、V原語實現進程互斥就是將臨界區置于P和V兩個原語操作之間。

示例算法如下:

void ProcessExecute( 參數列表 ){

……

P(s);//進入區

臨界區;

V(s); //退出區

…… //剩余區

}

3進程同步與互斥算法編寫過程

初學者能夠看懂他人編寫的進程同步互斥算法,但是自己動手編寫很困難。學生在寫該類算法時,總想一次完成,但是很多時候寫不好;或者不知道如何解決該類問題。針對這一現象,筆者分析了算法編寫過程,給學生總結了分析問題、解決問題的步驟:

(1) 找出問題中的執行進程,再描述其余各進程的執行過程。

以“多生產者——多消費者——多緩沖”問題為例,通過分析就會發現,該問題中生產者、消費者各是一類進程。執行過程為:

生產者的執行過程:

請求生產指標;

請求緩沖區使用權;

生產;

歸還緩沖區使用權;

消費者過程:

請求消費指標;

請求緩沖區使用權;

消費;

歸還緩沖區使用權;

(2) 分析進程中的同步、互斥關系,設置信號量。

本問題中緩沖區是臨界資源,需要互斥訪問?！吧a指標”就是空白緩沖區數目,每減少一個,產品就增加一個,“消費指標”就增加一個。每消費一個產品,空白緩沖區就增加一個,產品就減少一個。

用mutex信號量來保證對緩沖區的互斥訪問,emptyBufferCount記錄空白緩沖區數目,fullBufferCount記錄產品數目。

(3) 利用PV操作寫出同步互斥關系。用算法替換前面描述的執行過程。

生產者進程Producer:

P(mutex);//申請使用緩沖區, ①

P(emptyBufferCount); //生產許可申請, ②

生產

V(mutex); //離開,釋放!PV操作成對使用

V(emptyBufferCount);//⑤

消費者進程Consumer:

P(mutex); //申請使用緩沖區, ③

P(fullBufferCount); //消費許可申請,消費 ④

V(mutex); //離開,釋放

V(fullBufferCount); // ⑥

(4) 選擇并確定信號量的初值。

整型信號量mutex初值為1,記錄型信號量emptyBufferCount初值為緩沖區大小。

(5) 給出幾個進程,人工模擬算法執行,檢測算法并改正錯誤。

用一個生產者、一個消費者模擬進程執行,發現emptyBufferCount的PV操作②⑤,fullBufferCount的PV操作③⑥,在同一個進程中,不能發揮同步作用,所以⑤⑥位置互換。

互換后,如果生產者進程先一步執行,算法沒有問題。如果消費者先一步執行,就會被阻塞,由于生產者不能生產,產生死鎖。因此生產者進程中①②位置互換,消費者進程中③④互換,即一般情況同步信號量在前,互斥信號量在后。改正后再測試,算法無誤。

4生產者消費者的多線程仿真

“操作系統”的課程實驗旨在加深學生對理論的理解。很多高?！安僮飨到y”實驗基于Unix/Linux平臺,學習該

系統會對學生來說是很大負擔。筆者在課程實驗中,選擇學生更為熟悉也更容易使用的Windows平臺和VC++6.0開發環境,用線程模擬生產者消費者問題。這樣學生既容易上手編程,又能通過編程切實理解進程的同步與互斥理論。學生以調試該程序入手,獨立完成哲學家進餐問題的模擬。生產者消費者問題的線程函數原型如下:

DWORD WINAPI ProducerThread(LPVOID lpvThreadParm) { //生產者線程函數

BOOL fHasDone=FALSE;

while(!fHasDone){

EnterCriticalSection

(&g_CriticalSection);

//進入臨界區函數

if(producerRunTimes>=MAX_RUN_TIMES){

fHasDone=TRUE;

}else{

g_Buffer[in]=rand();

in=(in+1)%BUFFER_SIZE;

//循環隊列

producerRunTimes++;

//線程執行次數計數,防止死循環

}

LeaveCriticalSection

(&g_CriticalSection);

//退出臨界區函數

}

return 0;

}

DWORD WINAPI ConsumerThread(LPVOID lpvThreadParm)

{ //消費者線程函數

BOOL fHasDone=FALSE;

while(!fHasDone){

EnterCriticalSection (&g_CriticalSection);

if(consumerRunTimes>= MAX_RUN_TIMES){

fHasDone=TRUE;

}else{

g_Buffer[out]=rand();

out=(out+1)% BUFFER_SIZE;

consumerRunTimes++;

}

LeaveCriticalSection

(&g_CriticalSection);

}

return 0;

}

在上述程序中除掉同步互斥部分,學生就能實際理解圖1中銀行賬戶存款例子。多線程仿真實驗不但能讓學生深入理解進程同步互斥的理論和實現,還讓學生學會和理解了多線程的編程。

5結論

在“操作系統”課程中,筆者將知識點理清脈絡,并圍繞操作系統的五大管理功能展開教學。介紹操作系統的每個功能時,以知識點的內在特性為線索,連接看似不相關的知識。如在進程管理時,以單機環境下的程序執行為切入點,描述在多道程序中,每道程序模擬單機運行環境,需要完成哪些工作;為了多道程序的協調工作,如何進行同步和互斥;為了讓每個進程都能有機會運行,如何確定進程調度原則。特別是在介紹進程同步與互斥時,實例結合理論,由淺入深,以“銀行賬戶操作”實例讓學生明白并發操作與順序執行的不同之處,隨后提出操作系統中常用的并發處理方法——信號量機制。并就學生的學習難點——并發互斥操作的算法編寫,給出問題的解決步驟。在實驗中,用Windows多線程驗證課堂所學知識,學生既方便上手編程,又容易理解理論。

本教學方案充分照顧到了成教學生的實際基礎,調動了學生的積極性,設計的多線程實驗也使學生有能力實際動手參與。在本校教學中,筆者采用該方案后,學生對教學內容非常感興趣,也很容易接受理論性的知識。筆者在實際教學中,也發現一些問題,如該方案對學生的主動性要求較高,并要求學生有一定的編程能力,這不在本文探討范圍。

參考文獻:

[1] 湯小丹,梁紅兵,哲鳳屏,等. 計算機操作系統(修訂版)[M]. 西安:西安電子科技大學出版社,2003.

[2] 孫仲秀,費翔林,駱斌. 操作系統教程[M]. 北京:高等教育出版社, 2008.

[3] William Stallings. 操作系統——精髓與設計原理[M]. 5版. 北京:電子工業出版社,2006.

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

[5] 孟靜. 操作系統教程-原理和實例分析[M]. 2版. 北京:高等教育出版社,2006.

[6] 楊燕. 操作系統課程雙語教學的探討[J]. 北京大學學報:哲學社會科學版,2007(S2):174-175.

[7] 張坤.“操作系統”課程的教學方法研究[J]. 高等工程教育研究,2007(S1):151-152.

[8] 郝繼升. 計算機操作系統原理課程的教學探索[J]. 教育與職業,2007(8):99-101.

[9] Jeffrey Richter. Windows高級編程指南[M]. 北京:清華大學出版社,1999.