Multiprocessor hard real-time systems preemption threshold scheduling

被引：0

作者：

Peng, Hao ^{[1
]}

Han, Jianghong ^{[1
]}

Lu, Yang ^{[1
]}

Zhang, Jianjun ^{[1
]}

机构：

[1] School of Computer and Information, Hefei University of Technology, Hefei

来源：

Jisuanji Yanjiu yu Fazhan/Computer Research and Development | 2015年 / 52卷 / 05期

关键词：

Hard real-time systems; Multiprocessor; Preemption threshold; Preemption threshold assignment; Priority assignment; Schedulability test;

D O I：

10.7544/issn1000-1239.2015.20140018

中图分类号：

学科分类号：

摘要：

The preemption plays a critical role in hard real-time systems. Preemptions are able to increase the schedulability of system. However, in multiprocessor platform, the large amount of preemptions may cause significant run-time cost due to context switch, running scheduler, job migration, etc. Besides quite amount of these preemptions are unnecessary regarding to schedulability. Limited preemption scheduling is the hybrid method between preemptive and non-preemptive scheduling, which can reduce unnecessary preemptions. In this paper, we extend the preemption threshold scheduling (PTS), one of the major methods of limited preemption scheduling, to multiprocessor hard real-time systems, which is firstly proposed for uniprocessor. The main focus of this paper is reducing preemptions. Based on DA-LC test, we derive the schedulability test for PTS. An efficient priority assignment algorithm OPA-MLL is proposed which is optimized for PTS from the combination of OPA and DA-LC. We also establish the threshold assignment algorithm aiming at reducing preemptions. The simulation result shows the PTS can reduce preemptions significantly for multiple priority assignment algorithms. At the meantime OPA-MLL has the largest percentage of schedulable task sets and most potential for reducing preemptions. ©, 2015, Science Press. All right reserved.

引用

页码：1177 / 1186

页数：9

共 19 条

[1]

Guan N., Wang Y., Gu Z., Et al., New schedulability test conditions for non-preemptive scheduling on multiprocessor platforms, Proc of the 29th IEEE Int Real-Time Systems Symp, pp. 137-146, (2008)

[2]

Buttazzo G., Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, (2011)

[3]

Jin H., Wang Q., Wang H., Et al., Scheduling dynamic real-time tasks with preemption threshold, Journal of Computer Research and Development, 41, 3, pp. 393-398, (2004)

[4]

Davis R.I., Burns A., Marinho J., Et al., Global fixed priority scheduling with deferred pre-emption, Proc of the 19th IEEE Int Conf on Embedded and Real-Time Computing Systems and Applications, pp. 1-11, (2013)

[5]

Davis R.I., Burns A., A survey of hard real-time scheduling for multiprocessor systems, ACM Computing Surveys, 43, 4, pp. 1-44, (2011)

[6]

Bertogna M., Cirinei M., Lipari G., New schedulability tests for real-time task sets scheduled by deadline monotonic on multiprocessors, Proc of the 9th Int Conf on Principles of Distributed Systems, pp. 306-321, (2005)

[7]

Baruah S., Techniques for multiprocessor global schedulability analysis, Proc of the 28th IEEE Int Real-Time Systems Symp, pp. 119-128, (2007)

[8]

Cho H., Ravindran B., Jensen E.D., An optimal real-time scheduling algorithm for multiprocessors, Proc of the 27th IEEE Int Real-Time Systems Symp, pp. 101-110, (2006)

[9]

Lundberg L., Lennerstad H., Guaranteeing response times for aperiodic tasks in global multiprocessor scheduling, Real-Time Systems, 35, 2, pp. 135-151, (2007)

[10]

Lundberg L., Lennerstad H., Slack-based global multiprocessor scheduling of aperiodic tasks in parallel embedded real-time systems, Proc of the 6th IEEE/ACS Int Conf on Computer Systems and Applications, pp. 465-472, (2008)

← 1 2 →