[發(fā)明專利]綜合模塊化航空電子系統(tǒng)兩級調(diào)度模型與原型平臺

有效

• 申請?zhí)枺?/td>: 201711043644.9
• 申請日: 2017-10-31
• 公開（公告）號: CN107943568B
• 公開（公告）日: 2021-11-26
• 發(fā)明（設(shè)計）人: 路輝;周乾琳;池程芝
• 申請（專利權(quán)）人: 北京航空航天大學(xué);中國航空無線電電子研究所
• 主分類號: G06F9/48
• 分類號: G06F9/48
• 代理公司: 北京永創(chuàng)新實專利事務(wù)所 11121
• 代理人: 姜榮麗

1.綜合模塊化航空電子系統(tǒng)兩級調(diào)度模型，其特征在于：所述的兩級調(diào)度模型按照進(jìn)程時間是否連續(xù)分成兩大類，如果進(jìn)程時間連續(xù)，則每個進(jìn)程在所屬分區(qū)的第一次到達(dá)時刻同時到達(dá)，之后進(jìn)程的到達(dá)時間與所有分區(qū)無關(guān)，僅與每個進(jìn)程第一次進(jìn)入就緒狀態(tài)的時間和自身的周期有關(guān)；如果進(jìn)程時間不連續(xù)，則每個分區(qū)中的進(jìn)程執(zhí)行狀態(tài)在該分區(qū)的每次時間片結(jié)束時刻重置，任一分區(qū)的每次到達(dá)時刻，其內(nèi)部的進(jìn)程都會同時重新進(jìn)入就緒狀態(tài)；對于分區(qū)調(diào)度策略，包括分區(qū)輪轉(zhuǎn)調(diào)度和新到分區(qū)優(yōu)先執(zhí)行調(diào)度，根據(jù)分區(qū)調(diào)度策略的選擇不同，所有模型分為三類組合方式，且每一類組合方式中對進(jìn)程均有最早截止期限優(yōu)先EDF調(diào)度算法、單調(diào)速率調(diào)度RMS算法供選擇，根據(jù)第三類組合方式的模型的特點，對進(jìn)程的調(diào)度策略增加了搶占閾值調(diào)度PTS算法；在所需參數(shù)輸入下，針對上述每一類組合方式的模型，采用各自優(yōu)化算法以完成未知參數(shù)的優(yōu)化，并最終產(chǎn)生合理的調(diào)度方案及調(diào)度甘特圖；

所述的三類組合方式分別為：第一類組合方式進(jìn)程時間連續(xù)，分區(qū)調(diào)度策略選擇分區(qū)輪轉(zhuǎn)調(diào)度，進(jìn)程調(diào)度策略為EDF和RMS；第二類組合方式進(jìn)程時間連續(xù)，分區(qū)調(diào)度策略選擇新到分區(qū)優(yōu)先執(zhí)行，進(jìn)程調(diào)度策略為EDF和RMS；第三類組合方式進(jìn)程時間非連續(xù)，分區(qū)調(diào)度策略選擇新到分區(qū)優(yōu)先執(zhí)行，進(jìn)程調(diào)度策略為PTS、EDF和RMS；

所述分區(qū)的基本參數(shù)包括：分區(qū)個數(shù)、每個分區(qū)的周期、每個分區(qū)的時間片長度、每個分區(qū)的初始到達(dá)時間；進(jìn)程的基本參數(shù)包括每個進(jìn)程的周期、每個進(jìn)程的最壞執(zhí)行時間、每個進(jìn)程的截止時間；在單處理器下，對第一類組合方式，根據(jù)分區(qū)及進(jìn)程的所有執(zhí)行規(guī)則，所有分區(qū)的初始執(zhí)行先后順序不影響分區(qū)及進(jìn)程集的可調(diào)度性，且在給定分區(qū)執(zhí)行順序的情況下，如果所有分區(qū)及進(jìn)程的基本參數(shù)已知，則該分區(qū)及進(jìn)程集的執(zhí)行狀態(tài)是確定的；第一類組合方式中由于分區(qū)采取了分區(qū)輪轉(zhuǎn)調(diào)度策略，根據(jù)所有分區(qū)時間片長度之和等于分區(qū)主時間框架的假設(shè)，此時由每個分區(qū)的初始到達(dá)時間可推算出每個分區(qū)的時間片長度，且分區(qū)的主時間框架等于所有分區(qū)的周期；因此，待優(yōu)化的參數(shù)僅有每個分區(qū)的初始到達(dá)時間；在多處理器模式下，完成IMA系統(tǒng)兩級調(diào)度首先需要對所有輸入分區(qū)進(jìn)行合理分組以實現(xiàn)系統(tǒng)更高的可調(diào)度性；因此，在多處理器兩級調(diào)度優(yōu)化時，輸入?yún)?shù)還應(yīng)包括處理器個數(shù)，輸出參數(shù)還應(yīng)包括分區(qū)的分組方案；

對第一類組合方式中模型在輸入每個分區(qū)中的進(jìn)程的基本參數(shù)后，則應(yīng)首先判斷當(dāng)前輸入的處理器個數(shù)，如果為多個處理器，則應(yīng)對輸入的所有分區(qū)進(jìn)行分組操作，第一類組合方式的分組算法具體如下：

1)確定分組個數(shù)，即處理器個數(shù)，每個進(jìn)程的周期和每個進(jìn)程的最壞執(zhí)行時間；根據(jù)每個分區(qū)內(nèi)部所有進(jìn)程的周期和最壞執(zhí)行時間計算出每個分區(qū)的時間片長度在主時間框架中的最小占比假設(shè)第i分區(qū)中有n個進(jìn)程，j表示第i分區(qū)中的進(jìn)程序號，R_ij和P_ij分別表示第i分區(qū)中第j個進(jìn)程的最壞執(zhí)行時間和周期；

2)將所有分區(qū)按照最小占比α_i降序排列；

3)根據(jù)待分組分區(qū)的最小占比α_i和待分組數(shù)計算每組最小占比α_i的均值

其中，sum(α_i)表示分區(qū)中所有最小占比α_i的和，num_group表示待分組數(shù)目，其初始值為處理器個數(shù)；

4)比較α₁與大小關(guān)系，如果則α₁為一組，跳轉(zhuǎn)到步驟5)；如果α₁小于則比較α₁+α₂與的關(guān)系，直到前t個分區(qū)的最小占比之和不小于此時如果則前t個分區(qū)為一組，跳轉(zhuǎn)到步驟5)，否則逐個比較與的關(guān)系，直到找到滿足的k值，如果上式任意一個等號成立，則將對應(yīng)的分區(qū)分為一組，跳轉(zhuǎn)到步驟5)，否則計算取對應(yīng)的分區(qū)分為一組，跳轉(zhuǎn)到步驟5)，如果對任意k均有則計算其中t+m等于當(dāng)前未分組的分區(qū)個數(shù)，取對應(yīng)的分區(qū)為一組，跳轉(zhuǎn)到步驟5)；

5)更新尚未分組的分區(qū)，更新α_i編號，同時將待分組的組數(shù)減1；

6)重復(fù)步驟3)～5)，直到所有分區(qū)均已分組，輸出所有分區(qū)的分組情況；

在第一類組合方式得到所有分區(qū)的分組后，需對每一組分區(qū)運(yùn)行優(yōu)化算法尋找每個分區(qū)的最優(yōu)初始到達(dá)時間；由于分區(qū)采取時間片輪轉(zhuǎn)調(diào)度策略，在一個分區(qū)周期中，所有分區(qū)按順序各執(zhí)行一次，因此，此時的優(yōu)化目標(biāo)選為組內(nèi)分區(qū)的主時間框架最大以實現(xiàn)在滿足可調(diào)度的前提下最少的分區(qū)切換；對每一組分區(qū)運(yùn)行的優(yōu)化算法的具體流程如下：

輸入：組內(nèi)每個分區(qū)時間片長度在主時間框架中的最小占比組內(nèi)每個分區(qū)中的所有進(jìn)程周期、最壞執(zhí)行時間、截止時間，算法停止閾值；

變量含義：

mtf_max分區(qū)主時間框架最大值；

mtf_min分區(qū)主時間框架最小值；

mtf_curr當(dāng)前分區(qū)主時間框架值；

threshold算法停止閾值；

rate_min當(dāng)前不可調(diào)度分區(qū)的時間片長度在當(dāng)前次循環(huán)的主時間框架中占比的最小值，其與每個分區(qū)在主時間框架中的最小占比不同，該變量在偽碼中作為中間變量而存在，用不可調(diào)度分區(qū)的α_i進(jìn)行初始化；

rate_max當(dāng)前不可調(diào)度分區(qū)的時間片長度在當(dāng)前次循環(huán)的主時間框架中占比的最大值；

rate_curr當(dāng)前不可調(diào)度分區(qū)的時間片長度在當(dāng)前次循環(huán)的主時間框架中占比；

(1)初始化分區(qū)主時間框架上下界值分別為所有分區(qū)中所有進(jìn)程的周期最大值和0；

(2)當(dāng)mtf_min+thresholdmtf_max；

初始化mtf_curr為mtf_min和mtf_max的均值，并根據(jù)當(dāng)前mtf_curr以及每個分區(qū)在mtf_curr中的最小占比計算出此時每個分區(qū)的時間片長度，根據(jù)此時間片長度計算每個分區(qū)的初始到達(dá)時間，結(jié)合進(jìn)程基本參數(shù)計算此時分區(qū)和進(jìn)程集的可調(diào)度性，如不可調(diào)度則返回不可調(diào)度的分區(qū)號進(jìn)入步驟(3)，如可調(diào)度則用每個分區(qū)的時間片長度在主時間框架中的最小占比重新初始化當(dāng)前各分區(qū)時間片長度在主時間框架中占比，同時將mtf_curr的值賦給mtf_min，同時再次執(zhí)行步驟(2)；

(3)當(dāng)存在分區(qū)不可調(diào)度，假設(shè)為分區(qū)1；將當(dāng)前主時間框架中剩余的空閑占比全部分配給不可調(diào)度的分區(qū)1，此時分區(qū)1的占比為rate_max，判斷系統(tǒng)的可調(diào)度性；此時分為三種情況：第一種情況，如果此時分區(qū)和進(jìn)程集依然不可調(diào)度且此時不可調(diào)度的依然是同一個分區(qū)，則用每個分區(qū)時間片長度在主時間框架中的最小占比重新初始化當(dāng)前各分區(qū)時間片長度在主時間框架中占比，同時將mtf_curr的值賦給mtf_max，返回執(zhí)行步驟(2)；第二種情況，如果此時分區(qū)和進(jìn)程集完全可調(diào)度，則用每個分區(qū)時間片長度在主時間框架中的最小占比重新初始化當(dāng)前各分區(qū)時間片長度在主時間框架中占比，同時將mtf_curr的值賦給mtf_min，返回執(zhí)行步驟(2)；第三種情況，如果此時分區(qū)和進(jìn)程集依然不可調(diào)度但引起不可調(diào)度的分區(qū)不是分區(qū)1，則執(zhí)行步驟(4)；

(4)當(dāng)rate_min+threshold/mtf_currrate_max，由于步驟(3)中假設(shè)不可調(diào)度的分區(qū)是分區(qū)1，此處rate_min以及rate_max均是對于分區(qū)1而言；

初始化rate_curr為rate_min和rate_max的均值，計算此時所有分區(qū)的時間片長度并計算分區(qū)和進(jìn)程集的可調(diào)度性；此時存在兩種情況：第一種情況，如果此時分區(qū)和進(jìn)程集不可調(diào)度，且不可調(diào)度的分區(qū)依然是分區(qū)1，則將rate_curr的值賦給rate_min，同時再次執(zhí)行步驟(4)；第二種情況，如果此時系統(tǒng)不可調(diào)度但不可調(diào)度的分區(qū)不再是分區(qū)1，則將rate_curr的值賦給rate_max，同時再次執(zhí)行步驟(4)；

(5)更新此時分區(qū)主時間框架中剩余的空閑占比；如果此時所有分區(qū)均可調(diào)度，則返回執(zhí)行步驟(2)，否則返回步驟(3)；

經(jīng)過上述優(yōu)化算法之后，最終得出滿足分區(qū)和進(jìn)程集可調(diào)度的分區(qū)主時間框架以及每個分區(qū)時間片長度在該主時間框架中的占比，進(jìn)一步計算出每個分區(qū)的時間片長度，根據(jù)第一類組合方式中分區(qū)以及進(jìn)程執(zhí)行規(guī)則，所有分區(qū)及進(jìn)程在時間軸上的執(zhí)行情況唯一確定；此時計算出所有分區(qū)及進(jìn)程的執(zhí)行時間區(qū)間之后，在時間軸上畫出系統(tǒng)的調(diào)度甘特圖，即完成第一類組合方式中模型的仿真；

第二類組合方式中模型在進(jìn)程時間連續(xù)的基礎(chǔ)上對分區(qū)采用新到分區(qū)優(yōu)先執(zhí)行的分區(qū)調(diào)度策略；模型將分區(qū)的周期以及進(jìn)程的相關(guān)參數(shù)作為輸入?yún)?shù)，將分區(qū)的另外兩個參數(shù)作為待優(yōu)化參數(shù)；對第二類組合方式，模型在輸入每個分區(qū)中的進(jìn)程參數(shù)后，也應(yīng)首先判斷處理器個數(shù)，如為多處理器，則對輸入的所有分區(qū)進(jìn)行分組操作；對第二類組合方式的分組算法如下：

輸入：分組個數(shù)，即處理器個數(shù)，分區(qū)的周期，進(jìn)程的周期和進(jìn)程的最壞執(zhí)行時間；

1)如果分區(qū)個數(shù)小于處理器個數(shù)，則每個處理器上分配一個分區(qū)可以實現(xiàn)最大的可調(diào)度性，否則，根據(jù)每個分區(qū)中所有進(jìn)程的周期和最壞執(zhí)行時間計算出每個分區(qū)在一個主時間框架內(nèi)時間片總長度與在主時間框架內(nèi)的最小占比假設(shè)第i分區(qū)中有n個進(jìn)程，j表示第i分區(qū)中的進(jìn)程序號，R_ij和P_ij分別表示第i分區(qū)中第j個進(jìn)程的最壞執(zhí)行時間和周期；

2)根據(jù)分區(qū)周期對分區(qū)進(jìn)行初步分組：首先將所有具有倍數(shù)關(guān)系的分區(qū)分為一組；然后使用適應(yīng)度值函數(shù)f(x)選出具有最大適應(yīng)度值的一組，適應(yīng)度值函數(shù)f(x)如下：

此時x為每組內(nèi)分區(qū)的最小占比之和；然后將選出的一組分區(qū)從待分組分區(qū)中刪除，重復(fù)上述過程，直到所有分區(qū)均已分組；

3)此時的初步分組方案中分組個數(shù)與處理器個數(shù)關(guān)系不確定，同時每組之中的分區(qū)占比之和在極端情況仍然可能超出1；因此根據(jù)上述兩種不確定關(guān)系，分以下幾種情況進(jìn)一步考慮分區(qū)分組方案：i)分組個數(shù)恰與處理器個數(shù)相等，且每組中分區(qū)的最小占比之和相差不大且均小于1，則直接作為最終的分區(qū)分組方案；ii)分組個數(shù)少于處理器個數(shù)，且不存在分區(qū)最小占比之和多于1的情況，則首先選取分區(qū)最小占比之和最大的一組，按照第一類組合方式中模型的分組算法將該組之內(nèi)的分區(qū)分成兩組，然后檢查此時分組數(shù)與處理器個數(shù)的關(guān)系，如果分組數(shù)依然小于處理器個數(shù)，則再次選擇當(dāng)前分區(qū)最小占比之和最大的一組進(jìn)行盡量均分，不斷重復(fù)上述過程，直到分組數(shù)等于處理器個數(shù)，則輸出分組方案；iii)分組個數(shù)多于處理器個數(shù)，且不存在分區(qū)最小占比之和多于1的情況，則計算分區(qū)最小占比之和最小的兩組，如果該兩組的最小占比之和不大于均值或者雖然大于均值但是小于一個設(shè)定的閾值，則將該兩組直接合并為一組，如果將所有滿足上述條件的分組合并之后依然多于處理器個數(shù)，則按照最小占比之和遞升的順序依次選取一組以所有分區(qū)在所有處理器上最小占比的均值為根據(jù)進(jìn)行拆分，直到滿足所有分組個數(shù)與處理器個數(shù)相等；iv)若存在某些分組的最小占比之和多于1的情況，則首先以所有分區(qū)在所有處理器上最小占比的均值為根據(jù)將所有最小占比之和多于1的組拆成兩組且滿足一組盡量接近所有分區(qū)在所有處理器上最小占比的均值；然后比較經(jīng)過拆分的分組個數(shù)與處理器個數(shù)關(guān)系，分別轉(zhuǎn)化成ii)或者iii)進(jìn)行處理；

輸出：所有分區(qū)的分組情況；

在第二類組合方式下，在得出所有分區(qū)的分組情況之后，對每一組分區(qū)，算法的優(yōu)化目標(biāo)為找到一種可行的調(diào)度方案；為了簡化問題，約定所有分區(qū)初始到達(dá)時間順序按照分區(qū)周期的升序排列，根據(jù)當(dāng)前考慮分區(qū)的初始到達(dá)時間等于處理器上最早空閑時間的思想，通過逐個迭代的方式用所有分區(qū)的區(qū)間長度作為輸入計算每個分區(qū)的初始到達(dá)時間；這樣在減少一組優(yōu)化參數(shù)的基礎(chǔ)上，對每個分區(qū)的區(qū)間長度采用在特定約束條件下的隨機(jī)策略尋找滿足系統(tǒng)可調(diào)度性的調(diào)度方案；對每組分區(qū)的具體執(zhí)行過程如下：

1)將組內(nèi)所有分區(qū)按照周期的升序排列；

2)計算每組分區(qū)的主時間框架MTF＝LCM(P₁,P₂...P_t)；假設(shè)該組有t個分區(qū)，P_i表示第i個分區(qū)的周期，LCM()表示最小公倍數(shù)，計算每個分區(qū)在主時間框架中的執(zhí)行次數(shù)num(i)＝MTF/P_i；

3)根據(jù)已經(jīng)得出的每個分區(qū)在一個主時間框架中的時間片總長度在一個主時間框架中的最小占比與MTF長度，計算每個分區(qū)在主時間框架中的最小長度min_length_partition(i)；

4)對所有分區(qū)逐個依次執(zhí)行下述操作，計算第i個分區(qū)的時間片長度：

length_partition(i)＝min_length_partition(i)+floor((max_length_partition(i)-min_length_partition(i))×rand×CON)/CON

在上述公式中，floor()表示下取整，rand表示0到1之間的隨機(jī)數(shù)，CON等于10^q，q為正整數(shù)，其用來控制小數(shù)位的個數(shù)；length_partition(i)表示第i個分區(qū)的長度，max_length_partition(i)表示第i個分區(qū)的長度最大值，num(b)表示第b個分區(qū)在主時間框架中的執(zhí)行次數(shù)；

5)約定第一個分區(qū)的初始到達(dá)時間作為0時刻，根據(jù)當(dāng)前考慮分區(qū)的初始到達(dá)時間等于處理器上最早空閑時間的思想，逐個計算出每個分區(qū)的初始到達(dá)時間；

6)利用所有分區(qū)及進(jìn)程參數(shù)計算當(dāng)前系統(tǒng)的可調(diào)度性，如果可調(diào)度則計算出所有分區(qū)及進(jìn)程的執(zhí)行區(qū)間并畫出系統(tǒng)的調(diào)度甘特圖，如不可調(diào)度則重復(fù)4)～5)，直到系統(tǒng)可調(diào)度或達(dá)到初始設(shè)置的嘗試次數(shù)為止，此時則已完成第二類組合方式中模型的仿真；

第三類組合方式的仿真具體如下：

假設(shè)進(jìn)程時間在所屬分區(qū)的不同次執(zhí)行之間相互獨立，且選擇的分區(qū)調(diào)度策略為新到分區(qū)優(yōu)先執(zhí)行；該類組合方式在可調(diào)度的前提下，以最小化分區(qū)中斷次數(shù)和最小化所有分區(qū)的總執(zhí)行時間與等待時間之和作為優(yōu)化目標(biāo)，其中最小中斷次數(shù)為主優(yōu)化目標(biāo)，在相同中斷次數(shù)的前提下，最小化所有分區(qū)總執(zhí)行時間與等待時間之和；對于進(jìn)程調(diào)度策略選擇EDF、RMS或PTS調(diào)度策略；

在第三類組合方式下，約定每個分區(qū)的時間片長度為該分區(qū)內(nèi)部所有進(jìn)程最后一次執(zhí)行的截止時間的最大值，由于分區(qū)內(nèi)部所有進(jìn)程在該分區(qū)的到達(dá)時刻同時進(jìn)入就緒狀態(tài)，因此分區(qū)長度的計算方式如下：

length_partition(i)＝max((num_run_process(ij)-1)*period_process(ij)+deadline_process(ij))

在上述公式中，length_partiti(o)表示第i個分區(qū)的長度，num_run_process(ij)、period_process(ij)、deadline_process(ij)分別表示第i個分區(qū)中第j個進(jìn)程的執(zhí)行次數(shù)、周期、截止時間；

在計算出每個分區(qū)的時間片長度后，應(yīng)判斷處理器個數(shù)，如為多處理器，則應(yīng)對輸入的所有分區(qū)進(jìn)行分組操作；對該類組合方式，分組算法如下：

輸入：分組個數(shù)，即處理器個數(shù),分區(qū)的周期，分區(qū)的長度；

1)如果分區(qū)個數(shù)小于處理器個數(shù)，則每個處理器上分配一個分區(qū)以實現(xiàn)最大的可調(diào)度性，否則，根據(jù)分區(qū)周期和分區(qū)的長度計算出該分區(qū)在一個主時間框架中時間片總長度在一個主時間框架中的占比α_i＝L_i/P_i，L_i和P_i分別表示第i個分區(qū)的時間片長度和周期；

2)和3)同第二類組合方式中分區(qū)的分組算法的步驟2)和步驟3)；

輸出：所有分區(qū)的分組情況；

在進(jìn)行分區(qū)參數(shù)優(yōu)化之前需要先計算每個分區(qū)內(nèi)部進(jìn)程的執(zhí)行區(qū)間，如果進(jìn)程調(diào)度策略選為EDF或RMS，則直接根據(jù)進(jìn)程的執(zhí)行規(guī)則，對每個分區(qū)計算出內(nèi)部所有進(jìn)程在所屬分區(qū)的一個完整時間片中的執(zhí)行時間區(qū)間，并返回關(guān)鍵進(jìn)程所對應(yīng)的時間區(qū)間作為分區(qū)優(yōu)化時的不可中斷的約束條件；如果進(jìn)程調(diào)度策略選為PTS，則應(yīng)首先對每個分區(qū)中的進(jìn)程分別執(zhí)行優(yōu)先級和閾值分配的優(yōu)化算法；

接下來，以所有關(guān)鍵進(jìn)程的執(zhí)行區(qū)間為約束條件優(yōu)化所有分區(qū)的初始到達(dá)時間，采用更改邊界條件的標(biāo)準(zhǔn)粒子群算法，所述的標(biāo)準(zhǔn)粒子群算法的原理如下：

1)用實數(shù)編碼的方式表示每個分區(qū)的初始到達(dá)時間，假設(shè)N個粒子，n個分區(qū)，則初始化后每個粒子的位置為x_s(0)＝[x_s1,x_s2,x_s3…x_sn]，每個粒子的速度為v_s(0)＝[v_s1,v_s2,v_s3…v_sn]，其中x_sl表示第s個粒子位置的第l維取值，v_sl表示第s個粒子速度的第l維取值，s＝1,2,…N,l＝1,2…n；初始化粒子每個維度的位置以及速度的取值范圍均分別為[0,period_part(it)i-onll_ength(p)a]rt，1≤l≤n，設(shè)置粒子每個維度的速度最大值為(period_partition(l)-length_partition(l))/2；period_partition(l)表示第l個分區(qū)的周期，length_partition(l)表示第l個分區(qū)的時間片長度；

2)按照下述公式對所有粒子進(jìn)行更新，共迭代M次:

v_s(t+1)＝w×v_s(t)+c₁×rand×(pbest_s-persent_x_s)+c₂×rand×(gbest-persent_x_s)

x_s(t+1)＝x_s(t)+v_s(t+1)

其中，v_s(t+1)和x_s(t+1)分別表示第s個粒子在第t+1代的速度和位置；w表示隨迭代次數(shù)線性遞減的慣性權(quán)重，w的最大值w_max和最小值w_min分別等于0.95和0.4；c₁和c₂取值為2，rand表示0到1之間的隨機(jī)數(shù)，persent_x_s表示第s個粒子當(dāng)前的位置；如果在按照上述公式更新中粒子位置超出對應(yīng)的取值范圍，則對該粒子在取值空間中隨機(jī)更新；每次對所有粒子進(jìn)行更新之后計算所有更新粒子的適應(yīng)度值，并根據(jù)每個粒子的適應(yīng)度值更新pbest_s和gbest；

3)M次迭代完成后返回gbest；

該標(biāo)準(zhǔn)粒子群算法有兩個優(yōu)化目標(biāo)，分別為每個處理器上所有分區(qū)總中斷次數(shù)NI最小，每個處理器上所有分區(qū)總執(zhí)行時間與等待執(zhí)行時間之和SET最短，其中前者為主，在前者相同的前提下后者越小越好；這兩個優(yōu)化目標(biāo)的計算方式如下：

1)計算主時間框架；計算每個分區(qū)在主時間框架中的執(zhí)行次數(shù)；根據(jù)初始到達(dá)時間，計算每個分區(qū)在主時間框架內(nèi)的每次到達(dá)時間；計算所有分區(qū)在主時間框架中執(zhí)行的總次數(shù)SN；

2)將所有分區(qū)的到達(dá)時間按照從小到大進(jìn)行排序，如相等，則以分區(qū)的升序排列；

3)設(shè)置所有分區(qū)的等待執(zhí)行時間為0；

4)循環(huán)SN次；

(4.1)按照分區(qū)下次到達(dá)時間升序?qū)λ蟹謪^(qū)的等待執(zhí)行時間進(jìn)行排序；

(4.2)比較排好序的所有分區(qū)的最近的下次到達(dá)時間與當(dāng)前時間的差和當(dāng)前到達(dá)分區(qū)時間片長度的大小，如果前者較大，則主時間框架首先為當(dāng)前到達(dá)分區(qū)分配時間窗口，然后按照步驟(4.1)中的順序為所有待執(zhí)行的分區(qū)分配時間窗口，否則僅為當(dāng)前到達(dá)分區(qū)分配時間窗口；

(4.3)根據(jù)步驟(4.2)對每個分區(qū)的等待執(zhí)行時間進(jìn)行更新；

5)計算所有分區(qū)的執(zhí)行區(qū)間以及所有分區(qū)總中斷次數(shù)和總執(zhí)行時間；

最終經(jīng)過粒子群優(yōu)化算法之后得出每個分區(qū)的最優(yōu)初始到達(dá)時間，根據(jù)所有的分區(qū)及進(jìn)程參數(shù)，計算出在整個時間軸上的所有分區(qū)及進(jìn)程的執(zhí)行時間區(qū)間，畫出相應(yīng)的調(diào)度甘特圖即完成第三類組合方式中模型的仿真。