[發明專利]基于遞歸在線算法的進程任務塊可疑依賴關系的發現方法

有效

• 申請號: 201711216892.9
• 申請日: 2017-11-28
• 公開（公告）號: CN107861880B
• 公開（公告）日: 2021-06-22
• 發明（設計）人: 曲明成;陳蛟龍;王冠楠
• 申請（專利權）人: 曲明成
• 主分類號: G06F11/36
• 分類號: G06F11/36
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 岳泉清

1.基于遞歸在線算法的進程任務塊可疑依賴關系的發現方法，其特征在于：所述方法具體過程為：

步驟一、輸入正確和錯誤的測試用例，正確測試用例為a₁，a₂，...，a_i，a_i+1，...a_p，...a_j，a_j+1，...，a_m，ipj；根據一種基于矩陣的獲取進程任務塊依賴關系方法得到a_i在a_j之前執行，找出α個正確測試用例中a_i和a_j距離最近時a_i和a_j所在的正確測試用例，將該正確測試用例重新命名為a_[1]，a_[2]，...，a_[i]，a_[i+1]，...a_[p]，...，a_[j]，a_[j+1]，...，a_[m]；具體過程為：

步驟一一、輸入正確和錯誤測試用例，測試用例包括所有進程任務塊；

步驟一二、將測試用例轉換成關系矩陣；

關系矩陣包括正確關系矩陣、錯誤關系矩陣、關系相容矩陣和依賴關系矩陣；

在關系矩陣中，1代表先于執行，0代表后于執行，-1不予考慮；

正確關系矩陣：由正確的測試用例序列構建的矩陣；

錯誤關系矩陣：由錯誤的測試用例序列構建的矩陣；

關系相容矩陣：不同任務的子任務塊沒有先后關系的矩陣；

依賴關系矩陣：不同任務的子任務塊之間有確定的依賴關系；

步驟一三、當α≥β時，執行步驟一四；當αβ時，執行步驟一九；α為正確測試用例數目，β為錯誤測試用例數目；

步驟一四、對β個正確關系矩陣和錯誤關系矩陣進行矩陣減操作，得到新的矩陣B1’和B2’，根據B1’和B2’確定正確測試用例中有幾處與錯誤測試用例不一樣；執行步驟一五；

步驟一五、當αβ時，執行步驟一六；當α＝β時，執行步驟一七；

步驟一六、對α-β個正確關系矩陣進行矩陣交操作，得到關系相容矩陣；執行步驟一八；

步驟一七、對步驟一四得到的新的矩陣B1’和B2’進行矩陣交操作，得到依賴關系矩陣；執行一十三；

步驟一八、對步驟一四得到的新的矩陣B1’和B2’以及步驟一六得到的一個關系相容矩陣進行矩陣交操作，得到依賴關系矩陣；執行步驟一十三；

步驟一九、對α個正確關系矩陣和錯誤關系矩陣進行矩陣減操作，得到新的矩陣B1’和B2’，根據B1’和B2’確定正確測試用例中有幾處與錯誤測試用例不一樣；執行步驟一十；

步驟一十、對β-α個正確關系矩陣進行矩陣求補操作，得到補集關系矩陣b1和b2；執行步驟一十一；

步驟一十一、對補集關系矩陣b1和b2進行交操作，得到新的補集關系矩陣b1’；

步驟一十二、對步驟九得到的新的矩陣B1’和B2’以及步驟一十一得到的新的補集關系矩陣b1’進行矩陣交操作，得到依賴關系矩陣；執行步驟一十三；

步驟一十三、根據獲得的依賴關系矩陣，得到依賴關系并輸出；

步驟二、

令步驟一中正確測試用例a_[1]，a_[2]，…，a_[i]，a_[i+1]，...a_[p]，...，a_[j]，a_[j+1]，...，a_[m]中的a_[i]與a_[i+1]交換，生成新的測試用例；

步驟三、測試新的測試用例能否正確執行，若新的測試用例能正確執行，執行步驟四；若新的測試用例不能正確執行，將a_[p-1]與a_[p]交換，執行步驟七；

步驟四、

令步驟一中正確測試用例a_[1]，a_[2]，...，a_[i]，a_[i+1]，...a_[p]，...，a_[j]，a_[j+1]，...，a_[m]中的a_[i+1]與a_[i+2]交換，生成新的測試用例，測試新的測試用例能否正確執行，若新的測試用例能正確執行，執行步驟五；若新的測試用例不能正確執行，將a_[p-1]與a_[p]交換，執行步驟七；

步驟五、

令步驟一中正確測試用例a_[1]，a_[2]，...，a_[i]，a_[i+1]，...a_[p]，...，a_[j]，a_[j+1]，...，a_[m]中的a_[i+2]與a_[i+3]交換，生成新的測試用例；

步驟六、迭代執行步驟三-步驟五，直至a_i任務塊在a_j任務塊的位置之后；

步驟七、當a_i與a_p不能交換時，輸出a_i與a_p有依賴關系，將a_i任務塊存儲，將a_[p]與a_[p+1]交換，產生新的測試用例，執行步驟三；

當a_p與a_j不能交換時，同時a_i與a_j不能交換，即a_ia_pa_j，直接輸出a_ia_pa_j，程序結束；所述表示先于執行；

當a_p與a_j能交換時，交換a_p與a_j位置，產生新的測試用例a₁，a₂，...，a_i-1，a_i+1，...a_i，a_p+1...a_j，a_p，...，a_m，將該正確測試用例重新命名為a_[1]，a_[2]，...，a_[i]，a_[i+1]，...a_[p]，...，a_[j]，a_[j+1]，...，a_[m]，令測試用例a_[1]，a_[2]，...，a_[i]，a_[i+1]，...a_[p]，...，a_[j]，a_[j+1]，...，a_[m]中的a_[p-1]與a_[p]交換，生成新的測試用例；執行步驟三，直到a_i任務塊在a_j任務塊的位置之后；

a₁在a_[1]的位置，a₂在a_[2]的位置，a_i-1在a_[i-1]的位置，a_i+1在a_[i]的位置，a_i在a_[p-1]的位置，a_p+1在a_[p]的位置；a_j在a_[j-1]的位置，a_p在a_[j]的位置，a_m在a_[m]的位置。