Subject:
|
NXT-G/ROBOTC Firmware Scheduler and Clump Priority
|
Newsgroups:
|
lugnet.robotics.nxt
|
Date:
|
Thu, 6 Sep 2007 08:27:18 GMT
|
Reply-To:
|
<[dickswan@sbcglobal.net]StopSpammers[]>
|
Viewed:
|
22462 times
|
| |
|
|
In a typical operating system (OS), tasks are scheduled on a priority
basis. The highest priority task always executes ahead of lower
priority tasks. If there are multiple tasks at the highest priority,
then they are typically executed in a round robin fashion. This is not
the way the NXT-G firmware operates!
In the NXT-G firmware, there are a dozen or so software modules. They
are all designed to execute once per millisecond. There is no task
pre-emption. Each module is expected to be well-behaved and take only
a fraction of a millisecond to operate before returning to the calling
function.
User programs are executed within the VM (Virtual Machine) Interpreter
module. The VM module is "special" in that it provides the 1-msec tick
timing for the system; the design objective is that it is allowed to
execute for as much time is left in the current 1-msec tick.This
module executes a user file containing the "pseudo-code" (VM opcodes)
compiled and downloaded to the NXT from the NXT-G compiler.
The remainder of this note deals only with the NXT-G and ROBOTC VMs.
The NXT-G VM supports many simultaneous "Clumps" or "tasks" executing
at one time. Each clump represents a segment (subroutine, task,
MyBlock, group of blocks) of an end user program. All clumps that are
able to execute are given CPU cycles sequentially in a round robin
fashion. All NXT-G clump have equal priority. Each clump is run for a
variable length duration which, by default, is the time to execute 20
opcodes.
NOTE: "Clump" is National Instruments term to represent the smallest
"indivisible" group of LABVIEW instructions in a program.
The NXT-G firmware has a "Priority" variable associated with each
clump. It does not represent the obvious meaning of priority - recall
all clumps in NXT-G have equal scheduling priority. Instead it
represents the timeslice duration field!!! This can be confusing.
There is no capability to manipulate the Clump priority within NXT-G
graphical language. However, some of the alternative programming
environments that use the NXT-G firmware now allow user manipulation
of the "Priority" field. This should be done with caution.
The default "priority" of 20 opcodes was likely chosen because it
represents the number of instructions that can typically be executed
in under 1-msec. If you adjust the priority too large, then the VM
module starts taking timeslices much longer than 1 msec. This is not
good as it can very screw up the other software modules which expect
to get call periodically every millisecond.
The VM interpreter currently only checks at the end of a Clump
timeslice whether 1-msec tick has occurred; it might be better if it
checked after every interpreted opcode.
I did a very quick check to see the impact of above by taking a
typical program and making two runs - one for 20 opcodes per timeslice
and one for 200 opcodes. I kept a histogram of the number of 1-Msec
ticks in each VM Module timeslice - the target is that they are all
'1'!
| VM Module ..VM "Priority"..
| 1-Msec Ticks 200 20
|
| 0 0 0
| 1 1,880 60,025
| 2 0 7
| 3 549 0
| 4 335 0
| 5 524 0
| 6 4,173 0
| 7 2,435 1
| 8 1,079 0
| 9 215 0
| 10 0 0
The results are good with 'priority' 20. There were 7 timeslices that
spilled over to be 1 to 2 msec in length and one that took 7 to 8
msec. 60,025 took the desired 0 to 1 msec! I did four totals runs and
got nearly identical results. I found that the 7-msec timeslice was
the very first timeslice when program started up. The seven timeslices
that took 2-msec means that the hardware device drivers were skipped 7
times in 60K samples; this is probably OK.
When I changed the "priority" to 200 things really screwed up. The
average VM timeslice now took 7-msec! This means that the hardware
device handlers are only being called 1 of every 7 ticks. Hardware
should definitely be subtlely misbehaving. Motors will not be updated
as frequently - every 14-msec instead of every 2-msec; USB and BT
messages will start to timeout; motor regulation will fail; etc.
Following is similar information for the ROBOTC firmware and VM
operation.
- ROBOTC checks if 1-msec tick has expired after every interpreted
opcode and not at the end of a task timeslice. It does not miss
1-msec ticks. The VM is well-behaved.
- User tasks that are waiting do not consume CPU cycles. The VM has
a special state for this. NXT-G emulates a wait function with a
code loop that continually checks to see if system clock has reached
the "exit" time. This means in NXT-G, tasks consume same amount of
CPU cycles whether they are in a running or waiting condition.
- ROBOTC overall architecture is similar to NXT-G for the high level
software modules. However, there are major differences in
implementing the VM task (i.e. NXT-G clump) scheduler.
- ROBOTC has a priority based task scheduler for user tasks. It
follows the "conventional" definition of priority.
- ROBOTC scheduler is highest priority tasks always execute. Lower
priority tasks only get to execute if higher priority tasks are
blocked/waiting.
- ROBOTC has a dynamically adjusted task duration size based on the
number of runnable tasks. It's designed to minimize the number of
task context switches.
|
|
Message has 2 Replies:
3 Messages in This Thread:
  
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
