一种基于uC/OS-II的任务调度算法及其改进实现
A Task Scheduling Algorithm Based on uC/OS-II and Its Improved Implementation
DOI: 10.12677/CSA.2022.1212298, PDF,   
作者: 郭艳飞：中国化工油气股份有限公司，北京；韩 莹, 于 磊：北方工业大学信息学院，北京
关键词: 操作系统；就绪表；优先级；任务调度；位图法；Operating System； Readiness Table； Priority； Task Scheduling； Bitmap
摘要: 本文在研究不同操作系统任务调度算法的基础上，重点针对嵌入式系统需求，以提高算法的实时性与精简性为目的，提出一种改进方案。改进的调度算法对优先级判定表的冗余部分进行删减，同时引入辅助位图，将原调度算法改进为一种优先级与时间片轮转相结合的调度算法。通过实验分析，该改进算法很好地解决了其空间复杂度较高和最大任务数的瓶颈问题，并具有良好的实时性，不失一般性，对其他系统调度算法设计也具有一定的借鉴意义。
Abstract: Based on the research of task scheduling algorithms of different operating systems, this paper focuses on the requirements of embedded systems, and proposes an improved scheme to improve the real-time and simplicity of the algorithm. The improved scheduling algorithm deletes the redundant part of the priority decision table, and introduces an auxiliary bitmap to improve the original scheduling algorithm, and improves the original scheduling algorithm to combine priority with Round Robin. Through demonstration and analysis, the results show that the improved algorithm solves the bottleneck problem of high space complexity and maximum number of tasks, and has a good reference significance.
文章引用：郭艳飞, 韩莹, 于磊. 一种基于uC/OS-II的任务调度算法及其改进实现[J]. 计算机科学与应用, 2022, 12(12): 2937-2949. https://doi.org/10.12677/CSA.2022.1212298

参考文献

[1] 邢红星, 魏叶华, 乐懿. 硬件成本缩减的异构分布式嵌入式系统调度算法[J]. 计算机工程与科学, 2021, 43(2): 258-265.
[2] 阚宏伟, 马小平, 杜林. uC/OS-II任务数扩充的理论与实现[J]. 计算机工程, 2007, 33(13): 99-100+103.
[3] 潘佳腾. VC6.0的μC/OS-II移植可行性分析研究[J]. 单片机与嵌入式系统应用, 2018, 18(3): 19-22+28.
[4] 陆伟, 张龙妹. 嵌入式操作系统混合任务调度技术与策略研究[J]. 计算机工程与应用, 2015, 51(15): 6-11.
[5] 俞佳敏, 王成群, 徐伟强. 实时操作系统μC/OS-II最大优先级数扩展实现[J]. 无线电通信技术, 2018, 44(6): 550-553.
[6] 丁宇涛. 基于FPGA的μC/OS-II操作系统任务调度算法的研究与实现[D]: [硕士学位论文]. 哈尔滨: 哈尔滨理工大学, 2022.[CrossRef] 
[7] 陈刚, 关楠, 吕鸣松, 王义. 实时多核嵌入式系统研究综述[J]. 软件学报, 2018, 29(7): 2152-2176. [Google Scholar] [CrossRef] 
[8] Anderson, J.H., Bud, V. and Devi, U.C. (2005) An EDF-Based Scheduling Algorithm for Multiprocessor Soft Real-Time Systems. 17th Euromicro Conference on Real-Time Systems (ECRTS’05), Balearic Islands, 6-8 July 2005, 199-208. [Google Scholar] [CrossRef] 
[9] Andersson, B. and Tovar, E. (2006) Multiprocessor Scheduling with Few Preemptions. 12th IEEE International Conference on Em-bedded and Real-Time Computing Systems and Applications (RTCSA’06), Sydney, 16-18 August 2006, 322-334. [Google Scholar] [CrossRef] 
[10] Panda, S.K. and Jana, P.K. (2019) An Energy-Efficient Task Sched-uling Algorithm for Heterogeneous Cloud Computing Systems. Cluster Computing, 22, 509-527. [Google Scholar] [CrossRef] 
[11] 李欣, 白兴武. 基于Linux的嵌入式实时操作系统任务调度算法优化[J]. 自动化与仪器仪表, 2020(9): 48-51. [Google Scholar] [CrossRef] 
[12] 黄国兵, 李瑞玲, 李华丽, 王琼. μC/OS-II任务优先级调度算法分析与改进[J]. 计算机工程, 2015, 41(8): 52-54+60.
[13] Pathan, R., Voudouris, P. and Stenstrom, P. (2018) Scheduling Parallel Real-Time Recurrent Tasks on Multicore Platforms. IEEE Transactions on Parallel and Dis-tributed Systems, 29, 915-928. [Google Scholar] [CrossRef] 
[14] Lee, H., Roh, J. and Seo, E. (2018) A GPU Kernel Transaction-ization Scheme for Preemptive Priority Scheduling. 2018 IEEE Real-Time and Embedded Technology and Applications Symposium, Porto, 11-13 April 2018, 202-213. [Google Scholar] [CrossRef] 
[15] Lin, J.S., Huang, C.Y. and Fang, C.C. (2022) Analysis and As-sessment of Software Reliability Modeling with Preemptive Priority Queueing Policy. Journal of Systems and Software, 187, Article ID: 111249. [Google Scholar] [CrossRef] 
[16] Yildiz, B. (2021) Optimizing Bitmap Index Encoding for High Per-formance Queries. Concurrency and Computation: Practice & Experience, 33, e5943. [Google Scholar] [CrossRef] 
[17] Vanichayobon, S., Manfuekphan, J. andGruenwald, L. (2006) Scatter Bit-map: Space-Time Efficient Bitmap Indexing for Equality and Membership Queries. 2006 IEEE Conference on Cybernet-ics and Intelligent Systems, Bangkok, 7-9 June 2006, 1-6. [Google Scholar] [CrossRef] 
[18] Rajurkar, J. and Khan, T.K. (2015) Efficient Query Processing and Optimization in SQL Using Compressed Bitmap Indexing for Set Predicates. 2015 IEEE 9th International Confer-ence on Intelligent Systems and Control, Coimbatore, 9-10 January 2015, 1-5. [Google Scholar] [CrossRef] 
[19] Yildiz, B. (2019) High Performance Queries Using Com-pressed Bitmap Indexes. In: Schwardmann, U., Boehme, C., Heras, D.B., et al., Eds., Euro-Par 2019: Parallel Pro-cessing Workshops. Euro-Par 2019. Lecture Notes in Computer Science, Springer, Cham, 493-505. [Google Scholar] [CrossRef]