How to design a state machine in face of non-blocking I/O?
Qt framework has by default non-blocking I/O.
I'm developing an application navigating through several web pages (online stores) and carrying out different actions on these pages. I'm "mapping" specific web page to a state machine which I use to navigate through this page.
This state machine has these transitions;
Connect, LogIn, Query, LogOut, Disconnect
and these states;
Start, Connecting, Connected, LoggingIn, LoggedIn, Querying, QueryDone, LoggingOut, LoggedOut, Disconnecting, Disconnected
Transitions from *ing to *ed states (Connecting->Connected), are due to LoadFinished asynchronous network events received from network object when currently requested url is loaded. Transitions from *ed to *ing states (Connected->LoggingIn) are due to events send by me.
I want to be able to send several events (commands) to this machine (like Connect, LogIn, Query("productA"), Query("productB"), LogOut, LogIn, Query("productC"), LogOut, Disconnect) at once and have it process them. I don't want to block waiting for the machine to finish processing all events I sent to it. The problem is they have to be interleaved with the above mentioned network events informing machine about the url being downloaded. Without interleaving machine can't advance its state (and process my events) because advancing from *ing to *ed occurs only after receiving network type of event.
How can I achieve my design goal?
Re: How to design a state machine in face of non-blocking I/O?
But what exactly is the problem? Can't you build a queue of requests and whenever the machine will reach some point in processing, it will look into the queue for a matching next command? For example after "LogIn" there may either come a "Query" or a "LogOut". So when the machine reaches the LoggedIn state it should look into the queue for a matching Query or LogOut. If something fails, the machine should try to do error recovery by discarding pending events from the queue until it reaches a request it is able to process in its current state.
But maybe I just don't understand what you want...
Re: How to design a state machine in face of non-blocking I/O?
You got my question right and your idea with event queue looks good. That was my idea too. The problem is I can't enqueue network event because the machine will be stuck waiting for it. The machine will never receive this network event because it will be waiting behind other events enqueued earlier...
Re: How to design a state machine in face of non-blocking I/O?
But network events should not go into the same queue... The queue should only be for user events - network events are spontaneous and should be treated as such - they can happen at any point in time.
Try simplifying your machine. To me it seems you should have the following states:
Idle, Connecting, LoggingIn, Querying, LoggingOut, Disconnecting
and the following transitions:
Idle: 0 -> Idle
Idle: Connect -> Connecting
Idle: Login -> LoggingIn
...
Connecting: 0 -> Connecting
Connecting: <Connected> -> Idle
LoggingIn: <LoggedIn> -> Idle
...
etc.
Then "user command" processing is only done in the Idle state. That's also where error checking is performed (or you can have an extra InError state for that which would be reachable from any state other than Idle). While performing requests, the machine would spin in the appropriate "*Ing" state.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
But network events should not go into the same queue... The queue should only be for user events - network events are spontaneous and should be treated as such - they can happen at any point in time.
Without queue it's possible that the machine will be busy when the next network event comes in and it will miss this event. Am I right? If so than you can't afford not having some queue for this type of events, right?
Quote:
Originally Posted by
wysota
Try simplifying your machine. To me it seems you should have the following states:
Idle, Connecting, LoggingIn, Querying, LoggingOut, Disconnecting
and the following transitions:
Idle: 0 -> Idle
Idle: Connect -> Connecting
Idle: Login -> LoggingIn
...
Connecting: 0 -> Connecting
Connecting: <Connected> -> Idle
LoggingIn: <LoggedIn> -> Idle
...
etc.
How are you going to create Connected, LoggedIn and all other *ed type of events? Right now there's only one type of network event - Loaded - which is generated inside QWebPage's LoadFinished signal's handler. How are you going to know being inside this handler if you should generate and post Connected, LoggedIn, QueryDone or yet another type of event? All you know being inside this signal's handler is that some page was loaded.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
Try simplifying your machine. To me it seems you should have the following states:
Idle, Connecting, LoggingIn, Querying, LoggingOut, Disconnecting
and the following transitions:
Idle: 0 -> Idle
Idle: Connect -> Connecting
Idle: Login -> LoggingIn
...
Connecting: 0 -> Connecting
Connecting: <Connected> -> Idle
LoggingIn: <LoggedIn> -> Idle
...
etc.
Two more questions;
1. What does "O" as event mean?
2. You can't transit from Idle to LoggingIn on Login event if you haven't transited in the past through Connecting state. How are you going to check this constrain when you are in Idle state and just received Login event?
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
piotr.dobrogost
Without queue it's possible that the machine will be busy when the next network event comes in and it will miss this event. Am I right?
I don't think so. In any of these "network" states only a specific network event may come in. No "network" events should come in in the Idle state so none should be missed. And if you're worried about it, make another queue of those events and when you reach some state, check the queue for pending events.
Quote:
How are you going to create Connected, LoggedIn and all other *ed type of events? Right now there's only one type of network event - Loaded - which is generated inside QWebPage's LoadFinished signal's handler. How are you going to know being inside this handler if you should generate and post Connected, LoggedIn, QueryDone or yet another type of event? All you know being inside this signal's handler is that some page was loaded.
These are to be your events, not webview's. What exactly are you using QWebView for? Isn't QNetworkAccessManager enough for your needs?
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
I don't think so. In any of these "network" states only a specific network event may come in. No "network" events should come in in the Idle state so none should be missed.
Nice remark :) I would like to be ready for the situation when multiply network events may come at any network state.
Quote:
Originally Posted by
wysota
These are to be your events, not webview's.
I have to admit I have a felling I have my own logic mixed up with the logic of navigating some specific web page. Should I have one main state machine to control logic of my app and one state machine for every specific site? Wouldn't this be overkill?
Quote:
Originally Posted by
wysota
QNetworkAccessManager is not enough. I need cookies, DOM, CSS3 selectors and JS provided by QWebPage and QWebFrame.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
piotr.dobrogost
Nice remark :) I would like to be ready for the situation when multiply network events may come at any network state.
Then you will have multiple separate machines working and still for a particular machine only one event will come.
Quote:
I have to admit I have a felling I have my own logic mixed up with the logic of navigating some specific web page. Should I have one main state machine to control logic of my app and one state machine for every specific site? Wouldn't this be overkill?
I'm not so sure anymore what you are trying to do. I thought you were implementing some kind of web spider but when you said something about QWebView, I got lost.
What exactly does your program do?
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
I'm not so sure anymore what you are trying to do. I thought you were implementing some kind of web spider but when you said something about
QWebView, I got lost.
What exactly does your program do?
It is kind of web spider but smart one. It logs into several online shops and search for information. I'm not using QWebView (because I don't need rendering capabilities) but QWebPage and QWebFrame (because I need most of the other features of a web browser).
Let me remind my question
Quote:
I have to admit I have a felling I have my own logic mixed up with the logic of navigating some specific web page. Should I have one main state machine to control logic of my app and one state machine for every specific site? Wouldn't this be overkill?
Re: How to design a state machine in face of non-blocking I/O?
No, it would not be an overkill. It would be simplicity and elegance.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
Try simplifying your machine.
That's interesting advice as simultaneously I've got opposite advice here to introduce more states to my machine like for example ConnectingWithIntentToLogin.
Could you be so kind to take a look at this advice and others in the above thread and share your opinion on them with me?
Re: How to design a state machine in face of non-blocking I/O?
Having more states and simplifying the machine are not contradictory. If you read again what I have written till now you will notice that I advise you to have more states as well (the total set of states of the system is a cartesian product of state sets of all sub-systems of the FSM).
I don't agree with what's written in the thread you mention.
In general to me it seems you are overcomplicating things. I gave a though about your goal and how I would solve it and I would use a job pattern for that (if you'd use a thread pool for that or not is a secondary issue). I would separate jobs instead of trying to combine them as you're doing now.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
If you read again what I have written till now you will notice that I advise you to have more states as well
Could you point the place where you advised this? I can't find it.
Quote:
Originally Posted by
wysota
In general to me it seems you are overcomplicating things. I gave a though about your goal and how I would solve it and I would use a job pattern for that (if you'd use a thread pool for that or not is a secondary issue). I would separate jobs instead of trying to combine them as you're doing now.
I'm for separating jobs too. If they are not separated currently it's because I have bad design and I'm aware of this. I would like to change it and that's why I started this thread. The problem is I have a problem with coming up with sound design and need help with this. I hope with your help I will be able to change current design to a new, better one.
In your modification of the state machine you used new transitions like connected and loggedin. This is a new idea because currently they are states not transitions. Let me show you how it works now;
Start -> [connect] -> Connecting -> [loaded] -> Connected -> [LogIn] -> LoggingIn -> [loaded2] -> LoggedIn -> [query("something")] -> Querying -> [loaded3] -> Queried etc.
where States start with big letter and [transitions] start with small letter and are enclosed in brackets. Currently I have only one type of network event, namely {Loaded} which triggers all [loaded] transitions. I send it to the machine from within LoadFinished signal's handler. That's all I do when I receive LoadFinished signal - I always send exactly the same event. After the state machine receives this event a transition is triggered. Please take a note that {Loaded} event carries no information.
Now, in your proposal instead of one {Loaded} network event there are various ones like {Connected} and {LoggedIn}. The question is; how do I generate these events from within LoadFinished signal? Based on what data/criteria?
Currently in my state machine it's transitions that react to events and cause machine to change it's state. Maybe states should react to events instead of transitions? Maybe both should react to events? What do you think?
Remarks
We have 3 distinct types of objects - States, [transitions] and {Events}. Each transition is unique and that's why I called them [loaded], [loaded2],...,[loadedN].
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
piotr.dobrogost
Could you point the place where you advised this? I can't find it.
It's about dividing your machine into submachines and minimizing the number of transitions between states. Separating each sub-machine makes it easier to focus on one goal at a time - that's simplification.
Quote:
I'm for separating jobs too.
I don't understand what you meant when you were saying about that a network event can be missed because something else is currently doing something, etc.
Quote:
If they are not separated currently it's because I have bad design and I'm aware of this. I would like to change it and that's why I started this thread. The problem is I have a problem with coming up with sound design and need help with this. I hope with your help I will be able to change current design to a new, better one.
If your jobs are undependent on each other then separate them and focus on one of them at a time. If you have that done, others will work exactly the same and won't interfere.
Quote:
In your modification of the state machine you used new transitions like connected and loggedin. This is a new idea because currently they are states not transitions.
That's a very common technique - to change transitions into states and vice-versa.
Quote:
Currently I have only one type of network event, namely {Loaded} which triggers all [loaded] transitions.
Forget about WebKits "Loaded" state. Treat it as a signal that what was being done is currently finished. You should worry about your states and your transitions. It's a good concept to ask yourself a question - "if I was in each of the states, what input from the system would I expect?". It leads to a clean design of the FSM.
For instance - when I start I can only expect to receive a request to connect to a website. Every other input will be invalid (in other words for every other input one should spin in the current state). Then if I am performing a connection it can either succeed, fail or be aborted. Aborting the call will lead me back to the first state. If it fails, then we should probably go to some "Error" state and try to recover. If the connection succeeds then we can implement one of the two designs - either we treat the system as a whole (in that case we need a new state) or we divide the system into two sub-systems - one subsystem tells us what we are currently trying to do and the other tells us of the current state of our job. In the latter case we go back to the initial state (system is waiting for requests) and move the job into "Connected" state.
Let me come up with a drawing and post it here...
2 Attachment(s)
Re: How to design a state machine in face of non-blocking I/O?
Not the best pictures but I hope they are clear. The first one represents the "request" part of the system. The output part of each transition is a new state for the second submachine (second image) that marks the "job" state. {LOADED} is a trigger (your network event) and <CONNECT> is a user event.
Bear in mind that there are few transitions missing - when each of the calls fails you should do error recovery and change the state of both machines properly.
Note that this design doesn't assume that you need to login to the site to be able to perform queries (and you can even perform a few queries, then login and then perform some more queries) - which proves you don't need any special "Connect with intent to login" states - it's the input that decides which transition will be triggered and you don't need to know it upfront.
Re: How to design a state machine in face of non-blocking I/O?
Thank you very much for the time you spent on these pictures.
I'd like to ask a couple of questions because it seems to me like pictures are not consistent.
Let's take Idle and Connecting states from Rysunek1.
1. Transition from Idle to Connecting is marked with IDLE, <CONNECT>/- what I take as "When <CONNECT> user event is received go to Connecting state. Don't know what "/-" part means, however.
2. The opposite transition is marked as {LOADED}/CONNECTED which I don't get. I understand the first part of this transition's description - {LOADED} - but have no idea what CONNECTED here is supposed to mean.
Shouldn't the format of each transition's description be exactly the same? In the above case the first description is in format state, event/- and the second description is in format event/?
Quote:
Originally Posted by
wysota
Note that this design doesn't assume that you need to login to the site to be able to perform queries
Why it doesn't assume this? It's fundamental constrain.
4 Attachment(s)
Re: How to design a state machine in face of non-blocking I/O?
I created sketches of current design and the one you're proposing to be able to visually compare one with the other. In addition to .png files I'm attaching zipped source of these sketches in .dia format in case someone would like to use/modify them easily in open source Dia application.
al.current.png - the design of the state machine I'm using currently
al.new.user.png - the one of the two state machines you are proposing, controlling user actions
al.new.network.png - the one of the two state machines you are proposing, controlling network state
I haven't put any transitions nor events in the sketches of the design you are proposing because I don't understand notation you used in your sketches. See my previous post.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
piotr.dobrogost
1. Transition from Idle to Connecting is marked with IDLE, <CONNECT>/- what I take as "When <CONNECT> user event is received go to Connecting state. Don't know what "/-" part means, however.
When the other subsystem is in "IDLE" state and CONNECT is received as input to the system, go to Connecting state and output nothing.
Quote:
2. The opposite transition is marked as {LOADED}/CONNECTED which I don't get. I understand the first part of this transition's description - {LOADED} - but have no idea what CONNECTED here is supposed to mean.
When you receive the network event, move into the idle state and output CONNECTED (which will move the other subsystem to the CONNECTED state).
Quote:
Shouldn't the format of each transition's description be exactly the same? In the above case the first description is in format state, event/- and the second description is in format event/?
It is the same: "<state of other machine>, <external input> / <output>"
Quote:
Why it doesn't assume this? It's fundamental constrain.
No, it's not. You might want to perform queries as an unlogged user. But anyway, it doesn't assume you have to do it but it doesn't mean you have to take that path - you can remove the dead transitions if you want.
Re: How to design a state machine in face of non-blocking I/O?
Quote:
Originally Posted by
wysota
When the other subsystem is in "IDLE" state and CONNECT is received (...)
This means you have to check the state of the other (let's call it network) subsystem from outside of it. I was looking for some method allowing to find out which state a QStateMachine is in but don't see any such... When you think of it it's logical there is no such a method as a state machine itself is a tool that should be used to handle logic internally. This reminds me of Untangling the Signal Slot Spaghetti with SCXML where the author states that the very important purpose of state machines is to remove handling program flow manually with if and switch statements. As you know instead of having one Idle state in the first subsystem (let's call it user subsystem) and checking what the state of the other one is we could just introduce new states like Idle-Connected and Idle-LoggedIn and this way we wouldn't need to check manually for the state of network subsystem from within user subsystem. This represents going from if type of managing program's logic to state machine type of managing program's logic. Dividing my current state machine into two new ones and checking (using if) what's the state of the other one is like going in opposite direction. Any thoughts?
Quote:
Originally Posted by
wysota
When you receive the network event, move into the idle state and output CONNECTED (which will move the other subsystem to the CONNECTED state).
I thought the idea was to direct network events from withing LoadFinished handler directly to this other subsystem which is responsible for network state. Would it be viable? Would it be better? Wouldn't then be an issue of synchronization between the two subsystems?
Quote:
Originally Posted by
wysota
It is the same: "<state of other machine>, <external input> / <output>"
Ok.
Quote:
Originally Posted by
wysota
you can remove the dead transitions if you want.
Ok.
