NDLI: Time-Reversibility of Schedulability Tests

Content Provider	IEEE Xplore Digital Library
Author	Jinkyu Lee
Copyright Year	2014
Description	Author affiliation: Dept. of Comput. Sci. & Eng., Sungkyunkwan Univ. (SKKU), Seoul, South Korea (Jinkyu Lee)
Abstract	For timing guarantees of a set of real-time tasks under a target scheduling algorithm, a number of schedulability tests have been studied. However, there still exist many task sets that are potentially schedulable by a target scheduling algorithm, but proven schedulable by none of existing schedulability tests, especially on a multiprocessor platform. In this paper, we propose a new notion of time-reversibility of schedulability tests, which yields tighter schedulability guarantees by viewing real-time scheduling under a change in the sign of time. To this end, we first define the notion of a time-reversed scheduling algorithm against a target scheduling algorithm, for example, the time-reversed scheduling algorithm against EDF (Earliest Deadline First) is LCFS (Last-Come, First-Served), and the converse also holds. Then, a schedulability test for a scheduling algorithm is said to be time-reversible with respect to schedulability, if all task sets deemed schedulable by the test are also schedulable by its time-reversed scheduling algorithm. To exploit the notion of time-reversibility for tighter schedulability guarantees, we not only prove time-reversibility of an existing schedulability test, but also develop a new time-reversible schedulability test, both of which cover additional schedulable task sets. Next, we generalize the time-reversibility theory towards partial execution. Utilizing the notion, we can assure the schedulability of a task under a target scheduling algorithm in a divide-and-conquer manner: (i) the first some units of execution guaranteed by a schedulability test for the scheduling algorithm, and (ii) the remaining execution guaranteed by a time-reversible (with respect to partial execution) schedulability test for its time-reversed scheduling algorithm. Such a divide-and-conquer approach has not been directly applied to existing schedulability tests in that they cannot address (ii) effectively. As a case study, this paper develops RTA (Response-Time Analysis) for LCFS, proves its time-reversibility, and applies the divide-and-conquer approach to the test along with an existing EDF schedulability test. Our simulation results show that the time-reversibility theory helps to find up to 13.1% additional EDF-schedulable task sets on a multiprocessor platform.
Sponsorship	IEEE Comput. Soc.
Starting Page	294
Ending Page	303
File Size	308657
Page Count	10
File Format	PDF
ISBN	9781479972883
ISSN	10528725
DOI	10.1109/RTSS.2014.18
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2014-12-02
Publisher Place	Italy
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Scheduling algorithms Time factors Interference Silicon Scheduling Real-time systems Optimal scheduling divide-and-conquer apporoach real-time scheduling time-reversibility schedulability analysis
Content Type	Text
Resource Type	Article
Subject	Computer Networks and Communications Hardware and Architecture Software

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

Controlling Preemption for Better Schedulability in Multi-Core Systems

Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks

LLF Schedulability Analysis on Multiprocessor Platforms

Schedulability Analysis for a Mode Transition in Real-Time Multi-core Systems

Optimal Fixed Priority Scheduling with Deferred Pre-emption

MC-Fluid: Fluid Model-Based Mixed-Criticality Scheduling on Multiprocessors

Scheduling Arbitrary-Deadline Sporadic Task Systems on Multiprocessors

Exploiting precedence relations in the schedulability analysis of distributed real-time systems

Techniques for Multiprocessor Global Schedulability Analysis

Time-Reversibility of Schedulability Tests

Similar Documents

Controlling Preemption for Better Schedulability in Multi-Core Systems

Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks

LLF Schedulability Analysis on Multiprocessor Platforms

Schedulability Analysis for a Mode Transition in Real-Time Multi-core Systems

Optimal Fixed Priority Scheduling with Deferred Pre-emption

MC-Fluid: Fluid Model-Based Mixed-Criticality Scheduling on Multiprocessors

Scheduling Arbitrary-Deadline Sporadic Task Systems on Multiprocessors

Exploiting precedence relations in the schedulability analysis of distributed real-time systems

Techniques for Multiprocessor Global Schedulability Analysis

Time-Reversibility of Schedulability Tests