Process scheduling in QNX

bridged with qdn.public.qnxrtp.os
Post Reply
Jitendra Sasmal

Process scheduling in QNX

Post by Jitendra Sasmal » Tue Nov 25, 2003 8:40 am

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

Alain Bonnefoy

Re: Process scheduling in QNX

Post by Alain Bonnefoy » Tue Nov 25, 2003 12:31 pm

Hi,
I suppose the following could answer:
http://www.qnx.com/developer/docs/momen ... SCHEDULING

Alain.

Jitendra Sasmal a écrit:
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



Steve Furr

Re: Process scheduling in QNX

Post by Steve Furr » Tue Nov 25, 2003 3:59 pm

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

Jitendra Sasmal

Re: Process scheduling in QNX

Post by Jitendra Sasmal » Thu Nov 27, 2003 10:49 am

Hi,
Thank you very much for your valuable information.

With Regards
Jitendra Sasmal
SPA Computers Ltd.(Distributor of QNX RTOS in INDIA)
Bangalore,INDIA

Steve Furr wrote:
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

David Gibbs

Re: Process scheduling in QNX

Post by David Gibbs » Thu Nov 27, 2003 2:59 pm

Jitendra Sasmal <sasmal_jk@rediffmail.com> wrote:

An important note -- your subject says "process" scheduling, and
your question uses the term "tasks".

Under QNX6, processes are not schedulable entities -- threads are
the schedulable entity. (And different threads in the same process
are scheduled independently, and can have different priorites and
scheduling rules.)

-David
--
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.

Post Reply

Return to “qdn.public.qnxrtp.os”