操作系統(tǒng)課程之“讀者—寫者”問題教學(xué)探討

　　摘 要：針對(duì)操作系統(tǒng)教學(xué)中概念多而繁雜、容易混淆，初學(xué)者存在畏難情緒等問題，文章提出采取類比、逐層解剖、層層深入、循序漸進(jìn)的教學(xué)方法，并以操作系統(tǒng)中的進(jìn)程同步互斥問題中“讀者－寫者”問題為例，對(duì)其概念、算法進(jìn)行形象啟發(fā)、分層解剖的闡述，并結(jié)合多種教學(xué)方法，說明使學(xué)生能更深刻地理解進(jìn)程同步互斥問題的方法。教學(xué)實(shí)踐表明其效果良好。
　　關(guān)鍵詞：操作系統(tǒng)；分層解剖；讀者－寫者問題；PV原語；教學(xué)實(shí)踐
　　
　　操作系統(tǒng)是計(jì)算機(jī)專業(yè)的一門核心課程(圖1)，其在計(jì)算機(jī)系統(tǒng)中的特殊地位，使得該課程的學(xué)習(xí)在整個(gè)計(jì)算機(jī)學(xué)科教育中顯得尤為重要。作為一門理論性和實(shí)踐性并重的課程，它具有概念多、算法較抽象的特點(diǎn)，同時(shí)又涉及了程序設(shè)計(jì)語言、軟件工程思想、算法設(shè)計(jì)、計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)、網(wǎng)絡(luò)等相關(guān)知識(shí)。枯燥的理論講述往往使學(xué)生感到抽象、難懂，進(jìn)而產(chǎn)生厭學(xué)的思想。盡管近年來一些高校在加強(qiáng)理論教學(xué)的同時(shí)，引入對(duì)操作系統(tǒng)內(nèi)核的分析，如Linux操作系統(tǒng)，在教學(xué)實(shí)踐方面取得了一點(diǎn)的成效，但是對(duì)于初學(xué)者和教師而言，在一個(gè)學(xué)期內(nèi)課時(shí)數(shù)不變的情況下，完成教與學(xué)的工作顯得有點(diǎn)心有余而力不足。
　　為了在有限的教學(xué)時(shí)間內(nèi)，提高教學(xué)效率，既讓學(xué)生深入理解理論知識(shí)，又能借助PV操作原語來驗(yàn)證操作系統(tǒng)的算法思想，筆者根據(jù)以往教學(xué)經(jīng)驗(yàn)，結(jié)
　　
　　合初學(xué)者學(xué)習(xí)的實(shí)際情況，以進(jìn)程同步中“讀者－寫者”為例，探討如何由淺入深、循序漸進(jìn)地開展教學(xué)工作。
　　1 問題描述
　　“讀者—寫者”問題是現(xiàn)代操作系統(tǒng)中經(jīng)典的進(jìn)程同步互斥問題，在以C/S模式為代表的多進(jìn)(線)程通信系統(tǒng)都可以作為該模型的不同表現(xiàn)形式，有著廣泛的應(yīng)用[1]。該問題描述如下：
　　一個(gè)數(shù)據(jù)文件或記錄可被多個(gè)進(jìn)程所共享，我們將其中只要求讀該文件的進(jìn)程稱為讀者，即“Reader進(jìn)程”，其他進(jìn)程稱為寫者，即“Writer進(jìn)程”。多個(gè)Reader進(jìn)程和多個(gè)Writer進(jìn)程在某個(gè)時(shí)間段內(nèi)對(duì)該文件資源進(jìn)行異步操作，也就是說允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對(duì)象，但絕不允許一個(gè)Writer進(jìn)程和其他Reader進(jìn)程或Writer進(jìn)程同時(shí)訪問共享對(duì)象，因此，所謂“讀者—寫者問題”就是指必須保證一個(gè)Writer進(jìn)程和其他進(jìn)程(Writer進(jìn)程和Reader進(jìn)程)互斥地訪問共享對(duì)象的同步問題[2]。兩者的讀寫操作限制如下[3]：
　　1) 寫—寫互斥，即不允許多個(gè)寫者同時(shí)對(duì)文件進(jìn)行寫操作；
　　2) 讀—寫互斥，即不允許讀者和寫者同時(shí)對(duì)文件分別進(jìn)行讀寫操作；
　　3) 讀—讀允許，即允許多個(gè)讀者同時(shí)對(duì)文件進(jìn)行讀操作。
　　
　　
　　基金項(xiàng)目：2009年國家級(jí)質(zhì)量工程安徽大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)創(chuàng)新實(shí)驗(yàn)區(qū)項(xiàng)目(2009027042)；安徽省教育廳教改項(xiàng)目(2008jyxm274)；安徽省高等學(xué)校優(yōu)秀青年人才基金項(xiàng)目資助(2011SQRL018)；安徽大學(xué)青年科學(xué)研究基金(KJQN1015)。
　　作者簡介：邱劍鋒，男，講師，研究方向?yàn)橛?jì)算機(jī)操作系統(tǒng)、數(shù)據(jù)挖掘、信號(hào)與信息處理等。
　　
　　2 分層解剖，降低難度
　　PV操作及同步互斥的實(shí)現(xiàn)是操作系統(tǒng)中重點(diǎn)難點(diǎn)內(nèi)容之一，其中讀者寫者問題又是PV操作中經(jīng)典的案例，為了使學(xué)生更好地理解這個(gè)知識(shí)點(diǎn)，在教學(xué)實(shí)踐中，筆者采用分層解剖、化解難點(diǎn)、由淺到深的教學(xué)方法，取得了較好的教學(xué)效果。
　　“讀者—寫者”問題是一個(gè)有代表性的進(jìn)程同步問題，作為初學(xué)者要做到透徹理解并不容易，但是如果我們將該問題進(jìn)行細(xì)分，由簡單到復(fù)雜，理解難度將大大降低，在每一種情況下都需要滿足上述的讀寫規(guī)則。
　　1) 一個(gè)讀者，一個(gè)寫者共享一個(gè)數(shù)據(jù)文件。
　　為了更好地讓學(xué)生理解，我們把抽象的問題具體化。將一個(gè)讀者比喻為一個(gè)學(xué)生小明，而一個(gè)寫者比喻為老師王老師，而一個(gè)數(shù)據(jù)文件比喻成一個(gè)公告版。在該情況下，可以理解為王老師負(fù)責(zé)修改布告版的內(nèi)容，小明只能去閱讀報(bào)告版的內(nèi)容。王老師對(duì)布告版內(nèi)容修改時(shí)小明不能去讀，反之，小明讀的時(shí)候王老師也不能去修改。顯然，這是一個(gè)簡單的互斥問題。
　　解決這個(gè)問題時(shí)，我們只需設(shè)置一個(gè)互斥信號(hào)量Wmutex，表示寫進(jìn)程與讀進(jìn)程互斥地訪問數(shù)據(jù)文件，初值為1。
　　
　　讀進(jìn)程：
　　while(TRUE){
　　 P(Wmutex);
　　 讀數(shù)據(jù)文件;
　　 V(Wmutex);
　　}
　　
　　2) 一個(gè)讀者，多個(gè)寫者共享一個(gè)數(shù)據(jù)文件。
　　類似地，我們?nèi)詫⒁粋€(gè)讀者比喻為學(xué)生小明，而這個(gè)時(shí)候?qū)懻哂卸鄠€(gè)，這里以兩個(gè)寫者為例，分別稱作王老師和趙老師，而數(shù)據(jù)文件仍比喻成公告版。在這里，小明和兩位寫者之間是互斥的，王老師和趙老師之間作為寫者也是互斥地去訪問數(shù)據(jù)文件，所以解決方法如第一種情況所示，在此不再贅述。
　　3) 多個(gè)讀者，一個(gè)寫者共享一個(gè)數(shù)據(jù)文件。
　　這里我們有多個(gè)讀者，我們以兩個(gè)為例，分別稱之為小明和小強(qiáng)，而這個(gè)時(shí)候?qū)懻邽橐粋€(gè)稱之為王老師，而數(shù)據(jù)文件仍比喻成公告版。根據(jù)讀寫規(guī)則，小明和小強(qiáng)可以同時(shí)訪問數(shù)據(jù)文件，因?yàn)樽x是不會(huì)使數(shù)據(jù)文件發(fā)生混亂的，而王老師和小明、小強(qiáng)之間必須滿足互斥，即只有當(dāng)小明和小強(qiáng)都不讀時(shí)，王老師才可以寫數(shù)據(jù)文件，反之，當(dāng)王老師執(zhí)行寫操作時(shí)，小明和小強(qiáng)中任一個(gè)人都不能執(zhí)行讀操作。
　　根據(jù)上述思路，我們給出以下解決方案，在保留寫互斥信號(hào)量Wmutex基礎(chǔ)上，增加共享變量Readcount，該變量記錄當(dāng)前正在讀數(shù)據(jù)集的讀進(jìn)程數(shù)目，初值為0。此外，注意到Readcount是一個(gè)可被多個(gè)Reader進(jìn)程訪問的臨界資源，因此也需對(duì)它進(jìn)行互斥訪問，設(shè)置一個(gè)讀互斥信號(hào)量Rmutex，表示讀進(jìn)程互斥地訪問共享變量Readcount，初值為1。算法描述為：
　　
　　
　　幾點(diǎn)說明：
　　a. 這個(gè)時(shí)候允許多個(gè)讀進(jìn)程在讀，而讀和寫是互斥的，所以必須有個(gè)變量記錄讀者的數(shù)目，Readcount就起到這個(gè)作用，即可以被多個(gè)讀進(jìn)程訪問的臨界資源，所以必須互斥訪問。上述Reader( )過程中的兩對(duì)P(Rmutex)、V(Rmutex)表示對(duì)Readecount這個(gè)共享變量的互斥訪問操作。
　　b. 在Reader( )進(jìn)程中，如果是第一個(gè)來訪問的讀者(通過Readcount來判斷)，執(zhí)行P(Wmutex)，阻止寫者，防止在讀的過程中受到寫者的干擾。如果不是第一個(gè)來訪問的讀者，直接執(zhí)行Readcount加1操作，因?yàn)榘凑找?guī)則，多個(gè)讀者可以同時(shí)訪問數(shù)據(jù)文件。類似地，在讀完數(shù)據(jù)文件后，仍然先要去訪問Readcount這個(gè)共享變量，如果不是最后一個(gè)讀者，就不能釋放資源Wmutex，反之則通過V(Wmutex)操作通知寫者writer( )可以執(zhí)行寫操作。
　　4) 多個(gè)讀者，多個(gè)寫者共享一個(gè)數(shù)據(jù)文件。
　　這種情況和3)非常相似，雖然有多個(gè)寫者去訪問數(shù)據(jù)文件，但仍需滿足讀者和寫者的互斥、寫者和寫者的互斥，所以該情況下的解決方案和3)相同，在此不再贅述。
　　3 引入管程機(jī)制解決“讀者—寫者”問題
　　通過分層教學(xué)，將難點(diǎn)層層解剖使學(xué)生理解了“讀者—寫者”的概念，此時(shí)注意引導(dǎo)、啟發(fā)學(xué)生注意到在用信號(hào)量機(jī)制解決同步問題時(shí)，往往比較繁瑣這樣一個(gè)問題，很自然地引入到采用面向?qū)ο蟮某绦蛟O(shè)計(jì)思想，將資源及對(duì)資源的共享操作封裝起來，即用管程來管理進(jìn)程同步互斥問題，實(shí)現(xiàn)“讀者—寫者”問題，使用起來會(huì)更加方便。下面將實(shí)現(xiàn)的主要思想描述如下：
　　在具體使用管程機(jī)制來實(shí)現(xiàn)讀者與寫者問題時(shí)，首先建立一個(gè)管程，命名為ReaderWriter進(jìn)程。其中包括以下幾個(gè)過程：
　　
　　1) Read( )過程。讀者利用該過程獲取數(shù)據(jù)塊并擁有數(shù)據(jù)塊中的數(shù)據(jù)，用整型變量ReaderCount來表示現(xiàn)在正在讀取數(shù)據(jù)塊中的數(shù)據(jù)的讀者數(shù)量，當(dāng)ReaderCount為0且條件變量MesState不為0或-1時(shí)，讀者尚須等待。當(dāng)ReaderCount大于0時(shí)，預(yù)示著當(dāng)前數(shù)據(jù)塊已被讀者進(jìn)程占有，條件變量MesState應(yīng)
　　
　　為1，此時(shí)其他讀者可以進(jìn)入數(shù)據(jù)塊讀取數(shù)據(jù)信息。
　　2) EndRead( )過程。讀者讀完數(shù)據(jù)后退出管程，釋放數(shù)據(jù)資源，同時(shí)ReaderCount的數(shù)量做減1操作。當(dāng)ReaderCount的數(shù)量不為0時(shí)，不允許寫者占用該數(shù)據(jù)資源；當(dāng)ReaderCount的數(shù)量變?yōu)?時(shí)，將mesStated的值更改為0，以示數(shù)據(jù)資源現(xiàn)處于空閑狀態(tài)，允許讀者和寫者競爭該數(shù)據(jù)塊資源。
　　3) Write( )過程。模擬寫者利用該過程占有數(shù)據(jù)塊以及獲取數(shù)據(jù)塊中的數(shù)據(jù)，寫者可以修改數(shù)據(jù)。寫者具有追加、刪除、修改數(shù)據(jù)的權(quán)限。寫者占有管程及數(shù)據(jù)塊時(shí)條件變量MesState的值更改為-1，以示其他寫者及所有讀者均須等待該寫者完成此次操作完成后，才有機(jī)會(huì)訪問該資源，實(shí)現(xiàn)讀者和寫者的互斥、寫者和寫者的互斥。當(dāng)寫者完成寫操作后，釋放管程及數(shù)據(jù)塊資源，將MesState的值更改為0，以喚醒在等待對(duì)列的其他進(jìn)程競爭該資源。
　　4 結(jié)語
　　將操作系統(tǒng)中的一個(gè)復(fù)雜的進(jìn)程同步與互斥問題分解成若干個(gè)簡單的問題，由淺入深，層層解析，逐步擴(kuò)展，在講清基本概念之后，進(jìn)一步采取啟發(fā)式教學(xué)，進(jìn)一步深化學(xué)生對(duì)該問題的認(rèn)識(shí)。該教學(xué)方法符合教育教學(xué)規(guī)律，降低了難度，便于學(xué)生掌握課程的重難點(diǎn)，加深了關(guān)于同步問題的理解，提高了學(xué)習(xí)效率，教學(xué)效果也非常顯著。
　　
　　參考文獻(xiàn)：
　　[1] Crow ley C P. Operating systems: a design-oriented approach [M]. Beijing:World Publishing