DESIGN PROCESS OF REAL-TIME OPERATING SYSTEMS (RTOS) - Software Design for Six-Sigma: A Roadmap for Excellence - page 69

running simultaneously. When the time quantum has expired, the schedule preempts
the current task allowing the next task to run.
The operating system kernel also must allow preemption in a real-time environ-
ment. For example, a task with a lower priority currently may be executing and it
performs a system call. Then a higher priority task tries to interrupt the current task
so that it can execute. The operating system must be able to allow for the new task
to run within a certain amount of time; otherwise there is no guarantee that the new
task will meet its deadline.
Because time is of the essence, the worsts case execution time (WCET) must be
calculated for all tasks. This is especially difficult when tasks are preempted, but
the operating system kernel must provide WCET required for system calls before it
allows preemption to occur (Tan & Mooney, 2007). Table 3.4 shows task scheduling
design options and comparison.

3.4.4 Static Scheduling

A multitasking operating system must include a method to schedule tasks. One of
the basic methods of scheduling tasks is static scheduling. With static scheduling, the
priorities assigned to tasks does not change; it stays constant throughout the execution
of the program.
One of the most common and oldest static scheduling algorithms is called round-
robin. With round-robin, all tasks are treated as equals and each is allowed a prede-
termined time quantum in which they can use the CPU to execute their instructions.
When their time quantum expires, an interrupt occurs and the old task is switched
out and the new task is switched in. Although simple to implement, the round-robin
task scheduler does not give preference to tasks that are more important than other
tasks. These tasks may be more critical to the system, but round-robin does not give
preferential treatment.
Another type of scheduling algorithm is called rate monotonic (RM). With RM,
tasks are assigned a fixed priority based on the frequency of which they run. For
example, if there are three tasks, that run at 1 ms, 2 ms, and 10 ms. The task running
at 1 ms would have higher priority, and the one running at 10 ms would have the
lowest priority. This type of scheduling is the most efficient for fixed priority, meaning
that if a system cannot meet its deadlines with this algorithm, there is no other fixed
priority algorithm that would. A disadvantage to the RM scheduling method is that
the processor cannot be used fully and even on relatively low utilization, such as
70%, tasks may miss their deadline (Steward & Barr, 2002). However, research over
the past few years has been performed, and the algorithm has been modified to allow
for maximum processor utilization. The name of this modified algorithm is called the
delayed rate monotonic (DRM), and it has been proven that, in some cases, systems
that run safely on DRM are unsafe on RM (Naghibzadeh, 2002). In summary, RM
scheduling is the most optimal static scheduling algorithm. It is easy to implement,
and the concept is easy to understand. Many users are familiar with the algorithm, and
it is implemented on many multitasking, interrupt-driven systems. Table 3.5 shows
static scheduling design options and comparison.