Σήμερα θα μιλήσουμε για πολυβόλα, αλλά σε καμία περίπτωση για αυτά που κρατούν στα χέρια των στρατιωτών του ρωσικού στρατού. Θα αφορά ένα τόσο ενδιαφέρον στυλ προγραμματισμού μικροελεγκτών όπως ο αυτόματος προγραμματισμός. Πιο συγκεκριμένα, αυτό δεν είναι καν ένα στυλ προγραμματισμού, αλλά μια ολόκληρη ιδέα, χάρη στην οποία ένας προγραμματιστής μικροελεγκτή μπορεί να απλοποιήσει πολύ τη ζωή του. Χάρη σε αυτό, πολλές εργασίες που παρουσιάζονται στον προγραμματιστή επιλύονται πολύ πιο εύκολα και ευκολότερα, σώζοντας τον προγραμματιστή από πονοκεφάλους. Παρεμπιπτόντως, ο προγραμματισμός αυτόματα ονομάζεται συχνά Τεχνολογία SWITCH.

Θέλω να σημειώσω ότι το κίνητρο για τη συγγραφή αυτής της ανάρτησης ήταν μια σειρά άρθρων σχετικά με την τεχνολογία SWITCH Βλαντιμίρ Ταταρτσέφσκι. Η σειρά άρθρων ονομάζεται «Εφαρμογή της τεχνολογίας SWITCH στην ανάπτυξη εφαρμοσμένων λογισμικόγια μικροελεγκτές "Έτσι σε αυτό το άρθρο θα προσπαθήσω ως επί το πλείστον να δώσω ένα παράδειγμα κώδικα εργασίας και την περιγραφή του.

Παρεμπιπτόντως, έχω προγραμματίσει μια σειρά από άρθρα σχετικά με τον προγραμματισμό, στα οποία θα εξετάσω λεπτομερώς τις τεχνικές προγραμματισμού για μικροελεγκτές ATS, μην χάσετε…. Λοιπόν πάμε!

Το πρόγραμμα εκτελεί διαδοχικά τις εντολές που έχει ορίσει ο προγραμματιστής. Για τα συνηθισμένα πρόγραμμα υπολογιστήείναι απολύτως φυσιολογικό όταν το πρόγραμμα έχει ολοκληρώσει και έχει σταματήσει την εκτέλεσή του, ενώ εμφανίζει τα αποτελέσματα της εργασίας του στην οθόνη.

Ένα πρόγραμμα για έναν μικροελεγκτή δεν μπορεί απλώς να τερματίσει την εκτέλεσή του. Φανταστείτε ότι ενεργοποιείτε τη συσκευή αναπαραγωγής ή το μαγνητόφωνο. Έχετε πατήσει το κουμπί λειτουργίας, επιλέξατε το τραγούδι που θέλετε και απολαύσατε τη μουσική. Ωστόσο, όταν η μουσική σταμάτησε να κυματίζει στο τύμπανο του αυτιού σας, η συσκευή αναπαραγωγής πάγωσε και δεν αντέδρασε με κανέναν τρόπο στο πάτημα των κουμπιών, και ακόμη περισσότερο στους χορούς σας με ένα ντέφι.

Ποιό είναι το λάθος σ'αυτό? Όλα είναι καλά - το χειριστήριο, αυτό που βρίσκεται στα έγκατα της συσκευής σας, μόλις ολοκλήρωσε την εκτέλεση του προγράμματός του. Βλέπετε, κατά κάποιο τρόπο αποδεικνύεται αμήχανα.

Από εδώ λοιπόν συμπεραίνουμε ότι το πρόγραμμα για τον μικροελεγκτή απλά δεν πρέπει να σταματήσει. Στην ουσία θα έπρεπε να είναι ατελείωτος κύκλος- Μόνο σε αυτή την περίπτωση ο παίκτης μας θα λειτουργούσε σωστά. Περαιτέρω θα σας δείξω ποιες είναι οι κατασκευές του κώδικα προγράμματος για μικροελεγκτές, δεν πρόκειται καν για κατασκευές, αλλά για κάποια στυλ προγραμματισμού.

Στυλ προγραμματισμού.

"Styles of programming" - ακούγεται σαν κάτι ακατανόητο, αλλά οκ. Τι εννοώ με αυτό;Ας φανταστούμε ότι κάποιος δεν έχει ασχοληθεί ποτέ με τον προγραμματισμό, δηλαδή γενικά με ένα γεμάτο βραστήρα.

Αυτό το άτομο διάβασε πολλά βιβλία σχετικά με τον προγραμματισμό, μελέτησε όλες τις βασικές κατασκευές της γλώσσας.Συλλέγει πληροφορίες σπιθαμή προς σπιθαμή, αφού πλέον η πρόσβαση στις πληροφορίες είναι απεριόριστη. Καλά όλα αυτά, αλλά πώς θα είναι τα πρώτα του προγράμματα; Μου φαίνεται ότι δεν θα φιλοσοφήσει, αλλά θα ακολουθήσει το μονοπάτι από το απλό στο σύνθετο.

Αυτά τα στυλ λοιπόν είναι τα βήματα που οδηγούν από ένα απλό επίπεδο σε ένα πιο σύνθετο, αλλά ταυτόχρονα πιο αποτελεσματικό.

Στην αρχή δεν σκέφτηκα κανένα χαρακτηριστικά σχεδίουπρογράμματα. Μόλις σχημάτισα τη λογική του προγράμματος - σχεδίασα ένα διάγραμμα ροής και έγραψα τον κώδικα. Από την οποία έτρεχα συνεχώς σε μια τσουγκράνα. Αλλά αυτή ήταν η πρώτη φορά που δεν ασχολήθηκα και χρησιμοποίησα το στυλ "απλού βρόχου", μετά άρχισα να χρησιμοποιώ διακοπές, μετά υπήρχαν αυτόματα και φύγαμε ...

1. Απλό looping. Σε αυτήν την περίπτωση, το πρόγραμμα επαναλαμβάνεται χωρίς λεπτές αποχρώσεις και αυτό έχει τα θετικά και τα αρνητικά του. Επιπλέον, μόνο στην απλότητα της προσέγγισης, δεν χρειάζεται να εφεύρετε πονηρά σχέδια, γράφετε όπως νομίζετε (σκάβοντας σταδιακά τον δικό σας τάφο).

Void main (void) (initial_AL (); // αρχικοποίηση της περιφέρειας ενώ (1) (Leds_BLINK (); // συνάρτηση led flasher signal_on (); // συνάρτηση για ενεργοποίηση του σήματος signal_off (); // λειτουργία για την απενεργοποίηση του σήματος l = κουμπί (); // η μεταβλητή που είναι υπεύθυνη για το πάτημα του διακόπτη κουμπιών (l) // Ανάλογα με την τιμή της μεταβλητής, εκτελείται αυτή ή εκείνη η ενέργεια (περίπτωση 1: (Deistvie1 (); // Αντί για μια συνάρτηση, μπορεί να υπάρξει υπό όρους χειριστή Deistvie2 (); // ή μερικές ακόμη διακλαδώσεις διακόπτη θήκη Deistvie3 (); Deistvie4 (); Deistvie5 (); ) περίπτωση 2: (Deistvie6 (); Deistvie7 (); Deistvie8 (); Deistvie9 (); Deistvie10 (); ... ... ... ... ... ... ... ... )))

Το σημείο λειτουργίας του προγράμματος κινείται με τη σειρά. Σε αυτήν την περίπτωση, όλες οι ενέργειες, οι συνθήκες και οι κύκλοι εκτελούνται διαδοχικά. Ο κώδικας αρχίζει να επιβραδύνεται, πρέπει να εισαγάγετε πολλές περιττές συνθήκες, περιπλέκοντας έτσι την αντίληψη.

Όλα αυτά μπερδεύουν πολύ το πρόγραμμα, δημιουργώντας ένα κουβάρι συνθηκών από τον κώδικα. Ως αποτέλεσμα, δεν μπορείτε να προσθέσετε ή να αφαιρέσετε σε αυτόν τον κώδικα, γίνεται σαν ένα μονολιθικό κομμάτι. Φυσικά, όταν ο όγκος δεν είναι μεγάλος, ο κώδικας προσφέρεται για τροποποιήσεις, αλλά όσο πιο πολύ, τόσο πιο περίπλοκο.

Με αυτήν την προσέγγιση, έγραψα πολλά προγράμματα, δεν ήταν μεγάλα και λειτουργούσαν αρκετά, αλλά η σαφήνεια άφηνε πολλά να είναι επιθυμητή. Για να προσθέσω κάποια νέα συνθήκη, έπρεπε να φτυαρίσω ολόκληρο τον κωδικό, γιατί όλα ήταν δεμένα. Αυτό προκάλεσε πολλά λάθη και πονοκεφάλους. Ο μεταγλωττιστής ορκίστηκε όσο μπορούσε, ο εντοπισμός σφαλμάτων ενός τέτοιου προγράμματος μετατράπηκε σε κόλαση.

2. Βρόχος + διακόπτει.

Μπορείτε να επιλύσετε εν μέρει έναν ατελείωτο κύκλο πέδησης χρησιμοποιώντας διακοπές. Οι διακοπές βοηθούν να ξεφύγετε από τον φαύλο κύκλο, βοηθούν να μην χάσετε ένα σημαντικό γεγονός, προσθέστε πρόσθετη λειτουργικότητα (διακοπές από χρονόμετρα, εξωτερικές διακοπές).

Ας υποθέσουμε ότι μπορείτε να κλείσετε την επεξεργασία των κουμπιών σε μια διακοπή ή να παρακολουθήσετε ένα σημαντικό συμβάν. Ως αποτέλεσμα, το πρόγραμμα γίνεται πιο διαισθητικό αλλά όχι λιγότερο μπερδεμένο.

Δυστυχώς, η διακοπή δεν θα σας σώσει από το χάος στο οποίο μετατρέπεται το πρόγραμμα. Δεν θα είναι δυνατό να χωριστεί σε μέρη αυτό που αποτελεί ένα ενιαίο σύνολο.

3. Αυτόματος προγραμματισμός.

Εδώ φτάνουμε στο κύριο θέμα αυτού του άρθρου. Ο προγραμματισμός σε μηχανές πεπερασμένης κατάστασης εξαλείφει τα μειονεκτήματα που ενυπάρχουν στα δύο πρώτα παραδείγματα. Το πρόγραμμα γίνεται πιο απλό και εύκολο στην τροποποίηση.

Ένα πρόγραμμα γραμμένο σε στυλ αυτόματου είναι σαν ένας διακόπτης που αλλάζει σε μια κατάσταση ή στην άλλη ανάλογα με τις συνθήκες. Ο προγραμματιστής αρχικά γνωρίζει τον αριθμό των καταστάσεων.

Κατά έναν πρόχειρο τρόπο, είναι σαν διακόπτης φώτων. Υπάρχουν δύο καταστάσεις ενεργοποίησης και απενεργοποίησης και δύο συνθήκες ενεργοποίησης και απενεργοποίησης. Λοιπόν, πρώτα πρώτα.

Εφαρμογή multitasking στην τεχνολογία μεταγωγής.

Ο μικροελεγκτής μπορεί να ελέγχει το φορτίο, να αναβοσβήνουν τα LED, να παρακολουθεί τα πλήκτρα και πολλά άλλα. Πώς όμως να τα κάνεις όλα αυτά ταυτόχρονα; Υπάρχουν πολλές λύσεις για την αντιμετώπιση αυτού του ζητήματος. Το πιο απλό που έχω ήδη αναφέρει είναι η χρήση των διακοπών.

Ενώ το πρόγραμμα εκτελείται, όταν εμφανίζεται μια διακοπή, ο ελεγκτής αποσπάται από την εκτέλεση του κώδικα προγράμματος και εκτελεί για λίγο ένα άλλο τμήμα του προγράμματος για το οποίο ευθύνεται η διακοπή. Η διακοπή θα λειτουργήσει, τότε το σημείο λειτουργίας του προγράμματος θα συνεχίσει από το σημείο από το οποίο ο ελεγκτής διακόπηκε από τη διακοπή (η ίδια η λέξη υποδηλώνει ότι ο ελεγκτής έχει διακοπεί).

Ένας άλλος τρόπος για να εφαρμόσετε το multitasking είναι να χρησιμοποιήσετε λειτουργικά συστήματα... Ναι όντως, έχουν ήδη αρχίσει να εμφανίζονται μικρά λειτουργικά συστήματα, τα οποία μπορούν να εφαρμοστούν σε ελεγκτή χαμηλής κατανάλωσης. Αλλά συχνά αυτή η μέθοδος αποδεικνύεται κάπως περιττή. Άλλωστε, γιατί να σπαταλάτε τους πόρους του ελεγκτή με περιττή δουλειά όταν είναι πολύ πιθανό να τα βγάλετε πέρα ​​με λίγο αίμα.

Σε προγράμματα που γράφτηκαν με χρήση τεχνολογίας διακόπτη, μια παρόμοια «ψευδαίσθηση» πολλαπλών εργασιών επιτυγχάνεται χάρη στο σύστημα ανταλλαγής μηνυμάτων. Έγραψα "μια ψευδαίσθηση" γιατί πραγματικά είναι, επειδή ένα πρόγραμμα φυσικά δεν μπορεί να εκτελέσει διαφορετικά μέρη του κώδικα ταυτόχρονα. Θα μιλήσω για το σύστημα ανταλλαγής μηνυμάτων λίγο παρακάτω.

Σύστημα ανταλλαγής μηνυμάτων.

Μπορείτε να επιλύσετε πολλές διαδικασίες και να δημιουργήσετε την ψευδαίσθηση του multitasking χρησιμοποιώντας το σύστημα ανταλλαγής μηνυμάτων.

Ας υποθέσουμε ότι χρειαζόμαστε ένα πρόγραμμα στο οποίο ενεργοποιείται το LED. Εδώ έχουμε δύο μηχανήματα, ας τα ονομάσουμε LEDON - το μηχάνημα που είναι υπεύθυνο για την ενεργοποίηση του LED και το μηχάνημα LEDOFF - το μηχάνημα που είναι υπεύθυνο για το σβήσιμο του LED.

Κάθε ένα από τα μηχανήματα έχει δύο καταστάσεις, δηλαδή το μηχάνημα μπορεί να βρίσκεται σε ενεργή ή σε ανενεργή κατάσταση, καθώς ο διακόπτης είναι είτε ενεργοποιημένος είτε απενεργοποιημένος.

Όταν ενεργοποιείται το ένα μηχάνημα, το LED ανάβει, όταν ενεργοποιείται το άλλο, το LED σβήνει. Ας δούμε ένα μικρό παράδειγμα:

Int main (void) (INIT_PEREF (); // αρχικοποίηση περιφερειακών (LED) InitGTimers (); // αρχικοποίηση χρονοδιακόπτων InitMessages (); // προετοιμασία του μηχανισμού επεξεργασίας μηνυμάτων InitLEDON (); // προετοιμασία του μηχανήματος LEDON InitLEDOFF (); // προετοιμασία του αυτόματου LEDOFF SendMessage (MSG_LEDON_ACTIVATE); // ενεργοποίηση του αυτόματου LEDON sei (); // Ενεργοποίηση διακοπών // Κύριο βρόχο προγράμματος ενώ (1) (ProcessLEDON (); // επανάληψη του αυτόματου LEDON ProcessLEDOFF (); // επανάληψη του αυτόματου LEDOFF ProcessMessages (); // επεξεργασία μηνυμάτων);)

Στις γραμμές 3-7 γίνονται διάφορες αρχικοποιήσεις, οπότε δεν μας ενδιαφέρει ιδιαίτερα αυτό τώρα. Αλλά τότε συμβαίνει το εξής: πριν ξεκινήσουμε τον κύριο βρόχο (ενώ (1)), στέλνουμε ένα μήνυμα στο μηχάνημα

Αποστολή μηνύματος (MSG_LEDON_ACTIVATE)

υπεύθυνος για το φωτισμό του LED. Χωρίς αυτό το μικρό βήμα, το όργανό μας δεν θα λειτουργήσει. Στη συνέχεια, ο κύριος βρόχος endless while κάνει το μεγαλύτερο μέρος της δουλειάς.

Μικρή παρέκκλιση:

Το μήνυμα έχει τρεις καταστάσεις. Δηλαδή, η κατάσταση του μηνύματος μπορεί να είναι ανενεργή, ρυθμισμένη αλλά ανενεργή και ενεργή κατάσταση.

Αποδεικνύεται ότι το μήνυμα ήταν αρχικά ανενεργό, όταν στείλαμε το μήνυμα, πήρε την κατάσταση "εγκατεστημένο αλλά ανενεργό". Και αυτό μας δίνει το εξής. Όταν το πρόγραμμα εκτελείται διαδοχικά, το αυτόματο LEDON δεν λαμβάνει το μήνυμα. Υπάρχει μια αδράνεια επανάληψη του αυτόματου LEDON στην οποία το μήνυμα απλά δεν μπορεί να ληφθεί. Εφόσον το μήνυμα έχει την κατάσταση "εγκατεστημένο αλλά ανενεργό", το πρόγραμμα συνεχίζει την εκτέλεσή του.

Αφού όλα τα αυτόματα είναι σε αδράνεια, η ουρά έρχεται στη συνάρτηση ProcessMessages (). Αυτή η συνάρτηση τοποθετείται πάντα στο τέλος του βρόχου, αφού έχουν ολοκληρωθεί όλες οι επαναλήψεις των αυτόματα. Η συνάρτηση ProcessMessages () απλώς αλλάζει το μήνυμα από την κατάσταση "ρυθμισμένη αλλά ανενεργή" στην κατάσταση "ενεργό".

Όταν ο ατελείωτος βρόχος ολοκληρώσει τον δεύτερο κύκλο, η εικόνα είναι ήδη εντελώς διαφορετική. Η επανάληψη του αυτόματου ProcessLEDON δεν θα είναι πλέον αδρανής. Το μηχάνημα αυτόματης πώλησης θα μπορεί να λάβει το μήνυμα, να μεταβεί στην κατάσταση αναμμένης και, με τη σειρά του, θα στείλει επίσης το μήνυμα. Θα απευθύνεται στο μηχάνημα LEDOFF και κύκλος ζωήςτα μηνύματα θα επαναληφθούν.

Θέλω να σημειώσω ότι τα μηνύματα που έχουν την κατάσταση "ενεργό" καταστρέφονται όταν συναντούν τη λειτουργία ProcessMessages. Επομένως, ένα μήνυμα μπορεί να ληφθεί μόνο από ένα μηχάνημα. Υπάρχει ένας ακόμη τύπος μηνυμάτων - αυτά είναι μηνύματα εκπομπής, αλλά δεν θα τα εξετάσω, καλύπτονται επίσης καλά στα άρθρα του Ταταρτσέφσκι.

Χρονοδιακόπτες

Με τη σωστή οργάνωση των μηνυμάτων, μπορούμε να ελέγξουμε τη σειρά των κρατικών μηχανών, αλλά δεν μπορούμε να τα βγάλουμε πέρα ​​μόνο με μηνύματα.

Ίσως έχετε παρατηρήσει ότι το προηγούμενο τμήμα κώδικα παραδείγματος δεν θα λειτουργήσει όπως έπρεπε. Τα μηχανήματα θα ανταλλάξουν μηνύματα, τα LED θα αλλάξουν, αλλά δεν θα το δούμε. Θα δούμε μόνο ένα αμυδρά φωτισμένο LED.

Κι αυτό γιατί δεν σκεφτήκαμε την αρμόδια επεξεργασία των καθυστερήσεων. Άλλωστε το εναλλασσόμενο on-off των LED δεν μας αρκεί, το LED θα πρέπει να καθυστερεί σε κάθε κατάσταση, ας πούμε για ένα δευτερόλεπτο.

Ο αλγόριθμος θα είναι ο εξής:

Μπορείτε να κάνετε κλικ για μεγέθυνση

Ξέχασα να προσθέσω σε αυτό το μπλοκ διάγραμμα ότι όταν ο χρονοδιακόπτης είναι ενεργοποιημένος, φυσικά, εκτελείται μια ενέργεια - ανάβει το LED ή σβήνει.

1. Μπαίνουμε στην κατάσταση αποδεχόμενοι το μήνυμα.

2. Ελέγχουμε τις ενδείξεις του χρονοδιακόπτη / μετρητή, εάν είναι διακεκομμένο, τότε εκτελούμε την ενέργεια, διαφορετικά στέλνουμε απλώς ένα μήνυμα στον εαυτό μας.

3. Στέλνουμε το μήνυμα στο επόμενο μηχάνημα.

4. Έξοδος

Στην επόμενη είσοδο όλα επαναλαμβάνονται.

Πρόγραμμα τεχνολογίας SWITCH. Τρία βήματα.

Ας γράψουμε ένα πρόγραμμα σε μηχανές κατάστασης και για αυτό πρέπει να κάνουμε μόνο τρία απλά βήματα... Το πρόγραμμα θα είναι απλό, αλλά αξίζει να ξεκινήσετε με απλά πράγματα. Ένα πρόγραμμα με εναλλαγή LED είναι κατάλληλο για εμάς. Αυτό είναι ένα πολύ καλό παράδειγμα, οπότε ας μην επινοούμε κάτι νέο.

Θα γράψω το πρόγραμμα στη γλώσσα C, αλλά αυτό δεν σημαίνει καθόλου ότι σε μηχανές πεπερασμένης κατάστασης χρειάζεται να γράφετε μόνο σε C, είναι πολύ πιθανό να χρησιμοποιήσετε οποιαδήποτε άλλη γλώσσα προγραμματισμού.

Το πρόγραμμά μας θα είναι αρθρωτό και επομένως θα χωρίζεται σε πολλά αρχεία. Θα έχουμε τις παρακάτω ενότητες:

• Η ενότητα του κύριου βρόχου προγράμματος περιέχει τα αρχεία leds_blink.c, HAL.c, HAL.h
• Μονάδα χρονοδιακόπτη περιέχει αρχεία timers.c, timers.h
• Μονάδα επεξεργασίας μηνυμάτων περιέχει αρχεία messages.c, messages.h
  
• Μονάδα μηχανής 1 περιέχει αρχεία ledon.c, ledon.h
• Μονάδα μηχανής 2 περιέχει αρχεία ledoff.c, ledoff .h

Βήμα 1.

Δημιουργούμε ένα έργο και συνδέουμε αμέσως τα αρχεία των στατικών μας μονάδων σε αυτό: timers.c, timers.h, messages.c, messages.h.

Το αρχείο leds_blink.c της κύριας μονάδας βρόχου του προγράμματος.

#include "hal.h" #include "messages.h" // module processing message #include "timers.h" // timer module // Timer interrupts // ############# # ############################################## ############################ ISR (TIMER0_OVF_vect) // μεταπήδηση κατά μήκος του διανύσματος διακοπής (υπερχείλιση μετρητή T0) (ProcessTimers (); // Χειριστής διακοπής χρονοδιακόπτη) // ####################################################################################### ############################################# int main (κενό ) (INIT_PEREF (); // προετοιμασία της περιφέρειας (LED) InitGTimers (); // προετοιμασία των χρονόμετρων InitMessages (); // προετοιμασία του μηχανισμού επεξεργασίας μηνυμάτων InitLEDON (); // προετοιμασία του μηχανήματος LEDON InitLEDOFF () ; StartGTimer ( TIMER_SEK); // Εκκίνηση του χρονοδιακόπτη SendMessage (MSG_LEDON_ACTIVATE); // ενεργοποίηση του αυτόματου FSM1 sei (); // Ενεργοποίηση διακοπών // Κύριο βρόχο προγράμματος ενώ (1) (ProcessLEDON (); // επανάληψη της LEDON του αυτόματου ProcessLEDOFF (); ProcessMessages ( ); // επεξεργασία μηνυμάτων);)

Στις πρώτες γραμμές, οι υπόλοιπες μονάδες συνδέονται με το κύριο πρόγραμμα. Εδώ βλέπουμε ότι η μονάδα χρονοδιακόπτη και η μονάδα επεξεργασίας μηνυμάτων είναι συνδεδεμένα. Περαιτέρω στο κείμενο το πρόγραμμα πάειδιάνυσμα διακοπής υπερχείλισης.

Από τη γραμμή int main (void), μπορούμε να πούμε ότι ξεκινά το κύριο πρόγραμμα. Και ξεκινά με την αρχικοποίηση των πάντων και όλων. Εδώ αρχικοποιούμε τα περιφερειακά, δηλαδή ορίζουμε τις αρχικές τιμές για τις θύρες εισόδου/εξόδου του συγκριτή και όλα τα υπόλοιπα περιεχόμενα του ελεγκτή. Όλα αυτά γίνονται από τη συνάρτηση INIT_PEREF, εδώ την τρέχουμε, αν και το κύριο σώμα της βρίσκεται στο αρχείο hal.c.

Στη συνέχεια, βλέπουμε την προετοιμασία των χρονόμετρων, τη μονάδα επεξεργασίας μηνυμάτων και την προετοιμασία των μηχανών. Εδώ, αυτές οι λειτουργίες είναι επίσης εύκολο να εκτελεστούν, αν και οι ίδιες οι συναρτήσεις είναι γραμμένες στα αρχεία των μονάδων τους. Βλέπεις πόσο βολικό είναι. Το κύριο κείμενο του προγράμματος παραμένει ευανάγνωστο και δεν είναι γεμάτο με περιττό κώδικα από τον οποίο ο διάβολος σου σπάει το πόδι.

Οι κύριες αρχικοποιήσεις έχουν τελειώσει τώρα πρέπει να ξεκινήσουμε τον κύριο βρόχο. Για να γίνει αυτό, στέλνουμε ένα μήνυμα έναρξης και, επιπλέον, ξεκινάμε το ρολόι μας - ξεκινάμε το χρονόμετρο.

StartGTimer (TIMER_SEK); // Εκκίνηση του χρονοδιακόπτη SendMessage (MSG_LEDON_ACTIVATE); // ενεργοποιήστε τη μηχανή FSM1

Και ο κύριος βρόχος, όπως είπα, φαίνεται πολύ απλός. Καταγράφουμε τις λειτουργίες όλων των μηχανών, απλώς τις σημειώνουμε σε μια στήλη, χωρίς να τηρούμε τη σειρά. Αυτές οι λειτουργίες είναι χειριστές αυτόματα και βρίσκονται στις μονάδες αυτομάτων. Αυτή η αυτόματη πυραμίδα ολοκληρώνεται με τη λειτουργία της μονάδας επεξεργασίας μηνυμάτων. Φυσικά, έχω ήδη μιλήσει για αυτό νωρίτερα όταν ασχοληθήκαμε με το σύστημα αποστολής μηνυμάτων. Τώρα μπορείτε να δείτε πώς μοιάζουν δύο ακόμη αρχεία της ενότητας του κύριου βρόχου προγράμματος

Το Hal.h είναι το αρχείο κεφαλίδας για την κύρια μονάδα βρόχου.

#ifndef HAL_h #define HAL_h #include #περιλαμβάνω // Τυπική βιβλιοθήκη με διακοπές #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR // comparator #define ViklKomparator 1<

Όπως ίσως έχετε παρατηρήσει, αυτό το αρχείο, στην ουσία του, δεν περιέχει ούτε μια γραμμή εκτελέσιμου κώδικα - όλα αυτά είναι αντικαταστάσεις μακροεντολών και συνδέσεις βιβλιοθήκης. Η κατοχή αυτού του αρχείου κάνει τη ζωή πραγματικά καλή, βελτιώνει τη σαφήνεια.

Αλλά το αρχείο Hal.c είναι ήδη ένα εκτελέσιμο αρχείο, και όπως ήδη ανέφερα, περιέχει διάφορες αρχικοποιήσεις των περιφερειακών.

#include "hal.h" void INIT_PEREF (void) (// Initialize I / O ports // ########################## ############################################## ### Komparator = ViklKomparator; // προετοιμασία του συγκριτή - απενεργοποίηση DDRD = 1<

Λοιπόν, έδειξα τη μονάδα του κύριου βρόχου προγράμματος, τώρα πρέπει να κάνουμε το τελευταίο βήμα, πρέπει να γράψουμε τις μονάδες των ίδιων των μηχανών.

Βήμα 3.

Μένει να γράψουμε τα modules των κρατικών μηχανών, στην περίπτωσή μας το μηχάνημα LEDON και το μηχάνημα LEDOFF. Για αρχή θα δώσω το κείμενο του προγράμματος του μηχανήματος που ανάβει το LED, το αρχείο ledon.c.

// αρχείο ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" ανυπόγραφο char ledon_state; // κατάσταση μεταβλητής void InitLEDON (void) (ledon_state = 0; // εδώ μπορείτε να αρχικοποιήσετε άλλες // μεταβλητές μηχανής, εάν υπάρχουν) void ProcessLEDON (void) (switch (ledon_state) (περίπτωση 0: // ανενεργή κατάσταση εάν (GetMessage (MSG_LEDON_ACTIVATE)) // εάν υπάρχει μήνυμα, θα γίνει αποδεκτό (// και ο χρονοδιακόπτης θα ελεγχθεί εάν (GetGTimer (TIMER_SEK) == one_sek) // εάν ο χρονοδιακόπτης έχει μετρήσει 1 δευτερόλεπτο, τότε εκτελέστε (StopGTimer (TIMER_SEK ) PORTD = 1<

Εδώ, στις πρώτες γραμμές, όπως πάντα, συνδέονται βιβλιοθήκες και δηλώνονται οι μεταβλητές. Επιπλέον, έχουμε ήδη προχωρήσει τις λειτουργίες με τις οποίες έχουμε ήδη συναντηθεί. Αυτή είναι η λειτουργία προετοιμασίας του μηχανήματος InitLEDON και η λειτουργία του χειριστή του ίδιου του μηχανήματος ProcessLEDON.

Στο σώμα του χειριστή, οι λειτουργίες από τη μονάδα χρονοδιακόπτη και τη μονάδα μηνυμάτων υποβάλλονται ήδη σε επεξεργασία. Και η λογική του ίδιου του αυτόματου βασίζεται στην κατασκευή του διακόπτη. Και εδώ μπορείτε να παρατηρήσετε ότι ο χειριστής του αυτόματου μπορεί επίσης να είναι περίπλοκος προσθέτοντας αρκετούς διακόπτες θήκης.

Το αρχείο κεφαλίδας για το αυτόματο θα είναι ακόμα πιο απλό:

// αρχείο fsm1 #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON (void); void ProcessLEDON (κενό); #τέλος εαν

Εδώ συμπεριλαμβάνουμε το αρχείο γεφύρωσης hal.h και υποδεικνύουμε επίσης τα πρωτότυπα των συναρτήσεων.

Το αρχείο που είναι υπεύθυνο για την απενεργοποίηση του LED θα φαίνεται σχεδόν το ίδιο μόνο σε μια κατοπτρική αντανάκλαση, επομένως δεν θα το εμφανίσω εδώ - είμαι απρόθυμος 🙂

Μπορείτε να κατεβάσετε όλα τα αρχεία του έργου από αυτόν τον σύνδεσμο ==== >>> ΣΥΝΔΕΣΜΟΣ.

Εδώ είναι μόνο τρία βήματα και το πρόγραμμά μας έχει αποκτήσει ολοκληρωμένη μορφή, πράγμα που σημαίνει ότι η αποστολή μου για σήμερα τελείωσε και ήρθε η ώρα να ολοκληρώσω. Μου φαίνεται ότι οι πληροφορίες που δίνονται σε αυτό το άρθρο θα είναι πολύ χρήσιμες για εσάς. Αλλά θα φέρει πραγματικό όφελος μόνο όταν κάνετε πράξη αυτή τη γνώση.

Παρεμπιπτόντως, έχω προγραμματίσει μια σειρά από ενδιαφέροντα έργα που θα είναι ιδιαίτερα ενδιαφέροντα, οπότε φροντίστε να το κάνετε εγγραφείτε σε νέα άρθρα ... Σκοπεύω επίσης να στείλω πρόσθετο υλικό, έτσι πολλοί έχουν ήδη εγγραφεί μέσω της κύριας σελίδας του ιστότοπου. Μπορείτε επίσης να εγγραφείτε εδώ.

Λοιπόν, τώρα πραγματικά τα έχω όλα, οπότε σας εύχομαι καλή τύχη, καλή διάθεση και τα ξαναλέμε.

Με n / a Vladimir Vasiliev

Θεωρία μηχανών πεπερασμένης κατάστασης

Η θεωρία των αυτομάτων βρίσκεται στη βάση της θεωρίας των μεταγλωττιστών κτιρίων. Μια μηχανή πεπερασμένης κατάστασης είναι μια από τις βασικές έννοιες. Ένα αυτόματο δεν σημαίνει μια πραγματική τεχνική συσκευή, αν και μπορεί να κατασκευαστεί μια τέτοια συσκευή, αλλά ένα συγκεκριμένο μαθηματικό μοντέλο, οι ιδιότητες και η συμπεριφορά του οποίου μπορούν να προσομοιωθούν χρησιμοποιώντας ένα πρόγραμμα σε υπολογιστή. Το πεπερασμένο αυτόματο είναι το απλούστερο από τα μοντέλα της θεωρίας των αυτόματα και, κατά κανόνα, χρησιμεύει ως συσκευή ελέγχου για όλους τους άλλους τύπους αυτόματα. Μια μηχανή πεπερασμένης κατάστασης έχει μια σειρά από ιδιότητες:

· Το μηχάνημα κατάστασης μπορεί να λύσει μια σειρά από εύκολα προβλήματα μεταγλώττισης. Το λεξικό μπλοκ χτίζεται σχεδόν πάντα πάνω σε μια κρατική μηχανή.

· Το έργο της κρατικής μηχανής χαρακτηρίζεται από υψηλή απόδοση.

· Η προσομοίωση μιας μηχανής πεπερασμένης κατάστασης απαιτεί μια σταθερή ποσότητα μνήμης, η οποία απλοποιεί τη διαχείριση της μνήμης.

· Υπάρχει μια σειρά από θεωρήματα και αλγόριθμοι που σας επιτρέπουν να σχεδιάσετε και να απλοποιήσετε μηχανές πεπερασμένης κατάστασης.

Υπάρχουν αρκετοί εξαιρετικοί ορισμοί της κρατικής μηχανής στη βιβλιογραφία. Ωστόσο, αυτό που έχουν κοινό είναι ότι η μηχανή κατάστασης προσομοιώνει μια υπολογιστική συσκευή με σταθερή ποσότητα μνήμης που διαβάζει ακολουθίες χαρακτήρων εισόδου που ανήκουν σε κάποιο σύνολο εισόδου. Οι θεμελιώδεις διαφορές στους ορισμούς σχετίζονται με το τι κάνει το αυτόματο στην έξοδο. Η έξοδος του αυτόματου μπορεί να είναι μια ένδειξη για το εάν η δεδομένη αλυσίδα εισόδου είναι "επιτρεπτή" ή όχι. Μια καλοσχηματισμένη ή συντακτικά σωστή συμβολοσειρά ονομάζεται "έγκυρη". Για παράδειγμα, μια συμβολοσειρά που υποτίθεται ότι αντιπροσωπεύει μια αριθμητική σταθερά θεωρείται ότι έχει κατασκευαστεί εσφαλμένα εάν περιέχει δύο δεκαδικά ψηφία.

Ορισμός:Μια μηχανή πεπερασμένης κατάστασης είναι ένα επίσημο σύστημα που ορίζεται χρησιμοποιώντας τα ακόλουθα αντικείμενα:

· Ένα πεπερασμένο σύνολο χαρακτήρων εισαγωγής.

· Ένα πεπερασμένο σύνολο καταστάσεων.

· Συνάρτηση μεταβάσεων, η οποία εκχωρεί μια νέα κατάσταση σε κάθε ζεύγος (τρέχουσα κατάσταση, σύμβολο εισόδου).

· Αρχική κατάσταση;

· Ένα υποσύνολο καταστάσεων, που επιλέγονται ως αποδεκτές ή τελικές.

Παράδειγμα. Ας αναλύσουμε το έργο ενός ελεγκτή που ελέγχει τον άρτιο ή τον περιττό αριθμό των μονάδων σε μια αυθαίρετη αλυσίδα που αποτελείται από μηδενικά και μονάδες. Ας υποθέσουμε ότι το αντίστοιχο πεπερασμένο αυτόματο πρέπει να «παραδεχτεί» όλες τις συμβολοσειρές που περιέχουν περιττό αριθμό μονάδων και να «απορρίψει» συμβολοσειρές με έναν ζυγό αριθμό μονάδων. Ας ονομάσουμε αυτό το αυτόματο «ελεγκτή ισοτιμίας». Πιστεύουμε ότι στην είσοδο του μηχανήματος δεν μπορούν να τροφοδοτηθούν χαρακτήρες εκτός από το 0 και το 1. Έτσι, το αλφάβητο εισόδου του ελεγκτή έχει οριστεί (0, 1). Υποθέτουμε ότι σε μια συγκεκριμένη χρονική στιγμή η μηχανή πεπερασμένης κατάστασης ασχολείται με ένα μόνο σύμβολο εισόδου και αποθηκεύει πληροφορίες για τα προηγούμενα σύμβολα της αλυσίδας εισόδου χρησιμοποιώντας ένα πεπερασμένο σύνολο καταστάσεων. Ως σύνολο καταστάσεων θα θεωρήσουμε ένα σύνολο (ζυγό, περιττό), μία από αυτές τις καταστάσεις θα πρέπει να επιλεγεί ως αρχική. Έστω μια κατάσταση (ζυγή), αφού στο πρώτο βήμα ο αριθμός των διαβασμένων είναι μηδέν και το μηδέν είναι ζυγός αριθμός. Κατά την ανάγνωση του επόμενου συμβόλου εισόδου, η κατάσταση του αυτόματου είτε αλλάζει είτε παραμένει ίδια και η νέα του κατάσταση εξαρτάται από το σύμβολο εισόδου και την τρέχουσα κατάσταση. Αυτή η αλλαγή στην κατάσταση ονομάζεται μετάβαση.

Η λειτουργία του αυτόματου μπορεί να περιγραφεί μαθηματικά με μια συνάρτηση μετάβασης της μορφής d (Stek., X) = Snov. Διαφορετικά, μπορεί να γραφτεί ως εξής:

d (άρτιος, 0) = άρτιος δ (άρτιος, 1) = περιττός.

δ (περ., 0) = περιττός. δ (μονός, 1) = ζυγός

Ο ελεγκτής έχει μια ενιαία κατάσταση αποδοχής ODD, και ΖΥΓΗ είναι η κατάσταση "απόρριψης". Ας αντικατοπτρίσουμε την ακολουθία μεταβάσεων του αυτόματου όταν η αλυσίδα 1101 τροφοδοτείται στην είσοδο του.

EVEN ® ODD ® EVEN® EVEN® ODD

Ο πίνακας μετάβασης ενός τέτοιου αυτομάτου μοιάζει με αυτό:

ακόμη και	ακόμη και	Περιττός
Περιττός	Περιττός	ακόμη και

Ορισμός.Μια κρατική μηχανή είναι ένα επίσημο σύστημα

S = (A, Q, d, l, V),

των οποίων τα αντικείμενα είναι τα εξής:

* A - ένα πεπερασμένο σύνολο χαρακτήρων εισαγωγής (σύνολο

τερματικά)·

* Το Q είναι ένα πεπερασμένο σύνολο εσωτερικών καταστάσεων του αυτόματου

(πολλά μη τερματικά)

* V - ένα πεπερασμένο σύνολο χαρακτήρων εξόδου (αλφάβητο εξόδου).

* d - συνάρτηση μετάβασης, η οποία χαρακτηρίζεται από A ´ Q ® Q;

* l είναι η συνάρτηση εξόδου που καθορίζει την εμφάνιση της προβολής.

Σχόλιο: Αυτή η διάλεξη συζητά τους δύο πιο συνηθισμένους τρόπους οριστικοποίησης μιας επίσημης γλώσσας: γραμματικές και αυτόματα. Θεωρούμε πεπερασμένα αυτόματα που αντιστοιχούν σε δεξιές γραμμικές γραμματικές στην ιεραρχία Chomsky, ορίζουμε τις έννοιες ενός πεπερασμένου αυτόματου, ενός μη ντετερμινιστικού πεπερασμένου αυτόματου και μιας γλώσσας αναγνωρίσιμης από ένα πεπερασμένο αυτόματο. Παρέχει πρακτικά παραδείγματα και ασκήσεις για την εμπέδωση της ύλης

Οι δύο πιο συνηθισμένοι τρόποι οριστικοποίησης μιας επίσημης γλώσσας είναι οι γραμματικές και τα αυτόματα. Σε αυτό το πλαίσιο, οι μηχανές ονομάζονται μαθηματικά μοντέλα ορισμένων υπολογιστικών συσκευών. Σε αυτή τη διάλεξη, εξετάζουμε μηχανές πεπερασμένων καταστάσεων που αντιστοιχούν σε δεξιές-γραμμικές γραμματικές στην ιεραρχία Chomsky. Ισχυρότερη υπολογιστικά μοντέλαθα οριστεί αργότερα στις διαλέξεις «10», «14» και «15». Ο όρος "γλώσσα αυτόματου" αποδίδεται σε γλώσσες που αναγνωρίζονται από μηχανές πεπερασμένης κατάστασης και όχι από ευρύτερες οικογένειες αυτόματα (για παράδειγμα, αυτόματα με ώθηση ή αυτόματα γραμμικά οριοθετημένα).

Η ενότητα 2.1 ορίζει τις έννοιες ενός πεπερασμένου αυτόματου (για λόγους σαφήνειας, ένα τέτοιο αυτόματο μπορεί να ονομαστεί μη ντετερμινιστικό πεπερασμένο αυτόματο) και μιας γλώσσας που αναγνωρίζεται από ένα πεπερασμένο αυτόματο. Η επόμενη ενότητα δίνει έναν διαφορετικό, αλλά ισοδύναμο με τον πρώτο, ορισμό μιας γλώσσας που αναγνωρίζεται από μια κρατική μηχανή. Δεν είναι απαραίτητο για την περαιτέρω παρουσίαση, αλλά είναι ακριβώς αυτός ο ορισμός που προσφέρεται για γενίκευση σε περιπτώσεις αυτομάτων άλλων τύπων.

Στην Ενότητα 2.3, αποδεικνύουμε ότι η ίδια κατηγορία γλωσσών αυτόματων μπορεί να ληφθεί χρησιμοποιώντας μόνο πεπερασμένα αυτόματα μιας ειδικής φόρμας (διαβάζουν ακριβώς ένα σύμβολο σε κάθε κύκλο ρολογιού και έχουν ακριβώς μια αρχική κατάσταση). Σε πολλά σχολικά βιβλία, τέτοιες μηχανές ονομάζονται μηχανές πεπερασμένης κατάστασης.

Τα θεωρήματα σχετικά με την ακριβή αντιστοιχία ορισμένων κατηγοριών γραμματικών με ορισμένες κατηγορίες αυτόματα συνιστούν μια ολόκληρη σειρά κλασικών αποτελεσμάτων στη θεωρία των τυπικών γλωσσών. Το πρώτο θεώρημα αυτής της σειράς, το οποίο δηλώνει ότι οι δεξιές γραμμικές γραμματικές δημιουργούν ακριβώς αυτόματες γλώσσες, αποδεικνύεται στην Ενότητα 2.4.

Μια άλλη σειρά αποτελεσμάτων σχετίζεται με τη δυνατότητα περιορισμού μιας συγκεκριμένης κατηγορίας γραμματικών χωρίς αλλαγή της κατηγορίας γλωσσών που δημιουργούνται από αυτές. Συνήθως, σε αυτή την περίπτωση, οι γραμματικές από τη μικρότερη τάξη ονομάζονται γραμματικές σε κανονική μορφή. Η ενότητα 2.5 * διατυπώνει ένα αποτέλεσμα αυτού του τύπου για δεξιόγραμμες γραμματικές. Αυτό το ίδιο το θεώρημα παρουσιάζει μικρό ενδιαφέρον, αλλά παρόμοια αποτελέσματα, που αποδείχθηκαν αργότερα για γραμματικές χωρίς πλαίσιο, χρησιμοποιούνται σε πολλές αποδείξεις και αλγόριθμους.

Δεν είναι όλες οι μηχανές κατάστασης κατάλληλες για την κατασκευή συσκευών αναγνώρισης κατάλληλες για πρακτικές εφαρμογές, αφού στη γενική περίπτωση μηχανή πεπερασμένης κατάστασηςδεν παρέχει ακριβή ένδειξη για το πώς να προχωρήσετε στο επόμενο βήμα, αλλά επιτρέπει τη συνέχιση της υπολογιστικής διαδικασίας με διάφορους τρόπους. Οι ντετερμινιστικές μηχανές πεπερασμένης κατάστασης (μια ειδική περίπτωση μη ντετερμινιστικών μηχανών πεπερασμένης κατάστασης), που ορίζονται στην Ενότητα 2.6, δεν έχουν αυτό το μειονέκτημα. Στην Ενότητα 2.7, αποδεικνύουμε ότι κάθε γλώσσα αυτόματου ορίζεται από κάποιο ντετερμινιστικό πεπερασμένο αυτόματο.

2.1. Μη ντετερμινιστικές μηχανές πεπερασμένης κατάστασης

Ορισμός 2.1.1. Μηχανή πεπερασμένης κατάστασης(πεπερασμένο αυτόματο, μηχανή πεπερασμένης κατάστασης) είναι ένα πέντε, όπου είναι ένα πεπερασμένο αλφάβητο εισαγωγής(ή απλά αλφάβητο) ενός δεδομένου πεπερασμένου αυτόματου και είναι πεπερασμένα σύνολα,

, Τα στοιχεία του Q ονομάζονται πολιτείες(κατάσταση), στοιχεία I - αρχικός(αρχικές) καταστάσεις, στοιχεία F - τελικόςή παραδεχόμενοι(τελική, αποδεκτή) καταστάσεις. Αν μετά κάλεσε μετάβαση(μετάβαση) από το p στο q και η λέξη x είναι επιγραφή(ετικέτα) αυτής της μετάβασης.

Παράδειγμα 2.1.2... Έστω Q = (1,2), , I = (1), F = (2),

Τότε - κρατική μηχανή.

Παρατήρηση 2.1.3... Οι μηχανές πεπερασμένης κατάστασης μπορούν να παρασταθούν ως διαγράμματα κατάστασης(διάγραμμα κατάστασης) (μερικές φορές ονομάζεται διαγράμματα μετάβασης(διάγραμμα μετάβασης)). Στο διάγραμμα, κάθε κατάσταση υποδεικνύεται με έναν κύκλο και μια μετάβαση υποδεικνύεται με ένα βέλος. Το βέλος από το p στο q, με τη λέξη x, δείχνει ποια είναι η μετάβαση της μηχανής δεδομένης κατάστασης. Κάθε αρχική κατάσταση αναγνωρίζεται από ένα σύντομο βέλος που οδηγεί σε αυτήν. Κάθε κατάσταση αποδοχής σημειώνεται στο διάγραμμα με διπλό κύκλο.

Παράδειγμα 2.1.4... Το διάγραμμα δείχνει τη μηχανή κατάστασης από το παράδειγμα 2.1.2.

Παρατήρηση 2.1.5... Εάν το πεπερασμένο αυτόματο έχει πολλές μεταβάσεις με κοινή αρχή και κοινό τέλος, τότε τέτοιες μεταβάσεις ονομάζονται παράλληλο... Μερικές φορές οι παράλληλες μεταβάσεις απεικονίζονται με ένα μόνο βέλος στο διάγραμμα μηχανής κατάστασης μιας μηχανής κατάστασης. Σε αυτήν την περίπτωση, οι ετικέτες άλματος παρατίθενται διαχωρισμένες με κόμμα.

Παράδειγμα 2.1.6... Το διάγραμμα απεικονίζει πάλι τη μηχανή κατάστασης από το Παράδειγμα 2.1.2.

Ορισμός 2.1.7. Μονοπάτι(διαδρομή) μιας μηχανής κατάστασης είναι μια πλειάδα, όπου και για κάθε i. Επιπλέον, q 0 - η αρχή του δρόμου q n - τέλος του δρόμου n - μήκος διαδρομής w 1 ... w n - σημάδι διαδρομής.

Παρατήρηση 2.1.8... Υπάρχει δρόμος για κάθε κράτος. Η ετικέτα του είναι, η αρχή και το τέλος είναι ίδια.

Ορισμός 2.1.9... Το μονοπάτι λέγεται επιτυχήςαν η αρχή του ανήκει στο I και το τέλος ανήκει στον F.

Παράδειγμα 2.1.10... Εξετάστε τη μηχανή κατάστασης από το Παράδειγμα 2.1.2. Η διαδρομή είναι επιτυχημένη. Η ετικέτα του είναι baaab. Το μήκος αυτής της διαδρομής είναι 4.

Ορισμός 2.1.11... Λέξη w επιτρέπεται(είναι αποδεκτό, αναγνωρίζεται) από τη μηχανή κατάστασης M αν είναι ετικέτα κάποιας επιτυχημένης διαδρομής.

Ορισμός 2.1.12... Γλώσσα, ευκολογνώριστοςΗ μηχανή πεπερασμένης κατάστασης M είναι η γλώσσα L (M), που αποτελείται από ετικέτες όλων των επιτυχημένων μονοπατιών (δηλαδή, όλων των λέξεων που γίνονται δεκτές από το δεδομένο αυτόματο). Θα πούμε επίσης ότι το αυτόματο Μ αναγνωρίζει(αναγνωρίζει, αποδέχεται) γλώσσα Λ (Μ).

Παρατήρηση 2.1.13... Αν , τότε η γλώσσα που αναγνωρίζεται από την κρατική μηχανή , περιέχει.

Παράδειγμα 2.1.14... Έστω, όπου Q = (1,2), , I = (1), F = (1,2),

Ορισμός 2.1.15... Δύο κρατικές μηχανές είναι ισοδύναμααν αναγνωρίζουν την ίδια γλώσσα.

Ορισμός 2.1.16... Η γλώσσα L ονομάζεται αυτόματο(γλώσσα πεπερασμένης κατάστασης) εάν υπάρχει μηχανή πεπερασμένης κατάστασης που αναγνωρίζει αυτή τη γλώσσα.

Παρατήρηση 2.1.17... Συνήθως, τα σχολικά βιβλία χρησιμοποιούν έναν στενότερο ορισμό ενός μη ντετερμινιστικού πεπερασμένου αυτόματου, αλλά αυτό δεν αλλάζει την κατηγορία των αυτόματων γλωσσών (βλ. Λήμμα 2.3.3.).

Παράδειγμα 2.1.18... Σκεφτείτε ένα αλφάβητο ενός γράμματος. Με οποιοδήποτε σταθερό και γλώσσα είναι αυτόματη.

Παρατήρηση 2.1.19... Κάθε πεπερασμένη γλώσσα είναι αυτόματη.

Ορισμός 2.1.20... Πολιτεία q κατορθωτός(προσβάσιμο) από την κατάσταση p αν υπάρχει μονοπάτι που ξεκινά με p και τελειώνει με q.

Λήμμα 2.1.21. Κάθε γλώσσα αυτόματου αναγνωρίζεται από κάποιο πεπερασμένο αυτόματο στο οποίο κάθε κατάσταση είναι προσβάσιμη από κάποια αρχική κατάσταση και από κάθε κατάσταση είναι προσβάσιμη τουλάχιστον μία τελική κατάσταση.

Παράδειγμα 2.1.22... Σκεφτείτε μια μηχανή πεπερασμένης κατάστασης , όπου Q = (1,2,3,4), , I = (1,2,4), F = (1,3,4),

Σε αυτό το άρθρο, ο όρος "μηχανή κατάστασης" σημαίνει έναν αλγόριθμο που μπορεί να βρίσκεται σε μία από έναν μικρό αριθμό καταστάσεων. "Κατάσταση" είναι μια συγκεκριμένη συνθήκη που καθορίζει την καθορισμένη σχέση μεταξύ των σημάτων εισόδου και εξόδου, καθώς και των σημάτων εισόδου και των επακόλουθων καταστάσεων. Ο έξυπνος αναγνώστης θα σημειώσει αμέσως ότι οι μηχανές πεπερασμένης κατάστασης που περιγράφονται σε αυτό το άρθρο είναι μηχανές κατάστασης Mealy. Ένα αυτόματο Mealy είναι μια μηχανή πεπερασμένης κατάστασης όπου οι έξοδοι είναι συναρτήσεις της τρέχουσας κατάστασης και ένα σήμα εισόδου, σε αντίθεση με ένα αυτόματο Moore, στο οποίο οι έξοδοι είναι συναρτήσεις μόνο της κατάστασης. Και στις δύο περιπτώσεις, η επόμενη κατάσταση είναι συνάρτηση της τρέχουσας κατάστασης και του σήματος εισόδου.

Εξετάστε ένα παράδειγμα μιας απλής μηχανής κατάστασης. Φανταστείτε ότι πρέπει να αναγνωρίσετε την ακολουθία χαρακτήρων "//" σε μια συμβολοσειρά κειμένου. Το σχήμα 1 δείχνει πώς γίνεται αυτό χρησιμοποιώντας μια μηχανή κατάστασης. Η πρώτη εμφάνιση κάθετου δεν δίνει σήμα εξόδου, αλλά οδηγεί στο γεγονός ότι το μηχάνημα μεταβαίνει στη δεύτερη κατάσταση. Εάν το αυτόματο δεν βρει κάθετο στη δεύτερη κατάσταση, επιστρέφει στην πρώτη, αφού είναι απαραίτητο να υπάρχουν 2 κάθετες στη σειρά. Εάν βρεθεί η δεύτερη κάθετο, το μηχάνημα εκδίδει ένα σήμα «έτοιμο».

Μάθετε τι χρειάζεται ο πελάτης.

Κάντε ένα διάγραμμα μετάβασης κατάστασης

Κωδικοποιήστε τον «σκελετό» της κρατικής μηχανής χωρίς να αναφέρετε λεπτομερώς τις πράξεις μετάβασης.

Βεβαιωθείτε ότι οι μεταβάσεις λειτουργούν σωστά.

Περιορίστε τις λεπτομέρειες των μεταβάσεων.

Κάντε ένα τεστ.

Παράδειγμα κρατικής μηχανής

Εξετάστε ένα πιο ενδιαφέρον παράδειγμα μιας κρατικής μηχανής, ενός προγράμματος που ελέγχει την ανάκληση και την επέκταση του συστήματος προσγείωσης ενός αεροσκάφους. Ενώ τα περισσότερα αεροσκάφη εκτελούν αυτή τη διαδικασία χρησιμοποιώντας έναν ηλεκτροϋδραυλικό μηχανισμό ελέγχου (απλά επειδή δεν υπάρχει υπολογιστής στο αεροσκάφος), σε ορισμένες περιπτώσεις, όπως τα μη επανδρωμένα εναέρια οχήματα, αξίζει να χρησιμοποιήσετε έλεγχο λογισμικού.

Αρχικά, ας ρίξουμε μια ματιά στον εξοπλισμό. Το σύστημα προσγείωσης του αεροσκάφους αποτελείται από ένα μπροστινό στήριγμα, ένα αριστερό κύριο σύστημα προσγείωσης και ένα δεξί κύριο σύστημα προσγείωσης. Οδηγούνται υδραυλικά. Μια ηλεκτρικά κινούμενη υδραυλική αντλία παρέχει πίεση στον ενεργοποιητή ισχύος. Το λογισμικό ενεργοποιεί ή απενεργοποιεί την αντλία. Ο υπολογιστής προσαρμόζει τη θέση της βαλβίδας κατεύθυνσης - "κάτω" ή "πάνω" για να επιτρέψει την πίεση να ανυψώσει ή να χαμηλώσει το πλαίσιο. Κάθε ένα από τα πόδια του συστήματος προσγείωσης έχει έναν οριακό διακόπτη: το ένα κλείνει όταν το σασί είναι ανυψωμένο, το άλλο - εάν είναι κλειδωμένο στη θέση "κάτω". Για να προσδιορίσετε εάν το αεροπλάνο βρίσκεται στο έδαφος, ο οριακός διακόπτης στο μπροστινό πόδι στήριξης κλείνει όταν το βάρος του αεροπλάνου βρίσκεται στο μπροστινό στήριγμα. Τα χειριστήρια πιλότου αποτελούνται από ένα επάνω/κάτω μοχλό συστήματος προσγείωσης και τρία φώτα (ένα για κάθε σκέλος) που μπορούν να σβήσουν, πράσινο (κάτω) ή κόκκινο (μετάβαση).

Τώρα ας προχωρήσουμε στην ανάπτυξη μιας κρατικής μηχανής. Το πρώτο και πιο δύσκολο βήμα είναι να κατανοήσουμε τις πραγματικές προσδοκίες του πελάτη. Ένα από τα πλεονεκτήματα μιας κρατικής μηχανής είναι ότι αναγκάζει τον προγραμματιστή να σκεφτεί όλες τις πιθανές περιπτώσεις και, ως αποτέλεσμα, να λάβει όλες τις απαιτούμενες πληροφορίες από τον πελάτη. Γιατί το θεωρώ αυτό το πιο δύσκολο στάδιο; Και πόσες φορές σας έχει δοθεί μια περιγραφή ενός προβλήματος όπως αυτό: μην μετακινείτε το σύστημα προσγείωσης ενώ το αεροπλάνο είναι στο έδαφος.

Φυσικά, αυτό είναι σημαντικό, αλλά ο πελάτης πιστεύει ότι εδώ τελειώνουν όλα. Τι γίνεται με τις υπόλοιπες περιπτώσεις; Αρκεί να τραβήξετε το σύστημα προσγείωσης όταν το αεροπλάνο είναι εκτός εδάφους; Τι γίνεται αν το αεροπλάνο αναπηδήσει σε ένα χτύπημα στον διάδρομο; Τι θα συμβεί αν ο πιλότος μετακινήσει το μοχλό αλλαγής ταχυτήτων στην επάνω θέση κατά τη στάθμευση και, ως αποτέλεσμα, αρχίσει να απογειώνεται; Πρέπει να ανέβει το σασί σε αυτή την περίπτωση;

Ένα από τα πλεονεκτήματα της σκέψης με όρους μιας μηχανής πεπερασμένης κατάστασης είναι ότι μπορείτε να σχεδιάσετε γρήγορα ένα διάγραμμα μετάβασης κατάστασης σε έναν πίνακα προβολής, ακριβώς μπροστά στον πελάτη, και να περπατήσετε μαζί του στη διαδικασία. Ο ακόλουθος προσδιορισμός της μετάβασης κατάστασης είναι αποδεκτός: "το συμβάν που προκάλεσε τη μετάβαση" / "το σήμα εξόδου ως αποτέλεσμα της μετάβασης". Εάν αναπτύξαμε μόνο αυτό που ζήτησε αρχικά ο πελάτης («μην μετακινήσετε το σύστημα προσγείωσης εάν το αεροπλάνο είναι στο έδαφος»), τότε θα είχαμε το μηχάνημα που φαίνεται στο Σχήμα 2.

Κατά τη σύνταξη ενός διαγράμματος μετάβασης κατάστασης (ή οποιουδήποτε άλλου αλγόριθμου), έχετε υπόψη σας τα εξής:

Οι υπολογιστές είναι πολύ γρήγοροι σε σύγκριση με το μηχανικό υλικό

Ο μηχανολόγος μηχανικός που εξηγεί τι πρέπει να γίνει μπορεί να μην γνωρίζει όλα όσα γνωρίζετε για τους υπολογιστές και τους αλγόριθμους. Και αυτό είναι επίσης ένα θετικό σημείο, διαφορετικά, δεν θα σας ζητούσαν!

Πώς θα συμπεριφερθεί το πρόγραμμά σας εάν σπάσει ένα μηχανικό ή ηλεκτρικό μέρος;

Ένα μηχάνημα κατάστασης που βασίζεται σε αυτό που πραγματικά θέλει ο πελάτης φαίνεται στο Σχήμα 3. Εδώ θέλουμε να αποτρέψουμε την απόσυρση του συστήματος προσγείωσης έως ότου το σύστημα προσγείωσης είναι σίγουρα στον αέρα. Για να γίνει αυτό, μετά το άνοιγμα του διακόπτη προσγείωσης, το μηχάνημα περιμένει για αρκετά δευτερόλεπτα. Θέλουμε επίσης να ανταποκριθούμε στην ανερχόμενη άκρη του ραβδιού του πιλότου και όχι στο επίπεδο, κάτι που θα αποφύγει προβλήματα εάν κάποιος μετακινήσει το ραβδί ενώ το αεροπλάνο είναι σταθμευμένο. Η ανάσυρση ή η επέκταση του συστήματος προσγείωσης διαρκεί μερικά δευτερόλεπτα και πρέπει να είμαστε προετοιμασμένοι για την κατάσταση που ο πιλότος αλλάξει γνώμη κατά τη διάρκεια αυτής της λειτουργίας και μετακινήσει το μοχλό προς την αντίθετη κατεύθυνση. Σημειώστε επίσης ότι εάν το αεροπλάνο προσγειωθεί ξανά ενώ βρισκόμαστε στην κατάσταση "Αναμονή για απογείωση", ο χρονοδιακόπτης θα επανεκκινήσει και το σύστημα προσγείωσης θα αποσυρθεί μόνο εάν το αεροπλάνο είναι στον αέρα για 2 δευτερόλεπτα.

Υλοποίηση κρατικής μηχανής

Η λίστα 1 είναι η υλοποίηση του μηχανήματος κατάστασης που φαίνεται στο Σχήμα 3. Ας συζητήσουμε μερικές από τις λεπτομέρειες του κώδικα.

/ * καταχώρηση 1 * /

typedef enum(GEAR_DOWN = 0, WTG_FOR_TKOFF, RAISING_GEAR, GEAR_UP, LOWERING_GEAR) Κατάσταση_Τύπος;

/ * Αυτός ο πίνακας περιέχει δείκτες σε συναρτήσεις που καλούνται σε συγκεκριμένες καταστάσεις * /

κενός(* κατάσταση_πίνακας) () = (GearDown, WtgForTakeoff, RaisingGear, GearUp, LoweringGear);

State_Type curr_state;

InitializeLdgGearSM ();

/ * Η καρδιά του μηχανήματος είναι αυτός ο ατελείωτος βρόχος. Αντίστοιχη λειτουργία

Τρέχουσα κατάσταση, καλείται μία φορά ανά επανάληψη * /

ενώ (1) {

κατάσταση_πίνακας ();

DecrementTimer ();

κενός InitializeLdgGearSM ( κενός )

curr_state = GEAR_DOWN;

/ * Σταματήστε το υλικό, σβήστε τα φώτα κ.λπ. * /

κενός GearDown ( κενός )

/ * Μετάβαση σε κατάσταση αναμονής εάν το αεροπλάνο

Όχι στο έδαφος και ελήφθη η εντολή ανύψωσης του συστήματος προσγείωσης * /

αν((μοχλός_ταχυτήτων == ΠΑΝΩ) && (προηγούμενος_μοχλός_ταχυτήτων == ΚΑΤΩ) && (squat_switch == ΠΑΝΩ)) (

curr_state = WTG_FOR_TKOFF;

prev_gear_lever = μοχλός ταχυτήτων;

κενός RaisingGear ( κενός )

αν((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

curr_state = GEAR_UP;

/ * Εάν ο πιλότος έχει αλλάξει γνώμη, μεταβείτε στην κατάσταση "εξοπλισμού προσγείωσης" * /

αν(μοχλός_ταχυτήτων == ΚΑΤΩ) (

curr_state = LOWERING_GEAR;

κενός GearUp ( κενός )

/ * εάν ο πιλότος έχει μετακινήσει το μοχλό στη θέση "κάτω",

Πηγαίνουμε στην κατάσταση "κατέβασμα του πλαισίου" * /

αν(μοχλός_ταχυτήτων == ΚΑΤΩ) (

curr_state = LOWERING_GEAR;

κενός WtgForTakeoff ( κενός )

/ * Περιμένετε πριν σηκώσετε το πλαίσιο. * /

αν(μετρών την ώραν<= 0.0) {

curr_state = RAISING_GEAR;

/ * Εάν ακουμπήσουμε ξανά ή ο πιλότος αλλάξει γνώμη - ξεκινήστε από την αρχή * /

αν((squat_switch == DOWN) || (gear_lever == DOWN)) (

curr_state = GEAR_DOWN;

/ * Μην θέλεις να του ζητήσεις να αλλάξει ξανά το μοχλό

Αυτό ήταν απλώς μια αναπήδηση. * /

prev_gear_lever = ΚΑΤΩ;

κενός Lowering Gear ( κενός )

αν(μοχλός_ταχυτήτων == ΠΑΝΩ) (

curr_state = RAISING_GEAR;

αν((nosegear_is_down == MADE) && (leftgear_is_down == MADE) && (rtgear_is_down == MADE)) (

curr_state = GEAR_DOWN;

Αρχικά, μπορεί να παρατηρήσετε ότι η λειτουργικότητα κάθε κατάστασης υλοποιείται από μια ξεχωριστή συνάρτηση C. Φυσικά, θα ήταν δυνατό να εφαρμοστεί ένα αυτόματο χρησιμοποιώντας μια δήλωση διακόπτη με ξεχωριστές περιπτώσεις για κάθε κατάσταση, αλλά αυτό μπορεί να οδηγήσει σε μια πολύ μεγάλη συνάρτηση (10-20 γραμμές κώδικα ανά κατάσταση για καθεμία από τις 20-30 καταστάσεις ). Μπορεί επίσης να οδηγήσει σε σφάλματα εάν αλλάξετε τον κωδικό στα τελικά στάδια της δοκιμής. Ίσως δεν έχετε ξεχάσει ποτέ τη δήλωση διακοπής στο τέλος μιας υπόθεσης, αλλά μου έχουν συμβεί τέτοιες περιπτώσεις. Ο κωδικός μιας κατάστασης δεν θα μπει ποτέ στον κωδικό μιας άλλης εάν έχετε ξεχωριστή συνάρτηση για κάθε κατάσταση.

Για να αποφύγω τη χρήση της δήλωσης switch, χρησιμοποιώ έναν πίνακα δεικτών για να δηλώσω συναρτήσεις και δηλώνω τη μεταβλητή που χρησιμοποιείται ως ευρετήριο πίνακα τύπου enum.

Για λόγους απλότητας, το υλικό I/O που είναι υπεύθυνο για την ανάγνωση της κατάστασης των διακοπτών, την ενεργοποίηση και απενεργοποίηση αντλιών κ.λπ., αναπαρίσταται ως απλές μεταβλητές. Αυτές οι μεταβλητές υποτίθεται ότι αντιπροσωπεύουν «μαγικές διευθύνσεις» που σχετίζονται με εξοπλισμό με αόρατα μέσα.

Ένα άλλο προφανές πράγμα είναι ότι ο κώδικας δεν έχει μεγάλη σημασία σε αυτό το σημείο. Απλώς πηγαίνει από το ένα κράτος στο άλλο. Αυτό είναι ένα σημαντικό ενδιάμεσο βήμα και δεν πρέπει να αγνοηθεί. Παρεμπιπτόντως, θα ήταν ωραίο να προσθέσετε δηλώσεις εκτύπωσης μεταξύ οδηγιών μεταγλώττισης υπό όρους (#ifdef DEBUG .. #endif) που θα εκτυπώνουν την τρέχουσα κατάσταση και τις τιμές των σημάτων εισόδου.

Το κλειδί της επιτυχίας βρίσκεται στον κώδικα που ενεργοποιεί τη μετάβαση κατάστασης, δηλ. προσδιορίζει ότι έχει γίνει εισαγωγή δεδομένων.

Αν ο κώδικας περάσει σωστά από όλες τις καταστάσεις, το επόμενο βήμα είναι να γράψετε το «γέμισμα» του κώδικα, δηλαδή αυτό ακριβώς που παράγει το σήμα εξόδου. Θυμηθείτε ότι κάθε μετάβαση έχει μια είσοδο (το συμβάν που την ενεργοποίησε) και μια έξοδο (I/O υλικού, όπως στο παράδειγμά μας). Συχνά είναι χρήσιμο να αποτυπωθεί ως πίνακας μετάβασης κατάστασης.

Στον πίνακα μετάβασης κατάστασης, υπάρχει μία γραμμή ανά μετάβαση κατάστασης.

Κατά την κωδικοποίηση μιας κατάστασης μηχανής, προσπαθήστε να διατηρήσετε τη δύναμή της - μια ισχυρή αντιστοιχία μεταξύ των απαιτήσεων των πελατών και του κώδικα. Ίσως χρειαστεί να αποκρύψετε λεπτομέρειες υλικού σε ένα άλλο επίπεδο συναρτήσεων, για παράδειγμα, για να κάνετε τον κωδικό της μηχανής κατάστασης όσο το δυνατόν πιο κοντά στον πίνακα μετάβασης κατάστασης και στο διάγραμμα μετάβασης κατάστασης. Αυτή η συμμετρία βοηθά στην αποφυγή σφαλμάτων και εξηγεί γιατί οι μηχανές κατάστασης αποτελούν τόσο σημαντικό μέρος του οπλοστασίου του προγραμματιστή ενσωματωμένων συστημάτων. Φυσικά, θα μπορούσατε να επιτύχετε το ίδιο αποτέλεσμα με πλαίσια ελέγχου και έναν άπειρο αριθμό ένθετων δηλώσεων if, αλλά θα ήταν πολύ δύσκολο να παρακολουθήσετε τον κώδικα και να τον συγκρίνετε με τις επιθυμίες του πελάτη.

Το απόσπασμα κώδικα στη Λίστα 2 επεκτείνει τη συνάρτηση RaisingGear (). Σημειώστε ότι ο κώδικας για τη συνάρτηση RaisingGear () τείνει να αντικατοπτρίζει τις 2 σειρές του πίνακα μετάβασης για την κατάσταση Raising Gear.

κενός RaisingGear ( κενός )

/ * Αφού ενεργοποιηθούν όλοι οι διακόπτες, μεταβείτε στην κατάσταση "σασί επάνω" * /

αν((nosegear_is_up == MADE) && (leftgear_is_up == MADE) && (rtgear_is_up == MADE)) (

αντλία_μοτέρ = OFF;

gear_lights = EXTINGUISH;

curr_state = GEAR_UP;

/ * Εάν ο πιλότος αλλάξει γνώμη, αρχίστε να ανασύρετε το σύστημα προσγείωσης * /

αν(μοχλός_ταχυτήτων == ΚΑΤΩ) (

αντλία_κατεύθυνση = ΚΑΤΩ;

curr_state = GEAR_LOWERING;

Θυμηθείτε να αποφύγετε τις λανθάνουσες καταστάσεις. Η λανθάνουσα κατάσταση εμφανίζεται όταν, από τεμπελιά, προσπαθείτε να προσθέσετε μια υπό όρους υποκατάσταση αντί να προσθέσετε μια συγκεκριμένη κατάσταση. Για παράδειγμα, εάν ο κώδικάς σας χειρίζεται το ίδιο σήμα εισόδου με διαφορετικούς τρόπους (δηλαδή εκκινεί διαφορετικές μεταβάσεις κατάστασης) ανάλογα με τη λειτουργία, τότε πρόκειται για μια κρυφή κατάσταση. Σε αυτή την περίπτωση, θα αναρωτιόμουν, δεν θα έπρεπε να χωριστεί αυτό το κράτος στα δύο; Η χρήση κρυφών καταστάσεων αναιρεί όλα τα οφέλη της χρήσης μιας κρατικής μηχανής.

Ως προπόνηση, μπορείτε να επεκτείνετε το μηχάνημα κατάστασης που μόλις εξετάσαμε προσθέτοντας ένα χρονικό όριο στον κύκλο ανάσυρσης ή επέκτασης πλαισίου, αφού ένας μηχανολόγος μηχανικός δεν θέλει μια υδραυλική αντλία να λειτουργεί περισσότερο από 60 δευτερόλεπτα. Εάν ο κύκλος τελειώσει, ο πιλότος θα πρέπει να ειδοποιηθεί αναποδογυρίζοντας το πράσινο και το κόκκινο φως και θα πρέπει να μπορεί να μετακινήσει ξανά το μοχλό για να προσπαθήσει ξανά. Μπορείτε επίσης να ρωτήσετε έναν υποθετικό μηχανολόγο μηχανικό πώς επηρεάζεται η αντλία από την αντιστροφή κατεύθυνσης ενώ λειτουργεί, γιατί αυτό συμβαίνει σε 2 περιπτώσεις όταν ο πιλότος αλλάζει γνώμη. Φυσικά, ο μηχανικός θα πει αρνητικό. Τότε πώς θα αλλάζατε το μηχάνημα κατάστασης για να σταματά γρήγορα την αντλία όταν αλλάζετε κατεύθυνση;

Δοκιμή κρατικών μηχανών

Η ομορφιά των αλγορίθμων κωδικοποίησης ως μηχανών πεπερασμένης κατάστασης είναι ότι το σχέδιο δοκιμής γράφεται σχεδόν αυτόματα από μόνο του. Το μόνο που έχετε να κάνετε είναι να περάσετε από κάθε μετάβαση κατάστασης. Συνήθως το κάνω αυτό με ένα δείκτη στο χέρι, διαγράφοντας τα βέλη στο διάγραμμα μετάβασης κατάστασης καθώς περνούν τη δοκιμή. Αυτός είναι ένας καλός τρόπος για να αποφευχθούν οι "λανθάνουσες καταστάσεις" - παραβλέπονται πιο συχνά στα τεστ παρά σε συγκεκριμένες καταστάσεις.

Αυτό απαιτεί πολλή υπομονή και πολύ καφέ, καθώς ακόμη και ένα μεσαίου μεγέθους κρατικό μηχάνημα μπορεί να έχει έως και 100 διαφορετικές μεταβάσεις. Παρεμπιπτόντως, η καταμέτρηση λυκίσκου είναι ένας πολύ καλός τρόπος για να μετρήσετε την πολυπλοκότητα ενός συστήματος. Το τελευταίο καθορίζεται από τις απαιτήσεις του πελάτη και η κρατική μηχανή κάνει προφανές το πεδίο εφαρμογής της δοκιμής. Με μια λιγότερο οργανωμένη προσέγγιση, ο απαιτούμενος όγκος δοκιμών μπορεί να είναι εξίσου εντυπωσιακός, αλλά δεν θα το ξέρετε.

Είναι πολύ βολικό να χρησιμοποιείτε δηλώσεις εκτύπωσης στον κώδικα που εμφανίζουν την τρέχουσα κατάσταση, τις τιμές των σημάτων εισόδου και εξόδου. Αυτό σας επιτρέπει να παρατηρήσετε εύκολα τι εκφράζει ο "Χρυσός Κανόνας Δοκιμών Λογισμικού": βεβαιωθείτε ότι το πρόγραμμα κάνει αυτό που προορίζεται να κάνει και ότι δεν κάνει τίποτα περιττό. Με άλλα λόγια, παίρνετε μόνο τα αποτελέσματα που περιμένετε και τι άλλο συμβαίνει εκτός από αυτό; Υπάρχουν «δύσκολες» μεταβάσεις καταστάσεων, π.χ. καταστάσεις που περνούν κατά λάθος, για μία μόνο επανάληψη του βρόχου; Αλλάζουν τα σήματα εξόδου όταν δεν το περιμένετε; Στην ιδανική περίπτωση, η έξοδος των εκτυπώσεων σας θα πρέπει να μοιάζει αισθητά με πίνακα μετάβασης κατάστασης.

Τέλος - και αυτό ισχύει για οποιοδήποτε υλικολογισμικό, όχι μόνο για κρατικό λογισμικό που βασίζεται σε μηχανή - να είστε πολύ προσεκτικοί την πρώτη φορά που εκτελείτε το λογισμικό σε πραγματικό υλικό. Είναι πολύ εύκολο να κάνετε λάθος με την πολικότητα των σημάτων - "Ω, σκέφτηκα ότι" 1 "σκοπούσε να σηκώσει το πλαίσιο και" 0 "σήμαινε να το χαμηλώσει." Σε πολλές περιπτώσεις, ο βοηθός εξοπλισμού μου χρησιμοποίησε έναν προσωρινό "διακόπτη κοτόπουλου" για να προστατεύσει πολύτιμα εξαρτήματα μέχρι να βεβαιωθεί ότι το λογισμικό μου μετακινούσε τα στοιχεία στη σωστή κατεύθυνση.

Τρέξιμο

Όταν πληρούνται όλες οι απαιτήσεις του πελάτη, μπορώ να λειτουργήσω μια κρατική μηχανή αυτής της πολυπλοκότητας σε μερικές μέρες. Τα αυτόματα κάνουν σχεδόν πάντα αυτό που θέλω. Το πιο δύσκολο είναι, φυσικά, να καταλάβεις τι ακριβώς θέλει ο πελάτης και να βεβαιωθείς ότι ο ίδιος ο πελάτης ξέρει τι θέλει. Το τελευταίο διαρκεί πολύ περισσότερο!

Ο Μάρτιν Γκόμεζ είναι προγραμματιστής στο Εργαστήριο Εφαρμοσμένης Φυσικής στο Πανεπιστήμιο Τζονς Χόπκινς. Ασχολείται με την ανάπτυξη λογισμικού για υποστήριξη πτήσης ερευνητικών διαστημικών σκαφών. Έχει εργαστεί στην ανάπτυξη ενσωματωμένων συστημάτων για 17 χρόνια. Ο Martin είναι κάτοχος πτυχίου στην Αεροδιαστημική Μηχανική και MS στην Ηλεκτρολογία Μηχανικού από το Πανεπιστήμιο Cornell.

Το άρθρο εξετάζει απλές μηχανές κατάστασης και την υλοποίησή τους σε C ++ χρησιμοποιώντας κατασκευές μεταγωγέων, πίνακες χρόνου εκτέλεσης και τη βιβλιοθήκη Boost Statechart.

Εισαγωγή

Σε γενικές γραμμές, μια μηχανή πεπερασμένης κατάστασης, μέσα από τα μάτια ενός χρήστη, είναι ένα μαύρο κουτί στο οποίο μπορείτε να μεταφέρετε κάτι και να λάβετε κάτι από εκεί. Αυτή είναι μια πολύ βολική αφαίρεση για την απόκρυψη πολύπλοκων αλγορίθμων και οι μηχανές κατάστασης είναι πολύ αποτελεσματικές.

Οι μηχανές πεπερασμένων καταστάσεων απεικονίζονται με τη μορφή διαγραμμάτων που αποτελούνται από καταστάσεις και μεταβάσεις. Επιτρέψτε μου να εξηγήσω με ένα απλό παράδειγμα:

Όπως ίσως μαντέψατε, αυτό είναι ένα διάγραμμα κατάστασης ενός λαμπτήρα. Η αρχική κατάσταση υποδεικνύεται με μαύρο κύκλο, μεταβάσεις με βέλη, ορισμένα βέλη επισημαίνονται - αυτά είναι συμβάντα μετά τα οποία το αυτόματο μεταβαίνει σε άλλη κατάσταση. Έτσι, αμέσως από την αρχική κατάσταση, μπαίνουμε στην κατάσταση Σβηστό φως- η λάμπα είναι σβηστή. Εάν πατήσετε το κουμπί, το μηχάνημα θα αλλάξει την κατάστασή του και θα ακολουθήσει το βέλος που επισημαίνεται Πιέστε το κουμπί, στην πολιτεία Φως αναμμένο- η λάμπα είναι αναμμένη. Μπορείτε να μεταβείτε από αυτήν την κατάσταση ξανά κατά μήκος του βέλους, αφού πατήσετε το κουμπί, στην κατάσταση Σβηστό φως.

Οι πίνακες πλοήγησης χρησιμοποιούνται επίσης ευρέως:

Πρακτική εφαρμογή μηχανών

Οι μηχανές πεπερασμένων καταστάσεων χρησιμοποιούνται ευρέως στον προγραμματισμό. Για παράδειγμα, είναι πολύ βολικό να φανταστεί κανείς τη λειτουργία μιας συσκευής με τη μορφή ενός αυτόματου. Αυτό θα κάνει τον κώδικα απλούστερο και ευκολότερο στον πειραματισμό και τη συντήρηση.

Οι μηχανές κατάστασης χρησιμοποιούνται επίσης για τη σύνταξη όλων των ειδών αναλυτών και αναλυτών κειμένου, μπορούν να χρησιμοποιηθούν για την αποτελεσματική αναζήτηση υποσυμβολοσειρών, οι κανονικές εκφράσεις μεταφράζονται επίσης σε μια μηχανή κατάστασης.

Για παράδειγμα, θα εφαρμόσουμε ένα αυτόματο για την καταμέτρηση αριθμών και λέξεων σε ένα κείμενο. Αρχικά, ας συμφωνήσουμε ότι ένας αριθμός θα είναι μια ακολουθία ψηφίων από το 0 έως το 9 αυθαίρετου μήκους, που περιβάλλεται από χαρακτήρες κενού διαστήματος (κενό, πίνακας, τροφοδοσία γραμμής). Μια λέξη θα θεωρείται μια ακολουθία αυθαίρετου μήκους που αποτελείται από γράμματα και περιβάλλεται επίσης από χαρακτήρες κενού διαστήματος.

Εξετάστε το διάγραμμα:

Από την αρχική κατάσταση, φτάνουμε στην κατάσταση Αρχή... Ελέγχουμε το τρέχον σύμβολο και αν είναι γράμμα, τότε πηγαίνουμε στην κατάσταση Λέξηκατά μήκος του βέλους που σημειώνεται ως Γράμμα... Αυτή η κατάσταση προϋποθέτει ότι τη στιγμή που εξετάζουμε μια λέξη, η ανάλυση περαιτέρω συμβόλων είτε θα επιβεβαιώσει αυτήν την υπόθεση είτε θα τη διαψεύσει. Επομένως, σκεφτείτε το επόμενο σύμβολο, εάν είναι γράμμα, τότε η κατάσταση δεν αλλάζει (προσέξτε το κυκλικό βέλος που επισημαίνεται ως Γράμμα). Εάν ο χαρακτήρας δεν είναι γράμμα, αλλά αντιστοιχεί σε χαρακτήρα διαστήματος, τότε αυτό σημαίνει ότι η υπόθεση ήταν σωστή και βρήκαμε τη λέξη (κινούμε κατά μήκος του βέλους Χώροςσε μια πολιτεία Αρχή). Εάν ο χαρακτήρας δεν είναι γράμμα ή κενό, τότε κάναμε λάθος στην υπόθεση και η ακολουθία που εξετάζουμε δεν είναι λέξη (πηγαίνετε κατά μήκος του βέλους Αγνωστοςσε μια πολιτεία Παραλείπω).

Ικανός να Παραλείπωμένουμε μέχρι να συναντήσουμε έναν χαρακτήρα κενού διαστήματος. Αφού εντοπιστεί το διάστημα, ακολουθούμε το βέλος Χώροςσε μια πολιτεία Αρχή... Αυτό είναι απαραίτητο για την πλήρη παράλειψη μιας γραμμής που δεν ταιριάζει με το μοτίβο αναζήτησής μας.

Μετά την είσοδο στο κράτος Αρχή, ο κύκλος αναζήτησης επαναλαμβάνεται από την αρχή. Ο κλάδος αναγνώρισης αριθμών είναι παρόμοιος με τον κλάδο αναγνώρισης λέξεων.

Αυτόματη χρήση εντολών διακόπτη

Το πρώτο είναι οι πιθανές καταστάσεις:

Μετά από αυτό, επαναλαμβάνουμε τη συμβολοσειρά, ολισθώντας τον τρέχοντα χαρακτήρα στο μηχάνημα. Το ίδιο το αυτόματο είναι μια δήλωση διακόπτη που εκτελεί πρώτα μια μετάβαση στο τμήμα της τρέχουσας κατάστασης. Μέσα στο τμήμα υπάρχει μια κατασκευή if-else, η οποία, ανάλογα με το συμβάν (εισερχόμενο σύμβολο), αλλάζει την τρέχουσα κατάσταση:

const size_t μήκος = text.length (); για (μέγεθος_t i = 0; i! = μήκος; ++ i) (const char ρεύμα = κείμενο [i]; διακόπτης (κατάσταση) (περίπτωση State_Start: if (std :: isdigit (current)) (state = State_Number;) αλλιώς εάν (std :: isalpha (τρέχον)) (state = State_Word;) break; case State_Number: if (std :: isspace (current)) (

Εδώ βλέπουμε το διάγραμμα - την τρέχουσα κατάσταση Αριθμός, Εκδήλωση Χώρος(βρέθηκε λευκός χώρος), που σημαίνει ότι βρέθηκε ένας αριθμός:

FoundNumber (); κατάσταση = State_Start; ) αλλιώς εάν (! std :: είναι ψηφίο (τρέχον)) (state = State_Skip;) break; case State_Word: if (std :: isspace (current)) (FoundWord (); state = State_Start;) other if (! std :: isalpha (current)) (state = State_Skip;) break; case State_Skip: if (std :: isspace (current)) (state = State_Start;) break; ))

Αποτέλεσμα:

Υψηλής απόδοσης

Ευκολία υλοποίησης για απλούς αλγόριθμους

- Είναι δύσκολο να διατηρηθεί

Ερμηνεία χρόνου εκτέλεσης

Η ιδέα αυτής της προσέγγισης είναι απλή - πρέπει να δημιουργήσετε έναν πίνακα μετάβασης, να τον συμπληρώσετε και, στη συνέχεια, όταν συμβεί ένα συμβάν, να βρείτε την ακόλουθη κατάσταση στον πίνακα και να κάνετε μια μετάβαση:

enum Συμβάντα (Event_Space, Event_Digit, Event_Letter, Event_Unknown); void ProcessEvent (Συμβάν εκδηλώσεων). ... struct Transition (States BaseState_; Events Event_; State TargetState_;); void AddTransition (Πολιτεία από Πολιτεία, Συμβάντα Εκδηλώσεις, Πολιτεία σε Κράτος). ... typedef std :: διάνυσμα< transition>TransitionTable; TransitionTable Transitions_; Πολιτεία Τρέχουσα κατάσταση_;

Συμπλήρωση του πίνακα:

AddTransition (State_Start, Event_Digit, State_Number); AddTransition (State_Start, Event_Letter, State_Word); Προσθήκη Μετάβασης (Κατάσταση_Αριθμός, Χώρος_συμβάντος, Κατάσταση_Έναρξη); Προσθήκη Μετάβασης (Κατάσταση_Αριθμός, Γράμμα_Γεγονότος, Παράλειψη_Κατάστασης); Προσθήκη Μετάβασης (Κατάσταση_Αριθμός, Συμβάν_Άγνωστο, Κατάσταση_Παράλειψη); AddTransition (State_Word, Event_Space, State_Start); AddTransition (State_Word, Event_Digit, State_Skip); AddTransition (State_Word, Event_Unknown, State_Skip); AddTransition (State_Skip, Event_Space, State_Start);

Αποδείχθηκε αρκετά ξεκάθαρα. Το τίμημα για σαφήνεια θα είναι η πιο αργή λειτουργία του μηχανήματος, η οποία, ωστόσο, συχνά δεν έχει σημασία.

Για να μπορεί το αυτόματο, με την εμφάνιση ορισμένων γεγονότων, να ειδοποιήσει κάποιον κώδικα, μπορείτε να προσθέσετε στη δομή πληροφορίες σχετικά με τη μετάβαση ( Μετάβαση) δείκτης συνάρτησης ( Δράση), που θα ονομάζεται:

typedef void (DynamicMachine :: * Action) (); struct Transition (States BaseState_; Events Event_; State TargetState_; Action Action_;); ... void AddTransition (Πολιτεία απόΠολιτεία, Συμβάντα Εκδηλώσεις, Πολιτεία σε Κράτος, Δράση δράσης). ... AddTransition (State_Number, Event_Space, State_Start, & DynamicMachine :: FoundNumber);

Αποτέλεσμα:

Ευελιξία και ορατότητα

Πιο εύκολο στη συντήρηση

- Χαμηλότερη απόδοση σε σύγκριση με τα μπλοκ διακόπτη

Ερμηνεία χρόνου εκτέλεσης. Βελτιστοποιημένο για ταχύτητα

Μπορείτε να συνδυάσετε την ορατότητα με την ταχύτητα; Είναι απίθανο να είναι δυνατό να γίνει ένα αυτόματο τόσο αποτελεσματικό όσο ένα αυτόματο σε μπλοκ διακόπτη, αλλά είναι δυνατό να κλείσει το κενό. Για να το κάνετε αυτό, πρέπει να δημιουργήσετε έναν πίνακα από τον πίνακα, έτσι ώστε, για να λάβετε πληροφορίες σχετικά με τη μετάβαση, να μην κάνετε αναζήτηση, αλλά να κάνετε μια επιλογή από την κατάσταση και τον αριθμό συμβάντος:

Το αποτέλεσμα επιτυγχάνεται λόγω της κατανάλωσης μνήμης.

Αποτέλεσμα:

Ευελιξία, ορατότητα

Αποτελεσματικός

- Κατανάλωση μνήμης (πιθανότατα ασήμαντη)

Boost Statechart

Έχουμε συζητήσει διάφορους τρόπους για να εφαρμόσετε μόνοι σας μια κρατική μηχανή. Για μια αλλαγή, προτείνω να σκεφτείτε μια βιβλιοθήκη για την κατασκευή αυτόματα από το Boost. Αυτή η βιβλιοθήκη είναι πολύ ισχυρή, οι προσφερόμενες δυνατότητες σας επιτρέπουν να κατασκευάσετε πολύ περίπλοκες μηχανές πεπερασμένης κατάστασης. Θα το ρίξουμε μια γρήγορη ματιά.

Λοιπόν, πρώτα, ας ορίσουμε τα γεγονότα:

Συμβάντα χώρου ονομάτων (struct Digit: boost :: statechart :: event< Digit>() struct Γράμμα: boost :: statechart :: συμβάν< Letter>() struct Space: boost :: statechart :: event< Space>() struct Άγνωστο: boost :: statechart :: συμβάν< Unknown> { } ; }

Το ίδιο το μηχάνημα (σημειώστε ότι η δεύτερη παράμετρος του προτύπου είναι η αρχική κατάσταση):

struct Machine: boost :: statechart :: state_machine< Machine, States:: Start > { } ;

Και τα ίδια τα κράτη. Μέσα στις καταστάσεις, απαιτείται να οριστεί ένας τύπος που να περιγράφει μεταβάσεις ( αντιδράσεις), και αν υπάρχουν πολλές μεταβάσεις, τότε καταχωρίστε τις στη λίστα τύπων boost :: mpl :: λίστα. Δεύτερη παράμετρος προτύπου απλή_κατάσταση- τον τύπο που περιγράφει το αυτοκίνητο. Οι μεταβάσεις περιγράφονται από τις παραμέτρους του προτύπου μετάβασης, μερικά από Εκδήλωση - Επόμενη Πολιτεία:

Καταστάσεις χώρου ονομάτων (struct Start: boost :: statechart :: simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> αντιδράσεις. ) struct Number: boost :: statechart :: simple_state< Number, Machine>(typedef boost :: mpl :: λίστα< boost:: statechart :: transition < Events:: Space , States:: Start >, ενίσχυση :: διάγραμμα κατάστασης :: μετάβαση< Events:: Letter , States:: Skip >, ενίσχυση :: διάγραμμα κατάστασης :: μετάβαση< Events:: Unknown , States:: Skip >> αντιδράσεις. ) struct Word: boost :: statechart :: simple_state< Word, Machine>(typedef boost :: mpl :: λίστα< boost:: statechart :: transition < Events:: Space , States:: Start >, ενίσχυση :: διάγραμμα κατάστασης :: μετάβαση< Events:: Digit , States:: Skip >, ενίσχυση :: διάγραμμα κατάστασης :: μετάβαση< Events:: Unknown , States:: Skip >> αντιδράσεις. ) struct Skip: boost :: statechart :: simple_state< Skip, Machine>(ενίσχυση τύπου :: κατάσταση κατάστασης :: μετάβαση< Events:: Space , States:: Start >αντιδράσεις? ) )

Το μηχάνημα είναι κατασκευασμένο, μένει μόνο να το αρχικοποιήσετε και μπορείτε να χρησιμοποιήσετε:

Μηχανή μηχανής? machine.initiate (); ... machine .process_event (Events :: Space ());

Αποτέλεσμα:

Ευελιξία, επεκτασιμότητα

- Αποτελεσματικότητα

Εκτέλεση

Έγραψα ένα δοκιμαστικό πρόγραμμα για να δοκιμάσω την απόδοση των κατασκευασμένων αυτόματα. Μέσα από τα μηχανήματα, έτρεξα το κείμενο μεγέθους ~ 17 MB. Ιδού τα αποτελέσματα του τρεξίματος:

Φόρτωση μήκος κειμένου Κείμενο: 17605548 bytes 0.19 s Τρέξιμο Λέξεις BoostMachine: 998.002, αριθμοί: 6816 0,73 s Τρέξιμο Λέξεις DynamicMachine: 998.002, αριθμοί: 6816 0.56 s Τρέξιμο Λέξεις FastDynamicMachine: 998.002, αριθμοί: 6816 0,29 s Τρέξιμο Λέξεις SimpleMachine: 998.002, αριθμοί: 6816 0,20 s

Αυτό που μένει απρόσεκτο

Μερικές ακόμη υλοποιήσεις μηχανών πεπερασμένης κατάστασης παρέμειναν ακάλυπτες (συνιστώ http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml και http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), γεννήτριες που κατασκευάζουν αυτόματα από περιγραφές, τη βιβλιοθήκη Meta State Machine από την έκδοση Boost 1.44.0, καθώς και επίσημες περιγραφές καταστάσεων μηχανών. Ο περίεργος αναγνώστης μπορεί να εξοικειωθεί με όλα τα παραπάνω.