深海集矿机多任务调度及算法研究
|
摘要
深海底蕴藏着丰富的矿产资源，其开发手段的研究，对于我国矿产资源的可持续利用具有重要的战略意义。深海采矿集矿机工作于6000m深海底复杂的未知环境中，要求控制系统具有很高实时性，而多任务调度则是提高整个控制系统实时性关键，开展对集矿机多任务调度算法研究，能够提高系统控制质量和实时性能，进而保证深海采矿系统的安全性和采矿效率。
本文以深海采矿系统作为研究背景，对传统的任务调度算法进行深入分析，针对它们在应用于深海采矿系统时存在的问题，在考虑任务间同步基础上采用了基于任务优先级表的调度算法。从理论上分析了算法的可调度性，并通过仿真实验证明了算法的有效性和可行性。其主要工作和研究成果包括：针对采矿系统对集矿机行走控制、数据采集、数据通信等基本功能要求，对深海采矿控制系统的基本任务进行合理划分，并设计各部分任务单元的功能。通过总结深海采矿实时系统多任务特点的基础上，改进CDF等传统调度算法，考虑任务间的同步关联，并综合任务截止期和价值等多个特征参数以确定任务优先级。系统采用AMP结构框架对三片ARM7控制器进行硬件结构设计，并选用μC／OS-Ⅱ实时操作系统内核，实现内核改写和移植，同时在此内核基础上完成系统软件和应用软件的开发工作。
论文最后利用Matlab／Simulink仿真平台的Truetime工具包对调度算法进行仿真，对比RM调度算法验证该算法的有效性，以实现对深海采矿系统的多任务调度。
There are abundant mineral resources on deep-seabed. The research on it's explore technique has important significance in its continual owner for our country's mineral resource. The deep-seabed mining vehicle works in an unknown complex environment of 6000m-depth seabed. Its control system is required to have high real-time performance. Multi-task scheduling is the pivotal problem to improve the system's real-time performance. Research on multi-task scheduling algorithms for mining vehicle can improve the system's control quality and real-time performance. Then the security and mining efficiency of the mining system are guaranteed.
Knowing the ocean mining vehicle as the studying object, in order to meet the requirements of deep-seabed mining system, and considering tasks synchronization, a variety of scheduling algorithms based on tasks priority table under the analysis of traditional algorithms is used. The scheduling algorithm is tested and analyzed, and the effectiveness and feasibility of the algorithm is demonstrated with simulation results. The main research achievements include: Based on the mining system's requirements on walking control, data collection and data communication for deep seabed mining vehicle, the basic tasks of the mining control system is partitioned reasonably, and the function of each part is designed. Considering the characteristics of multi-task scheduling for deep seabed mining real-time system, a new priority table based on real-time scheduling algorithm, an improved CDF algorithm is proposed. This algorithm considers tasks synchronization, and takes the deadlines and value density of real-time tasks into account synthetically. Then three ARM7 controllers of hardware system are designed with AMP framework. Based onμC/OS-Ⅱreal-time system, kernel rewrite and transplantation is realized, and the development of system software and applications software is accomplished.
At last, the scheduling algorithm is simulated on Truetime toolkit of Matlab/Simulink platform. The simulation results demonstrate effectiveness of the scheduling algorithm by comparing with RM scheduling algorithm. The multi-task scheduling for deep seabed mining is realized.
本文以深海采矿系统作为研究背景，对传统的任务调度算法进行深入分析，针对它们在应用于深海采矿系统时存在的问题，在考虑任务间同步基础上采用了基于任务优先级表的调度算法。从理论上分析了算法的可调度性，并通过仿真实验证明了算法的有效性和可行性。其主要工作和研究成果包括：针对采矿系统对集矿机行走控制、数据采集、数据通信等基本功能要求，对深海采矿控制系统的基本任务进行合理划分，并设计各部分任务单元的功能。通过总结深海采矿实时系统多任务特点的基础上，改进CDF等传统调度算法，考虑任务间的同步关联，并综合任务截止期和价值等多个特征参数以确定任务优先级。系统采用AMP结构框架对三片ARM7控制器进行硬件结构设计，并选用μC／OS-Ⅱ实时操作系统内核，实现内核改写和移植，同时在此内核基础上完成系统软件和应用软件的开发工作。
论文最后利用Matlab／Simulink仿真平台的Truetime工具包对调度算法进行仿真，对比RM调度算法验证该算法的有效性，以实现对深海采矿系统的多任务调度。
There are abundant mineral resources on deep-seabed. The research on it's explore technique has important significance in its continual owner for our country's mineral resource. The deep-seabed mining vehicle works in an unknown complex environment of 6000m-depth seabed. Its control system is required to have high real-time performance. Multi-task scheduling is the pivotal problem to improve the system's real-time performance. Research on multi-task scheduling algorithms for mining vehicle can improve the system's control quality and real-time performance. Then the security and mining efficiency of the mining system are guaranteed.
Knowing the ocean mining vehicle as the studying object, in order to meet the requirements of deep-seabed mining system, and considering tasks synchronization, a variety of scheduling algorithms based on tasks priority table under the analysis of traditional algorithms is used. The scheduling algorithm is tested and analyzed, and the effectiveness and feasibility of the algorithm is demonstrated with simulation results. The main research achievements include: Based on the mining system's requirements on walking control, data collection and data communication for deep seabed mining vehicle, the basic tasks of the mining control system is partitioned reasonably, and the function of each part is designed. Considering the characteristics of multi-task scheduling for deep seabed mining real-time system, a new priority table based on real-time scheduling algorithm, an improved CDF algorithm is proposed. This algorithm considers tasks synchronization, and takes the deadlines and value density of real-time tasks into account synthetically. Then three ARM7 controllers of hardware system are designed with AMP framework. Based onμC/OS-Ⅱreal-time system, kernel rewrite and transplantation is realized, and the development of system software and applications software is accomplished.
At last, the scheduling algorithm is simulated on Truetime toolkit of Matlab/Simulink platform. The simulation results demonstrate effectiveness of the scheduling algorithm by comparing with RM scheduling algorithm. The multi-task scheduling for deep seabed mining is realized.
引文
[1] Liu J. W. S., Real-Time Systems [M], New Jersey: Prentice-Hall, Inc., 2000
[2] 王琳，喻成，李昌一．实时数据库的现状与发展[J]．河北理工学院学报，2003，25(3)：93～99
[3] Buttazzo G. C., Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications[J], Boston: Kluwer Academic Publicsh, 1997
[4] 中国大洋多金属结核矿产资源研究开发中试采矿系统技术设计(监控与动力子系统)(监控部分)[M]．中国大洋协会，2001
[5] 简曲，陈新明等．二十一世纪中国的大洋多金属结核工业开采[J]．中国矿业，1997，6(3)：16～19
[6] Holser A E. Manganese Nodules Resource and Minning Site Availability[J]. Washington D C: Professional Staff Study Ocean Mining Administration, U.S. Department of the Intetior, 1976
[7] Cronan D S. Under Water Mineral[J]. London: Academic Press, 1980, 362～378
[8] 陈峰．深海底采矿机器车运动建模与控制研究[D]．中南大学博士学位论文，2005
[9] Graham T M. Assessment of manganese nodules resource[J]. Seabed Mineral, 1982, 1:1～79
[10] Willing C. G. An advanced design deep sea mining system[J]. Proc. of Offshore Technology, Conference Houston, 1981, 1: 247～255
[11] 简曲．大洋采矿集矿机的现状与展望[J]．矿山机械，1997，30(8)：1～5
[12] Lawler E. L., Lenstra J. K., Rinnooy A. H. G., Shomoys D. B. Sequencing and scheduling: algorithms and complexity[M]. Technique report BS-R8909, Center for Mathematics and Computer Science, Erasmus University, Rotterdam, 1989
[13] Blazewiez J. Selected topics in scheduling theory[J]. Annuals of discrete mathematics, 1987, 31(1): 1～59
[14] Kao B., Molina H G, Adelberg B. On building soft real-time systems[J]. In the third workshop on Parallel and Distributed Real-time Systems, Santa Barbara, CA, USA, 1995
[15] Stankovic J A, Spuri M, Natale M, Buttazzo D. Implications of classical scheduling results for real-time systems[J]. Computer, 28(6): 1995.16～25
[16] 宾雪莲．实时系统中的任务调度技术研究[D]，国防科学技术大学博士学位论文，2004
[17] Liu C. L.&Layland J. W., Scheduling Algorithms for Multi-Programming in a Hard-Real-Time Environment[J], Jorunal ACM, 20(1): 1973. 46～61
[18] Horn W., Some simple scheduling algorithms[J], Naval Research Logistics Quarterly, 21, 1974
[19] Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness[J], W. H. Freeman and Company, 1979
[20] Burchard A., Liebeherr J., Oh Y.,& Son S. H., New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems[J], IEEE Trans. Computer, 1995, 44(12): 1429～1442
[21] Burns A., Broadening real-time system research[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[22] Tilborg A. V. Real-time research in the department of defense[J], ACM workshop on strategic directions in comuting research, New York, USA, 1996
[23] Jeffay K. Technique and educational challenges for real-time computing[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[24] Lee I. Formal verification, testing and checking of real-time systems[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[25] Sha L. Real-time in the real-world[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[26] Ready J. Real-time education. ACM workshop on strategic directions in computing research[J], New York, USA, 1996
[27] Lehoczky J. Analytic methods for real-time computing[J], ACM workshop on strategic directions in computing research, New York, USA, 1996
[28] Liu W S. Validation of time properties[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[29] 艾定军，徐家祥等．实时嵌入式多处理器操作系统实现框架[J]．计算机工程，2003，10(29)：89～91
[30] 沈悦明，陈启军．一种基于任务的机器人全局并行算法研究及实现[J]．机器人，2003，25(6)：495～500
[31] Jean J．Labrosse著，邵贝贝等译．嵌入式实时操作系统μC／OS-Ⅱ(第二版)[M]．北京航天航空大学出版社，2003
[32] Liu C L., Layland J. Scheduling algorithms for multiprogramming in real-time systems[J]. Journal of the ACM, 1973, 20(1): 46～61
[33] 王强，徐俊刚，王宏安，等．一种新的基于优先级表的实时调度算法[J]．电子 学报，2004，2(2)：310～313
[34] 阳春华．工业实时系统多任务容错调度技术及应用研究[D]．中南大学博士学位论文，2004
[35] 卢光辉，孙世新．分布存储系统上一种新的并行调度算法[J]．计算机研究与发展，2001．28(2)：223～227
[36] 王志平，熊光泽．实时调度算法研究[J]．电子科技大学学报，2000．29(2)：205～208
[37] Chen Min-ih, Lin Kwei-Jay. Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems[J]. Real—Time Systems, 1990,(2):325～346
[38] M. G. Harbour, M. H. Klein, and J. P. Lehoczky. Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priorit[J], In: Proceedings of 12th Real-Time Systems Symposium, IEEE 1991.116～128
[39] 张惠娟，瞿鸿鸣．一种固定优先级实时调度算法的可行性测定[J]．微机发展，2003．13(9)：65～67
[40] A. Burns, A. J. Wellings. Dual Priority Assignment: A practical Method for Increasing Processor utilization[J]. In: Proceedings of 14th Real-Time Systems Symposium, IEEE 1993. 48～53
[41] Han C. C, Lin K J, Scheduling distance-constrained real-time tasks[J]. Proceedings IEEE Real-Time Systems Symposium, New York, 1992. 300～308
[42] G Buttazzo, M Spuri, F Seensini. Value vs. deadline scheduling in overload conditions[J]. Proceedings of the 16th IEEE Real-Time Systems Symposium. Los Alarmitos, California: IEEE Computer Society, 1995. 90～99.
[43] 王随平．COMPACT-PCI IPC用于深海集矿作业车两级控制系统[J]．计算技术与自动化，2002，21(2)：7～10
[44] 龚德文．深海集矿机测控系统的研究开发[J]．矿冶工程，2004，24(3)：8～11
[45] Chenyang Lu, J A Stankovic, et al. Design and evaluation of a feedback control EDF scheduling algorithm[J]. Proceedings of the 20th IEEE Real-Time System Symposium. Phoenix, Arizona: IEEE Computer Society, 1999. 55～66.
[46] 王永炎，王强，王宏安，等．基于优先级表的实时调度算法及其实现[J]．软件学报，2004，15(3)：360～370
[47] 金宏，王宏安，王强，等．一种任务优先级的综合设计方法[J]．软件学报，2003，14(3)：376～382
[48] Henriksson D, Cervin, Arzen, K E. Turetime: real-time control system simulation with Matlab/Simulink[J]. Proceedings of the Nordic Matlab Conference. Copenhagen Denmark, 2003
[49] Cervin A, Henriksson D, Lincoln B, Arzen K E. Jitterbug and Truetime: analysis tools for real-time control systems[J]. Proceedings of the 2nd Workshop on Real-Time. Copenhagen, Denmark,2002
[50] 王轶卿，赵英凯．TrueTime在实时控制系统仿真中的应用[J]．机械与电子，2005，(3)：72～74
[51] 黄同宇，司济丽．多任务实时系统仿真软件TrueTime及其应用[J]．山东电力高等专科学校学报，2005，4(8)：26～28
[52] Henriksson D, Cervin A. Truetime 1.3-Reference Manual[M]. Lund, Sweden: Department of Automatic Control, Lund Institute of Technoloy,2005
[2] 王琳，喻成，李昌一．实时数据库的现状与发展[J]．河北理工学院学报，2003，25(3)：93～99
[3] Buttazzo G. C., Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications[J], Boston: Kluwer Academic Publicsh, 1997
[4] 中国大洋多金属结核矿产资源研究开发中试采矿系统技术设计(监控与动力子系统)(监控部分)[M]．中国大洋协会，2001
[5] 简曲，陈新明等．二十一世纪中国的大洋多金属结核工业开采[J]．中国矿业，1997，6(3)：16～19
[6] Holser A E. Manganese Nodules Resource and Minning Site Availability[J]. Washington D C: Professional Staff Study Ocean Mining Administration, U.S. Department of the Intetior, 1976
[7] Cronan D S. Under Water Mineral[J]. London: Academic Press, 1980, 362～378
[8] 陈峰．深海底采矿机器车运动建模与控制研究[D]．中南大学博士学位论文，2005
[9] Graham T M. Assessment of manganese nodules resource[J]. Seabed Mineral, 1982, 1:1～79
[10] Willing C. G. An advanced design deep sea mining system[J]. Proc. of Offshore Technology, Conference Houston, 1981, 1: 247～255
[11] 简曲．大洋采矿集矿机的现状与展望[J]．矿山机械，1997，30(8)：1～5
[12] Lawler E. L., Lenstra J. K., Rinnooy A. H. G., Shomoys D. B. Sequencing and scheduling: algorithms and complexity[M]. Technique report BS-R8909, Center for Mathematics and Computer Science, Erasmus University, Rotterdam, 1989
[13] Blazewiez J. Selected topics in scheduling theory[J]. Annuals of discrete mathematics, 1987, 31(1): 1～59
[14] Kao B., Molina H G, Adelberg B. On building soft real-time systems[J]. In the third workshop on Parallel and Distributed Real-time Systems, Santa Barbara, CA, USA, 1995
[15] Stankovic J A, Spuri M, Natale M, Buttazzo D. Implications of classical scheduling results for real-time systems[J]. Computer, 28(6): 1995.16～25
[16] 宾雪莲．实时系统中的任务调度技术研究[D]，国防科学技术大学博士学位论文，2004
[17] Liu C. L.&Layland J. W., Scheduling Algorithms for Multi-Programming in a Hard-Real-Time Environment[J], Jorunal ACM, 20(1): 1973. 46～61
[18] Horn W., Some simple scheduling algorithms[J], Naval Research Logistics Quarterly, 21, 1974
[19] Garey M. R. and Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness[J], W. H. Freeman and Company, 1979
[20] Burchard A., Liebeherr J., Oh Y.,& Son S. H., New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems[J], IEEE Trans. Computer, 1995, 44(12): 1429～1442
[21] Burns A., Broadening real-time system research[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[22] Tilborg A. V. Real-time research in the department of defense[J], ACM workshop on strategic directions in comuting research, New York, USA, 1996
[23] Jeffay K. Technique and educational challenges for real-time computing[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[24] Lee I. Formal verification, testing and checking of real-time systems[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[25] Sha L. Real-time in the real-world[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[26] Ready J. Real-time education. ACM workshop on strategic directions in computing research[J], New York, USA, 1996
[27] Lehoczky J. Analytic methods for real-time computing[J], ACM workshop on strategic directions in computing research, New York, USA, 1996
[28] Liu W S. Validation of time properties[J]. ACM workshop on strategic directions in computing research, New York, USA, 1996
[29] 艾定军，徐家祥等．实时嵌入式多处理器操作系统实现框架[J]．计算机工程，2003，10(29)：89～91
[30] 沈悦明，陈启军．一种基于任务的机器人全局并行算法研究及实现[J]．机器人，2003，25(6)：495～500
[31] Jean J．Labrosse著，邵贝贝等译．嵌入式实时操作系统μC／OS-Ⅱ(第二版)[M]．北京航天航空大学出版社，2003
[32] Liu C L., Layland J. Scheduling algorithms for multiprogramming in real-time systems[J]. Journal of the ACM, 1973, 20(1): 46～61
[33] 王强，徐俊刚，王宏安，等．一种新的基于优先级表的实时调度算法[J]．电子 学报，2004，2(2)：310～313
[34] 阳春华．工业实时系统多任务容错调度技术及应用研究[D]．中南大学博士学位论文，2004
[35] 卢光辉，孙世新．分布存储系统上一种新的并行调度算法[J]．计算机研究与发展，2001．28(2)：223～227
[36] 王志平，熊光泽．实时调度算法研究[J]．电子科技大学学报，2000．29(2)：205～208
[37] Chen Min-ih, Lin Kwei-Jay. Dynamic Priority Ceilings: A Concurrency Control Protocol for Real-Time Systems[J]. Real—Time Systems, 1990,(2):325～346
[38] M. G. Harbour, M. H. Klein, and J. P. Lehoczky. Fixed Priority Scheduling of Periodic Tasks with Varying Execution Priorit[J], In: Proceedings of 12th Real-Time Systems Symposium, IEEE 1991.116～128
[39] 张惠娟，瞿鸿鸣．一种固定优先级实时调度算法的可行性测定[J]．微机发展，2003．13(9)：65～67
[40] A. Burns, A. J. Wellings. Dual Priority Assignment: A practical Method for Increasing Processor utilization[J]. In: Proceedings of 14th Real-Time Systems Symposium, IEEE 1993. 48～53
[41] Han C. C, Lin K J, Scheduling distance-constrained real-time tasks[J]. Proceedings IEEE Real-Time Systems Symposium, New York, 1992. 300～308
[42] G Buttazzo, M Spuri, F Seensini. Value vs. deadline scheduling in overload conditions[J]. Proceedings of the 16th IEEE Real-Time Systems Symposium. Los Alarmitos, California: IEEE Computer Society, 1995. 90～99.
[43] 王随平．COMPACT-PCI IPC用于深海集矿作业车两级控制系统[J]．计算技术与自动化，2002，21(2)：7～10
[44] 龚德文．深海集矿机测控系统的研究开发[J]．矿冶工程，2004，24(3)：8～11
[45] Chenyang Lu, J A Stankovic, et al. Design and evaluation of a feedback control EDF scheduling algorithm[J]. Proceedings of the 20th IEEE Real-Time System Symposium. Phoenix, Arizona: IEEE Computer Society, 1999. 55～66.
[46] 王永炎，王强，王宏安，等．基于优先级表的实时调度算法及其实现[J]．软件学报，2004，15(3)：360～370
[47] 金宏，王宏安，王强，等．一种任务优先级的综合设计方法[J]．软件学报，2003，14(3)：376～382
[48] Henriksson D, Cervin, Arzen, K E. Turetime: real-time control system simulation with Matlab/Simulink[J]. Proceedings of the Nordic Matlab Conference. Copenhagen Denmark, 2003
[49] Cervin A, Henriksson D, Lincoln B, Arzen K E. Jitterbug and Truetime: analysis tools for real-time control systems[J]. Proceedings of the 2nd Workshop on Real-Time. Copenhagen, Denmark,2002
[50] 王轶卿，赵英凯．TrueTime在实时控制系统仿真中的应用[J]．机械与电子，2005，(3)：72～74
[51] 黄同宇，司济丽．多任务实时系统仿真软件TrueTime及其应用[J]．山东电力高等专科学校学报，2005，4(8)：26～28
[52] Henriksson D, Cervin A. Truetime 1.3-Reference Manual[M]. Lund, Sweden: Department of Automatic Control, Lund Institute of Technoloy,2005