買專利賣專利找龍圖騰，真高效！ 查專利查商標(biāo)用IPTOP,全免費(fèi)！專利年費(fèi)監(jiān)控用IP管家,真方便！

龍圖騰網(wǎng)獲悉大連理工大學(xué)申請(qǐng)的專利一種基于DAG的啟發(fā)式任務(wù)調(diào)度方法獲國(guó)家發(fā)明授權(quán)專利權(quán)，本發(fā)明授權(quán)專利權(quán)由國(guó)家知識(shí)產(chǎn)權(quán)局授予，授權(quán)公告號(hào)為：CN115686795B 。

龍圖騰網(wǎng)通過國(guó)家知識(shí)產(chǎn)權(quán)局官網(wǎng)在2025-08-08發(fā)布的發(fā)明授權(quán)授權(quán)公告中獲悉：該發(fā)明授權(quán)的專利申請(qǐng)?zhí)?專利號(hào)為：202211424686.8，技術(shù)領(lǐng)域涉及：G06F9/48；該發(fā)明授權(quán)一種基于DAG的啟發(fā)式任務(wù)調(diào)度方法是由孫振宇;孟亞坤;孫景昊;王繼偉;章宇;王英霖;鄭浩然;畢冉設(shè)計(jì)研發(fā)完成，并于2022-11-14向國(guó)家知識(shí)產(chǎn)權(quán)局提交的專利申請(qǐng)。

本一種基于DAG的啟發(fā)式任務(wù)調(diào)度方法在說明書摘要公布了：本發(fā)明屬于實(shí)時(shí)嵌入式系統(tǒng)技術(shù)領(lǐng)域，具體涉及一種基于DAG的啟發(fā)式任務(wù)調(diào)度方法。本發(fā)明將DAG的節(jié)點(diǎn)劃分為幾個(gè)子集，然后對(duì)每個(gè)節(jié)點(diǎn)子集進(jìn)行調(diào)度，并將所有節(jié)點(diǎn)子集的調(diào)度合并為針對(duì)整個(gè)DAG上所有任務(wù)節(jié)點(diǎn)的調(diào)度。該方法可以在具有DAG結(jié)構(gòu)的嵌入式系統(tǒng)設(shè)計(jì)的編譯階段對(duì)系統(tǒng)完成靜態(tài)調(diào)度。通過使用本發(fā)明提出的DAG上任務(wù)的調(diào)度方法，相對(duì)于經(jīng)典的Graham列表調(diào)度算法有效降低了系統(tǒng)的平均響應(yīng)時(shí)間，可以使計(jì)算資源有限的嵌入式系統(tǒng)提高單位時(shí)間內(nèi)完成的任務(wù)數(shù)量并且用盡可能少的運(yùn)行內(nèi)核數(shù)量完成任務(wù)，從而避免資源浪費(fèi)。

本發(fā)明授權(quán)一種基于DAG的啟發(fā)式任務(wù)調(diào)度方法在權(quán)利要求書中公布了：1.一種基于DAG的啟發(fā)式任務(wù)調(diào)度方法，其特征在于，步驟如下： 步驟一：確定系統(tǒng)的DAG模型 將實(shí)時(shí)系統(tǒng)或嵌入式系統(tǒng)上的實(shí)時(shí)任務(wù)建模為DAGG＝V,E，其中V是節(jié)點(diǎn)的集合，E是邊的集合；V中的每個(gè)節(jié)點(diǎn)vi表示一段連續(xù)的執(zhí)行代碼，并且具有執(zhí)行時(shí)間ei；每條邊vi,vj∈E表示節(jié)點(diǎn)vi和vj之間的優(yōu)先關(guān)系，vi是vj的前驅(qū)節(jié)點(diǎn)，vj是vi的后繼節(jié)點(diǎn)；如果vi是vj的前驅(qū)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，則稱節(jié)點(diǎn)vi是vj的祖先節(jié)點(diǎn)，稱vj是vi的后裔節(jié)點(diǎn)；； 步驟二：將DAG中的節(jié)點(diǎn)劃分為若干個(gè)節(jié)點(diǎn)子集 將DAGG的節(jié)點(diǎn)集V劃分為幾個(gè)子集，節(jié)點(diǎn)劃分表示為PV＝{V1,V2,...,Vl}，其中Vl＝kk＝1,...,l表示PV的第k個(gè)子集；通過在G中找到路徑序列集合來求解節(jié)點(diǎn)劃分PV，其中路徑序列集合記為Π＝{π1,π2,...,πl(wèi)}，使得Π的路徑覆蓋V中的所有節(jié)點(diǎn)，即并且Π的每個(gè)路徑πk包含至少一個(gè)不屬于{π1,...,πk-1}中的路徑的節(jié)點(diǎn)，即 步驟三：對(duì)各個(gè)節(jié)點(diǎn)子集分別進(jìn)行調(diào)度并整合為對(duì)整個(gè)DAG的調(diào)度 串行調(diào)度PV的節(jié)點(diǎn)子集；首先，將每個(gè)節(jié)點(diǎn)vi的開始時(shí)間bi和結(jié)束時(shí)間fi分別初始化為+∞和0；然后，將PV的子集從V1到Vl逐一進(jìn)行調(diào)度；對(duì)于每個(gè)子集Vk，假設(shè)Vk中的節(jié)點(diǎn)是按照優(yōu)先順序排序的，即對(duì)于Vk中的任意節(jié)點(diǎn)vi和vj，如果vi是vj的祖先節(jié)點(diǎn)，則ij； 依次對(duì)節(jié)點(diǎn)集Vk中的每一個(gè)節(jié)點(diǎn)vi的調(diào)度包括：計(jì)算可用的時(shí)間區(qū)間、核的分配以及重調(diào)度進(jìn)程，具體為：首先，計(jì)算節(jié)點(diǎn)vi可以執(zhí)行的可用時(shí)間間隔[ta,tb；然后，如果有足夠的核資源在可用時(shí)間間隔[ta,tb內(nèi)執(zhí)行vi，就將核分配給vi，并決定節(jié)點(diǎn)vi執(zhí)行的時(shí)間段；否則，通過重新安排vi的后裔節(jié)點(diǎn)來延長(zhǎng)可用時(shí)間間隔，并在延長(zhǎng)的可用時(shí)間間隔內(nèi)調(diào)度vi； 最終PV中的節(jié)點(diǎn)子集按下標(biāo)順序串行調(diào)度即為整個(gè)DAG的調(diào)度。

如需購(gòu)買、轉(zhuǎn)讓、實(shí)施、許可或投資類似專利技術(shù)，可聯(lián)系本專利的申請(qǐng)人或?qū)＠麢?quán)人大連理工大學(xué)，其通訊地址為：116024 遼寧省大連市甘井子區(qū)凌工路2號(hào)；或者聯(lián)系龍圖騰網(wǎng)官方客服，聯(lián)系龍圖騰網(wǎng)可撥打電話0551-65771310或微信搜索“龍圖騰網(wǎng)”。