實驗四：Priority Scheduling—Donation for Locks

一、實驗目的
解決由lock造成的優(yōu)先級反轉問題。

二、實驗方案
使用優(yōu)先級捐贈（Priority Donation）來解決由lock造成的優(yōu)先級反轉問題。
優(yōu)先級捐贈是指高優(yōu)先級的線程將自身優(yōu)先級捐給與其競爭資源的低優(yōu)先級線程，以促使其盡快釋放資源，進而保證自身能盡快得到運行所需資源的策略。
優(yōu)先級捐贈主要分以下幾種情況：
1.簡單捐贈，這是最為平常和簡單的一種捐贈情況。lock、優(yōu)先級流動及線程執(zhí)行時間順序如下圖所示：

2.遞歸捐贈，這是一種較為復雜的情況。lock、優(yōu)先級流動及線程執(zhí)行時間順序如下圖所示：

3.多重捐贈，這種情況也較為復雜。lock、優(yōu)先級流動及線程執(zhí)行時間順序如下圖所示：
三、詳細實現(xiàn)

修改數(shù)據(jù)結構
(1) 修改thread結構體，新增三個量，一個base_priority記錄線程的初始優(yōu)先級，一個locks記錄線程當前擁有的鎖（多個），一個lock_waiting用來記錄線程等待被釋放的鎖。
(2) 修改lock結構體，新增兩個量，一個elem記錄優(yōu)先級捐贈的列表元素，一個max_priority記錄請求鎖的所有線程的最大優(yōu)先級。

修改函數(shù)
(1) 修改init_thread()函數(shù)，實現(xiàn)對thread結構體中新增變量base_priority和lock_waiting的初始化。
(2) 修改lock_acquire()函數(shù)，在獲取鎖之前循環(huán)更新所有參與嵌套的線程的優(yōu)先級，即在P操作之前解決遞歸捐贈的情況。然后在線程被喚醒之后讓該線程持有該鎖。
(3) 定義函數(shù)thread_hold_the_lock實現(xiàn)將一個鎖資源賦給線程。
(4) 定義函數(shù)thread_donate_priority實現(xiàn)較高優(yōu)先級線程將優(yōu)先級捐贈給某一持有鎖的較低優(yōu)先級的線程。這里的優(yōu)先級捐贈是通過修改鎖的最高優(yōu)先級， 然后調用thread_update_priority ()更新被捐贈線程的當前優(yōu)先級實現(xiàn)的。
(5) 定義函數(shù)thread_update_priority ()實現(xiàn)線程優(yōu)先級的更新。該函數(shù)一方面被thread_donate_priority()函數(shù)調用以實現(xiàn)優(yōu)先級捐贈操作，另一方面考慮到當某線程釋放鎖之后，該線程的優(yōu)先級可能發(fā)生變化，可用thread_update_priority()函數(shù)來處理這個邏輯。
(6) 定義函數(shù)lock_cmp_priority()實現(xiàn)鎖隊列的排序。
(7) 定義函數(shù)thread_remove_lock()實現(xiàn)線程釋放鎖時進行的操作，該函數(shù)將被synch.c中的lock_release()函數(shù)調用。
(8) 在lock_release()函數(shù)中添加相應的語句調用(6)中的thread_remove_lock()函數(shù)。
(9) 在lock_release()函數(shù)中添加相應的語句調用(6)中的thread_remove_lock()函數(shù)。
(10) 修改thread_set_priority()函數(shù)。如果沒有鎖，那么優(yōu)先級捐贈的情況不用考慮，直接更新；如果更新的優(yōu)先級大于當前線程的優(yōu)先級，則更新當前線程優(yōu)先級?？傊?#xff0c;base_priority一定要在該函數(shù)中得到更新。
(11) 修改sema_up()和seme_down()函數(shù)，將信號量的wait_list實現(xiàn)為優(yōu)先級隊列，即將wait_list中的線程按優(yōu)先級降序排列，該過程在實驗三中已經(jīng)完成過一遍。
(12) 定義cond_sema_cmp_priority()函數(shù)實現(xiàn)條件變量wait_list中線程的優(yōu)先級比較，便于(12)中使用該函數(shù)作為list_sort()排序函數(shù)的參數(shù)。
(13) 修改 cond_signal()函數(shù)，將條件變量的wait_list也改成優(yōu)先級隊列，其中l(wèi)ist_sort()排序函數(shù)使用(11)中的定義的比較函數(shù)作為參數(shù)。
四、實驗結果

總結

以上是生活随笔為你收集整理的西电Pintos操作系统课程设计 实验四的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。