History of OnlineCourse/Modeling/Scheduler
Older Newer
2005-08-23 12:19:33 . . . . MembersPage/FredrikJagenheim [small cleanup; removed code that we have in svn now]
2005-04-16 07:31:36 . . . . MembersPage/MarcellGal [taskheap notes]
2005-04-15 10:36:49 . . . . MembersPage/MarcellGal [trick to know the conditions that we don't see]
2005-04-15 10:14:48 . . . . MembersPage/MarcellGal [more clear on prio and requirements]
2005-04-15 08:40:14 . . . . MembersPage/MarcellGal [improved code]
2005-04-15 08:31:56 . . . . MembersPage/MarcellGal [non-starving scheduler; 3 queues without softelapsed and somewhat more complex 4]
2005-04-15 03:25:37 . . . . MembersPage/FredrikJagenheim
2005-04-14 22:14:13 . . . . MembersPage/MarcellGal [scheduler thinking and notes]
2005-03-20 09:54:20 . . . . MembersPage/FredrikJagenheim [Answering Marcells worries]
2005-03-20 09:35:35 . . . . MembersPage/MarcellGal [1 queue => starvation]
2005-03-20 08:14:12 . . . . MembersPage/FredrikJagenheim [a proposal for a very simple scheduler]
2005-02-19 19:49:10 . . . . MembersPage/DaveBrul [added Nut/os]


Changes by last author:

Deleted:
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.

Resolution can be any. Proposed: 1 msec and 16 bit keys on AVR (32 bit on ARM)

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.

----

Deleted:
Ultimate solution
Deleted:
That gives us 3 useable queues:

Simplified solution

<code>

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

*/

</code>

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

Changed:
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.
The simplification in STABLE1_1 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.