課件操作系統(tǒng)處理機(jī)調(diào)度ppt課件-資料下載頁
2025-05-03 18:16本頁面
【正文】 期 限A4最 后 期 限A5最 后 期 限到 達(dá) 時(shí) 間 、 執(zhí) 行 時(shí) 間和 最 后 期 限A1固 定 優(yōu) 先 級(jí) 調(diào) 度固 定 優(yōu) 先 級(jí) 調(diào) 度A2 B1 A3 A4 A5 ， B2A5 ， B2A4A1( 錯(cuò)過 )A2 B1 A3( 錯(cuò)過 )A1 A2 B1( 錯(cuò)過 )A3 A4 A5 ， B20 10 20 30 40 50 60 70 80 90 1 0 0 時(shí)間 t / ms使 用 完 成 最 后 期 限最 早 和 最 后 期 限 調(diào) 度(A 有 較 高 優(yōu) 先 級(jí) )(B 有 較 高 優(yōu) 先 級(jí) )第三章 處理機(jī)調(diào)度與死鎖 為了說明通常的優(yōu)先級(jí)調(diào)度不能適用于實(shí)時(shí)系統(tǒng) ， 該圖特增加了第二和第三行 。 第二行中假定任務(wù) A具有較高的優(yōu)先級(jí) ， 所以在 t=0 ms時(shí) ， 先調(diào)度 A1執(zhí)行 ， 在 A1完成后 (t = 10 ms)才調(diào)度 B1執(zhí)行；在 t = 20 ms時(shí) ， 調(diào)度 A2執(zhí)行；在 t = 30 ms時(shí) ， A2完成 ， 又調(diào)度 B1執(zhí)行；在 t = 40 ms時(shí) ， 調(diào)度 A3執(zhí)行；在 t = 50 ms時(shí) ， 雖然 A3已完成 ， 但 B1已錯(cuò)過了它的最后期限 ， 這說明了利用通常的優(yōu)先級(jí)調(diào)度已經(jīng)失敗 。 第三行與第二行類似 ， 只是假定任務(wù) B具有較高的優(yōu)先級(jí) 。 第三章 處理機(jī)調(diào)度與死鎖 第四行是采用最早截止時(shí)間優(yōu)先算法的時(shí)間圖。 在 t = 0時(shí)， A1和 B1同時(shí)到達(dá)，由于 A1的截止時(shí)間比 B1早，故調(diào)度 A1執(zhí)行；在 t = 10時(shí)， A1完成，又調(diào)度 B1執(zhí)行；在 t = 20時(shí)， A2到達(dá)，由于 A2的截止時(shí)間比 B2早， B1被中斷而調(diào)度 A2執(zhí)行；在 t = 30時(shí)， A2完成，又重新調(diào)度 B1執(zhí)行；在 t = 40時(shí)， A3又到達(dá)，但 B1的截止時(shí)間要比 A3早，仍應(yīng)讓 B1繼續(xù)執(zhí)行直到完成 (t = 45)，然后再調(diào)度 A3執(zhí)行；在 t = 55時(shí)，A3完成，又調(diào)度 B2執(zhí)行。 在該例中利用最早截止時(shí)間優(yōu)先算法可以滿足系統(tǒng)的要求。 第三章 處理機(jī)調(diào)度與死鎖 2. 最低松弛度優(yōu)先即 LLF(Least Laxity First)算法 該算法是根據(jù)任務(wù)緊急 (或松弛 )的程度 ， 來確定任務(wù)的優(yōu)先級(jí) 。 任務(wù)的緊急程度愈高 ， 為該任務(wù)所賦予的優(yōu)先級(jí)就愈高 ， 以使之優(yōu)先執(zhí)行 。 如下例： 松弛度＝截止時(shí)間－ （ 就緒時(shí)間＋計(jì)算時(shí)間 ） 松弛度越小說明越緊迫 ， 優(yōu)先級(jí)會(huì)越高 ， 就緒后應(yīng)該盡快執(zhí)行 。 理解：在保證進(jìn)程被調(diào)度執(zhí)行的情況下 ， 最晚應(yīng)該在什么時(shí)間得到調(diào)度 ， 才能夠保證順利完成任務(wù) 。 中間可以有多大的寬裕度 。 第三章 處理機(jī)調(diào)度與死鎖 例子： 在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性的進(jìn)程 A和 B，任務(wù) A要求每 20毫秒執(zhí)行一次，執(zhí)行時(shí)間為 10毫秒；任務(wù) B只要求每 50毫秒執(zhí)行一次，執(zhí)行時(shí)間為 25毫秒。 請(qǐng)計(jì)算 A、 B進(jìn)程的每次的調(diào)度時(shí)間。 第三章 處理機(jī)調(diào)度與死鎖 圖 38 A和 B任務(wù)每次必須完成的時(shí)間 A1A2A3A4A5A6A7A820 40 60 80 1 0 0 1 2 0 1 4 0 1 6 0B1B2B3t0依照此圖中進(jìn)程 AB必須完成的時(shí)間點(diǎn)，向前推算什么時(shí)候隊(duì)各進(jìn)程進(jìn)行調(diào)度。（允許搶占 cpu） 第三章 處理機(jī)調(diào)度與死鎖 在剛開始時(shí) (t1=0)， A1必須在 20ms時(shí)完成 ， 而它本身運(yùn)行又需 10 ms， 可算出 A1的松弛度為 10ms； B1必須在 50ms時(shí)完成 ， 而它本身運(yùn)行就需 25 ms， 可算出 B1的松弛度為 25 ms， 故調(diào)度程序應(yīng)先調(diào)度 A1執(zhí)行 。 在t2=10 ms時(shí) ， A2的松弛度可按下式算出： A2的松弛度 =必須完成時(shí)間 其本身的運(yùn)行時(shí)間 當(dāng)前時(shí)間 =40 ms10 ms10 ms=20 ms 第三章 處理機(jī)調(diào)度與死鎖 B1的松弛度為 15ms， 故調(diào)度程序應(yīng)選擇 B1運(yùn)行 。 t3=30 ms， A2的松弛度已減為 0(即 401030)， 而 B1的松弛度為 15 ms(即 50530)， 于是調(diào)度程序應(yīng)搶占 B1的處理機(jī)而調(diào)度 A2運(yùn)行 。 t4=40 ms時(shí) ， A3的松弛度為 10 ms(即 601040)， 而 B1的松弛度僅為 5 ms(即 50540)， 故又應(yīng)重新調(diào)度 B1執(zhí)行 。 在 t5=45 ms時(shí) ， B1執(zhí)行完成 ， 而此時(shí) A3的松弛度已減為 5 ms(即 601045)， 而 B2的松弛度為 30 ms(即 1002545)， 于是又應(yīng)調(diào)度 A3執(zhí)行 。 第三章 處理機(jī)調(diào)度與死鎖 t6=55ms， 任務(wù) A尚未進(jìn)入第 4周期 ， 而任務(wù) B已進(jìn)入第 2周期 ， 故再調(diào)度 B2執(zhí)行 。 t7=70 ms， A4的松弛度已減至 0 ms(即 801070)，而 B2的松弛度為 20 ms(即 1001070)， 故此時(shí)調(diào)度又應(yīng)搶占 B2的處理機(jī)而調(diào)度 A4執(zhí)行 。 第三章 處理機(jī)調(diào)度與死鎖 圖 39 利用 ELLF算法進(jìn)行調(diào)度的情況 t1A1( 1 0 )10 20 30 40 50 60 80t0t1＝ 0B1( 2 0 )t2t370A2( 1 0 ) A3( 1 0 ) A4( 1 0 )t4t5t6t7t8B1( 5 ) B2( 1 5 ) B2( 1 0 )
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1