Function pointers for task scheduler

Discussion in 'Programmer's Corner' started by JMac3108, Mar 1, 2013.

  1. JMac3108

    Thread Starter Active Member

    Aug 16, 2010
    349
    66
    I'm starting to work on a simple non-preemptive task scheduler, written in C, to run on an MSP430 microcontroller. Its strictly for learning purposes. I'm trying to work out an issue and thought maybe someone here can point me in the right direction.

    This will be a very simple task scheduler. At the heart is an array of structures with each structure representing a task. Each structure has three elements.

    (1) Function pointer that points to the task
    (2) Integer to hold the period (how often to run the task)
    (3) Integer to hold the elapsed time (how long since the task was run last)

    I'm stuck at how to define the function pointer. Each function to be scheduled might have a different set of parameters and return value. But the structure has to have a specific type of function pointer in its definition. Let me write out the definition of the structure to clarify ...

    typedef struct TaskList
    {
    void (*prt_task)(void);
    int period;
    int elapsed_time;
    } TaskList;

    My function pointer is for a function with no parameters and no return value. How can I handle a more general case where the function may have any return value or parameters?

    If it helps to explain the rest of the scheduler, here it is ...

    Basically its nothing more than a global array of structures as explained above. Each structure represents a task by pointing to the task, and telling us how often to run the task, and how long since it was run last. Time is of course measured in timer ticks.

    Tasks are scheduled by adding them to the array.

    The ISR for the timer is called periodically (when the timer reaches a defined count). The ISR goes through each structure in the array, in a loop, looking for tasks with elapsed_time = period. Those with elapsed_time = period are run, and the elapsed time is incremented for the rest.
     
    Last edited: Mar 1, 2013
  2. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    You are touching OOP issues here or let say, issues that are commonly solved with OOP.

    How about using a standard parameter block for both input and output (the return value)? 16 Byte or something.

    There is not a proper way to handle different function types (or pointers to it) unless you can use templates (for instance).

    It can be done without OOP but is hard to modify once laid out.

    Think of assembler- using the register set as parameters and for return value.
    So use a 16 byte parameter block for all functions.
    Or a special byte, pointing into a record description table.

    If you could use OOP, allocate memory for each new function in the global function list, and use a special type to describe the parameters.

    But then you have to deal with allocation/deallocation.

    Might be quite simple for some specific purpose,i.E. pseudo allocation via array, not a problem unless you have many entries.

    Look at Visual Studio C++ how it is done there, I am not an expert but I do know the basics and how to make things working.

    The best thing would be to implement a small subset of C++ OOP, using static arrays for pseudo memory allocation.

    I mean you can then add entries for each function entry, describing the parameters let say with a small string, and later, access the return value (or values) also with a small string.

    Since you likely only will need a smaller number of such functions, you can allocate these entries from an array, from time to time, do a garbage collection. All static, not really dynamic memory allocation.
     
  3. JMac3108

    Thread Starter Active Member

    Aug 16, 2010
    349
    66
    I think there must be a simpler solution. People have designed these non-preemptive task schedulers for a long time in embedded systems. There must be a standard solution to the issue ...
     
  4. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    Each function to be scheduled might have a different set of parameters

    Parameter by name (small string) isn't so bad.
    In the end all functions have the same parameter (entry into parameter data table), you'd bypass the regular C system to pass and receive your values.

    What you ask for exists in C++ but not in C, I think you are aware of that.

    That's at least what I believe. And that's how I'd try to implement it.
     
  5. JMac3108

    Thread Starter Active Member

    Aug 16, 2010
    349
    66
    Perhaps I'm trying to solve a problem that doesn't need solving. I've found descriptions of MANY similar task schedulers using Google, and all use task pointers without parameters or a return value, like this ..

    void(*task_pointer)(void)

    If I assign high level tasks using the scheduler, then I don't need to pass parameters or get return values. In cases where I absolutely need return values, they can be placed into global variables.
     
  6. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    Yes if there are parameters, the pointer for that would reside in the task structure.

    You can try for just two strings, fully static. One or two, or nothing. Each string hax fixed length 8 chars.

    Nothing else than a 64 bit entry. The borders exist in human imagination.

    Longer strings only mean to add reundance into a shorter int handle, so it is better readable for humans. And has a literal sense as well.

    So the literal sense can act as a key into the parameter original data.

    Easy if you only have longint parameters.

    If you pass a string, you'd need one more pointer.

    so a pointer to the task structure, a pointer to the string table, and each key is searched there and yields a longint or a pointer.

    Takes a while to resolve so you need some 80 to 100 MHz to get it done quickly.
     
  7. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    I mean don't add a generalized subset for OOP, just specialized functions serving a narrow purpose (the parameter adding to the string table, and searching for them by 64bit handle/small string).

    If you reserve space for two strings always, you need no memory allocation/deallocation.

    What is the memory on this MCU?

    You don't need so much, but some 100 bytes eventually.
     
  8. thatoneguy

    AAC Fanatic!

    Feb 19, 2009
    6,357
    718
    As you found, declarations are usually void pointers.

    Return values are most frequently passed by reference, see the description/source code of the memcpy or strcpy functions to understand how passing by reference is done to have a function "return" multiple values.
     
  9. WBahn

    Moderator

    Mar 31, 2012
    17,725
    4,788
    If you have control of the functions being scheduled, then you can have it take a single void pointer as an argument and return a single void pointer. For each function, you define a stucture that holds all of the parameters being passed to that function and that structure can also have places for any return values you want (or, it can be a completely different structure, if you want). That's the approach I took, although I took it a couple steps further, as well. I included members in the structure that had the type of the structure and that I could store function pointers specific for that structure type, though I later went away from that in favor of something else. The result was a very OOP-like approach with the structures being the objects.
     
  10. thatoneguy

    AAC Fanatic!

    Feb 19, 2009
    6,357
    718
    Your solution combined essentially "public" and "private" structures, or were they global/"public"? Sounds like a nifty way to work it, building your own OOL, if you will.
     
  11. WBahn

    Moderator

    Mar 31, 2012
    17,725
    4,788
    The basic approach I've adopted is to have a structure that contains the data and then a hierarchy of functions. First I've got a pair of get/set functions that do nothing but get or set a particular element within the structure. Those are the ONLY functions that are allowed to directly dereference the structure pointer. Then I have a layer of utility functions that serve to translate between the information being stored in the object and the representation of that information within the structure. Then I have the functions that the programmer is expected to use. These include a new/del (constructor and destructor) functions that handle initialization and housekeeping. In order to get a semblence of private vs. public, I have a header file that contains the tyoedef for the structure and the prototypes for the "public" functions. The definition of the structure itself and all of the "private" functions are in a single source code file that the programmer is not supposed to dink with. Getting everything set up for a new "object" class used to be a bit of a chore, but now I've made a couple of pretty sophisticate macros (at least for me) that almost completely automate the process so that I can have the basic structure, get/set, and new/del functions created within a minute or two.
     
  12. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    It would be best only to keep single void pointers in the task list.

    Then you keep all free task list entries in a shadow list, which you work like a stack.

    The tasks are all worked linear. If one bit is not set, the task structure is not examined. Only a few cycles required.

    You can maintain some 100 tasks, only if they are active you use additional memory for the task structure.

    Synchronization is important for multitasking, and the order of execution.

    So this is why you need parameters, to send notifications between the functions.

    You can have multiple master programs running, and multiple device programs.
    Devices produce a result or stream and take some time to produce it, while a master program runs freely, only depending on the control flow.

    The master program must wait for a device, logically.
     
    Last edited: Mar 2, 2013
  13. JMac3108

    Thread Starter Active Member

    Aug 16, 2010
    349
    66
    Hmmm, interesting ideas, thanks.

    I thought about using a global data structure and declaring the function pointers with a pointer to a location in that structure in order to handle pass and return data for the function, However, I got stuck at the problem of not knowing in advance what kind of data might be passed or returned. I had never heard of a void pointer until this discussion. The use of a void pointer solves this problem in that it lets me point generically to a location without having to know in advance what is stored there.

    BUT, I have to say, the level of complexity of this scheme makes me think there is a better solution. I'm going to think about it some more and see what I can come up with.
     
  14. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    Well when you just came accross void pointers right now, there is not much point suggesting to program OOP functionality.

    But identifying parameters by a string name looks interesting. It could be compared to the "compile by runtime" now found in Windows softwares.

    It should be possible to get this started with some 500 lines code perhaps.

    If you have larger programs, such a system is essential. Void pointers are a solution, but you have to take care yourself about the casting.
     
  15. JMac3108

    Thread Starter Active Member

    Aug 16, 2010
    349
    66
    Not sure what this comment means. I've done a fair amount of OOP programming in C++ recently and never had to use void pointers. It seems to me that these are relatively obscure. The case where you need to point to something, but don't know in advance what kind of data you are pointing to ... this seems a little uncommon. Maybe someone can point me to a typical application for a void pointer.
     
  16. WBahn

    Moderator

    Mar 31, 2012
    17,725
    4,788
    One example would be a generic linked list utility. Linked list of ... what? So your links use a void pointer that let you hanf anything on them. It's up to the programmer to properly cast the things pointed to.

    I think what takao was referring to is that if you are just now learning about void pointers, then it might be a bit difficult to tackle the notion of implementing OOP functionality into a non-OOP language until you gain a more intimate familiarity with them. It doesn't mean that you need to know about void pointers to use OOP functionality in an OOP language. In fact, a big part of OOP is to abstract away the whole notion of pointers behind "classes" and "objects" and such. So while OOP uses pointers in a very heavy way, the programmer is insulated and isolated from that reality.
     
    takao21203 likes this.
  17. tgil

    New Member

    May 18, 2011
    19
    4
    void pointers are also used in posix systems when creating threads (see doc's for pthread_create() http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_create.html).

    It is very similar to the situation at hand, the new thread can point to any structure and the system code doesn't care what it is. The thread function can then cast the data as any structure it likes. A thread function is declared as:

    void * thread_func(void * args);

    So you have a void pointer for both the argument and the return value.
     
  18. takao21203

    Distinguished Member

    Apr 28, 2012
    3,577
    463
    I was thinking this is the existing situation and is clear somehow.

    Problem is you need to know the data structure the task is using.

    In OOP focus is on the interface, not how it works internally. So my idea was to use strings (short strings for the time being) both to add possible parameters, and to pass values to them by identifying them with a literal value.

    In the end you'd only need numeric handles but not so much readable.

    They can also easily be made kind of private, for instance adding a string prefix for the task name as well. Another task tries- and needs permission to do that.

    I think most small controllers don't have memory access schemes such as segment selectors on 80x386. You'd normally not mess with them, but they prevent a task going out of control accessing outside memory. At least, this should be the case.

    The more MHz, the more pheripherals, the more code and memory- one day you run into trouble. Reset button is a solution- sometimes reconfiguration.

    I rather think using multiple controllers is a solution. If one fails, this does not render the complete board unusuable or no longer executing code.

    Think of old assemler- one bit fails at the wrong place- crash.

    OOP programs don't neccessarily crash from one bit. In some cases, they'd just not recognize the access or interface- and do nothing.

    The step from numeric handle towards strings is actually adding reundancy.
     
Loading...