NDLI: Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Please wait, while we are loading the content...

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Content Provider	Springer Nature Link
Author	Bril, Reinder J. Lukkien, Johan J. Verhaegh, Wim F. J.
Copyright Year	2009
Abstract	Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions.This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.
Starting Page	63
Ending Page	119
Page Count	57
File Format	PDF
ISSN	09226443
Journal	Real-Time Systems
Volume Number	42
Issue Number	1-3
e-ISSN	15731383
Language	English
Publisher	Springer US
Publisher Date	2009-04-28
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Level-i active period Level-i busy period Worst-case response time Worst-case occupied time Periodic tasks Fixed-priority scheduling Deferred preemption Real-time systems Control , Robotics, Mechatronics Communications Engineering, Networks Performance and Reliability Special Purpose and Application-Based Systems Computer Systems Organization and Communication Networks
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

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Existing worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption is too optimistic

Worst-Case Response Time Analysis of Real-Time Tasks under Fixed-Priority Scheduling with Deferred Preemption Revisited

Towards best-case response times of real-time tasks under fixed-priority scheduling with deferred preemption

Approximation techniques for response-time analysis of static-priority tasks

Approximation scheme for real-time tasks under fixed-priority scheduling with deferred preemption

Worst case response time analysis of sporadic graph tasks with fixed priority scheduling on a uniprocessor

Response time analysis for fixed priority real-time systems with energy-harvesting

On the compatibility of exact schedulability tests for global fixed priority pre-emptive scheduling with Audsley’s optimal priority assignment algorithm

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Similar Documents

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Existing worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption is too optimistic

Worst-Case Response Time Analysis of Real-Time Tasks under Fixed-Priority Scheduling with Deferred Preemption Revisited

Towards best-case response times of real-time tasks under fixed-priority scheduling with deferred preemption

Approximation techniques for response-time analysis of static-priority tasks

Approximation scheme for real-time tasks under fixed-priority scheduling with deferred preemption

Worst case response time analysis of sporadic graph tasks with fixed priority scheduling on a uniprocessor

Response time analysis for fixed priority real-time systems with energy-harvesting

On the compatibility of exact schedulability tests for global fixed priority pre-emptive scheduling with Audsley’s optimal priority assignment algorithm

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption