The key is that there is a difference between scheduling and dispatch
(“scheduling”).
A rate monotic schedule is not usually implemented as a runtime scheduler,
but
mapped through static priority analysis to a priority scheme. When this is
done, it is mandatory that the dispatcher (“scheduler”) institute fixed
priority
preemptive dispatching in order for a feasible schedule to not miss
deadlines.
The dispatcher has no notion of deadlines, only priority.
This entails that the most eligible (not blocked) process at any point in
time
will be running (the highest priority). In the general case, selection of
the most
eligible process would be O(log n) with a heap implementation, but from a
practical
perspective, separate ready queues may be maintained for each priority level
to allow constant time insertions and removals. This is what Neutrino does.
Once selected to run, the process may continue to execute until it either
(a)
blocks (run-to-block), or (b) exceeds a quantum interval of time (time
slicing). In
POSIX terms, these are known as FIFO and RR (Round robin) scheduling,
respectively. Theoretically, neither of these impacts the feasibility of a
rate
monotonic schedule; however, RR scheduling can introduce scheduling overhead
(a non-schedulable activity), which if large enough may render a
theoretically
feasible RMS schedule infeasible.
EDF scheduling is actually not implemented by many (i.e. virtually no COTS)
RTOS implementations, and actually keeps track of a deadline.
“Jitendra Sasmal” <sasmal_jk@rediffmail.com> wrote in message
news:bpv4ii$kcr$1@tiger.openqnx.com…
Hi,
I want to know about the scheduling algorithm that QNX uses to preempt a
task.Is it like Rate Manotonic scheduling or Earliest Deadline First
scheduling ?One more thing I want to know, in QNX the context switching is
very fast. How it manages internally to manage the context switch fast.In
one of the article about the basic concepts of RTOS which I got from
internet, I found that RTOS generally uses “incrementally updated table”
to
avoid the search of a long queue of process to know which process should
run
next.If it is like this then please give some more details about the
management of “incrementally updated table”.
Thanking you in advance.
Jitendra Sasmal