NDLI: On Non-Utilization Bounds for Arbitrary Fixed Priority Policies

Content Provider	IEEE Xplore Digital Library
Author	Xue Liu Abdelzaher, T.
Copyright Year	2006
Description	Author affiliation: University of Illinois at Urbana Champaign (Xue Liu)
Abstract	Prior research on schedulability bounds focused primarily on bounding utilization as a means to meet deadline constraints. Non-trivial bounds were found for a handful of scheduling policies in which utilization is directly related to the ability of the policy to meet deadlines. Examples include Rate Monotonic, Deadline Monotonic and EDF scheduling. For most other scheduling policies, however, utilization is not correlated with schedulability. For example, shortest job first can miss deadlines at an arbitrarily low utilization. This raises the question of whether or not some other non-utilization-based metric might be more indicative of schedulability in those cases. This paper answers the above question positively by extending the notion of schedulability bounds, in a uniform manner, to arbitrary priorities and non-utilization metrics. We present a simple function that generates the schedulability metric to be bounded from the definition of a (fixed-priority) scheduling policy, and derive a non-trivial schedulability bound on that metric. It is shown that the generated metrics and bounds are valid in that no deadline misses occur when these bounds are not violated. This result allows efficient real-time admission control to be performed in systems with arbitrary fixed-priority scheduling policies. As an example, we illustrate applying schedulability bounds for admission control to shortest-jobfirst and velocity monotonic scheduling.
Starting Page	167
Ending Page	178
File Size	356507
Page Count	12
File Format	PDF
ISBN	0769525164
ISSN	15453421
DOI	10.1109/RTAS.2006.32
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2006-04-04
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Real time systems Aperiodic tasks. Schedulability analysis Pipelines Throughput Computer science Design engineering Sufficient conditions Real-time scheduling Processor scheduling Admission control Cost function Utilization bounds Testing
Content Type	Text
Resource Type	Article

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

On non-utilization bounds for arbitrary fixed priority policies ∗.

Non-Utilization Bounds and Feasible Regions for Arbitrary Fixed-Priority Policies (2007)

Non-utilization bounds and feasible regions for arbitrary fixed-priority policies.

Nonutilization bounds and feasible regions for arbitrary fixed-priority policies

A Schedulable Utilization Bound for Aperiodic Tasks (2000)

PASS: Priority assignment of real-time tasks with dynamic suspending behavior under fixed-priority scheduling

A new utilization based admission control algorithm for aperiodic tasks with constant time complexity under EDF scheduling

Hybrid-priority real-time scheduling

Fixed-Priority Schedulability of Arbitrary-Deadline Sporadic Tasks upon Periodic Resources

On Non-Utilization Bounds for Arbitrary Fixed Priority Policies

Similar Documents

On non-utilization bounds for arbitrary fixed priority policies ∗.

Non-Utilization Bounds and Feasible Regions for Arbitrary Fixed-Priority Policies (2007)

Non-utilization bounds and feasible regions for arbitrary fixed-priority policies.

Nonutilization bounds and feasible regions for arbitrary fixed-priority policies

A Schedulable Utilization Bound for Aperiodic Tasks (2000)

PASS: Priority assignment of real-time tasks with dynamic suspending behavior under fixed-priority scheduling

A new utilization based admission control algorithm for aperiodic tasks with constant time complexity under EDF scheduling

Hybrid-priority real-time scheduling

Fixed-Priority Schedulability of Arbitrary-Deadline Sporadic Tasks upon Periodic Resources

On Non-Utilization Bounds for Arbitrary Fixed Priority Policies