NDLI: Using a lag-balance property to tighten tardiness bounds for global EDF

Content Provider	Springer Nature Link
Author	Valente, Paolo
Copyright Year	2015
Abstract	Several tardiness bounds for global EDF and global-EDF-like schedulers have been proposed over the last decade. These bounds contain a component that is explicitly or implicitly proportional to how much the system may be cumulatively lagging behind, in serving tasks, with respect to an ideal schedule. This cumulative lag is in its turn upper-bounded by upper-bounding each per-task component in isolation, and then summing individual per-task bounds. Unfortunately, this approach leads to an over-pessimistic cumulative upper bound. In fact, it does not take into account a lag-balance property of any work-conserving scheduling algorithm. In this paper we show how to get a new tardiness bound for global EDF by integrating this property with the approach used to prove the first tardiness bounds proposed in the literature. In particular, we compute a new tardiness bound for implicit-deadline tasks, scheduled by preemptive global EDF on a symmetric multiprocessor. According to our experiments, as the number of processors increases, this new tardiness bound becomes tighter and tighter than the tightest bound available in the literature, with a maximum tightness improvement of 29 %. A negative characteristic of this new bound is that computing its value takes an exponential time with a brute-force algorithm (no faster exact or approximate algorithm is available yet). As a more general result, the property highlighted in this paper might help to improve the analysis for other scheduling algorithms, possibly on different systems and with other types of task sets. In this respect, our experimental results also point out the following negative fact: existing tardiness bounds for global EDF, including the new bound we propose, may become remarkably loose if every task has a low utilization (ratio between the execution time and the minimum inter-arrival time of the jobs of the task), or if the sum of the utilizations of the tasks is lower than the total capacity of the system.
Starting Page	486
Ending Page	561
Page Count	76
File Format	PDF
ISSN	09226443
Journal	Real-Time Systems
Volume Number	52
Issue Number	4
e-ISSN	15731383
Language	English
Publisher	Springer US
Publisher Date	2015-08-15
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multicore Tardiness EDF Computer Systems Organization and Communication Networks Communications Engineering, Networks Special Purpose and Application-Based Systems Performance and Reliability Control, Robotics, Mechatronics
Content Type	Text
Resource Type	Article
Subject	Control and Optimization Computer Networks and Communications Control and Systems Engineering Electrical and Electronic Engineering Computer Science Applications Modeling and Simulation

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling

Tardiness bounds under global EDF scheduling on a multiprocessor

Generalized tardiness bounds for global multiprocessor scheduling

Implementation and evaluation of global and partitioned scheduling in a real-time OS

Global EDF scheduling for parallel real-time tasks

Guest editorial: special issue on multicore systems

Improved multiprocessor global schedulability analysis

Partitioned EDF scheduling: a closer look

An analysis of global edf schedulability for arbitrary-deadline sporadic task systems

Using a lag-balance property to tighten tardiness bounds for global EDF

Similar Documents

Fair lateness scheduling: reducing maximum lateness in G-EDF-like scheduling

Tardiness bounds under global EDF scheduling on a multiprocessor

Generalized tardiness bounds for global multiprocessor scheduling

Implementation and evaluation of global and partitioned scheduling in a real-time OS

Global EDF scheduling for parallel real-time tasks

Guest editorial: special issue on multicore systems

Improved multiprocessor global schedulability analysis

Partitioned EDF scheduling: a closer look

An analysis of global edf schedulability for arbitrary-deadline sporadic task systems

Using a lag-balance property to tighten tardiness bounds for global EDF