Title :
Implementing task scheduling and event handling in RTOS+
Author :
Ngolah, Cyprian F. ; Wang, Yingxu ; Tan, Xinming
Author_Institution :
Dept. of Electr. & Comput. Eng., Calgary Univ., Alta., Canada
Abstract :
An important component in the kernel of a real-time operating system (RTOS) is the task scheduler. Various solutions on task scheduling, such as priority inheritance and priority ceiling, have been proposed to deal with the priority-inversion problem that arises when a preemptive priority driven scheduling scheme is used. However, the priority inheritance protocol introduces drawbacks such as multiple blocking of tasks and deadlock, while the priority ceiling protocol is hardly supported by most existing real-time operating systems. We first present a formal description of a task scheduling algorithm that provides a solution to the priority inversion problem and eliminates multiple blocking of tasks running in a single processor platform. We use RTPA (real-time process algebra), a formal specification notation, to describe rigorously the architecture, and static and dynamic behaviours of the task scheduler. Our method employs a multi-queue based scheduling system in which all tasks pending on a resource or event are put into different queues with preassigned priorities. This technique eliminates the problem of priority inversion and prevents multiple-blocking and deadlock from happening. Based on the new method, a framework for implementing task scheduling and event handling is implemented for RTOS+, which is a portable real-time operating system developed by the authors.
Keywords :
formal specification; inheritance; operating system kernels; process algebra; processor scheduling; protocols; queueing theory; deadlock; dynamic behaviour; event handling; formal specification notation; multi-queue based scheduling system; multiple task blocking; portable real-time operating system kernel; priority ceiling; priority ceiling protocol; priority inheritance protocol; priority-inversion problem; real-time process algebra; single processor platform; static behavior; task scheduling; Algebra; Dynamic scheduling; Formal specifications; Kernel; Operating systems; Processor scheduling; Protocols; Real time systems; Scheduling algorithm; System recovery;
Conference_Titel :
Electrical and Computer Engineering, 2004. Canadian Conference on
Print_ISBN :
0-7803-8253-6
DOI :
10.1109/CCECE.2004.1349696