Change search
ReferencesLink to record
Permanent link

Direct link
An investigation of the dual priorityscheduling paradigm
Mälardalen University, School of Innovation, Design and Engineering.
2012 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Real-time computing paradigm is being pervasively deployed in many critical and non-critical applicationssuch as aerospace and telecommunication systems. Most of these systems employ a preemptiveFixed Priority Scheduling (FPS) policy to schedule real-time tasks. Fixed priority scheduling is knownfor its implementation simplicity and low run-time overheads. However, FPS may not be able to use100% of the processor time, when compared to dynamic priority scheduling policies such as the EarliestDeadline First (EDF) scheduling scheme. Dynamic priority scheduling scheme, on the other hand, has tore-calculate the priorities on-line and hence may have significantly high run-time overheads.

In this thesis, we investigate a novel scheduling scheme, known as the Dual Priority Scheduling scheme,that can potentially guarantee a feasible schedule. The main advantage of using a dual priority scheduleris that, it can achieve the implementation simplicity of a FPS scheme, while potentially assuring 100%processor utilization similar to EDF. Alan Burns proved the optimality of the dual priority scheme for twotasks, leaving its optimality for n tasks as an open problem. We investigate the optimality of dual priorityscheduling for three tasks, using simulations. We propose and evaluate three different approaches: lastchance method, slack method and brute force method, to calculate the dual priorities and the time intervalswhere these priorities are valid.

Our evaluations showed that, of the proposed heuristics, the extended slack method which is a variationof the slack method, performed same as the brute force method. An interesting observation was that,the brute force and the extended slack methods could not schedule the same task sets, nor was the tasksets schedulable using any of the proposed methods.

Place, publisher, year, edition, pages
Keyword [en]
Dual Priority Scheduling, Real-time Systems
National Category
Computer and Information Science
URN: urn:nbn:se:mdh:diva-15444OAI: diva2:558238
2012-09-07, 14:16
Available from: 2012-10-02 Created: 2012-10-02 Last updated: 2012-10-02Bibliographically approved

Open Access in DiVA

fulltext(552 kB)303 downloads
File information
File name FULLTEXT01.pdfFile size 552 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
School of Innovation, Design and Engineering
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 303 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 95 hits
ReferencesLink to record
Permanent link

Direct link