操作系統(tǒng)中P、V操作實(shí)現(xiàn)進(jìn)程的同步與互斥

1、Computer Knowledge and Technology 電腦知識與技術(shù)第8卷第30期(2012年10月操作系統(tǒng)中P 、V 操作實(shí)現(xiàn)進(jìn)程的同步與互斥常靜(廣東外語外貿(mào)大學(xué)南國商學(xué)院信息科學(xué)技術(shù)系,廣東廣州510545摘要:操作系統(tǒng)是計(jì)算機(jī)科學(xué)與技術(shù)的專業(yè)基礎(chǔ)課程,進(jìn)程的同步與互斥問題是操作系統(tǒng)中的重要內(nèi)容。如何正確使用P 、V 操作實(shí)現(xiàn)進(jìn)程的同步與互斥是防止死鎖的重要手段,怎樣判斷進(jìn)程是同步還是互斥問題,以及如何正確使用P 、V 操作防止進(jìn)程死鎖,該文通過具體的實(shí)例給出一種通用的解決模式。關(guān)鍵詞:進(jìn)程同步;進(jìn)程互斥;信號量;P 、V 操作中圖分類號:TP393文獻(xiàn)標(biāo)識碼:A 文章編號

2、:1009-3044(201230-7144-04To Achieve Process Synchronism and Exclusion in Operating System By P 、V OperationsCHANG Jing(The Department of Information Science &Technology,South China business College,Guangdong University of Foreign Studies,Guangzhou 510545,ChinaAbstract:Operating system is the fou

3、ndation courses of Computer Science and Technology,Process synchronism and exclusionproblem is the important content of the operating system.How to properly use the P 、V operation in process synchronism and exclusion is an important means to prevent deadlocks,How do we judge the process is synchroni

4、sm or exclusion problem and howto use P,V operation preventing process Deadlock,This paper given in the mode of a universal solution By Specific examples.Key words:process synchronism;process exclusion;signal;P 、V operation操作系統(tǒng)中,可以使用軟件和硬件方法解決臨界區(qū)的問題,雖然它們都可以解決互斥問題,但是存在一定的缺陷。于是計(jì)算機(jī)科學(xué)家們努力尋找其他更有效地方法。荷蘭著名的

5、計(jì)算機(jī)科學(xué)家E.W.Dijkstra 提出了一個(gè)信號量和P 、V 操作同步機(jī)構(gòu)。其基本原則是在多個(gè)相互合作的進(jìn)程之間使用簡單的信號來協(xié)調(diào)控制。1信號量的含義信號量被定義為含有整型數(shù)據(jù)項(xiàng)的結(jié)構(gòu)變量,其整型值大于等于零代表可供并發(fā)進(jìn)程使用的資源個(gè)數(shù),小于零時(shí)其絕對值表示正在等待使用臨界資源的進(jìn)程數(shù)。其數(shù)據(jù)結(jié)構(gòu)表示為:typedef struct int value;pCB *pointer;semaphore;由此可以看出信號量是一個(gè)結(jié)構(gòu)變量,不是簡單變量。2P 、V 原語的含義信號量的值可以修改,但只能由P 和V 操作來訪問,對信號量的操作由P 、V 操作原語來實(shí)現(xiàn)。P 操作和V 操作在執(zhí)行時(shí)是

6、不可中斷的過程。P 操作P(s表示申請一個(gè)資源,將信號量s 的整型值減去1,若結(jié)果小于0,則將調(diào)用P(s的進(jìn)程插入等待該資源的阻塞隊(duì)列。V 操作V(s表示釋放一個(gè)資源,將信號量s 的整型值加上1,若結(jié)果不大于0,則從該資源的阻塞隊(duì)列首部喚醒一個(gè)進(jìn)程插入到就緒隊(duì)列中。P 、V 操作原語是一種阻塞等待的同步原語,若進(jìn)程通過該原語的調(diào)用而不允許繼續(xù)執(zhí)行時(shí),它將被阻塞或掛起,在此期間就沒收稿日期:2012-09-28作者簡介:常靜(1979-,女,河南新鄉(xiāng)人,講師,碩士,研究方向計(jì)算機(jī)教學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)。E-mail:jslt Tel:+86-551-56909635690964ISSN 1009-30

7、44Computer Knowledge and Technology 電腦知識與技術(shù)Vol.8,No.30,October 2012.第8卷第30期(2012年10月Computer Knowledge and Technology電腦知識與技術(shù)有機(jī)會(huì)獲得CPU執(zhí)行,直到它被喚醒為止。故可使得進(jìn)程在等待進(jìn)入臨界區(qū)時(shí),將CPU讓給了其他就緒進(jìn)程執(zhí)行。而忙等待的臨界區(qū)管理法,使得進(jìn)程在等待進(jìn)入臨界區(qū)時(shí),也和其他就緒進(jìn)程一起分享CPU的服務(wù)。3P、V操作在進(jìn)程同步中的意義進(jìn)程同步包括進(jìn)程互斥和進(jìn)程同步兩個(gè)方面,進(jìn)程互斥是同步的一種特例。用P、V操作解決進(jìn)程同步問題時(shí)首先要分清哪些是互斥問題(互斥訪

8、問臨界資源的,哪些是同步問題(具有前后執(zhí)行順序要求的。在互斥問題中,P操作的意義是申請資源,是否能進(jìn)入臨界區(qū);V操作的意義是退出臨界區(qū),從而釋放資源;通常只設(shè)置一個(gè)互斥信號量,且初值為1,代表一次只允許一個(gè)進(jìn)程對臨界資源進(jìn)行訪問。在同步問題中,P操作的意義是接受發(fā)來的信息、通知,表示可以執(zhí)行;V操作的意義是發(fā)送消息、通知,告知對方。在設(shè)置同步信號量時(shí),通常同步信號量的個(gè)數(shù)與參與同步的進(jìn)程種類有關(guān),即同步關(guān)系涉及幾類進(jìn)程,就有幾個(gè)同步信號量。同步信號量表示該進(jìn)程是否可以開始或該進(jìn)程是否已經(jīng)結(jié)束。在每個(gè)進(jìn)程中用于實(shí)現(xiàn)互斥的P、V操作必須成對出現(xiàn);用于實(shí)現(xiàn)同步的P、V操作也必須成對出現(xiàn),但可以分別出

9、現(xiàn)在不同的進(jìn)程中;在某個(gè)進(jìn)程中如果同時(shí)存在互斥與同步的操作,則其順序不能顛倒,必須先執(zhí)行對同步信號量的P操作,再執(zhí)行對互斥信號量的P操作,但V操作的順序沒有嚴(yán)格要求。4實(shí)現(xiàn)P、V操作的具體做法1確定進(jìn)程間的關(guān)系以及進(jìn)程的個(gè)數(shù)。這一環(huán)節(jié)非常重要,如果理解不準(zhǔn)確,則之后的操作都將是錯(cuò)誤的。進(jìn)程間的關(guān)系主要指是進(jìn)程同步還是進(jìn)程互斥,它決定了P、V操作在進(jìn)程中存在的意義。進(jìn)程的個(gè)數(shù)主要看題目中需要P、V控制的事件有多少個(gè),則進(jìn)程個(gè)數(shù)就是幾個(gè)。2信號量個(gè)數(shù)的設(shè)置,并給信號量賦初值。一般情況下,在進(jìn)程互斥中,信號量都為一個(gè);在同步中,要根據(jù)進(jìn)程間的同步關(guān)系來設(shè)置信號量的個(gè)數(shù),有一個(gè)也可能是多個(gè)。3畫出進(jìn)程

10、的工作流程圖。流程圖時(shí)最好反映題意的一種方法,工作流程圖越準(zhǔn)確,最后的算法就越容易實(shí)現(xiàn)。4根據(jù)流程圖使用一門語言來描述進(jìn)程之間的關(guān)系。這步主要是看個(gè)人的編程基礎(chǔ),用不同的語言實(shí)現(xiàn)都可以,最好是用自己掌握較好的一門語言。下面就一些典型例子做分析,在分析中理解P、V操作在進(jìn)程同步中的實(shí)際運(yùn)用:4.1用PV原語實(shí)現(xiàn)進(jìn)程的互斥為了正確地解決一組并行進(jìn)程對臨界資源的競爭使用,可以引入一個(gè)互斥信號量,對于互斥使用的資源,其信號量的初值就是系統(tǒng)中這個(gè)資源的數(shù)量。以哲學(xué)家進(jìn)餐問題為例:有四位哲學(xué)家圍著一個(gè)圓桌在思考和進(jìn)餐,每人思考時(shí)手中什么都不拿,當(dāng)需要進(jìn)餐時(shí),每人需要用刀和叉各一把,餐桌上的布置如圖1所示,

11、共有兩把刀和兩把叉,每把刀或叉供相鄰的兩個(gè)人使用。請用信號量及PV操作說明四位哲學(xué)家的同步過程。 圖11確定進(jìn)程的個(gè)數(shù)及其工作內(nèi)容。本例子涉及四個(gè)進(jìn)程,每個(gè)哲學(xué)家為一個(gè)進(jìn)程。因相鄰的兩個(gè)哲學(xué)家要競爭刀或叉,刀或叉就成為了臨界資源,所以屬于互斥關(guān)系。2第二步確定互斥信號量的個(gè)數(shù)、含義及PV操作。設(shè)置4個(gè)互斥信號量fork1,fork2,knife1,knife2,其初值均為“1”,分別表示叉1,叉2,刀1,刀2是可用的。3畫工作流程圖。一般情況下,進(jìn)程互斥問題的工作流程基本相同,所以只要畫出其中一個(gè)進(jìn)程的流程圖即可。4根據(jù)流程圖寫出相應(yīng)算法。用類C語言描述互斥關(guān)系,互斥描述如下:int fork

12、1=1;int fork2=1;int knife1=1;int knife2=1;main(pa(;pb(;pc(;pd(;Computer Knowledge and Technology電腦知識與技術(shù)第8卷第30期(2012年10月Pa( while(1 p(knife1; P(fork1;進(jìn)餐; V(knife1; V(fork1;思考; Pb(while(1p(knife2;P(fork1;進(jìn)餐;V(knife2;V(fork1;思考;Pc(while(1p(knife2;P(fork2;進(jìn)餐;V(knife2;V(fork2;思考;Pd(while(1p(knife1;P(fork

13、2;進(jìn)餐;V(knife1;V(fork2;思考;判斷進(jìn)程間是否互斥,關(guān)鍵是看進(jìn)程間是否共享某一臨界資源。在每個(gè)程序中用于實(shí)現(xiàn)互斥地P和V必須成對出現(xiàn),即先做P 操作,進(jìn)入臨界區(qū),后做V操作,推出臨界區(qū)?；コ庑盘柫康某踔凳琴Y源的個(gè)數(shù),一般為1。4.2用P、V原語實(shí)現(xiàn)進(jìn)程的同步進(jìn)程的同步是指相互合作的一組并行進(jìn)程,各自以獨(dú)立的、不可預(yù)知的速度向前推進(jìn),在前進(jìn)過程中彼此之間需要相互協(xié)調(diào)步伐,才能更好地完成同一項(xiàng)任務(wù)。為了解決進(jìn)程的同步,同樣地也可引入信號量,稱之為同步信號量。信號量的初值一般為0,同步信號量的P、V操作要“成對”出現(xiàn),但是,它們分別出現(xiàn)在不同的進(jìn)程代碼中,應(yīng)該注意P、V操作在程序代

14、碼中出現(xiàn)的位置。通過下面的例子來說明此問題:桌上有一空盤子,只允許放一個(gè)水果。爸爸可以向盤中放蘋果,也可以向盤中放桔子,兒子專等吃盤中的桔子,女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí),一次只能放一個(gè)水果,請用P、V操作實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)“并發(fā)進(jìn)程”的同步。1確定進(jìn)程間的關(guān)系。這是一個(gè)明顯的同步問題,也稱為生產(chǎn)者和消費(fèi)真問題。爸爸可以向盤子中放入兩類水果:桔子、蘋果;然后兒子、女兒每人可以消費(fèi)其中一種水果。爸爸是生產(chǎn)者,子女是消費(fèi)者,也就是只有爸爸放入水果,子女才能消費(fèi)水果;只有子女消費(fèi)完水果,爸爸才能再次放入水果。所以爸爸與子女之間是一種同步關(guān)系。2設(shè)置三個(gè)同步信號量:Sp表示盤子是否為空,其

15、初值為“1”,其含義是爸爸是否可以開始放入水果;So表示盤中是否有桔子,其含義是兒子是否可以開始取桔子,其初值為“0”表示不能取桔子;Sa表示盤中是否有蘋果,其含義是女兒是否可以開始取蘋果,其初值為“0”表示不能取蘋果。3畫出工作流程圖,如圖2所示。圖24根據(jù)流程圖寫出相應(yīng)算法。用類C語言描述同步關(guān)系: int Sp=1;int Sa=0;int So=0;main(father(;son(;daughter(;father(while(trueP(Sp;將水果放入盤中;If(放入的是桔子V(So;elseV(Sa;son(while(trueP(So;從盤中取出桔子;V(Sp;吃桔子;dau

16、ghter(while(trueP(Sa;從盤中取出蘋果;V(Sp;吃蘋果;4.3用P、V原語實(shí)現(xiàn)進(jìn)程的同步和互斥有了上面的分析后,下面來考慮進(jìn)程同步與互斥的混合問題就不難了。混合問題當(dāng)中關(guān)鍵就是協(xié)調(diào)同步操作和互斥操作的先后。通過下面的例子來說明此問題:設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū),A進(jìn)程順序地把信息寫進(jìn)緩沖區(qū),B進(jìn)程依次地從緩沖區(qū)中讀出信息,請用P、V操作表示A和B進(jìn)程的同步算法。1確定進(jìn)程間的關(guān)系。A和B兩個(gè)進(jìn)程對緩沖區(qū)的訪問必須互斥,并且當(dāng)緩沖區(qū)滿時(shí),A進(jìn)程不能寫入,必須等待;當(dāng)緩沖區(qū)空時(shí),B進(jìn)程不能讀,必須等待。所以這是一個(gè)同步加互斥的問題。2確定信號量及其值?？梢栽O(shè)置3個(gè)信號

17、量:互斥信號量S=1(表示對緩沖區(qū)的互斥使用;同步信號量Sw(代表緩沖區(qū)是否有空閑,即寫進(jìn)程能否寫、Sr(代表緩沖區(qū)是否有數(shù)據(jù),即讀進(jìn)程能否讀,假設(shè)初始時(shí)緩沖區(qū)沒有任何數(shù)據(jù),則Sw=N,Sr=0。3畫出工作流程圖,如圖3所示。圖34根據(jù)流程圖寫出相應(yīng)算法。在此就不再詳述。(下轉(zhuǎn)第7153頁2獲取相關(guān)知識:數(shù)據(jù)是挖掘知識最原始的資料,根據(jù)確定的數(shù)據(jù)分析對象,抽象出數(shù)據(jù)分析中所需要的特征信息模型。領(lǐng)域問題的數(shù)據(jù)收集完成之后,與目標(biāo)信息相關(guān)的屬性也隨之確定。這些數(shù)據(jù)有些是可以直接獲得的,有些則需要對學(xué)生進(jìn)行調(diào)查才能的得到。3數(shù)據(jù)預(yù)處理:此過程中是對已收集的大量數(shù)據(jù)進(jìn)行整合與檢查。因?yàn)榇娣旁跀?shù)據(jù)庫中的

18、數(shù)據(jù)一般是不完整的、不一致的,通常還含有噪聲的存在。因此就需要對數(shù)據(jù)庫中數(shù)據(jù)進(jìn)行清理、整理和歸并,以提高挖掘過程的精度和性能。4數(shù)據(jù)轉(zhuǎn)換:對預(yù)處理后的數(shù)據(jù)建立分析模型,對于特定的任務(wù),需要選擇合適的算法來建立一個(gè)準(zhǔn)確的適合挖掘算法的分析模型。本文采用決策樹技術(shù)進(jìn)行分類建模來解決相應(yīng)的問題。5分類挖掘知識和信息:此階段的工作目的是根據(jù)系統(tǒng)最終要實(shí)現(xiàn)的功能和任務(wù)來確定挖掘的分類模型。選擇合適的數(shù)據(jù)挖掘技術(shù)及算法,并采用恰當(dāng)?shù)某绦蛟O(shè)計(jì)語言來實(shí)現(xiàn)該算法,對凈化和轉(zhuǎn)換過得數(shù)據(jù)訓(xùn)練集進(jìn)行挖掘,獲得有價(jià)值的分析信息。6知識表示:將數(shù)據(jù)挖掘得到的分析信息進(jìn)一步的解釋和評價(jià),生成可用的、正確的、可理解的分類規(guī)則

19、呈現(xiàn)給管理者,應(yīng)用于實(shí)踐。7知識應(yīng)用:將分析得到的規(guī)則應(yīng)用到教學(xué)管理中,教師可以利用所得到的知識針對性的開展畢業(yè)設(shè)計(jì)的教學(xué)活動(dòng),進(jìn)一步指導(dǎo)教學(xué)工作,提高教學(xué)水平和學(xué)生的畢業(yè)論文質(zhì)量。4結(jié)論最終發(fā)現(xiàn)影響學(xué)生畢業(yè)論文成績主要的因素不是指導(dǎo)教師的職稱,學(xué)生的基礎(chǔ)及感興趣程度,而是指導(dǎo)教師的學(xué)歷高低。根據(jù)具體分類規(guī)則的結(jié)論,學(xué)校教學(xué)管理工作應(yīng)加重對教師的素質(zhì)及能力培養(yǎng),合理的分配每個(gè)教師的畢業(yè)論文指導(dǎo)工作,不僅能夠有效的完成畢業(yè)課題指導(dǎo)工作,更有助于學(xué)生整體論文質(zhì)量的提高。在高校教學(xué)數(shù)字化的時(shí)代趨勢下,利用數(shù)據(jù)挖掘技術(shù)來挖掘提取教學(xué)工作中的全面而有價(jià)值信息,可以為教育管理者的教學(xué)工作提供有效的參考信息,改進(jìn)教學(xué)管理方法,提高教學(xué)質(zhì)量和學(xué)生的綜合素質(zhì),是高校保持良好的可持續(xù)發(fā)展的有力工具。參考文獻(xiàn):1劉玉文.數(shù)據(jù)挖掘在高校招生中的研究與應(yīng)用D.上海:上海師范大學(xué),2008.2魏萍萍,王翠茹,王保義,張振興.數(shù)據(jù)挖掘技術(shù)及其在高校教學(xué)系統(tǒng)中的應(yīng)用J.計(jì)算機(jī)工程,2003.29(11:87-89.3劉林東.Web挖掘在考試系統(tǒng)中的應(yīng)用J.計(jì)算機(jī)應(yīng)用研究,2005(2:150-154.4Tom M Mitchell.(美卡內(nèi)基梅隆大學(xué).機(jī)器學(xué)習(xí)D.曾華軍,張銀奎,譯,北京:機(jī)械工業(yè)出版