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
相关论文
共 50 条
  • [1] Fixed-Priority Scheduling Policies and Their Non-utilization Bounds
    Chen, Guangyi
    Xie, Wenfang
    ADVANCES IN NEURAL NETWORKS - ISNN 2014, 2014, 8866 : 167 - 174
  • [2] Semi-Partitioned Fixed-Priority Scheduling on Multiprocessors
    Kato, Shinpei
    Yamasaki, Nobuyuki
    15TH IEEE REAL-TIME AND EMBEDDED TECHNOLOGY AND APPLICATION SYMPOSIUM: RTAS 2009, PROCEEDINGS, 2009, : 23 - 32
  • [3] On Partitioned Scheduling of Fixed-Priority Mixed-Criticality Task Sets
    Kelly, Owen R.
    Aydin, Hakan
    Zhao, Baoxian
    TRUSTCOM 2011: 2011 INTERNATIONAL JOINT CONFERENCE OF IEEE TRUSTCOM-11/IEEE ICESS-11/FCST-11, 2011, : 1051 - 1059
  • [4] Deadline-based scheduling of periodic task systems on multiprocessors
    Srinivasan, A
    Baruah, S
    INFORMATION PROCESSING LETTERS, 2002, 84 (02) : 93 - 98
  • [5] Preference-oriented fixed-priority scheduling for periodic real-time tasks
    Begam, Rehana
    Xia, Qin
    Zhu, Dakai
    Aydin, Hakan
    JOURNAL OF SYSTEMS ARCHITECTURE, 2016, 69 : 1 - 14
  • [6] Generalizing fixed-priority scheduling for better schedulability in mixed-criticality systems
    Chen, Yao
    Shin, Kang G.
    Xiong, Huagang
    INFORMATION PROCESSING LETTERS, 2016, 116 (08) : 508 - 512
  • [7] Preference-Oriented Fixed-Priority Scheduling for Real-Time Systems
    Begam, Rehana
    Zhu, Dakai
    Aydin, Hakan
    2014 IEEE 12TH INTERNATIONAL CONFERENCE ON DEPENDABLE, AUTONOMIC AND SECURE COMPUTING (DASC)/2014 IEEE 12TH INTERNATIONAL CONFERENCE ON EMBEDDED COMPUTING (EMBEDDEDCOM)/2014 IEEE 12TH INTERNATIONAL CONF ON PERVASIVE INTELLIGENCE AND COMPUTING (PICOM), 2014, : 159 - +
  • [8] Interference-aware fixed-priority schedulability analysis on multiprocessors
    Risat Mahmud Pathan
    Jan Jonsson
    Real-Time Systems, 2014, 50 : 411 - 455
  • [9] An Exact Schedulability Analysis for Global Fixed-Priority Scheduling of the AER Task Model
    Thilakasiri, Thilanka
    Becker, Matthias
    2023 28TH ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE, ASP-DAC, 2023, : 326 - 332
  • [10] Nonutilization Bounds and Feasible Regions for Arbitrary Fixed-Priority Policies
    Liu, Xue
    Abdelzaher, Tarek
    ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2011, 10 (03)
12345