Bachelor and Master Theses

Title: Operating System Support for Limited-Preemptive Scheduling on Multiprocessors
Subject: Computer Science
Level: Advanced
Description: The main goal of this thesis is to investigate the operating system support required to implement limited-preemptive scheduling and do a performance evaluation. In order to build on the best of fully preemptive and non-preemptive scheduling, several limited preemptive scheduling models have been proposed.

This thesis will consider the following limited preemptive scheduling models:

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.

Moreover, under multiprocessor limited preemptive scheduling, there are two approaches to preemption:

1. Eager Preemption Approach (EPA): Under this approach, a high priority task that is released will preempt the first lower priority executing task that finishes executing a non-preemptive region instead of the lowest priority one.

2. Lazy Preemption Approach (LPA): Under this approach, a high priority task that is released will wait for the lowest priority task to finish executing its non-preemptive region.

This thesis aims to identify and implement operating system support mechanisms to enable limited preemptive scheduling on a popular platform. Although some studies simulate a limited-preemptive scheduler using resource sharing protocols, this can be quite costly in terms of the overheads in the schedule.

Specifically, the main goals of this thesis are as follows:

1.Identify and implement operating system support required to implement floating non-preemptive region scheduler

2.Identify and implement operating system support required to handle fixed preemption points inserted in the task code

3. Measure overheads due to the OS mechanisms that enable limited-preemptive scheduling

4. Compare the the proposed mechanisms with resource sharing protocols that are typically used for enforcing limited-preemptive scheduling

The potential candidates for the platform include:

1. LITMUS^RT: http://www.litmus-rt.org/
2. SCHED_DEADLINE: https://www.kernel.org/doc/Documentation/scheduler/sched-deadline.txt , http://retis.sssup.it/~jlelli/talks/rts-like14/SCHED_DEADLINE.pdf
3. ERIKA: http://erika.tuxfamily.org/drupal/
4. Minix: http://www.minix3.org/ (this is not a real-time OS but is potentially extendable to make it real-time)


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.
Start date: 2015-09-07
Prel. end date: 2016-02-15
Presentation date: 2016-01-28
Student: Dennis Magnusson dmn07002@student.mdh.se
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