• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      計算機操作系統(tǒng)哲學(xué)家進餐問題的教學(xué)探討

      2009-08-28 09:09:14竇金鳳曹家寶郭忠文劉穎健
      計算機教育 2009年14期
      關(guān)鍵詞:信號量管程

      竇金鳳 曹家寶 郭忠文 劉穎健

      摘要:本文根據(jù)多年的教學(xué)經(jīng)驗,利用信號量機制、管程機制等思想對哲學(xué)家進餐問題進行研究,提出了解決思路,并在教學(xué)實驗過程中進行了驗證。希望與其他相關(guān)領(lǐng)域的學(xué)習(xí)者共享,方便“操作系統(tǒng)”的教學(xué)、學(xué)習(xí)和應(yīng)用。

      關(guān)鍵詞:進程同步;哲學(xué)家進餐問題;信號量;死鎖;管程

      中圖分類號:G642 文獻標(biāo)識碼:B

      1引言

      由荷蘭學(xué)者Dijkstra提出的哲學(xué)家進餐問題(The Dinning Philosophers Problem)是經(jīng)典的同步問題之一。哲學(xué)家進餐問題是一大類并發(fā)控制問題的典型例子,涉及信號量機制、管程機制以及死鎖等操作系統(tǒng)中關(guān)鍵問題的應(yīng)用,在操作系統(tǒng)文化史上具有非常重要的地位。對該問題的剖析有助于學(xué)生深刻地理解計算機系統(tǒng)中的資源共享、進程同步機制、死鎖等問題,并能熟練地將該問題的解決思想應(yīng)用于生活中的控制流程。

      2問題描述

      有五個哲學(xué)家,共用一張圓桌,分別坐在周圍的五把椅子上,圓桌上有五個碗和五只筷子,每人兩邊各放一只筷子,如圖1所示。哲學(xué)家們是交替思考和進餐,饑餓時便試圖取其左右最靠近他的筷子。

      哲學(xué)家進餐問題可看作是并發(fā)進程并發(fā)執(zhí)行時,處理共享資源的一個有代表性的問題。分析其約束條件:

      (1) 只有拿到兩只筷子時,哲學(xué)家才能吃飯。

      (2) 如果筷子已被別人拿走,則必須等別人吃完之后才能拿到筷子。

      (3) 任一哲學(xué)家在自己未拿到兩只筷子吃飯前,不會放下手中拿到的筷子。

      3用信號量機制解決問題

      3.1記錄型信號量

      筷子是臨界資源,一段時間只允許一位哲學(xué)家使用。為了表示互斥,用一個信號量表示一只筷子,五個信號量構(gòu)成信號量數(shù)組。由于計算機專業(yè)本科生先行課開設(shè)C語言,所以本文中算法用類C語言描述偽碼算法。算法描述如下:

      Semaphore chopstick[5]={1,1,1,1,1};/*分別表示5支筷子*/

      Main()

      {

      cobegin

      philosopher(0);

      philosopher(1);

      philosopher(2);

      philosopher(3);

      philosopher(4);

      coend

      }

      第I位哲學(xué)家的活動描述為:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      wait (chopstick [ I ]);

      wait (chopstick [(I+1)%5]);

      進餐;

      signal (chopstick [I]);

      signal (chopstick [(I+1)%5]);

      }

      }

      當(dāng)哲學(xué)家饑餓時,總是先去拿他左邊的筷子,執(zhí)行wait (chopstick [I]),成功后,再去拿他右邊的筷子,執(zhí)行wait (chopstick [I+1] %5);成功后便可進餐。進餐畢,先放下他左邊的筷子,然后再放下右邊的筷子。

      當(dāng)五個哲學(xué)家同時去取他左邊的筷子,每人拿到一只筷子且不釋放,即五個哲學(xué)家只得無限等待下去,引起死鎖。

      3.2死鎖問題的解決

      預(yù)防死鎖即是破壞死鎖的必要條件之一。通常用下列方法解決死鎖問題。

      3.2.1破壞請求保持條件

      利用原子思想完成。即只有拿起兩支筷子的哲學(xué)家才可以進餐,否則,一支筷子也不拿。

      解法一:利用AND機制實現(xiàn)第I位哲學(xué)家的活動描述為:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      swait(chopstick[(I+1)] % 5,chopstick[I]);

      進餐;

      ssignal(chopstick[I], chopstick[(I+1)% 5]);

      }

      }

      解法二:利用記錄型信號量機制實現(xiàn)在初始化中增加一個信號量定義:semaphore mutex = 1;

      第I位哲學(xué)家的活動描述:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      wait(mutex);

      wait (stick [ I ]);

      wait (stick [(I+1)%5]);

      signal (mutex);

      進餐;

      signal (stick [I]);

      signal (stick [(I+1)%5]);

      }

      }

      該方法將拿兩只筷子的過程作為臨界資源,一次只允許一個哲學(xué)家進入。

      3.2.2破壞環(huán)路等待條件

      在上述死鎖問題中,哲學(xué)家對筷子資源的申請構(gòu)成了有向環(huán)路,如圖2所示。

      解法一:奇數(shù)號哲學(xué)家先拿他左邊的筷子,偶數(shù)號哲學(xué)家先拿他右邊的筷子。這樣破壞了同方向環(huán)路,一個哲學(xué)家拿到一只筷子后,就阻止了他鄰座的一個哲學(xué)家吃飯。按此規(guī)定,將是1、2號哲學(xué)家競爭1號筷子;3、4號哲學(xué)家競爭4號筷子。兩種算法描述如下:

      (1) 第I個哲學(xué)家的活動:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      IfI % 2 == 1 then

      wait (stick [ I ]);

      wait (stick [(I+1)%5]);

      進餐;

      signal (stick [I]);

      signal (stick [(I+1)%5]);

      else

      wait (stick [(I+1)%5]);

      wait (stick [ I ]);

      進餐;

      signal (stick [(I+1)%5]);

      signal (stick [I]);

      }

      }

      (2) 第I個哲學(xué)家的活動:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      wait (chopstick[I +(I % 2)];

      wait (chopstick[(I+ (I+1) % 2) % 5] )

      進餐;

      signal (chopstick[I +(I % 2)]);

      signal (chopstick[(I+ (I+1) % 2) % 5] );

      }

      }

      解法二:至多允許四位哲學(xué)家進餐,將最后一個哲學(xué)家停止申請資源,斷開環(huán)路。最終能保證有一位哲學(xué)家能進餐,用完釋放兩只筷子,從而使更多的哲學(xué)家能夠進餐。增加一個信號量定義semaphorecount = 4;算法描述第I個哲學(xué)家的活動:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      wait (count);

      wait(chopstick[I ]);

      wait(chopstick[I+1]mod 5);

      進餐;

      signal(chopstick[I]);

      signal(chopstick[I+1]mod 5)

      signal(count)

      }

      }

      解法三:哲學(xué)家申請資源總是按照資源序號先大后小的順序,這樣0-3號哲學(xué)家先右后左,但是4號哲學(xué)家先左后右,改變方向,破壞了環(huán)路。算法描述第I個哲學(xué)家的活動:

      philosopher (int I)

      {

      while (true)

      {

      思考;

      if I >(I+1) % 5 then

      wait (chopstick [I ]);

      wait (chopstick [I+1]mod 5);

      else

      wait (chopstick [I+1]mod 5);

      wait (chopstick [I ]);/*哲學(xué)家總是先取最 大序號的筷子*/

      進餐;

      signal (chopstick [I ]);

      signal (chopstick [I+1]mod5);

      }

      }

      3.2.3破壞非剝奪條件

      打破約束條件(3),設(shè)立優(yōu)先權(quán)。比如,根據(jù)哲學(xué)家等待筷子的時間設(shè)定,時間越大優(yōu)先權(quán)越高,優(yōu)先權(quán)高的可以搶奪優(yōu)先權(quán)低的筷子。

      4用管程機制解決哲學(xué)家進餐問題

      在用信號量機制解決同步問題時,往往比較繁瑣,采用面向?qū)ο蟮乃枷?將資源及資源的共享操作封裝起來,用管程來管理,實現(xiàn)哲學(xué)家進餐問題,使用起來更加方便。

      算法實現(xiàn)描述如下:

      4.1建立管程

      monitor PC/*建立管程*/

      {

      semaphore chopstick [5] = {1,1,1,1,1};

      X: condition; /*定義條件變量*/

      void Get (int I) /*定義取筷子過程*/

      {

      If chopstick[I]=1 and chopstick [ ( i+1 )% 5] =1 then

      get the chopstick [I] and chopstick [ ( i+1 ) % 5];

      else X.wait;/*左右筷子沒有,則等待*/

      }

      void Put (int i) /*定義放下筷子過程*/

      {

      put the chopstick [I ] and chopstick ( i+1 ) % 5];

      If X.quene then X.signal;/*喚醒等待筷子 的哲學(xué)家*/

      }

      }

      4.2使用管程

      第I個哲學(xué)家的活動:

      void philosopher(int I)

      {

      while(true)

      {

      思考;

      get (I);

      進餐;

      put (I);

      }

      }

      5結(jié)束語

      哲學(xué)家進餐問題是操作系統(tǒng)中一個常見且復(fù)雜的同步問題,它可為多個競爭進程或者線程互斥地訪問有限資源這一類問題的解決提供思路。本文根據(jù)多年的教學(xué)所得,利用不同的機制探討并提出了這一問題的解決思路。然后提出了解決死鎖問題的相關(guān)思路,將其應(yīng)用到教學(xué)實驗中。提出的解決策略可有效地實現(xiàn),并且避免饑餓和死鎖現(xiàn)象的產(chǎn)生。希望與其他相關(guān)領(lǐng)域的學(xué)習(xí)者共享,方便操作系統(tǒng)的教學(xué)、學(xué)習(xí)和應(yīng)用。

      參考文獻:

      [1] Andrew S. Tanenbaum, Modern Operating System[M]. 2nd ed. Englewood Cliffs, New Jersey:Prentice Hall, 2001.

      [2] Abraham S. 操作系統(tǒng)概念(影印版)[M].6版. 北京: 高等教育出版社,2002.

      [3] 湯子瀛,哲鳳屏,湯小丹.計算機操作系統(tǒng)(修訂版)[M].西安:西安電子科技大學(xué)出版社,2002.

      [4] 周蘇,金海溶,李潔. 操作系統(tǒng)原理實驗[M]. 北京:科學(xué)出版社,2003.

      猜你喜歡
      信號量管程
      換熱器設(shè)計中無相變溫度交叉問題的技術(shù)措施
      山東化工(2024年6期)2024-05-10 01:47:14
      基于STM32的mbedOS信號量調(diào)度機制剖析
      互斥信號量初值不同情況分析
      螺旋套管式換熱器螺紋擾流及耦合傳熱數(shù)值模擬
      遼寧化工(2022年7期)2022-08-11 02:44:48
      Nucleus PLUS操作系統(tǒng)信號量機制的研究與測試
      硬件信號量在多核處理器核間通信中的應(yīng)用
      多管程布置微通道分液冷凝器的熱力性能
      利用管程概念求解哲學(xué)家進餐問題
      為RTX51Tiny項目添加管程模塊※
      μC/OS- -III對信號量的改進
      沭阳县| 泸溪县| 黔西县| 汾西县| 元谋县| 青河县| 南丹县| 台东县| 张北县| 刚察县| 濮阳市| 顺义区| 鹤峰县| 同心县| 孝昌县| 垦利县| 巧家县| 扶风县| 汉沽区| 浙江省| 醴陵市| 当涂县| 松潘县| 龙江县| 泰来县| 聂荣县| 且末县| 甘肃省| 宁明县| 鹤岗市| 贵德县| 监利县| 香港| 察隅县| 丰都县| 南昌县| 张家口市| 富源县| 盘山县| 泽普县| 白河县|