CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Design of an efficient ready queue for earliest-deadline-first (EDF) scheduler

Risat Mahmud Pathan (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
Proceedings of the 2016 Design, Automation and Test in Europe Conference and Exhibition, DATE 2016 p. 293-296. (2016)
[Konferensbidrag, refereegranskat]

Although dynamic-priority-based EDF algorithm is known to be theoretically optimal for scheduling sporadic real-time tasks on uniprocessor, fixed-priority (FP) scheduling is mostly used in practice. One of the main reasons for FP scheduling being popular in the industry is its efficient implementation: operations on the ready queue can be done in constant time. On the other hand, ready queue of EDF scheduler is generally implemented as a priority queue, for example, using a binary min-heap data structure in which (insertion/deletion) operation cannot be done in constant time. This paper proposes a new design of ready queue for EDF scheduler: a simple data structure for the ready queue and efficient operations to insert and remove task control blocks (TCBs) to and from the ready queue are proposed. Insertion of a TCB of a newly released job (that cannot preempt the currently-executing job) is done in non-constant time. However, insertion of a TCB of a preempted job or the removal of the TCB of job having the highest EDF priority from the ready queue can be done in constant time. Simulation using randomly generated task sets shows that the overhead of managing jobs in our proposed ready queue for EDF scheduler is significantly lower than that of other approaches. We believe that theoretically optimal EDF algorithm implemented based on our proposed ready-queue data structure will make EDF popular in industry.


Article number 7459325



Denna post skapades 2016-07-05.
CPL Pubid: 239000

 

Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datorteknik (Chalmers)

Ämnesområden

Datorteknik

Chalmers infrastruktur