Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors

被引：58

作者：

Baruah, SK ^{[1
]}

机构：

[1] Univ N Carolina, Dept Comp Sci, Chapel Hill, NC 27599 USA

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2004年 / 53卷 / 06期

基金：

美国国家科学基金会;

关键词：

Fixed-priority scheduling; Identical multiprocessors; Periodic task systems; Real-time systems; Utilization bounds;

D O I：

10.1109/TC.2004.16

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In fixed-priority scheduling, the priority of a job, once assigned, may not change. A new fixed-priority algorthm for scheduling systems of periodic tasks upon identical multiprocessors is proposed. This algorithm has an achievable utilization of (m + 1)/2 upon m unit-capacity processors. It is proven that this algorithm is optimal from the perspective of achievable utilization in the sense that no fixed-priority algorithm for scheduling periodic task systems upon identical multiprocessors may have an achievable utilization greater than (m + 1)/2.

引用

页码：781 / 784

页数：4

共 11 条

[1]

ANDERSSON B, 2003, THESIS CHALMERS U

[2]

BAKER TP, 2003, TR030202 FLOR STAT U

[3] Priority-driven scheduling of periodic task systems on multiprocessors [J].

Goossens, J ;

Funk, S ;

Baruah, S .

REAL-TIME SYSTEMS, 2003, 25 (2-3) :187-205

[4]

HA R, 1993, UIUCDCSR931833 U ILL

[5]

HA R, 1994, P 14 IEEE INT C DIST

[6]

HA R, 1995, UIUCDCSR951907

[7] SCHEDULING ALGORITHMS FOR MULTIPROGRAMMING IN A HARD-REAL-TIME ENVIRONMENT [J].

LIU, CL ;

LAYLAND, JW .

JOURNAL OF THE ACM, 1973, 20 (01) :46-61

[8]

Liu JaneW.S., 2000, Real-Time Systems, V1st

[9] Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems [J].

López, JM ;

García, M ;

Díaz, JL ;

García, DF .

EUROMICRO RTS 2000: 12TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS, PROCEEDINGS, 2000, :25-33

[10] Deadline-based scheduling of periodic task systems on multiprocessors [J].

Srinivasan, A ;

Baruah, S .

INFORMATION PROCESSING LETTERS, 2002, 84 (02) :93-98

← 1 2 →