nachos系統(tǒng)實驗報告：實驗三

1、實驗三一實驗目的學會運用實驗二中實現(xiàn)的工具來實現(xiàn)一些多線程并發(fā)問題。二實驗內容1)EventBarrier：EventBarrier與某個事件相聯(lián)系。事件有signaled和unsignale兩種狀態(tài)。線程想通過事件時必須等待事件被另外線程。只有當所有進入事件的線程完成動作時發(fā)出signal的線程才將事件狀態(tài)設為unsignaled2)AlarmClock：AlarmClock讓某個線程停止指定時間單位。當事件到達時重新將線程放入就緒隊列。3)Bridge：Bridge是一個單行橋且最大允許3量車在橋上行駛。實現(xiàn)應解決注意公平性與饑餓問題。4)Elevator：實現(xiàn)Elevator類并解決3個

2、并發(fā)問題一個電梯，電梯容量無限。b)一個電梯，電梯容量有限。c)多個電梯。三.實驗結果1.EventBarrier類定義：enumBarrierStatusunsignaled,signaled;classEventBarrierpublic:EventBarrier();EventBarrier();voidWait();voidSignal();voidComplete();intWaiters();private:LockO*lock;ConditionO*conSignal;/用于掛起和喚醒調用Signal()函數(shù)的線程。ConditionO*conComplete;/用于掛起和喚醒完

3、成response而處于等待別的事件response的線程ConditionO*conWait;/用于掛起和喚醒那些當事件處于unsignaled而調用Wait()的線程BarrierStatusstatus;/事件狀態(tài)intwaiterNum;voidEventBarrier:Wait()voidEventBarrier:Signal()lock-Acquire();lock-Acquire();waiterNum+;status=signaled;if(status=signaled)conWait-Broadcast(lock);/處于signaled狀態(tài)，直接/通知所有等待Event的

4、事件returnwhile(waiterNum!=0)lock-Release();return;conSignal-Wait(lock);/當還有事件沒response時掛起/處于unsignaled狀態(tài)conComplete-Broadcast(lock);/等到處于Signaled狀態(tài)為止。/通知所有等待別的線程response的線conWait-Wait(lock);程lock-Release();status=unsignaled;lock-Release();voidEventBarrier:Complete()lock-Acquire();waiterNum-;if(waiter

5、Num=0)conSignal-Signal(lock);/通知Signal線程全部事件已處理完conComplete-Wait(lock);/等待其它線程responselock-Release();主要函數(shù)）Wait():線程掛起待事件被signal，當事件已經(jīng)處于signaled狀態(tài)時直接return）Signal():線程通知所有等待事件的線程。并且掛起等待所有調用Wait()的線程結束操作并調用通知此線程（包括在掛起過程中調用Wait()的線程）。3)Complete():當所有Wait()線程都完成操作調用Complete后通知Signal線程,此線程已經(jīng)完成操作并且的等地其它線程

6、response。測試結果：測試中主線程來釋放Signal信號。另4個線程做為等待線程，名字分別為Thread4。Thread在主線程Signal之前就調用Wait()函數(shù)，Thread3,4在事件被標志Signaled狀態(tài)時才調用Wait()。最終結果如下圖所示，事件在四個線程都response自后才改變狀態(tài)，四個線程個主線程都運行正確。Thread1,2進入等待signal事件Thread3,4直接過Barrier。完成操作進入complete等待Thread1,2進入complete等待。通知所有正在等待response的線程所有線程都已經(jīng)complete2.AlarmClock類定義c

7、lassAlarmpublic:Alarm();Alarm();voidPause(inthowLong);/讓線程在howLong事件后開始運行voidThreadRestart();/鬧鐘結束后重新開始運行線程private:LockO*lock;ConditionP*conLock;/此條件變量里的線程隊列是按照優(yōu)先級排列的;/每次運行優(yōu)先級最高的線程主要函數(shù)：voidAlarm:Pause(inthowLong)voidAlarm:ThreadRestart()lock-Acquire();conLock-Signal(NULL);interrupt-Schedule(TimeUP,0

8、,howLong,AlarmInt);conLock-Wait(lock,stats-totalTicks+howLong);staticvoidTimeUP(intNoUse)lock-Release();alarmClock-ThreadRestart();1）Pause(inthowLong)：讓事件停止howLong個時間單位。調用了系統(tǒng)自帶的函數(shù)函數(shù)，在howLong時間后調用TimeUP（int0)函數(shù)。并將中斷的發(fā)生時間totalTicks+howLong當做此線程的優(yōu)先級將其掛起確保每次alarmClock喚醒的線程是設置鬧鐘最早的線程。）TimeUP（intNoUse):用于

9、當做中斷發(fā)生時的調用函數(shù)，函數(shù)中的alarmClock為全局鬧鐘變量。參數(shù)沒有任何作用。）)一個鬧鐘中斷到來。喚醒對應線程（最早線程），將其加入就緒隊列。測試結果：共七個線程，每個線程設置的howLong為1200隨即數(shù)。已運行多次進行檢驗。其中一次結果如下圖所示。每個線程在正確的時間結束鬧鐘進入就緒隊列。每次時鐘中斷增加事件隨機Thread0,184alarmendThread3,201alarmendThread2,271alarmendThread1,284alarmendThread6,289alarmendThread4,325alarmendThread5,400alarmend.

10、Bridge供Bridge模塊使用的靜態(tài)全局變量staticinttraDir;/此時橋的交通方向staticintcarNum;/橋上的車子數(shù)量staticList*dirQueue=newList();/按先來用于存儲等待的車的方向staticLockO*lock=newLockO(NULL);staticConditionO*conLock=newConditionO(NULL);voidArriveBridge(intdir)voidExitBridge(intdir)inttDir;boolis=1;lock-Acquire();if(carNum=3)lock-Acquire();

11、if(!dirQueue-IsEmpty()if(carNum=1)/Bridgefullis=0;/此時下13輛車可能時反向,dirQueue-Append(void*)dir);conLock-Wait(lock);elseif(carNum!=0)if(dir!=traDir)/oppositedirectionis=0;dirQueue-Append(void*)dir);conLock-Wait(lock);elseif(!dirQueue-IsEmpty()/Therearecarswaitingis=0;dirQueue-Append(void*)dir);conLock-Wai

12、t(lock);車/唯一一輛車下橋時發(fā)信號給下一輛for(inti=1;iIsEmpty();i+)tDir=(int)dirQueue-GetItem(1);traDir=tDir;if(tDir!=dir)dirQueue-Remove();conLock-Signal(lock);carNum+;elsebreak;elseif(carNum=3)/若下輛車方向一樣則if(is)carNum+;traDir=dir;lock-Release();tDir=(int)dirQueue-GetItem(1);if(tDir=traDir)dirQueue-Remove();conLock-S

13、ignal(lock);carNum+;carNum-;lock-Release();Bridge采用的是先到先進的政策，若方向為1的車進橋，此時橋上只有1輛方向為1的車，但對面有方向為0的車在等待時，此車也進入等待。以此達到公平和防止餓死，因為不會用車輛處于一直等待的狀態(tài)。1)ArriveBridge(intdir):當橋上由3輛車時：線程直接掛起。當橋上由1,2輛車時：若線程方向與橋的方向相反，線程掛起若線程方向與橋的方向相同但對面由車等待，則線程掛起當橋上沒有車時：線程直接通過）voidExitBridge(intdir)：當沒有車等待時直接exit。有車等待時：當橋上有1輛車時：等待的

14、車方向一定相反，按先后順序喚醒13輛方向與此線程方向相反的車。當橋上有2輛車時：因為此時等待隊列下一輛車不可能與其方向相同。所以當橋上車輛為2輛時不用處理。當橋上有3兩車時：若等待隊列下一輛車方向相同，車喚醒下一輛車。測試結果：創(chuàng)造6兩車，每輛車的方向為隨機0或1。已檢驗多次，其中一次截圖如下。結果正確。/從生成的車輛可以看出26號車將被掛起。1號車exit橋，喚醒下面3輛方向與其相反的車輛2號車出橋并喚醒5號車3號車出橋喚醒6號車除了隨機的測試之外還測試了一些具體的情況如：car1,dir0car2,dir1car3,dir0car4,dir1car5,dir0car6,dir1car1,d

15、ir0car2,dir0car3,dir0car4,dir0car5,dir0car6,dir0最終結果都顯示正確。4.ElevatorElevator代碼較多，下面按運行順序進行介紹。首先介紹Elevator的運行規(guī)則：1）當Elevator無人且無人等待此電梯時，電梯自動回到第1層。當電梯在第一無任何需要時，電梯自動進入就緒態(tài)，讓別的線程運行。2）當電梯運行的方向上還有人等待進入電梯（不分進入的方向）時，電梯繼續(xù)運行，直到電梯運行的方向上沒有人要進入（或電梯滿人）和退出為止，電梯改變方向。3）電梯先出后進，且進來的人必須全都完成RequsetFloor（）之后電梯才能關門。4）當有多個電梯

16、時，用GetClosestElevator（）函數(shù)來選擇一個最近的電梯。計算遠近時，假設此時電梯都按自己的方向運行到底之后才轉變方向來確定電梯到達此樓需跨過多少樓層來當做距離。函數(shù)介紹：電梯循環(huán)運行的Run()函數(shù)：voidElevator:Run()/run函數(shù)是elevator線程不斷運行的循環(huán)函數(shù)intdestFloor;while(true)destFloor=FindNextDest();/找到電梯下次進入的樓層if(destFloor=0)/此時表示電梯無動作dir=still;currentThread-Yield();continue;/確定電梯運行方向if(currentFl

17、oordestFloor)dir=down;chooseLock-Acquire();if(currentFloor!=destFloor)inttime=destFloor-currentFloor;time=time0?time:-time;alarmClock-Pause(time*100);VisitFloor(destFloor);chooseLock-Release();OpenDoors();CloseDoors();if(dir=still&IsElevatorOccupy()/處理電梯處于第一層的特殊情況dir=up;voidElevator:OpenDoors()voidE

18、levator:CloseDoors()exitBarriercurrentFloor.Signal();lock-Acquire();/先讓里面的人出去/再讓外面的人進來if(calledDir=up)enterBarrierUpcurrentFloor.Signal();closingBarriercurrentFloor.Wait(lock);lock-Release();elseif(calledDir=down)/此處的Barrier不是，此處Wait的功能是：只有進入電梯中的人都要求了要enterBarrierDowncurrentFloor.Signal();去的樓層后電梯才將門

19、關上boolElevator:Enter()voidElevator:RequestFloor(intfloor)窮lock-Acquire();/capacity表示電梯容量,0為無if(occupancy=capacity&capacity!=0)lock-Acquire();ASSERT(currentFloor!=floor)lock-Release();/電梯人滿if(calledDir=up)inWaiterUpcurrentFloor-;enterBarrierUpcurrentFloorplete();closingBarriercurrentFloor.SwitchOn();

20、/當所有調用AddSwitch函數(shù)再調用/SwitchOn()之后電梯便能。outWaiterfloor+;elseif(calledDir=down)inWaiterDowncurrentFloor-;exitBarrierfloor.Wait(lock);lock-Release();enterBarrierDowncurrentFloorplete();/因為rider函數(shù)循環(huán)會將其再次加入等待的隊列/所以即使沒有進入也要更新一次信息,調用completereturnfalse;occupancy+;lock-Release();closingBarriercurrentFloor.Ad

21、dSwitch();/AddSwitch必須所有運行過的線程都完成voidElevator:Exit()occupancy-;outWaitercurrentFloor-;exitBarriercurrentFloorplete();/RequestFloor的動作后，elevator才能CloseDoorif(calledDir=up)inWaiterUpcurrentFloor-;enterBarrierUpcurrentFloorplete();elseif(calledDir=down)inWaiterDowncurrentFloor-;enterBarrierDowncurrentF

22、loorplete();Elevator*Building:AwaitUp(intfromFloor)voidBuilding:CallUp(intfromFloor)Elevator*e;Elevator*e;if(elevatorNum=1)if(elevatorNum=1)e=elevator;e=elevator;e-globalLock-Acquire();e-ReciveCall(fromFloor,up);return;e-enterBarrierUpfromFloor.Wait(e-globalLock);e-globalLock-Release();returne;choos

23、eLock-Acquire();/在選擇電梯時,電梯不能移動e=GetClosestElevator(fromFloor,up);e-chooser+;chooseLock-Release();e-globalLock-Acquire();e-ReciveCall(fromFloor,up);e-enterBarrierUpfromFloor.Wait(e-globalLock);e-globalLock-Release();returne;測試結果：1.無容量限制的電梯，building有3層，共7個人測試結果如下每個人的開始層數(shù)和目的層數(shù)都是隨機的。結果正確2.1個電梯，容量為3，building有10層，共4個人。每個人一開始都在第三層等待。結果截圖如下。除此實驗外。還運行了多次building有3層，共10個人的測試程序（截圖太長），結果正確。四個人都從第3層出發(fā)，電梯容量為3Ri