操作系統(tǒng)課程設(shè)計報告優(yōu)先級捐贈Priority-Scheduling-Task-2

西安電子科技大學操作系統(tǒng)課程設(shè)計(2016年度)實驗報告實驗名稱：Priority-Scheduling-Task2班級：1403018姓名：張可心學號/p>

一、實驗內(nèi)容操作系統(tǒng)中存在優(yōu)先級反轉(zhuǎn)問題——當一個高優(yōu)先級線程通過信號量機制訪問共享資源時，該信號量已被一低優(yōu)先級任務(wù)占有，而這個低優(yōu)先級任務(wù)在訪問共享資源時，可能又被其他一些中等優(yōu)先級任務(wù)搶先，因此造成高優(yōu)先級任務(wù)被許多低優(yōu)先級任務(wù)阻塞，實時性難以保證。我們的任務(wù)是：解決由鎖（Lock）造成的優(yōu)先級反轉(zhuǎn)問題，解決策略是優(yōu)先級捐贈。二、分析及設(shè)計優(yōu)先級繼承(Priorityinheritance)簡單捐贈如圖所示：簡單捐贈三個線程的執(zhí)行順序是：H—>M—>L。執(zhí)行過程如下：首先H，M等待時間發(fā)生，處于掛起狀態(tài)，L運行，持有鎖A，M等待的時間發(fā)生，就緒，搶占CPU；H等待的時間發(fā)生，就緒，搶占CPU，并等待鎖A；由于A已被L獲得，H掛起，并將優(yōu)先級捐贈給L，L的優(yōu)先級提升，開始運行，并釋放所A，同時恢復原始優(yōu)先級，H被喚醒，運行，然后M運行，L運行。遞歸捐贈如圖所示：遞歸捐贈發(fā)生時各優(yōu)先級的執(zhí)行順序是：H—>M—>L。執(zhí)行過程如下：H、M等待時間發(fā)生，處于掛起狀態(tài)，L運行，持有鎖A，M等待的事件到達，就緒，搶占CPU，請求鎖B成功，并繼續(xù)請求鎖A，由于A已被L持有，M掛起，并捐贈自己的優(yōu)先級32給L，L的優(yōu)先級獲得提升，開始執(zhí)行，H等待的事件到達，就緒，搶占CPU，并請求鎖B，由于B被M持有，H掛起，并捐贈給自己的優(yōu)先級33給M，由于M因L而被阻塞，故優(yōu)先級33也捐贈給L，L的優(yōu)先級再次得到提升，開始運行，L釋放鎖A，M被喚醒，L的優(yōu)先級恢復到31，M開始執(zhí)行，釋放鎖B，H被喚醒，M的優(yōu)先級恢復到32，H運行，M運行，L運行。（3）多重捐贈如圖所示，當多重捐贈發(fā)生時，三個優(yōu)先級的執(zhí)行順序是：H—>M—>L。執(zhí)行過程如下：H、M等待的事件發(fā)生，處于掛起狀態(tài)，L運行，并先后持有鎖A和B，M等待的事件發(fā)生，就緒，搶占CPU，并請求鎖A，由于A被L占有，故M掛起，并將優(yōu)先級32捐贈給L，L運行，H等待的時間發(fā)生，就緒，搶占CPU，并請求鎖B，由于B已被L占有，H掛起，并捐獻優(yōu)先級33給L，L優(yōu)先級得到提升，運行，先后釋放A、B，L的優(yōu)先級恢復到31，H被喚醒，運行，M運行，L運行。具體分析：要實現(xiàn)優(yōu)先級捐贈問題，首先需要考慮保存原優(yōu)先級的問題，因此需要定義一個包含原先優(yōu)先級和被捐贈時捐贈者需要什么鎖兩個成員的結(jié)構(gòu)pri_stack，并在thread結(jié)構(gòu)體中加入類型為structpri_stack的成員，考慮到多重捐贈的情況，該成員是棧結(jié)構(gòu)。之后，再在thread結(jié)構(gòu)體中加入block_sema、block_lock兩個成員，分別記錄被哪個信號量阻塞、在等待哪個lock。在這之后，還需修改init_thread()函數(shù)，使其在初始化時同時初始化這些新加入的成員。在調(diào)用thread_set_priority()時，為了保證線程在捐贈完畢時其優(yōu)先級回到新的優(yōu)先級，在該函數(shù)中加入對線程是否被捐贈過的判斷，若是，只修改棧底存儲的優(yōu)先級；否則，修改線程當前優(yōu)先級，并執(zhí)行第二次實驗中加入的當前優(yōu)先級確認。在PV操作中，當調(diào)用P操作時，若此時該信號量為0，應(yīng)在線程的block_sema成員中記錄當前被哪個信號量阻塞；當調(diào)用V操作時，需在調(diào)用thread_unblock()后置空線程的block_sema。在鎖的acquire和release操作中，當線程發(fā)起對鎖的索取時，需先判斷該鎖對應(yīng)的信號量是否為0，若是，則說明已被占用，這時應(yīng)在線程的block_lock成員中保存阻塞該線程的鎖，并調(diào)用優(yōu)先級捐贈函數(shù)。而在釋放鎖的時候，如果該線程被捐贈過，會出現(xiàn)三種情況：該鎖在線程被捐贈棧的棧頂，則還原優(yōu)先級，刪除記錄；該鎖既不在棧頂也不在棧底，直接刪除記錄；該鎖在棧底，將棧底優(yōu)先級賦值給其上一層后，刪除記錄。而在實現(xiàn)優(yōu)先級捐贈函數(shù)時，我們還需要考慮被捐贈者是否在ready_list中，若是，需調(diào)整其在ready_list中的位置。同時，我們還需考慮被捐贈者是否在block_list中，若是，且被捐贈者也被某個鎖阻塞，此時調(diào)整其在信號量等待隊列中的位置，并觸發(fā)遞歸捐贈。三、詳細實現(xiàn)首先在文件thread.h中的structthread的結(jié)構(gòu)體中添加三個變量在文件thread.h中添加結(jié)構(gòu)體structdthread然后在文件thread.c的init_thread()函數(shù)中添加初始化代碼4、在thread_set_priority()函數(shù)中添加代碼在synch.c文件的lock_acquire()函數(shù)中添加代碼然后在lock_release()函數(shù)中添加代碼添加中有一個thread_prisort()函數(shù)，定義在thread.c文件中四、實驗結(jié)果在修改完成后，調(diào)用makecheck命令對../threads子目錄進行任務(wù)檢查，結(jié)果滿足題目要求。五、心得體會本次實驗內(nèi)容為優(yōu)先級反轉(zhuǎn)問題，我采用