Comment récupérer d'une panne de machine à états finis?

13

Ma question peut sembler très scientifique, mais je pense que c'est un problème courant et les développeurs et programmeurs chevronnés auront, espérons-le, quelques conseils pour éviter le problème que je mentionne dans le titre. Btw., Ce que je décris ci-dessous est un vrai problème que j'essaie de résoudre de manière proactive dans mon projet iOS, je veux l'éviter à tout prix.

Par machine à états finis, je veux dire ceci> J'ai une interface utilisateur avec quelques boutons, plusieurs états de session pertinents pour cette interface utilisateur et ce que cette interface utilisateur représente, j'ai des données dont les valeurs sont partiellement affichées dans l'interface utilisateur, je reçois et gère certains déclencheurs externes (représenté par les rappels des capteurs). J'ai fait des diagrammes d'état pour mieux cartographier les scénarios pertinents qui sont souhaitables et qui peuvent être autorisés dans cette interface utilisateur et cette application. Alors que j'implémente lentement le code, l'application commence à se comporter de plus en plus comme elle le devrait. Cependant, je ne suis pas très sûr qu'il soit suffisamment robuste. Mes doutes viennent du fait que j'observe mon propre processus de réflexion et de mise en œuvre au fur et à mesure. J'étais confiant que j'avais tout couvert, mais c'était suffisant pour faire quelques tests bruts dans l'interface utilisateur et je me suis vite rendu compte qu'il y avait encore des lacunes dans le comportement .. Je les ai corrigés. cependant, comme chaque composant dépend et se comporte en fonction des entrées d'un autre composant, une certaine entrée de l'utilisateur ou d'une source externe déclenche une chaîne d'événements, des changements d'état ... etc. J'ai plusieurs composants et chacun se comporte comme ce déclencheur reçu en entrée -> déclencheur et son expéditeur analysés -> sortie quelque chose (un message, un changement d'état) basé sur l'analyse

Le problème est que ce n'est pas complètement autonome et mes composants (un élément de base de données, un état de session, l'état de certains boutons) ... POURRAIENT être modifiés, influencés, supprimés ou autrement modifiés, en dehors de la portée de la chaîne d'événements ou scénario souhaitable. (le téléphone se bloque, la batterie est vide, le téléphone s'éteint soudainement). Cela introduira une situation non valide dans le système, à partir de laquelle le système NE POURRAIT PAS être CAPABLE de récupérer. Je vois cela (bien que les gens ne réalisent pas que c'est le problème) dans beaucoup de mes applications concurrentes qui sont sur Apple Store, les clients écrivent des choses comme ça> "J'ai ajouté trois documents, et après y être allé et là, je ne peux pas les ouvrir, même si on les voit. " ou "J'ai enregistré des vidéos tous les jours, mais après avoir enregistré une vidéo trop log, je ne peux pas désactiver les sous-titres sur eux .., et le bouton pour les sous-titres ne fonctionne pas"

Ce ne sont que des exemples abrégés, les clients le décrivent souvent plus en détail ... à partir des descriptions et du comportement qui y sont décrits, je suppose que l'application particulière a une panne FSM.

La question ultime est donc de savoir comment puis-je éviter cela et comment protéger le système contre le blocage?

EDIT> Je parle dans le contexte de la vue d'un contrôleur de vue sur le téléphone, je veux dire une partie de l'application. Je comprends le modèle MVC, j'ai des modules séparés pour des fonctionnalités distinctes .. tout ce que je décris est pertinent pour un canevas sur l'interface utilisateur.

Earl Grey
la source
2
Cela ressemble à un étui pour les tests unitaires!
Michael K

Réponses:

7

Je suis sûr que vous le savez déjà, mais juste au cas où:

  1. Assurez-vous que chaque nœud du diagramme d'état possède un arc sortant pour CHAQUE type d'entrée légal (ou divisez les entrées en classes, avec un arc sortant pour chaque classe d'entrée).

    Chaque exemple que j'ai vu d'une machine d'état n'utilise qu'un seul arc sortant pour TOUTE entrée erronée.

    S'il n'y a pas de réponse définitive quant à ce qu'une entrée fera à chaque fois, c'est soit une condition d'erreur, soit il y a une autre entrée qui manque (qui devrait systématiquement générer un arc pour les entrées allant vers un nouveau nœud).

    Si un nœud n'a pas d'arc pour un type d'entrée, cela suppose que l'entrée ne se produira jamais dans la vie réelle (il s'agit d'une condition d'erreur potentielle qui ne serait pas gérée par la machine d'état).

  2. Assurez-vous que la machine d'état ne peut prendre ou suivre qu'un seul arc en réponse à l'entrée reçue (pas plus d'un arc).

    S'il existe différents types de scénarios d'erreur ou types d'entrées qui ne peuvent pas être identifiés au moment de la conception de la machine à états, les scénarios d'erreur et les entrées inconnues doivent se transformer en un état avec un chemin complètement séparé distinct des «arcs normaux».

    IE si une erreur ou une inconnue est reçue dans un état "connu", les arcs suivis à la suite de l'entrée de gestion des erreurs / inconnue ne doivent pas retourner dans les états dans lesquels la machine se trouverait si elle ne recevait que des entrées connues.

  3. Une fois que vous atteignez un état terminal (final), vous ne devriez pas pouvoir revenir à un non-terminal uniquement à l'état initial (initial).

  4. Pour une machine à états, il ne devrait pas y avoir plus d'un état de démarrage ou initial (basé sur les exemples que j'ai vus).

  5. Sur la base de ce que j'ai vu, une machine d'état ne peut représenter que l'état d'un problème ou d'un scénario.
    Il ne doit jamais y avoir plusieurs états possibles à la fois dans un diagramme d'état.
    Si je vois le potentiel de plusieurs états simultanés, cela me dit que je dois diviser le diagramme d'état en 2 ou plusieurs machines d'état distinctes qui ont le potentiel de chaque état à être modifié indépendamment.

UN B
la source
9

Le point d'une machine à états finis est qu'elle a des règles explicites pour tout ce qui peut arriver dans un état. C'est pourquoi c'est fini .

Par exemple:

if a:
  print a
elif b:
  print b

N'est pas fini, car nous pourrions obtenir une entrée c. Cette:

if a:
  print a
elif b:
  print b
else:
  print error

est fini, car toutes les entrées possibles sont prises en compte. Cela représente les entrées possibles dans un état , qui peuvent être distinctes de la vérification des erreurs. Imaginez une machine d'état avec les états suivants:

No money state. 
Not enough money state.
Pick soda state.

Dans les états définis, toutes les entrées possibles sont traitées pour l'argent inséré et le soda sélectionné. La panne de courant est en dehors de la machine d'état et "n'existe pas". Une machine d'état ne peut gérer les entrées que pour les états qu'elle possède, vous avez donc deux choix.

  1. Garantissez que toute action est atomique. La machine peut avoir une perte de puissance totale et tout laisser dans un état stable et correct.
  2. Étendez vos états pour inclure un problème inconnu et faites en sorte que les erreurs vous amènent à cet état, où les problèmes sont traités.

Pour référence, l' article wiki sur les machines à états est complet. Je suggère également Code Complete , pour les chapitres sur la construction de logiciels stables et fiables.

Spencer Rathbun
la source
"Nous pourrions obtenir l'entrée c" - c'est pourquoi les langages de typeafe sont si importants. Si votre type d'entrée est un booléen, vous pouvez obtenir trueet false, mais rien d'autre. Même alors, il est important de comprendre vos types - par exemple, les types nullables, les virgules flottantes NaN, etc.
MSalters
5

Les expressions régulières sont implémentées comme des machines à états finis. La table de transition générée par le code de bibliothèque aura un état d'échec intégré, pour gérer ce qui se passe si l'entrée ne correspond pas au modèle. Il y a au moins une transition implicite vers l'état de défaillance de presque tous les autres états.

Les grammaires du langage de programmation ne sont pas des FSM, mais les générateurs d'analyseurs (comme Yacc ou Bison) ont généralement un moyen de mettre un ou plusieurs états d'erreur, de sorte que des entrées inattendues peuvent entraîner le code généré à se retrouver dans un état d'erreur.

On dirait que votre FSM a besoin d'un état d'erreur ou d'un état d'échec ou de l'équivalent moral, ainsi que de transitions explicites (pour les cas que vous prévoyez) et implicites (pour les cas que vous n'anticipez pas) vers l'un des états d'échec ou d'erreur.

Bruce Ediger
la source
Pardonnez-moi, si ma question vous semble idiote, car je n'ai aucune éducation formelle en CS, et j'apprends la programmation depuis quelques mois. Cela signifie-t-il que, lorsque j'ai laissé dire une méthode de gestionnaire, pour un événement poussé pour un bouton, et dans cette méthode, j'ai une structure de conditionnement de commutateur if-else-switch modérément compliquée (20-30 lignes de code), que Dois-je toujours gérer les entrées indésirables de manière explicite? OU voulez-vous dire au niveau "mondial"? Dois-je avoir une classe distincte qui surveille ce FSM, et lorsque le problème se produit, il réinitialise les valeurs et les états?
Earl Grey
Expliquer les analyseurs générés par Yacc ou Bison me dépasse, mais généralement, vous traitez des cas connus, puis vous avez un petit bloc de code pour "tout le reste passe à l'état d'erreur ou d'échec". Le code de l'état d'erreur / d'échec ferait tout la réinitialisation. Vous devez peut-être avoir une valeur supplémentaire qui explique pourquoi vous êtes arrivé à l'état d'échec.
Bruce Ediger
Votre FSM doit avoir au moins un état pour les erreurs ou plusieurs états d'erreur pour différents types d'erreurs.
whatsisname
3

Le meilleur moyen d'éviter cela est le test automatisé .

La seule façon d'avoir une réelle confiance dans ce que fait votre code en fonction de certaines entrées est de les tester. Vous pouvez cliquer autour de votre application et essayer de faire les choses de manière incorrecte, mais cela n'évolue pas bien pour vous assurer de ne pas avoir de régressions. Au lieu de cela, vous pouvez créer un test qui passe une mauvaise entrée dans un composant de votre code et s'assure qu'il le gère de manière saine.

Cela ne sera pas en mesure de prouver que la machine d'état ne peut jamais être cassée, mais cela vous dira que la plupart des cas courants sont traités correctement et ne cassent pas d'autres choses.

unholysampler
la source
2

ce que vous recherchez, c'est une gestion des exceptions. Une philosophie de conception pour éviter de rester dans un état incohérent est documentée comme the way of the samuraisuit: retour victorieux ou non retour. En d'autres termes: un composant doit vérifier toutes ses entrées et s'assurer qu'il pourra les traiter normalement. Si ce n'est pas le cas, cela devrait déclencher une exception contenant des informations utiles.

Une fois qu'une exception est levée, elle bouillonne dans la pile. Vous devez définir une couche de gestion des erreurs qui saura quoi faire. Si un fichier utilisateur est corrompu, expliquez à votre client que les données sont perdues et recréez un fichier vide propre.

La partie importante ici est de revenir à un état de fonctionnement et d'éviter la propagation des erreurs. Lorsque vous avez terminé, vous pouvez travailler sur des composants individuels pour les rendre plus robustes.

Je ne suis pas un expert objectif-c, mais cette page devrait être un bon point de départ:

http://developer.apple.com/library/ios/#documentation/cocoa/conceptual/objectivec/Chapters/ocExceptionHandling.html

Simon Bergot
la source
1

Oubliez votre machine à états finis. Ce que vous avez ici est une grave situation de multi-threading . Vous pouvez appuyer sur n'importe quel bouton à tout moment et vos déclencheurs externes peuvent se déclencher à tout moment. Les boutons sont probablement tous sur un même fil, mais un déclencheur peut littéralement s'éteindre au même instant que l'un des boutons ou un, plusieurs ou tous les autres déclencheurs.

Ce que vous devez faire, c'est déterminer votre état au moment où vous décidez d'agir. Obtenez tous les boutons et les états de déclenchement. Enregistrez-les dans des variables locales . Les valeurs d'origine peuvent changer à chaque fois que vous les regardez. Agissez ensuite sur la situation telle que vous l'avez. C'est un instantané de l'apparence du système à un moment donné. Une milliseconde plus tard, cela pourrait sembler très différent, mais avec le multithreading, il n'y a pas vraiment de courant "maintenant" auquel vous pouvez vous accrocher, seulement une image que vous avez enregistrée dans des variables locales.

Ensuite, vous devez répondre à votre état - historique - enregistré. Tout est fixe et vous devez avoir une action pour tous les états possibles. Il ne prendra pas en compte les modifications apportées entre le moment où vous avez pris l'instantané et le moment où vous affichez vos résultats, mais c'est la vie dans le monde multi-threading. Et vous devrez peut-être utiliser la synchronisation pour éviter que votre instantané ne soit trop flou. (Vous ne pouvez pas être à jour, mais vous pouvez vous rapprocher de la totalité de votre état à un instant donné.)

Lisez sur le multi-threading. Vous avez beaucoup à apprendre. Et à cause de ces déclencheurs, je ne pense pas que vous puissiez utiliser un grand nombre des astuces souvent fournies pour faciliter le traitement parallèle ("Worker Threads" et autres). Vous ne faites pas de "traitement parallèle"; vous n'essayez pas d'utiliser 75% de 8 cœurs. Vous utilisez 1% de l'ensemble du processeur, mais vous avez des threads très indépendants et très interactifs, et il faudra beaucoup de réflexion pour les synchroniser et empêcher la synchronisation de verrouiller le système.

Testez à la fois sur des machines monocœur et multicœurs; J'ai trouvé qu'ils se comportaient plutôt différemment avec le multi-threading. Les machines à cœur unique génèrent moins de bogues multithreads, mais ces bogues sont beaucoup plus étranges. (Bien que les machines multi-cœurs vous époustouflent jusqu'à ce que vous vous y habituiez.)

Une dernière pensée désagréable: ce n'est pas facile à tester. Vous devrez générer des déclencheurs aléatoires et des pressions de bouton et laisser le système fonctionner à plat pendant un certain temps pour voir ce qui se passe. Le code multithread n'est pas déterministe. Quelque chose peut échouer une fois sur un milliard d'exécutions, simplement parce que le chronomètre était arrêté pendant une nanoseconde. Mettez des instructions de débogage (avec des instructions if prudentes pour éviter 999 999 999 messages inutiles) et vous devez effectuer un milliard d'exécutions juste pour obtenir un message utile. Heureusement, les machines sont très rapides de nos jours.

Désolé de jeter tout cela sur vous si tôt dans votre carrière. J'espère que quelqu'un trouvera une autre réponse avec un moyen de contourner tout cela (je pense qu'il y a des choses qui pourraient apprivoiser les déclencheurs, mais vous avez toujours le conflit déclencheur / bouton). Si c'est le cas, cette réponse vous permettra au moins de savoir ce que vous manquez. Bonne chance.

RalphChapin
la source