[發(fā)明專利]一種基于linux實(shí)時(shí)操作系統(tǒng)的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法

在審

• 申請(qǐng)?zhí)枺?/td>: 201710694888.7
• 申請(qǐng)日: 2017-08-15
• 公開(kāi)（公告）號(hào): CN107589993A
• 公開(kāi)（公告）日: 2018-01-16
• 發(fā)明（設(shè)計(jì)）人: 方雪靜
• 申請(qǐng)（專利權(quán)）人: 鄭州云海信息技術(shù)有限公司
• 主分類號(hào): G06F9/50
• 分類號(hào): G06F9/50
• 代理公司: 濟(jì)南舜源專利事務(wù)所有限公司37205
• 代理人: 張亮

技術(shù)領(lǐng)域

本發(fā)明屬于實(shí)時(shí)操作系統(tǒng)技術(shù)領(lǐng)域，具體涉及一種基于linux實(shí)時(shí)操作系統(tǒng)的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法。

背景技術(shù)

在眾多的實(shí)時(shí)操作系統(tǒng)中，基于Linux的實(shí)時(shí)操作系統(tǒng)，由于開(kāi)放源代碼，以及Linux系統(tǒng)的穩(wěn)定性，日益受到人們的歡迎。但Linux本身并不是真正的實(shí)時(shí)操作系統(tǒng)，必須通過(guò)對(duì)Linux操作系統(tǒng)作相應(yīng)的改進(jìn)，提高它的實(shí)時(shí)性，使之具有滿足實(shí)時(shí)系統(tǒng)要求的實(shí)時(shí)性和可靠性。

實(shí)時(shí)系統(tǒng)的行為正確性不僅取決于結(jié)算結(jié)果的正確性，還取決于得到這個(gè)結(jié)果所花費(fèi)的時(shí)間。實(shí)時(shí)系統(tǒng)的基本特性是任務(wù)響應(yīng)時(shí)間的確定性和系統(tǒng)處理任務(wù)的高吞吐量。實(shí)時(shí)系統(tǒng)的應(yīng)用領(lǐng)域十分廣泛，不同的應(yīng)用對(duì)時(shí)間確定性的要求也不同。除了必須具備響應(yīng)時(shí)間確定性以外，實(shí)時(shí)系統(tǒng)其它的重要特性包括并發(fā)性、可預(yù)測(cè)性和可靠性。并發(fā)性是指實(shí)時(shí)系統(tǒng)必須能夠在規(guī)定時(shí)段內(nèi)處理多個(gè)外部輸入。可預(yù)測(cè)性實(shí)質(zhì)上是對(duì)響應(yīng)時(shí)間確定性的保證。外部輸入的本質(zhì)是并發(fā)和隨機(jī)分布，每一個(gè)輸入觸發(fā)實(shí)時(shí)系統(tǒng)產(chǎn)生相應(yīng)的動(dòng)作，而這些動(dòng)作的流程、所需的處理器時(shí)間是可預(yù)知的。只有在這種情況下才能保證響應(yīng)時(shí)間的確定性。

實(shí)時(shí)調(diào)度算法是實(shí)時(shí)系統(tǒng)解決并發(fā)和保證可預(yù)測(cè)性的基本手段。實(shí)時(shí)調(diào)度算法根據(jù)調(diào)度策略為并發(fā)的外部輸入確定處理順序，并按照該順序?yàn)槊恳粋€(gè)處理操作分配系統(tǒng)資源。實(shí)時(shí)調(diào)度算法的另一個(gè)主要功能是根據(jù)可調(diào)度條件確定系統(tǒng)現(xiàn)有資源是否滿足處理操作的時(shí)間確定性。與通用調(diào)度算法不同，實(shí)時(shí)調(diào)度算法首先保證所有就緒處理操作均能在規(guī)定時(shí)限前結(jié)束，其次才是盡可能多地處理外部事件以提高系統(tǒng)的資源利用率。如何在保證時(shí)間確定性的前提下提高系統(tǒng)資源利用率是實(shí)時(shí)調(diào)度算法研究的熱點(diǎn)問(wèn)題。

經(jīng)典的EDF(Earliest Deadline First)算法是一種基于優(yōu)先級(jí)的動(dòng)態(tài)調(diào)度算法，這種算法雖然能夠保證在出現(xiàn)某個(gè)任務(wù)的最終期限不能滿足之前，不存在處理器的空閑時(shí)間，從而盡可能的保證任務(wù)調(diào)度的實(shí)時(shí)性，理論上可對(duì)可調(diào)度負(fù)載進(jìn)行優(yōu)化，但它不能解決過(guò)載問(wèn)題。一旦發(fā)生過(guò)載，就會(huì)導(dǎo)致CPU將大量時(shí)間花費(fèi)在調(diào)度上，導(dǎo)致性能迅速退化。

另外，EDF調(diào)度算法采用的是非搶占式的調(diào)度策略，在內(nèi)核分配給實(shí)時(shí)任務(wù)的時(shí)間片內(nèi)，實(shí)時(shí)任務(wù)在執(zhí)行時(shí)間到來(lái)之前就能完成了任務(wù)。這樣，在空余的時(shí)間片內(nèi)別的任務(wù)是不可以搶占內(nèi)核，CPU在這一段的空閑時(shí)間內(nèi)有可能是空閑的，這就會(huì)造成了實(shí)時(shí)任務(wù)的延誤。另一方面一個(gè)實(shí)時(shí)任務(wù)超出任務(wù)執(zhí)行時(shí)間后，任務(wù)并沒(méi)有完成，則在下一周期內(nèi)以當(dāng)前的最高優(yōu)先級(jí)繼續(xù)搶占內(nèi)核，會(huì)造成了后續(xù)的實(shí)時(shí)任務(wù)執(zhí)行時(shí)間的順延，由此形成的“多米諾骨牌”效應(yīng)會(huì)使多個(gè)進(jìn)程超出任務(wù)最后截止時(shí)間，而導(dǎo)致任務(wù)系統(tǒng)的崩潰。

針對(duì)以上問(wèn)題的出現(xiàn)，Lin和Brandt基于ISM思想，提出了SLAD(SLACK Donation)算法和BACKSLASH(BACK SLACK Donation)算法。ISM的思路是將實(shí)時(shí)任務(wù)分別分配到幾個(gè)同級(jí)別服務(wù)級(jí)，各個(gè)服務(wù)按照一定比例分配CPU，如果某個(gè)服務(wù)上的實(shí)時(shí)任務(wù)超限繼續(xù)運(yùn)行下去，則占用該服務(wù)的CPU，并順延該服務(wù)上的其它實(shí)時(shí)任務(wù)。這種策略不考慮任務(wù)間的影響，對(duì)減小截止期錯(cuò)失率DMR(deadline miss ratio)有一定效果。

雖然SLAD和BACKSLASH算法可以讓一個(gè)超預(yù)算的任務(wù)更好的動(dòng)態(tài)分配剩余時(shí)間和在處理從下一個(gè)周期借入時(shí)間片，這樣就能解決系統(tǒng)的實(shí)時(shí)任務(wù)(超限)overrun問(wèn)題。但是由于對(duì)時(shí)限任務(wù)有一個(gè)預(yù)先的判斷，以便決定是否采用動(dòng)態(tài)分配剩余時(shí)間和在處理從下一個(gè)周期借入時(shí)間片。這樣就會(huì)占用處理器的資源，當(dāng)不是頻繁出現(xiàn)實(shí)時(shí)任務(wù)超限的情況時(shí)；這種調(diào)度是效率不高的。

由以上可知，上述兩種類型算法單獨(dú)應(yīng)用于Linux實(shí)時(shí)操作系統(tǒng)中時(shí)，均無(wú)法滿足實(shí)時(shí)系統(tǒng)要求的實(shí)時(shí)性和可靠性的要求。此為現(xiàn)有技術(shù)中的不足之處。

發(fā)明內(nèi)容

本發(fā)明的目的在于，針對(duì)上述現(xiàn)有技術(shù)存在的問(wèn)題，提出一種基于linux實(shí)時(shí)操作系統(tǒng)的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，以解決上述技術(shù)問(wèn)題。

為了達(dá)到上述目的，本發(fā)明的技術(shù)方案是：

一種基于linux實(shí)時(shí)操作系統(tǒng)的動(dòng)態(tài)優(yōu)先級(jí)調(diào)度算法，包括以下步驟：

實(shí)時(shí)任務(wù)加入任務(wù)隊(duì)列時(shí)，更新當(dāng)前的釋放時(shí)間并獲取當(dāng)前任務(wù)的狀態(tài)，實(shí)時(shí)任務(wù)進(jìn)入緩存記憶模塊；

當(dāng)實(shí)時(shí)任務(wù)超限時(shí)，調(diào)用SLAD或BACKSLASH算法，并在緩存記憶模塊中計(jì)數(shù)；否則調(diào)用EDF算法，并在緩存記憶模塊中計(jì)數(shù)；