#37 State Machines Part-3: Input-Driven State Machines
HTML-код
- Опубликовано: 11 июл 2024
- This lesson continues on the subject of STATE MACHINES, whereas today's subject is "input-driven state machines". This type of software state machine is the closest to its hardware precursors.
The lesson starts with an introduction to Mealy and Moore circuits and how they can be described by truth tables and state diagrams.
Later the lesson introduces input-driven state machines in software and shows several examples and terminology. You will learn about the inputs driving the state machines, the execution environment of such state machines, and the main problems.
The project for this lesson is based on an input-driven Blinky state machine used briefly in lesson 21. You will see examples of problems with unreliable polling of the inputs. You will also see how adding more and more buffering of inputs gradually leads to event-driven state machines.
-------
Resources:
Companion web page for this video course:
www.state-machine.com/quickstart
GitHub repository for projects for this video course:
github.com/QuantumLeaps/moder...
Transcript of this lesson:
www.state-machine.com/course/...
Video credits:
--------------
The video fragment about computer games comes from:
• Unity Open World AI - ...
The video fragment about robotics comes from:
• Atlas The Next Generat...
Music credits:
--------------
The background music comes from:
www.bensound.com/royalty-free... 
Наука
NOTE: The source code, as presented in the video, might cause compilation errors with the newer MDK-ARM / uVision toolsets. This is because the underlying compiler in MDK-ARM has been changed to "Compiler-6", while the older "Compiler-5" is considered now obsolete. The updated code that compiles cleanly with "Compiler-6" is available from the companion website at:
www.state-machine.com/video-course
and from GitHub:
github.com/QuantumLeaps/modern-embedded-programming-course
Mr. Sameek is the best teacher in embedded systems
Mr. Samek is an embedded God! Thank You!
God bless you, Mr. Samek. Your tutorials have been a great help in my career.
So glad someone feels the same as I do.
Been following your course for years. Certainly one of the best embedded software courses on RUclips.
After making some mistakes while designing a relatively complex embedded system I started searching through literature for the "right way" to do it. Looking forward to more videos, especially if you plan to go into more detail on the implementation of systems combining AO and hierarchical state machines in C.
You're at the right place. All of this is coming up. Stay tuned! --MMS
Thanks for the sound explanation of state machine history. Learned a lot. Based on my experience of FPGA design, the input driven state machine is doing the job which hardware/FPGA is doing. Because our world is analog, and we are just sampling at certain rate. To derive a reliable event, like debounced button click, special modules are developed to filter out the glitches. And FPGAs run at MHz, so the sampling rate can be as high as MHz. Right, to deal with asynchronous inputs, buffering is a common method.
Amazing insight on this one. Demistifying state machines
Great course ever
one of best lecture thanks and regards
I think there might be some errors in Moore's Raising Edge Detection circuit. Due to the AND symbol, there are no conditions where Q1 will transition to 1 if we start from 0 0. AND symbol will never show 1 if either of the inputs is 0, and, correspondly, the transition from 0 1 to 1 0 will never occur.
Great video! Indeed, I was wondering how debouncing can be added to an event driven architecture. My idea was to use an RTOS task running in parallel. Looking forward to the next video!
Actually, simple things like debouncing noisy inputs, should be done as early and cheaply as possible. Using a whole RTOS task just for that is like rolling out a cannon to kill a mosquito. A task is expensive (remember the private stack?) and slow compared to doing this directly in an ISR, exactly as demonstrated in lessons 35 and 36. --MMS
Miro, I agree with the interrupts approach, actually I had found a very cool debouncing library with auto-repeat which however does not use any interrupts and I was thinking how I can make it work with event driven projects. Because RUclips does not let me post the link here for some unknown reason, you can find it by googling for "Auto-repeat and debouncing" on the Embedded Systems Blog.
I been following your lectures for almost two years, when I started in embedded systems, I always felt simple super loop inadequate, RTOS is overkill, unnecessary overhead, I always wanted something in middle, simple as super loop yet with multitasking capabilities that's where I found your blog and video lectures, I'm every much interested in event driven Run to completion task
Whenever I start a program its start as event driven but as I add more and more codes it becomes spaghetti code, no matter how hard I tried I can't quite to implement the state chart in code, it stays only on paper, things don't really scale up, please any advice ?
Hi Dr.Samek,
The robotics example you give in the lecture. So in an event driven architecture for a robot, the event would consist of a variety of inputs e.g forces at different locations, current position etc to decide how the motors would position the robot to balance itself. But that would happen asynchronously, so Robot decision time can get affected ?? Are Input driven state machines more responsive compared to event driven state machines in this particular case, and hence more advantageous for Robotics or Gaming ??
Thank you again.
In *every* real-time system you have delays between the stimulus and the response. The delay is typically smaller in event-driven systems because the code that responds runs as soon as possible after recognizing the event. (This is assuming that the event is posted to a high-priority active object). The delays between an interrupt that recognizes an event and the processing of the event inside a high-priority AO can be on the order of microseconds. In contrast, time-triggered systems respond only when the time tick arrives, which can be significantly later than the original event. The delays in that case are on the order of clock tick, that is milliseconds (1000 times slower).
Having said that, the delay might be negligible. For example, a time tick in a robot could run at 1kHz (every millisecond). This is much faster than any mechanical actuator can react. Similarly in a game, human reaction time is much longer than the "frame rate" of the game.
The point I was trying to explain in such systems (robots or games) is that it is impractical to decide externally what an "interesting" combination of inputs is for the system. That means that it is impractical to generate external events because that changes depending on the internal state of the robot or the game. So, the checking of the inputs and their combinations is most efficiently done inside the state machine anyway. Hence, these systems probably could use "input-driven" state machines, even though they are "less responsive".
@@StateMachineCOM Dr.Samek, thank you for the reply. I took some time to digest it. Please see if i am understanding this correctly.
Taking the example of robot further, depending upon if the robot is carrying a heavy load or not. The interesting combination of inputs needed to stabilize the robot i.e. which sensors to poll, will depend on the current state of the robot i.e. carrying a load or not. Therefore we need to poll for the particular interesting combination of inputs inside the state machine.
In contrast, if we use Event driven machines, where events are essentially decoupled from the state machine and posted independently for further processing. We essentially have no control what events are being posted into the queue, or the interesting combination of events that we really need to stabilize the robot (in a given state). If we do decide to start checking the inputs, we have already shifted from Event Driven to Input driven architecture.
That is why in this case, a periodic input driven state machines makes more sense.
Hi Miro! Thanks for your videos! I'm trying to extend the functionality on this board and to use the SW2 switch. What I did so far is to initialize it similarly as you do for SW1 but what I get is that if this button is always pressed (i.e. if I make it this button to lighten up an LED then this LED is always on). Do you have an idea what I'm missing?
The SW2 switch on TivaC LaunchPad requires extra steps to properly configure, because it's shared with the NMI. Please see embeddedguruji.blogspot.com/2019/02/tiva-launchpad-tm4c123-part-2-push.html --MMS
Great course, I somehow missed the other 35 lessons, even if subscribed. Can you suggest a good place to buy the evaluation board in Europe?
All lessons in this video course are included in the "Modern Embedded Systems Programming Course" playlist posted at the top of this channel. Regarding the TivaC LauchPad board in Europe, you can simply go to Amazon.de or Amazon.uk or some other local Amazons. Also, the board is carried by the Swatee distributor ( www.swatee.com/ ), where you can search for "EK-TM4C123GXL". --MMS
@@StateMachineCOM The link you mentioned shows a 503 overloaded error. Btw, will the board EK-TM4C1294XL also work or does it have to be exactly EK-TM4C123GXL. I can only find the former on amazon.de.
@@shreyjain2752 I'm sorry about the Internet links. They are notoriously volatile and obviously out of my control. Regarding the board, the EK-TM4C1294XL is close, but not identical and the provided projects won't work on it without modifications. I would recommend to look for EK-TM4C123GXL. --MMS
Great content! Question for 4:22 : Shouldnt the "next state" here be called the "previous state" instead, since it is memory that records the previous state of the input? Calling it next state is confusing in my opinion.
Sir,can I build simple RTOS on MSP430?
Hello Miro!. I really appreciate and enjoy all your work. No offence but to add my humble opinion on your example. I think the button part is violating DRY .
And I might move the button part out of the switch case statement. any idea?
You are right! Absolutely! But the DRY (Don't Repeat Yourself) principle has been violated already in the *state machine design* at 22:25. The code is merely a reflection of that design, because it turns out that the traditional, "flat" state machines lead to such repetitions, which is known as the "transition explosion" problem. This problem is exactly addressed by Hierarchical State Machines, which are introduced in lesson #40 ( ruclips.net/video/lUvUNuUMQHo/видео.html ). Please watch! --MMS
Hi Miro, thank you for this incredible course! I have been following along but have run into an issue. No matter what code I try to download, I am receiving an error the flash loader program failed and values at address XXX do not match, verify target memory and memory map.
I have looked all over and double-checked my debugger settings. I'm unable to download any code to my board, even code that was working fine before. Do you have any suggestions on where I should begin troubleshooting?
Please, visit the companion web-page to this video course, which is advertised in every single video: state-machine.com/quickstart . You can find there, among other resources, the *Troubleshooting Guide*. Your problem and the solution are described in there. --MMS
Which board are you using ?
@@raja4521 This video course is based on the EK-TM4C123GXL board (a.k.a. TivaC LaunchPad). You can just google for the board name to find out more. Or, you can visit the companion page to this video course, which is advertised in every single video lesson: state-machine.com/quickstart --MMS
If I understand correctly from this lecture, input driven state machines still have their purposes. So I wonder if they can be modeled using QM. So far I thought it can only work with events.
Yes, absolutely. You can use QM for input-driven state machines, because *every* input-driven state machine can be directly converted into an event-driven state machine. I tried to explain that at 26:55, where you can see the conversion. The simple procedure is to invent an event, like SAMPLE, and package all the inputs as parameters for this event. This already provides the buffering of inputs that you typically need anyway. (Please note that this does not provide full event-queuing yet). The invented event (SAMPLE) is "low-quality", because it arrives "always", but the state machine is "event-driven" and can be modeled with QM. Please note that you still have all of the guard conditions, but QM supports them as "choice-segments". --MMS
@@StateMachineCOM Yes, I saw that part, I was actually talking about the state machine at 30:53, if it can be modeled directly with QM
What if change the first and third "else if" to "if"?
Great and excellent Work.
i have one question when you at (27:00 ) convert from input driven with capturing the data into local var (buffering ) to Event driven what the value it added or it's just way to show us how the conversion should be between them cause at the end they are the same. and from my understanding i think the only difference between input driven and event driven is the buffering right??
Data buffering inside events is just one of the lesser important things. The most important difference is that event discovery is *coupled* with event processing in the input-driven state machines, while it is *separated* in the event-driven state machines. That's why input-driven state machines have to run "constantly" to poll for events. In the code, it shows up as an IF-statement in every state of an input-driven state machine. These IF-statements (guard conditions) check the inputs for "interesting" conditions, and only after that some processing can happen. In contrast, event discovery happens *outside* event-driven state machines. The event discovery can be interrupt-driven, so constant polling for events is unnecessary. I must have done a rather poor job explaining the differences... My most sincere apologies! --MMS
@@StateMachineCOM Great. I got you. but that's show us that you truly didn't convert from input driven to event driven because in every case state in code we have (IF - ELSE) and the event discovery is coupled with event processing and the whole state machine run inside super loop. that's right ?
the method used in the code is input driven not event driven ?
even after when you say i'm gonna to modify it to event driven?
@@MahmoudAli-sv7fj Yes, that's true. After the conversion, the "event-driven" state machine had all the guard conditions that the original input-driven state machine had. That's because the event that was fed to the event-driven state machine was very low quality. It didn't mean anything yet, and therefore the guard conditions were needed to find find the *real* events. As they say: garbage in, garbage out. The moral here is that direct conversion from an input-driven state machine usually ends up with a crappy event-driven state machine. To end up with a better state machine, you need to create higher quality events. --MMS
@@StateMachineCOM million thanks of times
Very very useful. All your videos are so wet done. They are, for me, the best in the field. Just a very short remark at 7:00 min. The Moore state machine must show a constant output at a given state... which is not the case in your table... At state S1, the output Y (Q0) changes according to Input A... (as in a Mealy machine)...
I don't see a problem at 7:00 or at 8:00. Could you please elaborate where do you see error(s) in the table, in the state diagram, or my narration? Also, please note that the output Y assumes the new value on the *next* clock cycle, as shown in the timing diagram at 9:40. --MMS
I'm not trying to bother you too much, but do you happen to know of any alternative input-driven framework that would still allow for easy programming-by-difference and input-driven statemachine nesting with some sort of publish-subscribe mechanism as well? Or does that sound like a stupid idea even?
Everything else seems so spot-on about your approach, but I would like to think of the statemachines as "concurrent" actual machines that change their behavior given the state they are in (but don't sort of dissappear when there's no change in state), whereas these event-driven ones remind me more of fixed circuits that are only passed through on cue..
Trying to develop for time-triggered architecture automotive system.
Going to probably go with behavioral trees or something, thanks for lots of useful info on these subjects anyway.
I'm not aware of any "input-driven framework" that would have the properties you describe. In fact, this seems an impossibility to me because input-driven state machines deal with "inputs" instead of events. These "inputs" and their various combinations are then constantly checked in a polling fashion, so the code is littered with IF statements. I'm not aware of any way of publishing, subscribing, or reusing IF statements. Do you? Additionally, the "inputs" are typically shared (e.g., with ISRs), so you need to worry about the usual concurrency hazards, such as race conditions. For all these reasons, the industry has chosen the event-driven approach and frameworks (e.g., OXF for IBM Rhapsody, or QP frameworks used in these videos).
But if you are interested in input-driven state machines, the resource for that would be the book "Modeling Software with Finite State Machines: A Practical Approach". For time-triggered schedulers, the resource is Michael Pont's website "SafeTTy Systems" ( www.safetty.net ).
@@StateMachineCOMthank you, I was thinking about some sort of compromise the way the input-driven machines can be used to generate the events, so maybe mixing them a little bit. But I don't really know what I'm talking about yet.
I guess I should still take a closer look into your "fly and shoot" example as well, it seems to work very similarly to what I need.
In the time-triggered RTOS I have to work with I can't use interrupts directly, only the time-triggered threads can be relatively prioritized, and the only way to raise priority otherwise is to take ownership of some resource temporarily with a lock. So I can't use the AO priorities directly, but otherwise it should be safe and sound.
It also already has the facility to debounce the inputs I need to use, so I get stuck thinking if I should put the input polling inside the AOs that use them or put them in their own AO or just poll them separately..
要是有详细工程案例好了
讲的很好,就是没搞懂
in event-driven programming the only way to post events by making task higher priority or through interrupt right?
In event-driven programming, posting events is completely natural and does NOT require anything special. You just post an event by calling the post() operation on the recipient active object. In particular, you don't need to mess up with task priorities. Also, events can be posted from anywhere: interrupts, active objects, or any other code (e.g., "device drivers"). The posted event will be processed depending on the priority of the recipient of the active object. If that priority is high and you run on top of a preemptive kernel, the event processing can preempt lower-priority processing. This is also natural and you don't need to do anything special to achieve that. --MMS
Weren't they George Mealy and Edward Moore? Just saying... :).
Great course otherwise. Thanks a lot!
Yes, my apologies for the mix-up in the first and last names of the state machine pioneers. This has been corrected in the subtitles, but, unfortunately it's harder to fix the narration. --MMS
1 question
Why count is written in bap layer?
As far as I know, counting with a timer and use it for example as a gp timer is something related to lower layers and not to the bsp! In bsp you should only code those things that are really related to the board... also the implementation of sm is really poor. Don’t know why this was in my recommended videos!
I'm not sure what this question is really about, but BSP *is* the low-level stuff, isn't i? For example, counting with a timer interrupt is definitely dependent on the particular board and the implementation will be very different if you chose a different board. Therefore, you typically don't want to do such stuff in the main application logic. But perhaps I'm missing the point of this question? --MMS
@@StateMachineCOM counting stuff are completely related to the processor and if you consider something like that, it should be written in HAL. So for example the function that do the counting should have "hal" in its name... not "bsp".
Now imagine there is an LED on your board. All of the functions that controls the behavior of this LED, should be written in BSP layer and should have "bsp" in their name.
The important thing here is knowing the difference between timer counting (which is a feature of the MCU) and LED's functions (which is a feature of your board). BTW, there was no question, just wanted to give a critic.
@@sillfsxa1927 The concepts of BSP and HAL are both related to the low-level hardware interface and largely overlap in meaning (please simply google for "BSP vs HAL"). The most important thing is to separate the application logic from the low-level stuff, which is demonstrated. I don't think that splitting the hair even further into separate BSP and HAL will improve the design and will certainly trigger questions "what goes into the BSP and what goes into the HAL?". But I would rather focus on the important points of the lesson instead of side issues like this.
Hi Dr.Samek,
Let me first say, I have taken a number of paid courses for embedded systems (I am self learning embedded), and nothing has come closer to what you have done for us the students, thank you so much !! , I had four questions :
1) I am a little confused between input driven and event driven state machines. From the comments, my current understanding is input driven state machines are constantly polling for input in a superloop, meanwhile event driven state machines the events can be posted asynchronously from anywhere interrupts, other objects etc. So even if the event driven state machine is not currently active ( eg if it is a low priority task), we will not miss anything ?? Is this what we are trying to imply ?? that Input driven State Machines are running synchronously coupled with time , and Event driven state machines asynchronously ??
2) I was searching up on Internet, and I came across slides from Dr.Koopman from CMU. In this particular slide (users.ece.cmu.edu/~koopman/lectures/ece649/07_distributed_tt.pdf), he talks about Event Triggered vs Time Triggered Approach to network a distributed embedded system. Is the Time Triggered approach something similar to input driven state machine that you are describing in the current lecture ??
3) I am slightly confused about what constitutes an Active Object ?? In the previous lecture we first had two active objects 1) Button and 2) Blinky. Later we combined them together to form one AO, which resulted in more efficient memory usage. Can you give some guideline regarding that ?? How would I decide that this is one Active Object.
4) I am trying to read more about embedded software architecture (design patterns etc), and the only two resources have come across are your wonderful wonderful lectures and your two books. Another one is from Dr.Doughlass (Design Patterns for Embedded Software). Are there any other resources , I can read on ?? As I am thinking more, I am seeing by and large most of the problems can be solved via AO approach safely and in a scalable way, rather than mud-ball created by RTOS synchronization primitives.
Thank You.
Ovais
I'm glad that you study the video lessons.
Regarding your question (1): your understanding seems mostly correct, except that "input-driven" state machines are not limited to the "superloop" only. They can also run periodically. The defining characteristic of "input-driven" approach is the existence of "inputs" that are then checked in every state (so you have the if (...) statements in every state).
Regarding your question (2): I frankly don't quite understand the referenced lecture by Dr. Koopman. He apparently talks about "distributed" systems connected by networks. This is a particularly difficult class of systems and is currently outside the scope of this course. Here we are still talking about a single CPU and single address space.
Regarding your question (3): optimal partitioning of the system into Active Objects is an art, similar to partitioning an object-oriented system into classes. Big books have been written, such as the classic GoF "Design Patterns" book, where you can read that experts typically come up with quite non-intuitive classes. An example of application design is provided in my video "Active Objects and State Machines" (ruclips.net/video/h_u92uLssDo/видео.html ).
Regarding your question (4): a few resources I recommend are: "Managing Concurrency in Complex Embedded Systems" Dr. David Cummings (www.state-machine.com/doc/Cummings2006.pdf ), "New Directions in RTOS Kernels" by Dr. David Kalinsky ( www.state-machine.com/doc/Kalinsky2014.pdf ), "Message Passing for Intertask Communication" (www.state-machine.com/doc/Kalinsky2010.pdf ), writings by Herb Sutter on concurrency (google it). Most of these articles don't explicitly mention the "Active Object" pattern, but I'm sure you will immediately see that this is what they advocate.
@@StateMachineCOM Dr.Samek, thank you for all the detailed resources and reply. The video is precisely what i was looking for, a more involved example. And the first paper especially looks very interesting. Thank you so much !!