“操作系統(tǒng)”課程中進(jìn)程同步互斥教學(xué)研究

金海東　徐云龍

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

關(guān)鍵詞:進(jìn)程;同步;互斥;信號(hào)量;多線程

中圖分類號(hào):G642 文獻(xiàn)標(biāo)識(shí)碼:B

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

為了既讓學(xué)生深入掌握理論知識(shí),又能通過編碼驗(yàn)證理論,本文根據(jù)實(shí)際教學(xué)經(jīng)驗(yàn),結(jié)合普通高校學(xué)生學(xué)習(xí)該課程的狀況,以進(jìn)程同步互斥為例,從以下四個(gè)方面討論如何循序漸進(jìn)地展開教學(xué)。

1 “進(jìn)程同步與互斥”的引入

教學(xué)中,首先帶領(lǐng)學(xué)生回憶在DOS環(huán)境下的C語(yǔ)言編程,使學(xué)生明白什么是單道程序環(huán)境。然后就提高系統(tǒng)的利用率,提出了程序并發(fā)執(zhí)行的載體——進(jìn)程。程序并發(fā)執(zhí)行時(shí),涉及到相同資源會(huì)引起一些問題,但抽象的理論并不利于學(xué)生的深入理解,筆者設(shè)計(jì)了一個(gè)銀行存取款問題的案例:

某一銀行賬戶M,尚有存款100元;用戶P、Q同時(shí)對(duì)該賬戶進(jìn)行操作,可能會(huì)導(dǎo)致數(shù)據(jù)不一致,操作過程如圖1所示:

① 時(shí)間T2>T1>T0;

② T0時(shí)刻,p0操作讀出Mp0=100;

③ T0時(shí)刻,q0操作讀出Mq0=100;

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

⑤ T2時(shí)刻,q1操作寫入數(shù)據(jù):存款100,M=Mq0+ 100=200;

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

2信號(hào)量描述

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

(1) 信號(hào)量定義

信號(hào)量是進(jìn)程在某一特殊點(diǎn)上被迫停止執(zhí)行直到接收到一個(gè)對(duì)應(yīng)的特殊變量值。進(jìn)程使用P、V兩個(gè)原語(yǔ)操作發(fā)送和接受信號(hào),如信號(hào)沒有送到,進(jìn)程被掛起,直到信號(hào)到達(dá)。

信號(hào)量按其用途可分為:用于進(jìn)程互斥訪問臨界資源的公用信號(hào)量;用于進(jìn)程同步時(shí)協(xié)調(diào)相互關(guān)系的私有信號(hào)量。

信號(hào)量按其取值可分為:整型信號(hào)量、可用資源數(shù)目的記錄型信號(hào)量。

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

信號(hào)量結(jié)構(gòu)中需要一個(gè)整型計(jì)數(shù)和一個(gè)等待對(duì)象。

P操作表示現(xiàn)行進(jìn)程向系統(tǒng)申請(qǐng)資源,將信號(hào)量值減1,如結(jié)果小于0,則調(diào)用進(jìn)程被置成等待信號(hào)量的狀態(tài)。

V操作表示現(xiàn)行進(jìn)程釋放該類資源,信號(hào)量值加1,系統(tǒng)可用資源數(shù)也增加一個(gè),如果s.value≤0,等待隊(duì)列中有等待進(jìn)程,則喚醒其中一個(gè)。

信號(hào)量定義,PV操作算法C語(yǔ)言描述如下:

typedef struct {

int value; //信號(hào)量值

QueueType waitQueue; //等待隊(duì)列

} semaphore;

void P(semaphore s){

--s.value;

if (s.value<0){

阻塞調(diào)用進(jìn)程;

進(jìn)程進(jìn)入等待隊(duì)列s. waitQueue;

}

}

void V(semaphores){

++s.value;

if(s.value<=0){

從等待隊(duì)列s. waitQueue中取出一個(gè)進(jìn)程;

將該進(jìn)程入就緒隊(duì)列;

}

}

(3) 關(guān)于信號(hào)量與PV操作的幾個(gè)結(jié)論

結(jié)論1:若信號(hào)量s為正值,則該值等于在封鎖進(jìn)程之前對(duì)信號(hào)量s可施行的P操作數(shù),亦等于s所代表的實(shí)際還可以使用的物理資源數(shù)。

結(jié)論2:若信號(hào)量s為負(fù)值,則其絕對(duì)值等于排列在該信號(hào)量s隊(duì)列中等待的進(jìn)程個(gè)數(shù),亦等于對(duì)信號(hào)量s實(shí)施P操作而被封鎖起來并進(jìn)入信號(hào)量s隊(duì)列的進(jìn)程數(shù)。

結(jié)論3:PV操作一定要成對(duì)使用。

(4) 進(jìn)程中信號(hào)量操作模型

通過對(duì)臨界區(qū)訪問過程的分析,信號(hào)量機(jī)制中P原語(yǔ)相當(dāng)于進(jìn)入臨界區(qū)操作,V原語(yǔ)相當(dāng)于退出臨界區(qū)操作。用P、V原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥就是將臨界區(qū)置于P和V兩個(gè)原語(yǔ)操作之間。

示例算法如下:

void ProcessExecute( 參數(shù)列表 ){

……

P(s);//進(jìn)入?yún)^(qū)

臨界區(qū);

V(s); //退出區(qū)

…… //剩余區(qū)

}

3進(jìn)程同步與互斥算法編寫過程

初學(xué)者能夠看懂他人編寫的進(jìn)程同步互斥算法,但是自己動(dòng)手編寫很困難。學(xué)生在寫該類算法時(shí),總想一次完成,但是很多時(shí)候?qū)懖缓?或者不知道如何解決該類問題。針對(duì)這一現(xiàn)象,筆者分析了算法編寫過程,給學(xué)生總結(jié)了分析問題、解決問題的步驟:

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

以“多生產(chǎn)者——多消費(fèi)者——多緩沖”問題為例,通過分析就會(huì)發(fā)現(xiàn),該問題中生產(chǎn)者、消費(fèi)者各是一類進(jìn)程。執(zhí)行過程為:

生產(chǎn)者的執(zhí)行過程:

請(qǐng)求生產(chǎn)指標(biāo);

請(qǐng)求緩沖區(qū)使用權(quán);

生產(chǎn);

歸還緩沖區(qū)使用權(quán);

消費(fèi)者過程:

請(qǐng)求消費(fèi)指標(biāo);

請(qǐng)求緩沖區(qū)使用權(quán);

消費(fèi);

歸還緩沖區(qū)使用權(quán);

(2) 分析進(jìn)程中的同步、互斥關(guān)系,設(shè)置信號(hào)量。

本問題中緩沖區(qū)是臨界資源,需要互斥訪問?！吧a(chǎn)指標(biāo)”就是空白緩沖區(qū)數(shù)目,每減少一個(gè),產(chǎn)品就增加一個(gè),“消費(fèi)指標(biāo)”就增加一個(gè)。每消費(fèi)一個(gè)產(chǎn)品,空白緩沖區(qū)就增加一個(gè),產(chǎn)品就減少一個(gè)。

用mutex信號(hào)量來保證對(duì)緩沖區(qū)的互斥訪問,emptyBufferCount記錄空白緩沖區(qū)數(shù)目,fullBufferCount記錄產(chǎn)品數(shù)目。

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

生產(chǎn)者進(jìn)程Producer:

P(mutex);//申請(qǐng)使用緩沖區(qū), ①

P(emptyBufferCount); //生產(chǎn)許可申請(qǐng), ②

生產(chǎn)

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

V(emptyBufferCount);//⑤

消費(fèi)者進(jìn)程Consumer:

P(mutex); //申請(qǐng)使用緩沖區(qū), ③

P(fullBufferCount); //消費(fèi)許可申請(qǐng),消費(fèi) ④

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

V(fullBufferCount); // ⑥

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

整型信號(hào)量mutex初值為1,記錄型信號(hào)量emptyBufferCount初值為緩沖區(qū)大小。

(5) 給出幾個(gè)進(jìn)程,人工模擬算法執(zhí)行,檢測(cè)算法并改正錯(cuò)誤。

用一個(gè)生產(chǎn)者、一個(gè)消費(fèi)者模擬進(jìn)程執(zhí)行,發(fā)現(xiàn)emptyBufferCount的PV操作②⑤,fullBufferCount的PV操作③⑥,在同一個(gè)進(jìn)程中,不能發(fā)揮同步作用,所以⑤⑥位置互換。

互換后,如果生產(chǎn)者進(jìn)程先一步執(zhí)行,算法沒有問題。如果消費(fèi)者先一步執(zhí)行,就會(huì)被阻塞,由于生產(chǎn)者不能生產(chǎn),產(chǎn)生死鎖。因此生產(chǎn)者進(jìn)程中①②位置互換,消費(fèi)者進(jìn)程中③④互換,即一般情況同步信號(hào)量在前,互斥信號(hào)量在后。改正后再測(cè)試,算法無誤。

4生產(chǎn)者消費(fèi)者的多線程仿真

“操作系統(tǒng)”的課程實(shí)驗(yàn)旨在加深學(xué)生對(duì)理論的理解。很多高?！安僮飨到y(tǒng)”實(shí)驗(yàn)基于Unix/Linux平臺(tái),學(xué)習(xí)該

系統(tǒng)會(huì)對(duì)學(xué)生來說是很大負(fù)擔(dān)。筆者在課程實(shí)驗(yàn)中,選擇學(xué)生更為熟悉也更容易使用的Windows平臺(tái)和VC++6.0開發(fā)環(huán)境,用線程模擬生產(chǎn)者消費(fèi)者問題。這樣學(xué)生既容易上手編程,又能通過編程切實(shí)理解進(jìn)程的同步與互斥理論。學(xué)生以調(diào)試該程序入手,獨(dú)立完成哲學(xué)家進(jìn)餐問題的模擬。生產(chǎn)者消費(fèi)者問題的線程函數(shù)原型如下:

DWORD WINAPI ProducerThread(LPVOID lpvThreadParm) { //生產(chǎn)者線程函數(shù)

BOOL fHasDone=FALSE;

while(!fHasDone){

EnterCriticalSection

(&g_CriticalSection);

//進(jìn)入臨界區(qū)函數(shù)

if(producerRunTimes>=MAX_RUN_TIMES){

fHasDone=TRUE;

}else{

g_Buffer[in]=rand();

in=(in+1)%BUFFER_SIZE;

//循環(huán)隊(duì)列

producerRunTimes++;

//線程執(zhí)行次數(shù)計(jì)數(shù),防止死循環(huán)

}

LeaveCriticalSection

(&g_CriticalSection);

//退出臨界區(qū)函數(shù)

}

return 0;

}

DWORD WINAPI ConsumerThread(LPVOID lpvThreadParm)

{ //消費(fèi)者線程函數(shù)

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;

}

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

5結(jié)論

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

本教學(xué)方案充分照顧到了成教學(xué)生的實(shí)際基礎(chǔ),調(diào)動(dòng)了學(xué)生的積極性,設(shè)計(jì)的多線程實(shí)驗(yàn)也使學(xué)生有能力實(shí)際動(dòng)手參與。在本校教學(xué)中,筆者采用該方案后,學(xué)生對(duì)教學(xué)內(nèi)容非常感興趣,也很容易接受理論性的知識(shí)。筆者在實(shí)際教學(xué)中,也發(fā)現(xiàn)一些問題,如該方案對(duì)學(xué)生的主動(dòng)性要求較高,并要求學(xué)生有一定的編程能力,這不在本文探討范圍。

參考文獻(xiàn):

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

[2] 孫仲秀,費(fèi)翔林,駱斌. 操作系統(tǒng)教程[M]. 北京:高等教育出版社, 2008.

[3] William Stallings. 操作系統(tǒng)——精髓與設(shè)計(jì)原理[M]. 5版. 北京:電子工業(yè)出版社,2006.

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

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

[6] 楊燕. 操作系統(tǒng)課程雙語(yǔ)教學(xué)的探討[J]. 北京大學(xué)學(xué)報(bào):哲學(xué)社會(huì)科學(xué)版,2007(S2):174-175.

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

[8] 郝繼升. 計(jì)算機(jī)操作系統(tǒng)原理課程的教學(xué)探索[J]. 教育與職業(yè),2007(8):99-101.

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