Email: Password: Remember Me | Create Account (Free)

Back to Subject List

Old thread has been locked -- no new posts accepted in this thread
???
08/08/08 14:15
Read: times


 
#157331 - prioritizing in super-loop
Responding to: ???'s previous message
Yes, super-loop as the "mother of all loops".

The work to do should always be prioritized, and the developer should before starting to code write down down all the timing requirements.

It is important that when you reach:
if (lowprio_pending) {
    do_lowprio();
    continue;
}

that the individual actions are broken down into short enough steps that they don't introduce too much lag getting back to testing for pending high-prio jobs.

To get the code simple to maintain, you want low granularity of all jobs to perform, i.e. few steps in the state machines.

But to get low latencies, the jobs has to be broken into state machines with many, tiny steps.

With a large number of tasks, the time to test all if statements can also accumulate, so there may be a need for a two-level hierarchhy. For example:
for (;;) {
    if (critical_task0_pending) {
        critical_task0();
        continue;
    }
    if (critical_task1_pending) {
        critical_task1();
        continue;
    }
    if (mediumprio_pending) {
        if (mediumprio_task0_bit) {
            mediumprio_task0();
            continue;
        }
        if (mediumprio_task1_bit) {
            mediumprio_task1();
            continue;
        }
        ...
    }
    if (lowprio_pending) {
        if (lowprio_task0_bit) {
            lowprio_task0();
            continue;
        }
        if (lowprio_task1_bit) {
            lowprio_task1();
            continue;
        }
        ...
    }
}

But the problem with "continue" after all performed actions is that the guys at the end of the long lists of tests may be totally starved for time. But removing the "continue" means that the worst-case runtime for one iteration through the loop may be very high, if every single task needs servicing.

Because of this, there may be a need to use round-robin scheduling of jobs:
for (;;) {
    // Test all critical jobs on every iteration.
    if (critical_task0_pending) critical_task0();
    if (critical_task1_pending) critical_task1();

    // "time-slice" medium-priority jobs.
    if (++mediumprio_idx >= MAX_MEDIUMPRIO) mediumprio_idx = 0;
    if (mediumprio_task[mediumprio_idx]) {
        switch (mediumprio_idx) {
            case MEDIUMPRIO_TASK0: mediumprio_task0(); break;
            case MEDIUMPRIO_TASK1: mediumprio_task1(); break;
            ...
            default: alert_internal_error();
        }
        continue;
    }

    // "time-slice" low-priority jobs.
    if (++lowprio_idx >= MAX_LOWPRIO) lowprio_idx = 0;
    if (lowprio_task[lowprio_idx]) {
        switch (lowprio_idx) {
            case LOWPRIO_TASK0: lowprio_task0(); break;
            case LOWPRIO_TASK1: lowprio_task1(); break;
            ...
            default: alert_internal_error();
        }
        continue;
    }
}

Now, a medium-priority task will never get starved by another medium-priority task and a low-priority task will never get starved by another medium-priority task.

The above may be suitable for actions trigged by external events, but are not optimal when a large number of timer-based jobs exists. Then it may be better with:
for (;;) {
    // Jandle high-priority event-driven actions
    ...

    // Look for timer-driven jobs (where the head of the priority
    // list is decremented by an interrupt every x ms.
    t = prioqueue[prioueue_head].time;
    if (t <= 0) {
        // Most prioritized timer is "ringing". Pick up and process.
        switch (prioqueue[prioqueue_head].event) {
            case TIMER_EVENT0: delta_t = timer_event0(); break;
            case TIMER_EVENT1: delta_t = timer_event1(); break;
            case TIMER_EVENT2: delta_t = timer_event2(); break;
            ...
        }
        if (delta_t <= 0) {
            // Was single-shot. Release timer.
            old_head = prioqueue_head;
            prioqueue_head = prioqueue[old_head].next;
            prioqueue[old_head].next = prioqueue_nextfree;
            prioqueeu_nextfree = old_head;
        } else {
            // Repetitive timer.
            // Reload either counting from "now" or from timeout
            reload_prioqueue_head();
        }
        continue;
    }
    {
        // no scheduled jobs to do, so handle any background tasks or sleep
        ...
    }
}

By having at least one repetitive timer event in the priority queue (such as a one-second update of a clock display), the main loop need not test if the priority queue is empty.

List of 27 messages in thread
TopicAuthorDate
Non Blocking timer            01/01/70 00:00      
   Use a hardware timer            01/01/70 00:00      
      Thanks - But.....            01/01/70 00:00      
         State machines            01/01/70 00:00      
            THANKS - That's a great idea            01/01/70 00:00      
               if you have a lot to delay by various delays            01/01/70 00:00      
                  I Like that Idea as well            01/01/70 00:00      
                  A Linked List might be better here            01/01/70 00:00      
                     the correct use takes care of this            01/01/70 00:00      
                        Not necessarily            01/01/70 00:00      
   Cooperative or preemptive multitasking            01/01/70 00:00      
      Super-loop contra cooperative multitasking            01/01/70 00:00      
         Multasking can work on the 8051 ... sometimes            01/01/70 00:00      
            Not just stack            01/01/70 00:00      
               I agree            01/01/70 00:00      
                  Choose your battles carefully            01/01/70 00:00      
               I agree, too            01/01/70 00:00      
                  and            01/01/70 00:00      
                     Never underestimate the usefulnes of interrupts            01/01/70 00:00      
                        a flavor            01/01/70 00:00      
                           prioritizing in super-loop            01/01/70 00:00      
                              the fact is ..            01/01/70 00:00      
                  C works well            01/01/70 00:00      
                  Circular argument?            01/01/70 00:00      
                     Re: Circular Argument            01/01/70 00:00      
                        going round in circles            01/01/70 00:00      
            small multitasker            01/01/70 00:00      

Back to Subject List