|
|
论文:2012,Vol:30,Issue(1):117-123 |
|
|
引用本文： |
|
|
黄姝娟, 朱怡安, 李兵哲, 陆伟. 基于利用率和负载均衡的多核实时调度算法研究[J]. 西北工业大学 |
|
|
Huang Shujuan, Zhu Yi'an, Li Binzhe, Lu Wei. An Efficient BUWBP(Based on Utilization and Workload Balance Partition) Algorithm for Multiprocessor Real-Time System[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 基于利用率和负载均衡的多核实时调度算法研究 |
|
| 黄姝娟1,2, 朱怡安1,2, 李兵哲1, 陆伟2 |
|
1. 西北工业大学 软件与微电子学院,陕西 西安 710072;
2. 西北工业大学 计算机学院,陕西 西安 710072 |
| 摘要: |
| 针对分区调度算法在实时多处理器系统中处理器利用率不高的现象,提出一种基于利用率和负载均衡的分区调度算法BUWBPA(BasedonUtilizationandWorkloadBalancePartitionAlgorithm)。该算法在满足任务实时性要求的基础上,以寻求高利用率和负载均衡为目标进行任务分配,将任务分配分成两个阶段:第一个阶段以高利用率为原则,选择任务集内利用率最高的任务先分配;第二个阶段以负载均衡为原则,根据处理器数选择利用率总和等于1或接近于1的任务进行分配,并且在此阶段对于未达到充分利用的处理器,选取可能调度的零星任务,对任务进行再次重新分配,以达到负载均衡和系统最大利用率。实验证明,该算法在实现最大利用率的前提下能很好地达到负载均衡。 |
| 关键词:
多核
实时系统
负载均衡
启发式算法
|
|
| An Efficient BUWBP(Based on Utilization and Workload Balance Partition) Algorithm for Multiprocessor Real-Time System |
|
| Huang Shujuan1,2, Zhu Yi'an1,2, Li Binzhe1, Lu Wei2 |
|
1. Department of Software Engineering, Northwestern Polytechnical University, Xi'an 710072, China;
2. Deparfment of Computer Science and Engineering, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| The partition algorithm cannot achieve the high-utilization for the multiprocessor system.We propose anew heuristic partition scheduling algorithm which can achieve the high-utilization and make workload balance.Sec-tions 1, 2 and 3 of the full paper explain BUWBP algorithm mentioned in the title,which we believe is more effi-cient than previous ones.The core of section 1, 2 and 3 consists of: "It has two phases: in the first phase,we allo-cate the tasks to the cores; in the second phase,we choose the complementary or similar complementary element forthe allocated task of each core.Subsection 1.2 gives ten definitions and four theorems."Simulation results, presen-ted in Fig.2 and Table 1,and their analysis show preliminarily that our BUWBP algorithm can indeed find better u-tilization and make the workload balance for the cores. |
| Key words:
algorithms
analysis
codes(symbols)
delay
design
efficiency
embedded systems
evaluation
flowcharting
information technology
models
multiprocessing systems
parallel processing systems
real-time systems
resource allocation
scheduling
schematic diagrams
simulation
software engi-neering
multi-core
utilization
workload balance
|
|
| 收稿日期: 2011-04-07
修回日期:
|
| DOI: |
| 基金项目: 航空科学基金(20100753022)；西北工业大学基础研究基金(JC20110283)资助 |
| 通讯作者:
Email： |
| 作者简介: 黄姝娟(1975-),女,西北工业大学讲师,主要从事嵌入式与普适计算研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Brandenburg B B，Anderson J H. On the Implementation of Global Real-Time Schedulers. Real-Time Systems Symposium，2009, 214～224
[2] Baruah S K，et al. Proportionate Progress: A Notion of Fairness in Resource Allocation. Algorithmica, 1996, 15: 600～625
[3] Baruah S，Fisher N. The Partitioned Scheduling of Sporadic Real-Time Tasks on Multiprocessor Platforms. Parallel Processing．International Conference Workshops on Parallel Processing, 2005, 346～353
[4] 王 涛, 刘大昕. 多处理器单调速率任务分配算法性能评价. 计算机科学, 2007, 34(1): 272～277Wang Tao，Liu Daxin. The Performance Evaluation of Rate Monotonic Tasks Assignment Algorithms on Multiprocessor. Comput-er Science, 2007, 34(1): 272～277 (in Chinese)
[5] Andersson B，Bletsas K. Sporadic Multiprocessor Scheduling with Few Preemptions. Euromicro Conference on Real-Time Sys-tems, 2008, 243～252
[6] Baruah S，Fisher N. The Partitioned Dynamic-Priority Scheduling of Sporadic Task Systems. Real-Time Systems, 2007, 36: 199～226
[7] Sanjoy B，Fisher N. The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems. IEEE Trans onComputers, 2006, 55: 918～923
[8] Lakshmanan K，et al. Partitioned Fixed-Priority Preemptive Scheduling for Multi-Core Processors. 21st Euromicro Conference onReal-Time Systems, 2009, 239～248
[9] George L, Hermant J F. A Norm Approach for the Partitioned EDF Scheduling of Sporadic Task Systems. 21st Euromicro Confer-ence on Real-Time Systems, 2009, 161～169
[10] Liu C L，Layland J W. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. Journal of the Associa-tion for Computing Machinery, 1973, 20: 46～61 |
|
|
|
|
|
|
|
