Scheduling algorithm used in utasker

[lthyagar]

Hello, What is the scheduling algorithm used in utasker?
Thanks !!

[mark]

Hi

The scheduling can be found in uTaskerSchedule() in uTasker.c.

It is based on state-event operation, where it is expected that each task only runs for a short time and always runs to the end.
The following (and links in it) give an overview of the operation and also background to its advantages and disadvantages:
http://www.utasker.com/forum/index.php?topic=413.0

Regards

Mark

[JuKu]

The scheduling can be found in uTaskerSchedule() in uTasker.c.

It is based on state-event operation, where it is expected that each task only runs for a short time and always runs to the end.

In principle, and in normal operation, yes, but... I haven't actually tried this yet, but I did spend some time yesterday reading the code,  and I think it is possible for a task not to run at the end. I am on a different computer so I might get the details wrong (I don't have the code here to reference), but:

The scheduler calls the tasks only if they are ready to run. So, if a have a lengthy operation or have to wait for something, I think I can do this:

state= GetStateOfThisTask();  // remember the state
SetStateOfThisTask(STOP); // so the scheduler doesn't call
InitiateSomething();
while (IsSomethingReady()==FALSE)
{
  uTaskerSchedule(); // let other tasks run
};
SetStateOfThisTask(state);   // restore state

Am I missing something? I hope not, I want to do this. 

[mark]

Hi

What you have suggested is a technique which has been used in some projects. You just need to ensure that the waiting task is not re-scheduled in the process..

Generally I don't advise this use (also the simulator can not work with it) - in most cases it is possible to wait on an event rather than polling and often lengthy operations can be divided into chunks (progressed through a state-event-machine) - but I have indeed used it myself too (in very spacial circumstances).

When working on the FAT (as discussed elsewhere) it is envisaged to add a semaphore system (since several tasks may want to wait on external memory) based on the same idea, but this requires some study. The idea of the uTasker is to keep things as simple as possible and as soon as even the simplest pre-emptive/semaphore services are added the complexity tends to explode (not necessarily code complexity but overall design complexity with increased risks of hidden project bugs) which may not be what is really desired.

Regards

Mark

[JuKu]

>...(also the simulator can not work with it)...

Why not? (And can I overcome this somehow?)

>... in most cases it is possible to wait on an event rather than polling ...

But as I understand it, the task still has to run to the end.( This has more to do with the general design philosophy than the scheduling algorithm itself.) A co-operative multitasking is just fine in most cases, and neatly avoids the complications of a pre-emptive multitasking. Still, in my opinion/application, the requirement for the task to run to end is a big, (hopefully) unnecessary complication. As you said, it can be worked around with a state machine, but when the application conducts a kind of dialog with outside world, the state machine fast gets tens, if not hundreds of states and the code is a nightmare to read and maintain. I much rather write say something-wait for response-choose action-say something more-wait new response etc. style, where at each wait, other tasks get to run.

[mark]

Hi

As long as there is only one task using the wait technique it is generally a valid method and has been used in several projects, so there should be no reason to not use it if it gives you the most appropriate solution.

The reason why it can't be (presently) used in the simulator is because the simulator is a single thread which is calling the scheduler a few times before simulating timers, interrupts etc. before re-scheduling again. If the code doesn't return during scheduling the simulator will stop working (no timers, interrupts etc.) - this is not the case on the HW since the interrupts, timers, etc. work in parallel and 'really' interrupt the executing code.

At the moment I don't know how to (best) fix this. Maybe it requires the simulator to be constructed from multiple tasks so that the execution can be really 'interrupted'.

I think that I mentioned that I would like to make use of this technique for a semaphore wait on SD-Card accesses by multiple sources (if it doesn't cause more problems than it solves) and this is also a problem that I need to solve to be able to work with the simulator. Therefore I don't have a solution at the moment but I am trying to find a simple technique for the near future.

Regards

Mark

[JuKu]

Hi Mark,

Thank you for the explanation. For this trick to work in the simulator, could the timer etc. simulation part be put in a routine of their own, let's say "SimulateInterrupts()"? Then the wait loop would become

while (IsSomethingReady()==FALSE)
{
#ifdef _WINDOWS
  SimulateInterrupts();
#endif
  uTaskerSchedule(); // let other tasks run
};

?

[mark]

Hi

This can work for interrupts but not generally (for timers, UART simulation from external COM port, etc.).

In one case I waited for I2C reception by interrupt like this, where there is some additional _WINDOWS code:


    // Now we wait until the answer is received
    while (!(fnMsgs(IICPortID))) {
#ifdef _WINDOWS
        char *argv2[3];                                                  // this blocks UART interrupt simulation
        int iMax = 0;
        argv2[0] = (char *)&iMax;
        argv2[1] = (char *)&iMax;
        argv2[2] = (char *)&iMax;

        do {
        } while (fnSimInts(argv2) & IIC_INT0);                           // allow interrupt simulation to complete
#endif
    }


This works, but is a very restricted solution and will not solve waiting for reception from a COM port.

I am still thinking how a general solution might be possible...

Regards

Mark

[JuKu]

Hi Mark,

Any updates or ideas on this front? In other words, could you change the simulator so, that there is a function for a task to call or some other solution to keep the simulation running even if a task doesn't return for a while? (I can put in scheduling calls in my tasks, but I can't make them run to the end in reasonable time.)

Regards,

Juha

[mark]

Hi Juha

Unfortunately there has been no progress here.

I believe that the solution would be to construct the main part of the simulator from two (or more threads). The lowest priority thread being the project code and the higher priority one(s) being used for timers and other interrupts. The higher priority thread would effectively interrupt the lower priority thread as long as the lower priority thread has not disabled interrupts - when the lower priority thread re-enables interrupts it would also immediately give the higher priority thread the chance to generate the interrupt.

This would probably result in higher accuracy of hardware interactions and interrupts and would enable pre-emptive type operation.

On a side note I did once port a commercial operating system based project (for the 80186 and M68000) to run a PC - this was in fact quite easy to do since the instruction set of the Pentium (80586 I think) is very similar 80186 (for which all assembler code was available). This allowed the complete project (although with limited HW simulation) to be tested on a PC with task switching etc. - this is however not the same exercise as the uTasker simulator, but it was interesting to see how the task switching worked and also made it a bit easier to follow the operation of the project since the task switching operation can otherwise sometimes be a bit tricky to understand.

The biggest problem that I see in the uTasker project is the amount of work required (plus the fact that I don't really have that much experience with working with threads in the project) to modify the operation and also achieve the desired result (hopefully without new degradations in the development process). Basically I do see the method and I do see the advantages that it should offer but it seems to be a big work package that is difficult to get started on...

It is therefore difficult to promise anything at the moment.

Regards

Mark