looking for design patterns of interacting state machine
in [OOP]
|
Prev: The reality of Topmind (Was: Topic-Organized Object-OrientedProgramming)
Next: struggling with Design -Paradigms
From: Steven P on 11 Feb 2007 06:29 Hi, I would like to ask if there is design patterns of 2 interacting state machine? I have following scenario in my project: There are 2 state machines A and B. 1. A and a timer control B. 2. B checks some variables when time out. The variables are set by A. 2. A's state change depends on the B's state/signals, and also user input. Any ideas will be very appreciated. Steven
From: H. S. Lahman on 11 Feb 2007 12:13 Responding to Steven P... > I would like to ask if there is design patterns of 2 interacting state > machine? I think the only "pattern" is making events announcements (I'm Done vs. Do This). If one thinks of events as announcements, then synchronization protocols tend to just fall out. > > I have following scenario in my project: > > There are 2 state machines A and B. > > 1. A and a timer control B. > 2. B checks some variables when time out. The variables are set by A. This is an unusual view of a timer. Typically a timer exists to do one thing: generate an event when some period of time elapses. In fact, in OOA/D models they are usually not even explicitly identified; it is assumed they are part of some external, low-level infrastructure subsystem and the event announcing the timeout is treated as being external to the subsystem. So... > 2. A's state change depends on the B's state/signals, and also user > input. Usually some action in A (or another object) would make a synchronous call to the infrastructure subsystem requesting an event after some period of time. When that time has elapsed, an external event would be put on A's event queue by the subsystem interface. When that event is popped from the queue, A would change state to one that would "check some variables" and presumably do something relevant. Having said all that, I suspect you want something different. That is, after some elapsed time A needs to change state but the state that it should change to is determined by its own state variables. So, quite correctly, you are trying to move the transition decision out of A so that you can avoid self-directed events. One way to accomplish that is to separate the timer from B and have it send an event to B. Then B looks are whatever context it needs to, makes a decision about what the state of the solution is, and sends the appropriate event to A to announce that state. While that separates out the timer and puts the context decision in B, I am not very keen on it. The problem is that the decision is being made purely on A's own state variables. While OO state variables are orthogonal to state machine states, that is still a tad too cozy for my taste -- especially when A's actions are setting the state variables. That is very, very close to saving history information so that a state can know what the previous state was or next state will be, which violates basic FSA rules. So it might be possible to convince me that this was OK in a particular problem situation, but I would look long and hard at the way the objects and their responsibilities were abstracted to see if there was a better way of describing the context decision outside A (e.g., somebody else logically owning at least some of the state variables or having somebody else set them). [As an alternative, one could simply use conditional transitions in A's state machine to respond to the timer event. That is pretty much what they were designed to do. However, I tend to be more of a purist and I don't like conditional events for the coziness reason above. Consequently I never use them, so I wouldn't dream of suggesting them. B-)] ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl(a)pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info(a)pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH
From: Steven P on 13 Feb 2007 14:17 On Feb 11, 6:13 pm, "H. S. Lahman" <h.lah...(a)verizon.net> wrote: > Responding to Steven P... > > > I would like to ask if there is design patterns of 2 interacting state > > machine? > > I think the only "pattern" is making events announcements (I'm Done vs. > Do This). If one thinks of events as announcements, then > synchronization protocols tend to just fall out. > > > > > I have following scenario in my project: > > > There are 2 state machines A and B. > > > 1. A and a timer control B. > > 2. B checks some variables when time out. The variables are set by A. > > This is an unusual view of a timer. Typically a timer exists to do one > thing: generate an event when some period of time elapses. In fact, in > OOA/D models they are usually not even explicitly identified; it is > assumed they are part of some external, low-level infrastructure > subsystem and the event announcing the timeout is treated as being > external to the subsystem. So... > > > 2. A's state change depends on the B's state/signals, and also user > > input. > > Usually some action in A (or another object) would make a synchronous > call to the infrastructure subsystem requesting an event after some > period of time. When that time has elapsed, an external event would be > put on A's event queue by the subsystem interface. When that event is > popped from the queue, A would change state to one that would "check > some variables" and presumably do something relevant. > > Having said all that, I suspect you want something different. That is, > after some elapsed time A needs to change state but the state that it > should change to is determined by its own state variables. So, quite > correctly, you are trying to move the transition decision out of A so > that you can avoid self-directed events. > > One way to accomplish that is to separate the timer from B and have it > send an event to B. Then B looks are whatever context it needs to, makes > a decision about what the state of the solution is, and sends the > appropriate event to A to announce that state. > > While that separates out the timer and puts the context decision in B, I > am not very keen on it. The problem is that the decision is being made > purely on A's own state variables. While OO state variables are > orthogonal to state machine states, that is still a tad too cozy for my > taste -- especially when A's actions are setting the state variables. > That is very, very close to saving history information so that a state > can know what the previous state was or next state will be, which > violates basic FSA rules. > > So it might be possible to convince me that this was OK in a particular > problem situation, but I would look long and hard at the way the objects > and their responsibilities were abstracted to see if there was a better > way of describing the context decision outside A (e.g., somebody else > logically owning at least some of the state variables or having somebody > else set them). > > [As an alternative, one could simply use conditional transitions in A's > state machine to respond to the timer event. That is pretty much what > they were designed to do. However, I tend to be more of a purist and I > don't like conditional events for the coziness reason above. > Consequently I never use them, so I wouldn't dream of suggesting them. B-)] > > ************* > There is nothing wrong with me that could > not be cured by a capful of Drano. > > H. S. Lahman > h...(a)pathfindermda.com > Pathfinder Solutionshttp://www.pathfindermda.com > blog:http://pathfinderpeople.blogs.com/hslahman > "Model-Based Translation: The Next Step in Agile Development". Email > i...(a)pathfindermda.com for your copy. > Pathfinder is hiring:http://www.pathfindermda.com/about_us/careers_pos3.php. > (888)OOA-PATH Thanks you very much for the answer. I would like to make my problem more clear. FSM B is action control entity which has idle, do_x, wait_x, do_y, wait_y, do_z, wait_z state. It actually sends commands in state like do_x, do_y, do_z to an extern equipment, waits for the answer and then changes to Idle state. The time needed to get answer is not fix defined. Therefore a timer is used to check if the answer is arrived. FSM A is a process control entity which has defined action sequences. It sends signals to B, let it execute the desired actions. A needs to know the state of B, like B is in Idle state after doing wait_x, so A can tell B do the next desired action. B checks event/signals only when time out fires. While the programm runs in windows. The Timer is a windows timer, which is separated from B. Just as you said, decoupling the FSM is important for me. While I have quite large FSM, each has more than 25 states. So I am looking for existing patterns specially to deal with such problem. Any new suggestions? Steven
From: H. S. Lahman on 14 Feb 2007 13:51 Responding to Steven P... > FSM B is action control entity which has idle, do_x, wait_x, do_y, > wait_y, do_z, wait_z state. It actually sends commands in state like > do_x, do_y, do_z to an extern equipment, waits for the answer and > then changes to Idle state. The time needed to get answer is not fix > defined. Therefore a timer is used to check if the answer is arrived. This sounds like B is using the timer to see if there is a timeout on the response to whatever events it generated if do_x, do_y, or do_Z(?) If so, I am not sure I understand what the wait states are for. (Wait states in an FSM, especially if accompanied by self-directed events, are almost always a no-no, so I always look for ways to avoid them.) I would expect something like: +----------->[Idle]<------------------+ | | | | | E1: time_for_x | | | | | E5: time_x V | +----------- [do_x] | | | | | | E2: x_acknowledged | E4: z_acknolwledged | | | | E6: time_y V | +----------- [do_y] | | | | | | E3: y_acknolwedged | | | | | E7: time_z V | +----------- [do_z] ------------------+ where each of the do_ states sets the timer and E5, E6, E7 represent different timeouts. Then the STT would look like: event\current state | Idle | do_x | do_y | do_z | --------------------+---------+---------+---------+----------+ E1 | do_x | can't | can't | can't | E2 | can't | do_y | can't | can't | E3 | can't | can't | do_z | can't | E4 | can't | can't | can't | Idle | E5 | ignore | Idle | ignore | ignore | E6 | ignore | ignore | idle | ignore | E7 | ignore | ignore | ignore | Idle | --------------------+---------+---------+---------+----------+ > > FSM A is a process control entity which has defined action sequences. > It sends signals to B, let it execute the desired actions. A needs to > know the state of B, like B is in Idle state after doing wait_x, so A > can tell B do the next desired action. B checks event/signals only > when time out fires. I'm afraid I have to strongly disagree here. A should not know anything about the current state of B's FSM; that is a purely private matter between B, the developer, and God. A only needs to know that B has been reset to Idle. So when B goes into the Idle state it should announce that to A and A can fugure out whther that is a Good Thing or not. A's state machine should have an appropriate transition to deal with its own reset if that event arrives at an inconvenient time. IOW, the A state machine is going to look somewhat like B's with acknowledgment going in the other direction. When it gets the reset event in a state where it expects, say, an acknowledgment event that B::do_y generates, it should transition to a state like Idle that resets its own state machine. [If timeout delays can be long enough so that one gets exotic race conditions in the next control cycle, one might need to have a state dedicated to processing the timeout events in B prior to resetting to Idle. That state could do things like disabling the timer, clearing the event queue, and notifying A. A would acknowledge receiving the notification and that event would transition from the timeout state to Idle.] > > While the programm runs in windows. The Timer is a windows timer, > which is separated from B. > > Just as you said, decoupling the FSM is important for me. While I have > quite large FSM, each has more than 25 states. So I am looking for > existing patterns specially to deal with such problem. Alas, I have a much bigger problem here. Any time an object state machine gets over 6-8 states I would would get very worried as a reviewer; at 25 I would probably go into anaphylactic shock. B-) Any object that has 25 distinct, logically indivisible sets of business rules and policies desperately needs delegation of its behavior responsibilities to other objects. ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl(a)pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info(a)pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH
From: Steven P on 18 Feb 2007 02:58
On Feb 14, 7:51 pm, "H. S. Lahman" <h.lah...(a)verizon.net> wrote: > Responding to Steven P... > > > FSM B is action control entity which has idle, do_x, wait_x, do_y, > > wait_y, do_z, wait_z state. It actually sends commands in state like > > do_x, do_y, do_z to an extern equipment, waits for the answer and > > then changes to Idle state. The time needed to get answer is not fix > > defined. Therefore a timer is used to check if the answer is arrived. > > This sounds like B is using the timer to see if there is a timeout on > the response to whatever events it generated if do_x, do_y, or do_Z(?) > > If so, I am not sure I understand what the wait states are for. (Wait > states in an FSM, especially if accompanied by self-directed events, are > almost always a no-no, so I always look for ways to avoid them.) I would > expect something like: In do_? state, B sends commands to the external board via RS232. And in Wait_? state, it checks the answer when time out fires. Maybe you suggest that the sends command action be moved in the IDLE state when it makes transition. So I only need one state like do_? to check the answer? > > +----------->[Idle]<------------------+ > | | | > | | E1: time_for_x | > | | | > | E5: time_x V | > +----------- [do_x] | > | | | > | | E2: x_acknowledged | E4: z_acknolwledged > | | | > | E6: time_y V | > +----------- [do_y] | > | | | > | | E3: y_acknolwedged | > | | | > | E7: time_z V | > +----------- [do_z] ------------------+ > > where each of the do_ states sets the timer and E5, E6, E7 represent > different timeouts. Then the STT would look like: > > event\current state | Idle | do_x | do_y | do_z | > --------------------+---------+---------+---------+----------+ > E1 | do_x | can't | can't | can't | > E2 | can't | do_y | can't | can't | > E3 | can't | can't | do_z | can't | > E4 | can't | can't | can't | Idle | > E5 | ignore | Idle | ignore | ignore | > E6 | ignore | ignore | idle | ignore | > E7 | ignore | ignore | ignore | Idle | > --------------------+---------+---------+---------+----------+ > > > > > FSM A is a process control entity which has defined action sequences. > > It sends signals to B, let it execute the desired actions. A needs to > > know the state of B, like B is in Idle state after doing wait_x, so A > > can tell B do the next desired action. B checks event/signals only > > when time out fires. > > I'm afraid I have to strongly disagree here. A should not know anything > about the current state of B's FSM; that is a purely private matter > between B, the developer, and God. > That is a good advice, I had not thought through it. But I have simplified the whole process in the posts, I will check if I can implement it. > Alas, I have a much bigger problem here. Any time an object state > machine gets over 6-8 states I would would get very worried as a > reviewer; at 25 I would probably go into anaphylactic shock. B-) Any > object that has 25 distinct, logically indivisible sets of business > rules and policies desperately needs delegation of its behavior > responsibilities to other objects. It is an industrial application and has so many states. If I seperate states in more FSM, I may have more work to do to sync the reset / error state, is there also patterns to do this job? Thanks Steven |