NDLI: Complexity of scheduling real-time tasks subjected to cache-related preemption delays

Content Provider	IEEE Xplore Digital Library
Author	Phavorin, G. Richard, P. Maiza, C.
Copyright Year	2015
Description	Author affiliation: LIAS, Univ. de Poitiers, Poitiers, France (Phavorin, G.; Richard, P.) \|\| Grenoble INP, Grenoble, France (Maiza, C.)
Abstract	We consider the computational complexity problems of scheduling hard real-time tasks subjected to cache-related preemption delays upon uniprocessor platforms. Several schedulability analyses have been proposed in the literature to explicitly take into account preemption delays due to loss of cache affinity. But, these previous results do not study the complexity of taking scheduling decisions under preemption delay constraints and only focus on classical real-time schedulers (e.g., Rate Monotonic, Earliest Deadline First). In this paper, we focus on the computational complexity of taking scheduling decisions to meet task deadlines while minimizing cache-related preemption delay effects. We design two basic cache-related scheduling problems that are the most simple NP-hard problems to cover the largest set of intractable real-world cache-related scheduling problems. We establish several NP-hardness results for preemptive systems. These results prove that tighter timing analysis leads in practice to harder real-time scheduling problems. These two basic NP-hard scheduling problems are the following: (i) scheduling with cache-related preemption delays and (ii) scheduling with information about the cache state and the sequence of requested memory blocks for every task. We also prove for the first problem that neither fixed-task nor fixed-job priority-based scheduling algorithms can be optimal.
Starting Page	1
Ending Page	8
File Size	264780
Page Count	8
File Format	PDF
e-ISBN	9781467379298
DOI	10.1109/ETFA.2015.7301519
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-09-08
Publisher Place	Luxembourg
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Processor scheduling Delays Schedules Real-time systems Silicon Cache memory
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

Multiprocessor Scheduling with Cache Related Preemption Delays

Cache-Aware Task Partitioning for Multicore Real-Time Systems

Addressing cache related preemption delay in fixed priority assignment

Minimizing Cache Overhead via Loaded Cache Blocks and Preemption Placement

Minimizing cache related preemption delay in preemptive scheduler

Memory efficient global scheduling of real-time tasks

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

A New Notion of Useful Cache Block to Improve the Bounds of Cache-Related Preemption Delay

Cache-Related Preemption Delays and Real-Time Scheduling: A Survey for Uniprocessor Systems

Complexity of scheduling real-time tasks subjected to cache-related preemption delays

Similar Documents

Multiprocessor Scheduling with Cache Related Preemption Delays

Cache-Aware Task Partitioning for Multicore Real-Time Systems

Addressing cache related preemption delay in fixed priority assignment

Minimizing Cache Overhead via Loaded Cache Blocks and Preemption Placement

Minimizing cache related preemption delay in preemptive scheduler

Memory efficient global scheduling of real-time tasks

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

A New Notion of Useful Cache Block to Improve the Bounds of Cache-Related Preemption Delay

Cache-Related Preemption Delays and Real-Time Scheduling: A Survey for Uniprocessor Systems

Complexity of scheduling real-time tasks subjected to cache-related preemption delays