Hi,
I want to get the exact definition of ticksize and how it affects the
performance of real-time application.
Thanks,
Belinda
Belinda <yye@is2.dal.ca> wrote:
Hi,
I want to get the exact definition of ticksize and how it affects the
performance of real-time application.
Ticksize, also called clock period or clock resolution, is the frequency
at which the operating system gets an interrupt from its time source,
and from this becomes the fundamental resolution (quantum) for time
and time-based operations for the operating system. (There are some
exceptions, e.g. ClockCycles() which essentially dives under the OS
to some hardware to get something with finer detail.)
There are two main ways this affects a real-time application:
– if you are doing anything that is based on an OS timer (sleep,
timer_create, clock_gettime, etc), then you can not get woken
up more frequently, or with a tighter accuracy than the ticksize
Decreasing the ticksize will give you more precision.
– there is an interrupt load due to handling the hardware interrupt.
Decreasing the ticksize, will increase the interrupt load, increasing
overall system overhead, increase average scheduling latency, potentially
increase worst-case scheduling, and potentially increase you interrupt
latency depending on your hardware interrupt priorities – essentially
it will slow down your whole system
Choosing a ticksize is based on the trade-off between the conflicting
concerns above.
There is a third way things may be affected, though this is less
likely for a real-time application. The timeslice, that is, the
length of time a Round-Robin scheduled thread will hold the CPU before
being moved from the head to the tail of the READY queue at its
priority is 4* the ticksize, so changing the ticsize will change the
timeslice. Most real-time applications are not timeslicing, they
are event driven, so this does not usually affect them.
In the SMP case, there may be a scheduling reevaluation and migration of
threads between CPUs on each timeslice as well.
Hope this helps,
-David
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.
“Bill Caroselli (Q-TPS)” <QTPS@earthlink.net> wrote:
“David Gibbs” <> dagibbs@qnx.com> > wrote in message
news:aiuaki$agq$> 1@nntp.qnx.com> …
In the SMP case, there may be a scheduling reevaluation and migration of
threads between CPUs on each timeslice as well.Is this true? A running thread can be moved to another CPU?
Why not? Imagine a high-priority thread that has the affinity mask
set to the CPU that your thread is currently using. Suddenly, this
high-priority thread goes READY. It’ll then go RUNNING and your
thread gets bumped. IF YOU ARE LUCKY your thread will get bumped
to another CPU…
The “IF YOU ARE LUCKY” part is based on my understanding of the SMP
scheduling algorithm. Inuitively, you’d figure that if you had N
CPUs then N of the highest priority threads are running, guaranteed,
but unfortunately that’s not necessarily the case. As I understand
it only the highest priority READY thread is guaranteed to be RUNNING
on a processor.
Someone kick me if I’m wrong!
Cheers,
-RK
–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.
“David Gibbs” <dagibbs@qnx.com> wrote in message
news:aiuaki$agq$1@nntp.qnx.com…
In the SMP case, there may be a scheduling reevaluation and migration of
threads between CPUs on each timeslice as well.Is this true? A running thread can be moved to another CPU?
“Robert Krten” <nospam86@parse.com> wrote in message
news:aiueck$6um$1@inn.qnx.com…
“Bill Caroselli (Q-TPS)” <> QTPS@earthlink.net> > wrote:
“David Gibbs” <> dagibbs@qnx.com> > wrote in message
news:aiuaki$agq$> 1@nntp.qnx.com> …
In the SMP case, there may be a scheduling reevaluation and migration
of
threads between CPUs on each timeslice as well.Is this true? A running thread can be moved to another CPU?
Why not? Imagine a high-priority thread that has the affinity mask
set to the CPU that your thread is currently using. Suddenly, this
high-priority thread goes READY. It’ll then go RUNNING and your
thread gets bumped. IF YOU ARE LUCKY your thread will get bumped
to another CPU…OK. This I can understand. It got bumped off the CPU it was running on by
a higher priority thread, period. Then it got rescheduled.
I misread Dave’s statement. I interpreted his ‘timeslice’ to mean clock
tick. And that an equal priority thread that became ready could bump it to
another CPU before it’s timeslice was done. This I assume CAN NOT happen.
Right? Of course at the end of it’s timeslice it gets moved to the back of
the ready queue so it can next run anywhere.
Just curious. When the scheduler looks at scheduling the next thread(s),
does it try to look N threads deep where N is the number of available CPUs?
I.E. If CPUs 2 & 4 are available and threads A and B are ready but not
running, if it just assigns the first thread to the first CPU and then looks
at the second thread, which maybe isn’t allowed to run on the second CPU, OR
can it look at the second thread, determine that is can satisfy both threads
if it assigns the second thread to the first available CPU and the first
thread to the second CPU? (How’s that for a run on sentence?)
“Bill Caroselli (Q-TPS)” <QTPS@EarthLink.net> wrote in message
news:aiufp6$8bj$1@inn.qnx.com…
Just curious. When the scheduler looks at scheduling the next thread(s),
does it try to look N threads deep where N is the number of available
CPUs?
I.E. If CPUs 2 & 4 are available and threads A and B are ready but not
running, if it just assigns the first thread to the first CPU and then
looks
at the second thread, which maybe isn’t allowed to run on the second CPU,
OR
can it look at the second thread, determine that is can satisfy both
threads
if it assigns the second thread to the first available CPU and the first
thread to the second CPU? (How’s that for a run on sentence?)
That’s a lot of work for a scheduler, particularly if it has to run every
time a thread finishes its timeslice/execution period. I suppose it could be
written that way, but it would probably start to drain CPU time away from
the very threads it’s supposed to be making more efficient. More than
likely, if there’s much need to restrict which threads run on which
processors, there will be some sort of inherent thread-level structure that
specifies how they’re to be scheduled. For example, I worked briefly with a
chip that had eight ALU’s, each of which was capable of performing a limited
set of operations and had access to only half of the registers (four ALU’s
for the A registers, and four almost identical ALU’s for the B registers).
The assembly language was written so that operations could be scheduled
inherently between ALU’s. Each instruction contained an operation (or NOP)
to be performed on each of the eight ALU’s simultaneously, and either the
programmer or a compiler had to decide how best to schedule instructions to
maximize ALU usage. I know it’s not the same as CPU scheduling, but perhaps
a similar technique could be used to do what you’re suggesting.
- Matt Katinas
Robert Krten <nospam86@parse.com> wrote:
“Bill Caroselli (Q-TPS)” <> QTPS@earthlink.net> > wrote:
Why not? Imagine a high-priority thread that has the affinity mask
set to the CPU that your thread is currently using. Suddenly, this
high-priority thread goes READY. It’ll then go RUNNING and your
thread gets bumped. IF YOU ARE LUCKY your thread will get bumped
to another CPU…The “IF YOU ARE LUCKY” part is based on my understanding of the SMP
scheduling algorithm. Inuitively, you’d figure that if you had N
CPUs then N of the highest priority threads are running, guaranteed,
but unfortunately that’s not necessarily the case.
Actually, it would be better to phrase it as “fortunately that is
not the case”. That is the easy, and obvious way to schedule things
as you mention – unfortunately, scheduling that way made system
throughput far too slow, in fact, in some cases things could run
slower with 2 CPUs than with one.
The big issue with SMP scheduling is to reduce cache coherency issues.
As I understand
it only the highest priority READY thread is guaranteed to be RUNNING
on a processor.
If there is a single highest priority READY thread, it will be RUNNING.
If there are several at the same priority, you are only guaranteed that
the one at the head of the queue at its priority will be running. (That
is, the same guarantee as in the single CPU case.) The others may or
may not be running.
An example of where this might be happen:
Thread A – server – priority 10 RUNNING on CPU1
Thread B – other – priority 8 RUNNING on CPU2
Thread A replies to thread C, after the reply:
Thread A – server – priority 10 RUNNING on CPU1
Thread C – client – priority 10 READY
Thread B – other – priority 8 RUNNING on CPU2
Thread C will get to run either when thread A blocks, or when the
next timeslice is hit and a global re-evaluation is done.
The reason: usually thread C is about to deal with data that thread A
has modified, therefor thread C’s data is in CPU1’s cache, and Thread A
will usually call MsgReceive() to block itself “soon”. If thread C was
immediately scheduled on CPU2, all of the “dirty” data in CPU1’s cache
would have to be transferred to CPU2’s cache/memory causing lots of
interprocessor interrupts and overhead. But, if thread C waits just
a little bit until thread A blocks (the usual case) it can run on the
same CPU and avoid all those inter-CPU transactions. Of course, if
thread A doesn’t block… well thread C will have to wait for the next
timeslice interval, at which point it will be run on some other CPU.
(In the single-CPU case, thread C would not run until thread A blocked
anyway.)
Hope this helps to clarify what I meant by timeslice affecting
scheduling in some cases for SMP.
-David
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.
“Bill Caroselli (Q-TPS)” <QTPS@earthlink.net> wrote:
In the SMP case, there may be a scheduling reevaluation and migration
of between CPUs on each timeslice as well.Is this true? A running thread can be moved to another CPU?
I misread Dave’s statement. I interpreted his ‘timeslice’ to mean clock
tick. And that an equal priority thread that became ready could bump it to
another CPU before it’s timeslice was done. This I assume CAN NOT happen.
Right? Of course at the end of it’s timeslice it gets moved to the back of
the ready queue so it can next run anywhere.
I’ve explained in more detail what I meant about re-evaluation on the
timeslice boundary in another post.
A thread will not generally get bumped from one CPU to another by
an equal priority thread. It may in the processor locked cases, but
I don’t know what the algorithms are in that case.
Just curious. When the scheduler looks at scheduling the next thread(s),
does it try to look N threads deep where N is the number of available CPUs?
I.E. If CPUs 2 & 4 are available and threads A and B are ready but not
running, if it just assigns the first thread to the first CPU and then looks
at the second thread, which maybe isn’t allowed to run on the second CPU, OR
can it look at the second thread, determine that is can satisfy both threads
if it assigns the second thread to the first available CPU and the first
thread to the second CPU? (How’s that for a run on sentence?)
My understanding is that it doesn’t look multiple threads deep – most of
the time it doesn’t need to, so this would cost more than it would save in
the few times it does need to.
Also, locking threads to a particular processor is not, in my understanding
the usual case, but rather a fairly rare exception.
-David
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.
A lucid and informative post (as I’ve come to expect from you 
, thanks
for taking the time to put it together.
Let me see if I understand this properly? Only the highest priority
process is guarenteed to be scheduled when it becomes ready. Other
processes may or may not be running in priority order. This is more
efficient as rescheduling can cause a loss of useful cache contents?
Another way of saying this might be, one processor is used for real
time, and all others balance real time and throughput?
–
Mitchell Schoenbrun --------- maschoen@pobox.com
What does it means for FIFO sched. on two or more CPU’s.
Two procs with the same prio FIFO scheduled can run ‘parallel’ if more than
one CPU is present?
hmmm…?
“David Gibbs” <dagibbs@qnx.com> schrieb im Newsbeitrag
news:aj0itm$1dm$1@nntp.qnx.com…
Robert Krten <> nospam86@parse.com> > wrote:
“Bill Caroselli (Q-TPS)” <> QTPS@earthlink.net> > wrote:Why not? Imagine a high-priority thread that has the affinity mask
set to the CPU that your thread is currently using. Suddenly, this
high-priority thread goes READY. It’ll then go RUNNING and your
thread gets bumped. IF YOU ARE LUCKY your thread will get bumped
to another CPU…The “IF YOU ARE LUCKY” part is based on my understanding of the SMP
scheduling algorithm. Inuitively, you’d figure that if you had N
CPUs then N of the highest priority threads are running, guaranteed,
but unfortunately that’s not necessarily the case.Actually, it would be better to phrase it as “fortunately that is
not the case”. That is the easy, and obvious way to schedule things
as you mention – unfortunately, scheduling that way made system
throughput far too slow, in fact, in some cases things could run
slower with 2 CPUs than with one.The big issue with SMP scheduling is to reduce cache coherency issues.
As I understand
it only the highest priority READY thread is guaranteed to be RUNNING
on a processor.If there is a single highest priority READY thread, it will be RUNNING.
If there are several at the same priority, you are only guaranteed that
the one at the head of the queue at its priority will be running. (That
is, the same guarantee as in the single CPU case.) The others may or
may not be running.An example of where this might be happen:
Thread A – server – priority 10 RUNNING on CPU1
Thread B – other – priority 8 RUNNING on CPU2Thread A replies to thread C, after the reply:
Thread A – server – priority 10 RUNNING on CPU1
Thread C – client – priority 10 READY
Thread B – other – priority 8 RUNNING on CPU2Thread C will get to run either when thread A blocks, or when the
next timeslice is hit and a global re-evaluation is done.The reason: usually thread C is about to deal with data that thread A
has modified, therefor thread C’s data is in CPU1’s cache, and Thread A
will usually call MsgReceive() to block itself “soon”. If thread C was
immediately scheduled on CPU2, all of the “dirty” data in CPU1’s cache
would have to be transferred to CPU2’s cache/memory causing lots of
interprocessor interrupts and overhead. But, if thread C waits just
a little bit until thread A blocks (the usual case) it can run on the
same CPU and avoid all those inter-CPU transactions. Of course, if
thread A doesn’t block… well thread C will have to wait for the next
timeslice interval, at which point it will be run on some other CPU.
(In the single-CPU case, thread C would not run until thread A blocked
anyway.)Hope this helps to clarify what I meant by timeslice affecting
scheduling in some cases for SMP.-David
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.
Mitchell Schoenbrun <maschoen@pobox.com> wrote:
Let me see if I understand this properly? Only the highest priority
process is guarenteed to be scheduled when it becomes ready. Other
processes may or may not be running in priority order. This is more
efficient as rescheduling can cause a loss of useful cache contents?Another way of saying this might be, one processor is used for real
time, and all others balance real time and throughput?
Hmmm… if I may choose to be pedantic
“one processor is used for real time”, seems to imply a particular processor.
I don’t believe that this is the case. If you were to rephrase as
“and, in such a system, at least one processor (an arbitrary one) will run
the highest priority thread that’s been waiting the longest”, I could buy that
Your choice of words implies an exclusivity of realtime attributes.
Cheers,
-RK
–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.
Peter Weber <pw@dolphin.de> wrote:
What does it means for FIFO sched. on two or more CPU’s.
Two procs with the same prio FIFO scheduled can run ‘parallel’ if more than
one CPU is present?
hmmm…?
YES!
This is exactly why all the documentation, training courses, etc, state “do not
use FIFO scheduling to ensure mutual exclusivity in an SMP environment”.
The only absolute, guaranteed way of ensuring exclusivity is to use a high-level
synchronization primitive, like a mutex.
Cheers,
-RK
–
Robert Krten, PARSE Software Devices +1 613 599 8316.
Realtime Systems Architecture, Books, Video-based and Instructor-led
Training and Consulting at www.parse.com.
Email my initials at parse dot com.
Mitchell Schoenbrun <maschoen@pobox.com> wrote:
Let me see if I understand this properly? Only the highest priority
process is guarenteed to be scheduled when it becomes ready.
Yes.
Other processes may or may not be running in priority order.
Yes.
This is more
efficient as rescheduling can cause a loss of useful cache contents?
Yes.
Another way of saying this might be, one processor is used for real
time, and all others balance real time and throughput?
As RK said, the “one processor is used…” implies that a particular
processor is dedicated to realtime, and will always get the highest
priority thread/longest waiting. This is not the case. Again, doing
it that way could cause unneccessary thread migrations, more inter-CPU
interrupts for cache consistency, etc.
Most of the time, you will get the expected case, e.g. if a higher priority
thread than any other thread on the system becomes READY, it will
pre-empt the lowest priority RUNNING thread, on whatever CPU that thread
was running on.
-David
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.
Peter Weber <pw@dolphin.de> wrote:
What does it means for FIFO sched. on two or more CPU’s.
FIFO scheduling means what it always means – that the thread will
run until it blocks, or is pre-empted by a higher priority thread.
If pre-empted, it will still be at the head of the queue at its
priority, and when a CPU becomes available (at its priority) will
be chosen to run. (Well, it might maintain its spot at 2nd in the
queue at its priority… etc.)
Two procs with the same prio FIFO scheduled can run ‘parallel’ if more than
one CPU is present?
Absolutely. FIFO will not act as any sort of mutual exclusion device
for threads in an SMP system.
The System Architecture manual talks about using FIFO scheduling for
exclusion, but then notes:
Note that this exclusive-access relationship doesn’t apply in
multi-processor systems, since each CPU could run a thread
simultaneously through the region that would otherwise be
serially scheduled on a single-processor machine.
(As, I think, RK also mentioned.)
-David
QNX Training Services
http://www.qnx.com/support/training/
Please followup in this newsgroup if you have further questions.