【正文】 o farthen best_round = round end if remove m from its slot in roundend forplace m into its slot in best_round if one was identifieduntil the WCGD is not improved}end for如前所述，實時系統(tǒng)通信中消息的可調(diào)度性與全局延遲是同等重要的，那么如何在消息調(diào)度的過程中，實時任務集合具有最大可調(diào)度性的同時，而且還能得到最優(yōu)或者近優(yōu)的WCGD。圖11 可調(diào)度性最優(yōu)及全局延時近似最優(yōu)算法程序框圖算法實現(xiàn)：for each node Nido // set the slot sizes sizeSi = max(size of messages mj sent by node Ni)end forfor each node Nido // find the min. no. of rounds that can hold... nmi = number of messages sent from Ni// ...all the messages end formin_rounds = max (nmi)for each message mi// create a minimal plete MEDL find round in [1..min_rounds] that has an empty slot for mi place mi into its slot in roundend forfor each rounds_no in [min_rounds...max_rounds] do{repeat// insert messages in such a way that the cost is minimized for each process pi that receives a message mi do if Di Ri is the smallest so farthen m = mpi end ifend forfor each round in [1..rounds_no] do place m into its corresponding slot in round calculate the cost_function if the cost_function is smallest so farthen best_round = round end if calculate the WCGD if the WCGD is smallest so farthen best_round = round end if remove m from its slot in roundend forplace m into its slot in best_round if one was identifieduntil the cost_function is not improved}end for為對算法進行仿真，假設采用雙節(jié)點通信，A節(jié)點有進程P0,分別發(fā)送消息m1，m2，m3，m4給B節(jié)點上的進程P1，P2，P3，P4。計算機進程模型如圖所示。圖12 進程模型采用可調(diào)度性最優(yōu)算法得到結(jié)果如圖所示。其cost值為6503=14。圖13 可調(diào)度性最優(yōu)算法結(jié)果圖采用可調(diào)度性及全局延遲近似最優(yōu)算法得到結(jié)果如圖所示。圖14 考慮全局延時可調(diào)度性最優(yōu)算法結(jié)果圖其cost值為1553=14。WCGD值較可調(diào)度性最優(yōu)算法1。比較兩種方法發(fā)現(xiàn)，可調(diào)度性最優(yōu)算法由于沒有考慮到WCGD值的影響，致使其算法只能使得cost值最優(yōu)而無法保證全局延遲最優(yōu)。通過對可調(diào)度性最優(yōu)算法的改進，添加WCGD值最優(yōu)條件，能夠在滿足可調(diào)度性最優(yōu)情況下，得到最優(yōu)或近似最優(yōu)的全局延遲算法。第五章 總結(jié)本文在對TTP通信協(xié)議進行研究的基礎上，發(fā)現(xiàn)嵌入式實時系統(tǒng)通信過程中的消息調(diào)度算法只考慮消息的可調(diào)度性而沒有對全局延遲進行考慮的問題，從而提出基于可調(diào)度性及全局延遲的實時通信的總線訪問優(yōu)化的研究課題，隨后對實時通信總線的訪問優(yōu)化算法進行了研究，其中包括：靜態(tài)單消息算法、靜態(tài)多消息算法、動態(tài)消息分配算法以及動態(tài)數(shù)據(jù)包分配，并對可調(diào)度性的判斷依據(jù)進行了說明，最后通過研究現(xiàn)有可調(diào)度性最優(yōu)算法，從而給出改進后的算法描述并加以實現(xiàn)。通過本次課程設計，學習研究TTP總線信息調(diào)度算法相關的論文文獻資料，提高了查找文獻的能力和科研能力。同時學習了通信方面的專業(yè)知識，為今后的工作學習打下了良好的基礎，將自己的想法通過實踐表現(xiàn)出來，給個人帶來了一定的成就感。參考文獻[1]. 張海濤, Petri網(wǎng)的分布式實時嵌入式系統(tǒng)調(diào)度的建模[J]. 計算機工程, 2006, 32( 18): 69[2]. Pop P, Eles P, Peng Z. Bus access optimization for distributed embedded systems based on schedulability analysis[C]//Proceedings of the conference on Design, automation and test in Europe. ACM: 567575. 2000[3]. Eles P, Doboli A, Pop P, et al. Scheduling with bus access optimization for distributed embedded systems[J]. Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 8(5): 472491. 2000[4]. Tindell K, Clark J. Holistic schedulability analysis for distributed hard realtime systems[J]. Microprocessing and microprogramming, 40(2): 117134. 1994[5]. Pop P, Eles P, Peng Z, et al. Analysis and optimization of distributed realtime embedded systems[C]//ACM Transactions on Design Automation of Electronic Systems (TODAES). ACM, 11(3): 593625. 2004[6]. Jakob Rosen,CarlFredrik Neikter,Petru Eles,Zebo Peng,Paolo Burgio,Luca Benini:Bus Access Design for Combined Worst and Average Case Execution Time Optimization of Predictable RealTime Applications on Multiprocessor SystemsonChip.IEEE RealTime and Embedded Technology and Applications Symposium 2011: 291301[7]. Alexandru Andrei,Petru Eles,Zebo Peng,Jakob Rosen:Predictable Implementation of RealTime Applications on Multiprocessor SystemsonChip.VLSI Design 2008: 103110[8]. Jakob Rosen,Alexandru Andrei,Petru Eles,Zebo Peng:Bus Access Optimization for Predictable Implementation of RealTime Applications on MultiprocessorSystemsonChip.RTSS 2007: 4960[9]. Paul Pop,Petru Eles,Zebo Peng:Analysis and synthesis of distributed realtime embedded systems.Springer 2004, ISBN 9781402028724, pp. IXIX, 1326[10]. Paul Pop,Petru Eles,Zebo Peng:SchedulabilityDriven Communication Synthesis for Time Triggered Embedded Systems.RTCSA 1999: 287294[11]. Petru Eles,Krzysztof Kuchcinski,Zebo Peng,Alexa Doboli,Paul Pop:Scheduling of Conditional Process Graphs for the Synthesis of Embedded Systems.DATE 1998: 132138[12]. Paul Pop,Petru Eles,Zebo Peng:Scheduling with optimized munication for timetriggered embedded systems.CODES 1999: 178182[13]. Krishna C M. Real‐Time Systems[M]. John Wiley amp。 Sons, Inc., 1999.[14]. Audsley N, Burns A, Richardson M, et al. Applying new scheduling theory to static priority preemptive scheduling[J]. Software Engineering Journal, 1993, 8(5): 284292.[15]. Tindell K W, Burns A, Wellings A J. An extendible approach for analyzing fixed priority hard realtime tasks[J]. RealTime Systems, 1994, 6(2): 133151.[16]. Sha L, Rajkumar R, Lehoczky J P. Priority inheritance protocols: An approach to realtime synchronization[J]. Computers, IEEE Transactions on, 1990, 39(9): 11751185.[17]. Paul Pop,Petru Eles,Zebo Peng:Schedulability analysis for systems with data and control dependencies.ECRTS 2000: 201208Paul Pop,Petru Eles,Zebo Peng,Traian Pop:Analysis and optimization of distributed realtime embedded systems.ACM Trans. Design Autom. Electr. Syst. 11(3): 593625 (2006)[18].