Bachelor and Master Theses

Title: Limiting preemptions in real-time tasks on multiprocessors
Subject: Computer Science
Level: Basic or Advanced (contact supervisor)
Description: The purpose of this thesis is to investigate the effectiveness of limited-preemptive scheduling of real-time tasks on multiprocessors. Among others, the following models are the most interesting ones for this thesis.

1. Floating non-preemptive model (Floating-NPR): In this model, suppose a higher priority task is released during the execution of a lower priority task at time instant “t”, the scheduler defers the rescheduling decision to time instant t+L instead of performing a rescheduling operation at t.

2. Fixed non-preemptive regions (Fixed-NPR): In this model each task is composed of several non-preemptive regions. If higher priority tasks are released during the execution of a non-preemptive region of a lower priority task, the scheduler waits until the NPR completes before rescheduling the tasks. Many variants of Fixed-NPR scheduling for multiprocessors can be developed based on which of the currently executing tasks is preempted (remember that many tasks will be executing in parallel on multiprocessors) e.g., 1) preempt the lowest priority task that becomes preemptible or 2) preempt the first executing lower priority task that becomes preemptible.

The thesis aims to investigate one or more of the following questions (please contact supervisor):

1. Scenarios in which the above models can be applied, using case studies (e.g., its applicability in the context of hard real-time systems such as autonomous vehicles)


2. Effects on Worst Case Execution Time analysis estimations, using case studies and simulations

3. Comparison/integration with other limited-preemptive scheduling approaches, such as preemption threshold scheduling


References:

1. Buttazzo, G.C. ; Bertogna, M. ; Gang Yao, Limited Preemptive Scheduling for Real-Time Systems. A Survey, , IEEE Transactions on Industrial Informatics, 2012.

2. K. Jeffay, D. F. Stanat, and C. U. Martel: On non-preemptive scheduling of periodic and sporadic tasks with varying execution priority, Proceedings of the IEEE Real-Time Systems Symposium, 1991.

3. A. Burns: Preemptive priority based scheduling: An appropriate engineering approach, Advances in Real-Time Systems (S. Son, editor), pp. 225–248, 1994.

4. Y. Wang and M. Saksena: Scheduling fixed-priority tasks with preemption threshold, Proceedings of the IEEE Int. Conference on Real-Time Computing Systems and Applications, 1999.

5. S. K. Baruah: The limited-preemption uniprocessor scheduling of sporadic task systems, Proceedings of the Euromicro Conference on Real-Time Systems, July 2005.

6. R. J. Bril, J. J. Lukkien, andW. F. J. Verhaegh: Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption, Real-Time Systems, Vol. 42, No. 1-3, pp. 63–119, 2009.

7. G. Yao, G. Buttazzo and M. Bertogna: Feasibility Analysis under Fixed Priority Scheduling with Limited Preemptions, Real-Time Systems, Vol. 47, No. 3, pp. 198-223, May 2011.

8. Marinho et al., Limited Pre-emptive Global Fixed Task Priority,The 34th Real-Time Systems Symposium , 2013.

9. Abhilash Thekkilakattil, Sanjoy Baruah, Radu Dobrin, Sasikumar Punnekkat, The Global Limited Preemptive Earliest Deadline First Feasibility of Sporadic Real-time Tasks, The 26th Euromicro Conference on Real-Time Systems, 2014.
Proposed: 2015-03-10
IDT supervisor: Abhilash Thekkilakattil
abhilash.thekkilakattil@mdh.se, 021-101689
Examinator: Radu Dobrin
Radu Dobrin
radu.dobrin@mdh.se, 021-107356

Rapport och bilagor

Size

Senaste uppdatering


  • Mälardalen University |
  • Box 883 |
  • 721 23 Västerås/Eskilstuna |
  • 021-101300, 016-153600 |
  • webmaster |
  • Latest update: 2017.10.14