作業系統複習筆記(四)

10.司機和售票員之間要協同工作:一方面隻有售票員把車門關好了司機才能開車，是以售票員關好車門應通知司機開車;另一方面隻有當汽車已經停下時,售票員才能開門讓乘客上下客,司機停車後應該通知售票員,假定某輛汽車有一名司機和兩名售票員,汽車目前正在始法站停車上客,

分析:   活動規律:

         司機                售票員(2名)

        啟動車輛            上乘客

        正常行駛             關車門

        到站停車            售票

                                       開車門

                                     下乘客

售票員關好車門應該通知司機開車,是以要設定一個信号量用于司機判斷是否可以啟動車輛;此外，當汽車到站停下時,司機停車後要通知售票員,是以也要設定一個信号量用于通知售票員打開車門．由于有兩名售票員，是以相應的信号量都需要設定兩個.

 begin 

                  var stop1=0,stop2=0,run1=0,run2=0:semaphore;

                    cobegin

                        process driver

                            begin

                               repeat

                                    p(run1);

                                    p(run2);

                啟動車輛；

        正常行駛；

        到站停車；

                v(stop1);

                v(stop2);

                            end

                        process conductor1

                      repeat;

                   上乘客；

        關車門；

        v(run1);

        售票；

        p(stop1);

        開車門；

        下乘客;

                           end

                        process conductor2

        v(run2);

        p(stop2);

               coend

    end

注:這是售票員優先的方式,若以司機優先的方式,程式如下:

         v(stop1);

                 p(stop2);

11.兩個學校之間有一條路,其中從s到t一段路每次隻允許一輛車通過,但中間有一個小的"安全島"M(同時允許兩輛車停留),可供兩輛車已經從兩端進入小路的情況下錯車使用.

分析:由于安全島M僅僅允許兩輛車停留,本應該作為臨界資源而要設定信号量,但根據題意,任意時刻進入安全島的車不會超過兩輛(兩個方向最多各有一輛),是以，不需要為M設定信号量,在路口s和路口t都需要設定信号量,以控制來自兩個方向的車對路口資源的争奪.這兩個信号量的初值都是1.此外，由于從s到t的一段路隻允許一輛車通過,是以還需要設定另外的信号量用于控制,由于M的存在,可以為兩端的小路分别設定一個互斥信号量.

begin 

                  var s=1,t=1,sk=1,lt=1:semaphore;

                        process p1

        p(s);

        p(sk);

        通過sk路段；

        進入安全島M;

                 v(sk);

        p(lt);

        通過lt路段；

        v(lt);

        v(s);

        until false

      process p2

                          repeat;

               p(t);

                 v(lt);

        v(sk);

        v(t);

12.有一個理發師,一把理發椅和n把供等候理發的顧客坐的椅子,若沒有顧客,則理發師睡覺,當一個顧客到來時,必須喚醒理發師進行理發,若理發師正在理發,又有顧客到來,則若有空椅子可坐就坐下來等,若沒有空椅子就離開.

分析:需要設定一個信号量barber,初值為0,用于控制理發師和顧客之間的同步關系.還需要設定一個信号量customer,初值為0,用于離開顧客與等候顧客之間的同步控制,為了記錄等候的顧客數,應該設定一個計數器count,初值為0.當一個顧客到達時,需要在count上做加1操作,并根據count值的不同分别采取不同的動作，當顧客離開時,要對count上做減1操作,并根據count值的不同分别采取不同的動作;由于count是共享變量,是以要互斥使用，為此設定一個互斥信号量mutex;

                  var barber=0,customer=0,count=0,mutex=1:semaphore;

                        process barber

        p(customer);

        p(mutex);

        count = count -1;

                 v(barber);

        v(mutex);

        理發;

          process customer

        if(count<n)

        {

            count = count +1;

            v(customer);

            p(barber);

                   理發；

        }

        else

            v(mutex);

            離開；

注:變形:有3個理發師,3把理發椅子,n把供等候理發的顧客坐的椅子.由于有3位理發師,是以一次同時可以為三個顧客服務,設定信号量max_capacity,用于表示空閑椅子的數量,初值為n.信号量barber_chair表示空閑理發師(椅)的數量,初值為3;信号量cust_ready,finished,leave_b_chair分别表示是否有顧客到來,理發完成,離開理發椅,它們的初值都為0;

                  var max_capacity=n,barber_chair=3,cust_ready=0,finished=0,leave_b_chair = 0:semaphore;

        p(cust_ready);

        p(max_capacity);//是否有空閑椅子；

        進入店裡；

        p(barber_chair);//是否有空閑的理發椅；

        坐在理發椅上；

        v(cust_ready);//喚醒理發師；

        p(finished);//是否完成理發；

        離開理發椅；

        v(leave_b_chair);

        離開店；

        v(max_capacity);

13.程序p0,p1共享變量flag,turn;他們進入臨界區的算法如下:

 var flag:array[0..1] of boolean;//初值為false

            turn:01

    process i (0或1)

        while true

            do begin

                flag[i] =true;

                while turn!=i

                    do begin 

                        while flag[j]==false

                            do skip;//skip為空語句

                            turn = i

                        臨界區;

                        flag[i] = false;

                        出臨界區;

                end

該算法能否正确地實作互斥?若不能,應該如何修改(假設flag,turn單元内容的修改和通路是互斥的).

分析:不能正确實作互斥.考慮如下情況:process0先執行到flag[0] = true,process1開始執行,進入内循環時,将turn設定為1;此時程序排程轉到process0,process0可以進入内循環,由于flag[1]的值為true,是以process0再次将turn的值設定為0,重複上述操作,兩個程序誰也不能進入臨界區.

var flag:array[0..1] of boolean;//初值為false

    process 0

                flag[0] =true;

    turn = 1

                  while flag[1]==true and turn = 1

                        flag[0] = false;

  process 0

            while true

                do begin

                flag[1] =true;

    turn = 0

                  while flag[0]==true and turn = 0

                        flag[1] = false;

容易證明這種方法保證了互斥,對于程序0,一旦它設定flag[0]為true,程序1就不能進入其臨界段.若程序1已經在其臨界段中，那麼flag[1]=true并且程序0被阻塞進入臨界段.另一方面,防止了互相阻塞,假設程序0阻塞于while循環,這意味着flag[1]為true,而且turn=1,當flag[1]為false或turn為0時,程序0就可進入自己的臨界段了.

本文轉自Phinecos(洞庭散人)部落格園部落格，原文連結：http://www.cnblogs.com/phinecos/archive/2006/08/28/488556.html，如需轉載請自行聯系原作者