Thread: Fsm

    #1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    4
    Rep Power
    0

    Fsm


    Hi,

    I am new to finite state machine's use in C and C++. Can anbody refer to any useful material, tutorial or a personal experience regarding these.

    Cheers,

    Comments on this post

    • requinix agrees : definitive resource for everything FSM: www.venganza.org
  2. #2
  3. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    Are we now to the point that it is too much trouble to even Google?

    Comments on this post

    • ptr2void agrees : Can say that about 99% of the posts on forums, sadly.

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,854
    Rep Power
    481
    flex

    bison

    Comments on this post

    • jakotheshadows agrees : Thats what I've been using in my programming languages course. Can't imagine trying to write all of it by hand without these tools.
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,162
    Rep Power
    2222
    First you design the FSM by sketching a directed graph. You draw circles representing the nodes which are the states of the FSM, then you draw lines with arrows (vertices) connecting the nodes. On each line, you annotate the conditions under which you are to transition to another state; depending on what your FSM does, you could transition from one node to any of several other nodes depending on what conditions are met or you remain in that state.

    When you have designed the FSM, then you implement it in C/C++/C# with a switch statement wherein each case represents one of the states of your FSM; you use the current state number in the switch statement, which means that you will have a variable that is set to the state that you are to be in. In each case, you perform whatever task is called for in that state, if any, and then you test the conditions and set the state variable accordingly to the next state (or not, if you are to remain in this state). You will call this switch statement repeatedly.

    As a practical example, consider processing a byte stream coming in through a serial port. The data format of that input stream is such that there is a short sequence of start characters (usually two) to mark the beginning of a message, followed by a header containing information about the message (eg, command/message-type byte, length of entire message and/or length of the data portion of the message, header checksum), followed by the data, followed by a short sequence of stop characters (usually one or two). The FSM will have an initial state from which it will test for the first start character; if found then you transition to the state that tests for the second, but if not found then you stay in that first state. Then the second state tests for the second start character, etc. You process the bytes of the input stream one at a time, calling the FSM's switch statement for each sequential byte. When you have transitioned all the way through the FSM, you will have processed one message, whereupon you return to the first state where you search for the first start character of the next message.

    So your task would be to first define the states and transitions for the state machine with that hand-drawn directed graph and then translating that to a switch statement for implementation should be fairly trivial.

    IMPLEMENTATION NOTE:
    While the states are assigned numbers, a good practice is to assign them meaningful names either with #define statements or as enums. This makes your code more self-documenting and helps you and others to understand the FSM. If you should decide against assigning meaningful names to the states, then you should comment each and every state copiously. Actually, you should comment each state anyway.

    Comments on this post

    • b49P23TIvg agrees : Great information. A company is considering me as a PIC \mu controller programmer.
    Last edited by dwise1_aol; October 24th, 2012 at 11:45 AM.
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,162
    Rep Power
    2222
    Originally Posted by b49P23TIvg agrees
    Great information. A company is considering me as a PIC \mu controller programmer.
    We were not taught this technique in school -- we learned about fsa's and fsm's and that graphing technique, but it was all just theory -- , but rather I learned it over 20 years ago from a fellow programmer as a "OBTW, ever see this before?". Then in my current job's products the original programmers had used this FSM technique from the start.

    One of its advantages is that it retains memory of where you are in the processing. Without it, you'd have to maintain several flags to remind yourself of exactly where in the message you are, which would be horrendously complex.

    Another advantage is that if you have to go off and do something else, when you come back to processing that input stream you just start from where you had left off. For example, I had a test program with which I was developing an FSM using captured stream data as test input. That test data was in a binary file, so I'd open the file and read in a 2K block and start processing it. Then, right in the middle of processing a message I'd hit the end of the block, so I went off to read in the next 2K of binary data and resumed processing that message. The FSM state retained memory of where I was in that message and I continued parsing it as if no interruption had occurred.

    It's a simple, powerful, and elegant technique that I think should be taught in the schools instead of programmers having to pick it up OJT.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    4
    Rep Power
    0
    dwise1_aol Thank you for such detailed reply. One thing. You mentioned that with FSM u can do some thing else. You mean asynchronous here. But if I am working with a single thread will fsm help me to to do asynchronous stuff aswell. Like if I am reading data using spi, will fsm assist in this case.
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    4
    Rep Power
    0
    and i want to do other tasks as well.
  14. #8
  15. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,162
    Rep Power
    2222
    Of course you're going to need to buffer the input stream, but you'd have to do that no matter what method you'd use to process that input. So then when you'd call the function containing the FSM, you'd either feed it the next byte in the input buffer or you'd have it read bytes from the input buffer and process them one at a time until it either has emptied the buffer or has to return so that you can do other things. The point with the FSM and its state variable is that you can leave it for a while and when you come back you continue right from where you had left off as if it had never been interrupted.

    BTW, your state variable should normally be a local variable declared as static; eg:
    static int iState = FSM_STATE_INITIAL;
    Local because only your FSM function would need to access it and static so that it will retain its current value when you return from the function and then come back to it later -- in fact, declaring it as static is absolutely necessary.
  16. #9
  17. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2012
    Posts
    4
    Rep Power
    0
    Thanks again. Actually i am reading data from spi in blocks of 2k Bytes

    1. i send command for read (time consumed)
    2. i wait for command to accept (time consumed)
    3. i copy byte by byte 2k data into the buffer of memory (time consumed)

    From your response i understand that state machine can only help me to save the time consumed in step 2. where at the moment i wait for the ok response in a while loop. So using fsm i can go out at this step. Do other stuff and when my command is accepted (the step 2.), an interrupt can bring me back or i set up a flag or some thing. And fsm will help me to continue read from where i left. I am thinking to design an fsm which covers the three mentioned steps as its states. I hope I have understood right from your exp. If you think I am missing any point plz add.

IMN logo majestic logo threadwatch logo seochat tools logo