Developer info to improve scheduler
The simple scheduler used now (mainloop) will be improved so latency of some high-priority actions is improved. So we can
- move some high priority trigger-data processing to userspace
- move some tables from SRAM to EEPROM (to free space for MMC logging and networking), where there are limits of when it can be accessed for read (not during EPPROM write).
- the EEPROM write (if there is a demand) can only start right after all necessary variables for fuel VE/lambda/ign calc had been cached in SRAM (seach_table result and 2x2 grid of each table).
- Also, the above cached table-data cannot be updated during EEPROM write (new calc would be possible nevertheless, with some boundary-check consideration ; but easier to avoid it, and only recalc new injPW from changed MAP if it's absolutely needed within 8.5 msec; many competition controllers cannot even finish a full calc within that period)
- when these userspace calcs are allowed (not in EEPROM write and at least 4 msec passed since last) they can be medium priority
- implement more convenience features
Requirements
- prio0 must be absolute highest priority: if anything runnable in prio0, that must be run hopefully within 500 usec, and before any prio1..prio3; we must take care that the conditions are careful, and not consume all clocks
- max 1 queue is allowed to starve (the lowest priority, eg prio3)
- round-robin (or alike) within a queue for equality
- if possible, not preemptive (we have the eventqueue already for whatever needs immediate attention)
- low CPU clocks overhead (surprise)
- low memory footprint
- support the EEPROM write-start - calc "synchronization" above.
- it could be done with merging the EEPROM write-start and the calc to one function. However this is not desirable, the calc itself should be possible to split to several functions
- EEPROM write-start and calc functions can be apparently independent (likely in prio1), but ordered smartly and communicating through the "runnable condition", that use common variables (timestamp of when calc was last run, is EEPROM write in progress, etc...). I hope this will work
- it might sound like this requirement calls for dynamic prioritazation, but hopefully that is avoidable.
See the priority ideas on GenBoard/UnderDevelopment/FirmWare (TODO: delete from there)
Even though it is relatively simple, it's a good idea to model it in JAVA first (see package org.vemsgroup.firmware.scheduler in JTune CVS) to verify operation (and maybe tune some variables).
Similar scheduler is implemented in most real-time operating systems.
See task-states on an [an x86 RTOS].
However we don't need preemptive multitasking. Cooperative is fine. So no need for separate stack for each process. When the process returns, it's stack is back to normal anyway. Timing sensitive tasks must be done in interrupt or high-priority process.
A nice OS with non-preemptive multitasking running on the atmega16 (gpl and compilable with avr-gcc) can be found here [ethernut.de]
Simple scheduler
Actually rather a task runner, since it just executes what was added with scheduler_add(). The operation solely depends on the conditions aroung scheduler_add().
<This was the one we decided to kill. We now are back at the original idea with 4 queue implementation. Look at scheduler.[c|h] in HEAD. Only main_loop uses this scheduler now, and it's just rescheduling itself immediatly after it has run.>
There are 3 queues that starve (unless scheduler_add() conditions are very tricky), while there should be max 1 queue that can starve.
scheduler_sleep() is putting the AVR to sleep. I think this is very dangerous, this is the easiest to get wrong. For battery powered systems it's worth it, but v3 consumes appr. 100 mA so we cannot save significant power. There are no scheduler_sleep in the new version. Sleeping was mostly for the emulator not running at 100% anyway.
Any task may re-schedule itself either by calling scheduler_add itself, or using the eventqueue to schedule itself sometimes in the future. Can I use the existing eventqueue for this?
We only set schedule flags from interrupt/eventqueue when we are there for other reason (eg. trigger, or action).
Otherwise userspace actions should not use interrupt for this. However if you feel uncomfortable to do many false comparisons (like softelapsed does), a second heap maintained from userspace is perfect. Just like eventqueue, but separate heap and actions from it are only executed when the scheduler thinks right (not asynchronously):
- not delaying any high priority task
- and no race/locking issues.
Dispatcher actions are also independent. 16 bit is perfect, no need to spare clocks by using 8 bit values.
Yes, we discussed this on the IRC channel. It's not in the current implementation though.
If you still like this implementation, please provide examples for the conditions of may re-schedule itself. It sounds very hard in many cases, when the task is activated from async message (eg. comm rx/tx, trigger processing, etc...). Than we can compare requirement-conformance, SRAM footprint and CPU overhead with other solutions.
Non starving scheduler - actually max 1 queue (prio3) can be allowed to starve
Ultimate solution
- if there is anything runnable in prio0 (such as trigger data processing), that must be run. We take care that this is limited, and not starve prio1..prio3.
- else if there is nothing in prio1 and prio2, than prio3 can run (eg. LCD can be in prio3 with always runnable condition). This way prio3 can starve theoretically, but .. read below
- if there is sg. in prio1 or prio2, prio1 and prio2 are different "priority" (frequency of turn), but prio1 cannot starve prio2:
- run max 2 consequtives tasks from prio1 (eg. fuel/ign calcs, comm tx/rx data; wbo2)
- than run max 1 task from prio2. Note that prio2 always has it's turn after prio1 queue was checked twice (wether sg. from prio1 actually did run or not)
Runnable conditions
- flagged asynchronously, eg. from irq or other places. (such as trigger data available; or comm data available or sending buffer almost empty). The amount of events must be limited so this consumes max 10..60% of CPU.
- softelapsed: a certain amount of time passed since last run. With some tuning, this ensures that there are times when nothing is runnable in prio0..prio2 so prio3 can run. IMHO this is the key for the nice behaviour. If all process just asks "I want to be run" after they run, we more or less get back the mainloop behaviour.
- always runnable (only allowed in prio3)
- other condition ???
If scheduler does not see softelapsed type runnable conditions (because conditions are hidden inside the functions, so the scheduler itself does not see them; the conditions hidden in the functions can still be there and result in some functions decide themselves to not take their turn and return without doing much), that means we basically have 2 queues (prio3 is definitely meaningles than)
- prio0 (with just "flagged async conditions")
- and a lower priority queue. This can be divided as the prio1-prio2 trick above, so that prio1 tasks get more timeslot altogether (but prio1-prio2 is not "true" priority).
That gives us 3 useable queues:
Simplified solution\n
for(;;){
uint8_t sg_in_prio0=0;
// prio0 is very high prio, run ASAP:
if(cond_prio0_0){ run what necessary; sg_in_prio0 |= 1; }
if(cond_prio0_1){ run what necessary; sg_in_prio0 |= 2; }
if(cond_prio0_2){ run what necessary; sg_in_prio0 |= 4; }
if(sg_in_prio0 == 0 ){
// only run if nothing in prio0 had to run
time_old = ... save time
prio12();
}
/*
* Note1: this could be a simple array of function pointers, like in lcd_display.c
* Note2:
*/
void prio12(void)
{
step_down(prio12_idx, PRIO12_MAXIDX);
switch(prio12_idx){
case 1: prio1_1(); break;
case 2: prio1_2(); break;
case 3: prio2_1(); break;
case 4: prio1_3(); break;
case 5: prio1_4(); break;
case 6: prio2_2(); break;
....
// note that though prio1 and prio2 are round robined together
// prio1 tasks appear twice in the sequence, appr. "180 degrees" apart so they get more chance
case 13: prio1_1(); break;
case 14: prio1_2(); break;
case 15: prio2_5(); break;
case 16: prio1_3(); break;
case 17: prio1_4(); break;
case 18: prio2_6(); break;
}
if ( not much time passed since time_old){
// alternatively ret = prio1_4();
// return values from above functions could be used for decision,
// but time is harder to get wrong and considers
// time spent in interrupt as well.
prio3() ;
}
}
/* Note1:
* SRAM usage is 3 bytes,
* (uint16_t time_old timestamp and uint8_t prio12_idx);
* FLASH and CPU overhead is negligible.
*
* Note2:
* we can trade some SRAM for CPU:
* adding an appr. 16 element heap (64 SRAM bytes) - called "taskheap"
* which is independent from the interrupt eventqueue,
* since all processed in userspace,
* resolution is 64usec (not 4 usec)
* will allow us to stuff all time-controlled recurring tasks,
* such as WBO2 evaluation, real-time maintenance,
* TPSdot, iac-recalc, stepper actuation, boostcontrol, etc...
* to that heap.
* we can decide if taskheap is prio1 or prio2
* (or a task within prio1, among others) - the other is simple
* (switch-case implemented above) round robin. Or we can use
* prio1=round robin,
* prio2=taskheap
* prio3=round robin,
* prio4=lowest prio
*/
Note that the mainloop is not usable in the original form.
So basically mainloop is split to parts:
- priox_x() functions (names can be descriptive, of course)
- and if(cond_prio0_2){ run what necessary; ... parts
The simplification from the Ultimate solution is that we cannot tell by a quick look if there is sg. runnable in prio1 or prio2. We just execute something that has it's turn, that can have it's own condition (eg. softelapsed()) and might not do anything.
In general lack of the knowledge of "explicite" (known by the scheduler) "runnable conditions" of tasks in a queue makes any lower priority queue of little use.
The trick of if ( not much time passed since time_old){ might be a simple yet efficient way to know if we have a free slot right now to execute sg. from prio3(). Not exactly the same condition as "if prio1 and prio2 has no runnable at all", though.
TODO: meet the EEPROM-write requirement
can probably be met as well.
That allows any number of upto 16x16 tables (psychological benefit...);painless, 0 overhead switching to alternative (95-98 octane) fuel ignition-map, etc...
The rx21 rip (already in STABLE1_0) allows easy addition of individual (per table) RPM and MAP ranges for each tables.