A la question des tampons (ring)

«Si vous trouvez les coûts de développement de l'architecture excessifs, considérez combien une mauvaise architecture peut vous coûter»

- Je ne me souviens pas exactement de la source

Une fois, "il y a longtemps, dans une galaxie lointaine", j'ai acheté le merveilleux livre Etudes for Programmers de Charles Weatherly, dans l'introduction à laquelle l'auteur a démontré la nécessité d'étudier des exemples et des tâches pédagogiques avant de commencer une programmation indépendante. Je vous recommande fortement de trouver ce livre, de lire la préface (et sans vous y arrêter, de lire le reste et de résoudre les problèmes qui y sont donnés), car je ne peux pas mieux justifier la nécessité d'une telle pratique. Même si vous suivez ma recommandation et acquérez beaucoup de connaissances et de compétences pratiques lors de la lecture du livre, vous pouvez revenir en arrière et lire ce post, car il est consacré à plusieurs autres questions. Et si vous ne suivez pas mes recommandations, alors vous devriez d'autant plus passer sous le chat.

Il n'y a pas si longtemps, dans un article dans lequel j'ai grondé, j'ai exprimé mon opinion sur un RTOS national, j'ai mentionné que la mise en œuvre du tampon en anneau dans la bibliothèque bien connue (et à certains égards, absolument merveilleuse) de mcucpp ne pouvait pas être considérée comme idéale. Je vais essayer d'expliquer mon point de vue et d'imaginer la mise en œuvre idéale (autant que possible dans le monde réel). Remarque - le texte proposé à votre attention est resté dans le "inachevé" pendant un certain temps, puis un cas si pratique s'est présenté.

Nous continuons à développer une bibliothèque pour travailler avec un périphérique, et nous sommes à côté pour la gestion de la mémoire et la mise en mémoire tampon (oui, nous continuons toujours les opérations préparatoires, mais sans eux en aucune façon). D'où vient le besoin d'organiser les tampons et de quel type d'animal s'agit-il? Le fait est qu'une partie importante de la périphérie a une vitesse limitée et que le processus de transmission, démarré d'une manière ou d'une autre, prend un certain temps, et parfois très important, par rapport à la création d'une autre partie des informations à transmettre. Bien sûr, avant que ce temps ne soit écoulé, la prochaine transmission ne peut pas être effectuée et, par conséquent, ne peut pas être démarrée.

Nous avons un cas classique d'une paire écrivain-lecteur avec différentes vitesses. Il est tout simplement impossible de résoudre ce problème sous une forme générale, car «avec un excès arbitrairement petit, mais pas nul, du flux de demandes sur le flux de service, la taille de la file d'attente tend vers l'infini» et l'infini est fondamentalement impossible. Mais un cas particulier du problème, lorsque nous avons des rafales locales de demandes, mais qu'en moyenne le flux de service est capable de faire face à la charge, une mémoire tampon de capacité suffisante peut être résolue. Prenons garde à l'expression «capacité suffisante», nous apprendrons plus tard à la calculer, tant que le fait que cela soit fondamentalement possible nous suffit.

Que la mémoire tampon soit une exigence absolue ne l'est bien sûr pas. Pour les informations transmises, vous pouvez utiliser un enregistrement de blocage, mais avec les informations reçues, c'est un peu pire, il faudra l'ajouter quelque part avant le traitement, si vous ne prenez pas les mesures appropriées dans le protocole de haut niveau (l'expression magique xon / xoff n'est pas née de zéro), ce qui n'est pas toujours possible et, dans tous les cas, conduit généralement à une limitation importante du débit de transmission. Il existe également une implémentation matérielle des tampons internes dans les périphériques (au moins pour un élément), mais cela n'est pas toujours fait et la taille du tampon est strictement limitée par le haut.

Par conséquent, nous allons toujours implémenter le tampon de programme, pour lequel il serait naturel d'utiliser la méthode FIFO (c'est-à-dire la file d'attente) pour organiser un tel tampon, et la file d'attente, à son tour, est mieux implémentée sur un tampon en anneau avec deux pointeurs. Lorsque j'écris «mieux», cela ne signifie pas du tout que d'autres implémentations (par exemple, une file d'attente de référence) sont impossibles ou présentent des failles fatales autres que fatales. Cette expression signifie seulement que la mise en œuvre ne sera pas trop compliquée et assez efficace, bien que d'autres puissent avoir des avantages indéniables par rapport à cela, pour lesquels ils devront payer avec quelque chose, car DarZaNeBy.

Comme il est hautement improbable que votre modèle MK ait une implémentation matérielle d'un tel appareil à usage général (les modules périphériques individuels peuvent avoir leurs propres tampons en anneau, mais ils n'ont rien à voir avec le sujet de cet article), nous devrons créer un tampon en anneau dans la mémoire linéaire (implémenter sur vecteur, c'est, en général, le seul objet naturel dans la mémoire adressable), et pour cela, un index de tampon (ou peut-être même deux index, mais plus à ce sujet plus tard) sera nécessaire. À mon avis, un tampon circulaire avec deux pointeurs (indices) est le seul moyen acceptable d'implémenter une file d'attente sur un vecteur, mais il existe différents points de vue sur cette question et j'ai vu de mes propres yeux une implémentation dans le style de «x1 = x2; x2 = x3; ... x8 = nouveau symbole ", si vous voulez, je ne considérerai pas comme exotique. Le fait que le fragment donné puisse avoir le droit d'exister dans une situation spécifique très limitée ne le rend pas acceptable en général.

Nous considérerons la mise en œuvre correcte du module de programme pour organiser le pointeur, et pour commencer, faites attention au premier mot de la définition. La différence entre un code correct et un mauvais n'est pas seulement parce que le code correct ne contient pas d'erreurs, bien qu'il s'agisse d'une exigence absolue. Même le code qui remplit pleinement ses fonctions peut être incorrect s'il est incompréhensible, ou s'il existe une option qui n'est pas moins claire, mais qui s'exécute plus rapidement ou qui s'exécute tout aussi rapidement, mais plus clairement écrite, de sorte que le concept de correction est quelque peu relatif. Nous continuons notre examen de notre exemple d'implémentation de tampon, qui nous permettra de démontrer la différence entre les différents degrés de correction.

Avant de passer à l'essentiel, un point important sur la suite de la discussion. Je veux dire que votre compilateur est toujours activé à un niveau d'otpimisation non nul (-O2), donc nous n'avons pas à penser à des améliorations mineures comme 1) la modification du préfixe par rapport à postfix, ou 2) utiliser les résultats de l'opération précédente, ou 3) la différence entre l'incrémentation et l'ajout unités et ainsi de suite - nous supposons que le compilateur fera beaucoup pour nous. Bien sûr, ce n'est pas une hypothèse stricte, mais sinon nous devrons plonger dans les entrailles de l'assembleur, qui à notre époque n'est pas le courant dominant.

Permettez-moi de vous rappeler que nous avons été chargés d'implémenter l'index (pointeur) du tampon en anneau, c'est-à-dire que nous devons créer un comportement variable qui traverse séquentiellement une série de valeurs, de l'initiale à la finale . Supposons immédiatement que la valeur initiale sera nulle, sinon nous devrons immédiatement écrire un code plus ou moins correct, ce qui contredit les objectifs éducatifs et nous ne sommes pas pressés, et le dernier est Max.

Ce comportement de la variable peut être implémenté en utilisant la construction suivante:

volatile int Counter = 0; Counter = (++Counter) % (Max+1); 

et c'est précisément un tel code que nous pouvons voir dans de nombreux cas (c'est-à-dire très souvent). Qu'est-ce qui ne va pas - eh bien, premièrement, pendant un certain temps (de l'exécution de l'opération d'incrémentation à l'attribution du résultat), notre variable sera supérieure à la valeur maximale autorisée et, si à ce moment une interruption se produit qui doit prendre en compte la valeur de cette variable, alors je prédit personnellement Je ne présume pas des résultats. Par conséquent, nous réécrivons le programme:

 int Counter=0; Counter = (Counter + 1) % (Max + 1); 

Nous avons éliminé une erreur, et le code (ci-après je veux dire le code «exécutable» signifie le code exécutable généré par le compilateur) n'est pas devenu plus long et ne s'exécute plus (en fait, il s'exécute plus rapidement, mais uniquement parce que dans la première version le mot volatile est utilisé complètement redondant dans ce cas), et n'est pas devenu moins clair (plutôt, encore plus clair, mais c'est une question de goût).

Remarque nécessaire sur volatile - cette directive est nécessaire si nous voulons éviter l'optimisation de code qui conduit à une exécution incorrecte, et dans ce cas particulier (lorsque la valeur de la variable ne change pas en dehors de la portée du module et qu'il n'y a pas d'entrées séquentielles), elle (directive ) complètement redondant. Je vous recommande fortement de regarder le code généré pour les deux options sur godbolt.org. Pourquoi ne pas abuser de la directive volatile, contrairement au mot-clé statique, dont l'utilisation est recommandée dans la mesure du possible. Eh bien, premièrement, nous interdisons l'optimisation, c'est-à-dire que le code ne deviendra certainement pas plus rapide (très probablement, il deviendra plus gros et plus lent, mais nous préférons des formulations strictes). Et deuxièmement, dans ce cas particulier, ce mot est trompeur, car par rapport à notre programme, la valeur du compteur ne peut en aucun cas changer en dehors de notre contrôle. Dans un programme qui lit sa valeur - c'est-à-dire, dans l'implémentation du tampon en anneau lui-même, vous pouvez considérer le compteur mutable en dehors du module, et là il est discutable, donc cet attribut n'est tout simplement pas applicable au compteur. Si une variable doit être interprétée différemment dans différents modules, nos services doivent être combinés, si nous parlons d'organiser une section critique, par exemple, lors de la mise en œuvre d'une transaction ou d'opérations atomiques, alors cette directive ne donne rien du tout.

Nous revenons au code et voyons que le programme est toujours faux - quel est le problème - et le fait est qu'il ne fait pas ce dont nous avons besoin (voir la description de la tâche), mais autre chose (calcule le reste de la division), juste les résultats correspondre. Eh bien, nous le pensons (je ne pense pas, mais les auteurs du code certainement), que les résultats coïncident, en fait, dans le cas général, ils ne coïncident pas, nous avons juste eu de la chance avec la plage de la variable (valeurs positives). De plus, le processus d'exécution du code est plus long qu'il ne pourrait l'être, car dans le meilleur des cas, nous avons l'opération de division entière (si elle fait partie des commandes de notre architecture), et elle n'est effectuée en aucun cas dans un cycle de processeur (une valeur caractéristique de 10 cycles pour une architecture 8 bits), et dans le pire des cas, nous verrons l'appel de procédure de division à partir de la bibliothèque standard (et bien, si la division est courte), alors le temps d'exécution sera de dizaines de cycles d'horloge.

Alors, pourquoi une telle approche complètement fausse est-elle encore possible de se rencontrer très souvent. Ici, du public, ils me disent qu'avec la valeur de Max + 1, qui est une puissance de deux, le compilateur devinera au lieu de l'opération de division, placera l'opération de multiplication au niveau du bit sur le masque correspondant (égal à Max), qui sera effectuée très rapidement et tout ira bien.

Je serais d'accord avec cette déclaration et adopterais cette approche, sinon pour les circonstances suivantes:

• cela n'est possible que pour Mach défini statiquement au stade de la compilation,
• cela ne se produit que lorsque l'optimisation est activée,
• cela ne se produit que lorsque Mach remplit cette condition,
• cela ne se produit pas pour tous les types cardinaux.

De plus, c'est dans ce cas particulier (lorsque la variable est définie comme un signe), en plus de la commande de multiplication (logique) par le masque, une commande de comparaison avec zéro et une branche pour les valeurs négatives sera générée, et bien que cette branche ne sera jamais pour notre gamme il sera exécuté, il prendra de la place dans la mémoire (et dans le cas d'une fonction substituable, il faudra plusieurs fois) et il faudra du temps pour effectuer l'opération de comparaison, si vous n'y croyez pas, nous suivons à nouveau le site indiqué et voyons par vous-même. Un autre argument en faveur des cardinaux non signés, auquel j'ai récemment consacré un poste entier.

Par conséquent, si nous voulons utiliser la multiplication logique avec un masque (obtenu en optimisant le calcul du reste), nous devons réécrire le module en conséquence:

 typedef uint8_t Counter_t; typedef int8_t sCounter_t; static inline Counter_t NextCounter(const Counter_t Counter) { #if IS_POWER2(Max + 1) return (Counter + 1) & Max #else return (Counter + 1) % (Max + 1); #endif }; 

Dans cette version, tout est complètement clair et contrôlable et tout est vrai (même si un certain nombre de lacunes sont restées, mais elles sont maintenant évidentes et non masquées), donc c'est correct, bien que ce soit plus correct et nous allons maintenant les chercher. Le principal inconvénient, à mon avis, est une violation du principe KISS, car l'utilisation de l'opération restante par division néglige complètement ce principe. Par conséquent, nous allons maintenant détruire tous les défauts d'un seul coup (ne vous inquiétez pas de leur sort, ils renaîtront 100 500 fois, car tous les programmeurs d'Arduino ne lisent pas mes messages).

Mais d'abord, une légère déviation sur le côté. Comment pouvons-nous implémenter une vérification de la puissance de deux (un nombre binaire peut être représenté par {0} 1 {0}) que nous venons d'utiliser


Et comment pouvons-nous implémenter la vérification qu'un nombre est une bonne séquence d'unités {0} 1 {1} en notation binaire - une option est évidente

 #define IsRightSequence(N) IsPower2 ((N) + 1) 

et le second est trivial

 #define IsRightSequence(N) ( (((N) + 1) & (N)) == 0) 

Remarque: je ne peux pas m'empêcher de rappeler le magnifique théorème: "Un nombre transcendantal à un degré transcendantal est toujours transcendantal, à moins que l'inverse ne soit évident ou trivial."

Et comment pouvons-nous vérifier qu'un nombre est une séquence d'unités {0} 1 {1} {0}

 #define IsSequence(N) IsPower2( (N) ^ ((N) << 1)) 

Et enfin - comment sélectionner le bit le moins significatif d'un nombre (je ne sais pas pourquoi cela pourrait être nécessaire, mais cela sera utile)

 #define LowerBit(N) ((((N) - 1) ^ (N)) & (N)). 

Mais il est venu avec ce qui peut être utile

 #define IsRightSequence(N) (IsSequence(N) && (LowerBit(N) == 1)) 

Une observation curieuse - ces macros ne sont pas tout à fait correctes, il s'avère que 0 est à la fois une puissance de deux et une bonne séquence (bien sûr, une séquence aussi), ce qui est un peu étrange. Mais 1 est tous ces objets à juste titre, donc zéro, semble-t-il, doit simplement être considéré séparément. Une autre propriété intéressante de ces macros est que nous ne faisons aucune hypothèse sur la longueur de l'argument, c'est-à-dire qu'elles fonctionnent correctement avec n'importe quel type cardinal.

Il existe un merveilleux livre, Tricks for Programmers, où vous pouvez trouver les macros mentionnées et de nombreuses autres tâches tout aussi amusantes et instructives, je vous recommande vivement de le lire, d'autant plus qu'il n'y a pas trop de lettres.

Mais revenons à notre indice de tampon en anneau. Nous avons donné la bonne solution, mais promis encore plus correctement, ce qui signifie que notre dernière solution a des défauts (qui en douteraient). L'une d'entre elles - la longueur du tampon doit être déterminée statiquement au stade de la compilation, la seconde - en cas de longueur infructueuse, le temps d'exécution est très long et il y a encore un certain nombre d'erreurs dans un morceau relativement petit du programme, ce qui nous fait rappeler une blague sur 4 erreurs d'écriture du mot «plus». Nous les éliminerons tous (certains seront laissés pour plus tard) et immédiatement, pour lesquels, enfin, nous écrirons la solution au problème d'origine telle qu'elle est:

 static inline Counter_t NextCounter(const Counter_t Counter) { if ((Counter + 1) > Max) { return 0; } else { return Counter + 1; }; }; 

(Comme vous l'avez déjà compris, je suis partisan des crochets égyptiens et il n'y a rien à faire à ce sujet).

Prenons attention au fait que nous avons simplement réécrit l'état du problème à partir d'un langage naturel dans le langage de programmation choisi, de sorte qu'il s'avère extrêmement clair et compréhensible. Est-il possible de l'améliorer - sans doute, mais uniquement du point de vue des performances du code, car il n'y a tout simplement pas d'autres défauts pour cette solution (il n'y a pas de défauts évidents, en fait ils le sont et nous les éliminerons avec succès).

Évaluons la complexité de calcul de cette solution - addition avec unité (1) et comparaison (2) toujours, puis affectation de zéro (1) (rarement) ou addition (1) (presque toujours) - ce qui donne 1 + 2 + 1 + Δ ~ 4 élémentaire opérations et zéro mémoire. Il est possible qu'un bon compilateur dans le bon mode fasse certaines optimisations et réduise le temps d'exécution du code, mais il vaut mieux le faire explicitement. Voici l'option suivante:

 static inline Counter_t NextCouner(const Counter_t Counter) { register sCounter_t Tmp; Tmp = (Counter + 1); if (Tmp > Max) { Tmp = 0; }; return Tmp; }; 

Nous évaluons la complexité - addition et comparaison toujours, en attribuant zéro (rarement) - environ 3 opérations et un élément de mémoire. En fait, la version précédente avait également un élément mémoire (implicite), nous avons donc un gain net en une seule opération élémentaire. De plus, la version précédente avait deux autres inconvénients - 1) violé le principe DRY (calculé l'augmentation d'une fois deux fois) et 2) avait plus d'un point de sortie, ce qui n'est pas bon. Nous n'avons pas non plus perdu de vue, c'est-à-dire que nous avons réussi à tuer un tas de lapins d'un seul coup, et nous n'avons pas dépensé de cartouches non plus - c'est juste une histoire dans le style du baron Munchausen.

Notez que je n'ai pas utilisé la construction if ( (Tmp = Counter + 1) > Max) , bien qu'elle contienne une instruction explicite au compilateur pour essayer de ne pas effectuer de transferts redondants. C'est l'aromatisation sous la forme la plus flagrante, je n'aime tout simplement pas la valeur retournée par l'opérateur d'affectation et j'essaie d'éviter de l'utiliser. Je ne peux pas expliquer la raison de ce sentiment fort, selon Freud, il s'agit très probablement d'un traumatisme psychologique dans l'enfance. Les compilateurs modernes sont tout à fait capables d'effectuer eux-mêmes une simple optimisation, et en plus, j'ai également ajouté un qualificatif de registre, afin que le code de ma version et celui correct (du point de vue du langage C) correspondent. Néanmoins, je ne limite pas du tout votre liberté d'utiliser la méthode qui vous semble préférable.

Nous continuons à nous améliorer, car il n'y a pas de limite à la perfection et nous ne l'avons pas encore atteinte. Pour y parvenir, nous reformulons quelque peu le problème d'origine et ne laissons que l'exigence de la variable dans la plage de valeurs, sans indiquer la direction du changement. Cette approche vous permet de réécrire le programme comme suit

 static inline Counter_t NextCouner(const Counter_t Counter) { register Counter_t Tmp; Tmp = (Counter - 1); if (Tmp < 0) { Tmp = ; }; return Tmp; }; 

À première vue, rien n'a beaucoup changé, mais nous obtenons néanmoins un gain de temps. Bien sûr, non pas du fait que l'opération de diminution de un fonctionne plus vite que l'opération d'augmentation par celle-ci (bien que j'aie entendu une version similaire), mais en raison des particularités de la comparaison. Si dans les versions précédentes je considérais la comparaison comme 2 opérations élémentaires (on soustrait d'abord puis on prend une décision), alors dans ce cas le résultat de l'opération précédente est utilisé pour prendre une décision directement et la comparaison prend une opération élémentaire, ce qui conduit à deux opérations toujours et une affectation (rarement) et nous avons sauvé une opération (sans rien perdre), comme le dit le proverbe, "une bagatelle, mais agréable." La solution résultante est-elle idéale - malheureusement, non. Il est légèrement inférieur à la solution avec un masque (qui nécessite exactement 2 opérations élémentaires) en termes de vitesse et c'est peut-être son seul inconvénient.

Il existe une solution encore plus rapide - il suffit d'augmenter (de diminuer) la valeur du compteur et de ne rien faire d'autre, mais ce n'est possible que dans le seul cas où la valeur maximale coïncide avec la valeur la plus représentative du type accepté. Pour un compteur 8 bits (c'est-à-dire, comme uint8_t), ce sera 255, puis nous écrivons simplement Counter = Counter + 1 et je crois que l'écriture de Counter + = 1 ou ++ Counter est complètement facultative, bien que beaucoup le soient et ils écriront et auront tout à fait raison. Si nous ne considérons pas sérieusement la version sur la nécessité de sauvegarder les caractères (puisque la première option est la plus longue), cela n'a aucun sens, du moins si nous écrivons un programme pour l'architecture ARM ou AVR (pour d'autres que je n'ai tout simplement pas vérifié, je soupçonne que le résultat sera la même chose) sous le compilateur GCC (l'auteur comprend qu'ils écrivent le programme dans l'éditeur de l'environnement de programmation intégré, ce n'est qu'une révolution vocale du passé lorsque les ordinateurs étaient grands et la mémoire petite), et avec l'optimisation activée à n'importe quel niveau, car le code donné sera absolument identique.

Les compilateurs modernes sont très, très avancés en termes d'optimisation et génèrent vraiment du très bon code, bien sûr, si vous avez activé le mode correspondant. Bien que je sois prêt à convenir que de telles constructions de langage ne nuisent pas et peuvent être utiles dans certaines conditions, la seule chose que je note est que les expressions Counter ++ (dans ce cas particulier, bien sûr) doivent être évitées sans ambiguïté, car elles sont destinées à des situations complètement différentes et peuvent donner lieu à code plus lent, bien que facultatif.

Une autre question est qu'un tampon de 256 éléments n'est pas toujours acceptable, mais si vous avez suffisamment de mémoire, alors pourquoi pas. Avec cette implémentation, si vous pouvez aligner le tampon sur la bordure de page, l'accès aux éléments peut être rendu très rapide en éliminant l'opération de déplacement d'index en index (le mot-clé union vous indiquera l'implémentation d'une telle fonctionnalité, je ne l'apporterai pas afin de ne pas apprendre mauvais), mais c'est déjà une décision très, très spécifique avec un fort attachement à l'architecture, qui est dangereusement proche des astuces au pire sens du terme, et ce n'est pas notre style.

Bien sûr, personne ne nous interdit d'écrire un wrapper qui appellera telle ou telle méthode en fonction de la valeur du maximum (et du minimum, car de nombreuses méthodes ne fonctionnent tout simplement pas avec un minimum non nul), j'ai déjà proposé les principes de base d'une telle solution, donc nous proposerons cela comme un exercice.

Eh bien, en conclusion, pour résumer - nous allons rassembler différentes implémentations de travail avec un indice d'anneau et évaluer leurs propriétés.

La deuxième ligne entre parenthèses indique le nombre de valeurs de taille de tampon (ne dépassant pas 256) pour lesquelles cette implémentation est disponible, mais nous voulons dire qu'un tampon de taille 0 ne nous intéresse pas.

Comme vous pouvez le voir sur ce tableau, DarZaNeBy (mon expression préférée, comme vous l'avez peut-être remarqué), et les avantages sont achetés au prix d'inconvénients, la seule chose qui peut être déclarée sans équivoque est que l'incrément avec vérification a un concurrent plus efficace sous la forme d'une décrémentation avec vérification et ne passe pas au cycle suivant en aucun cas.

Une note nécessaire - il existe des langages de programmation dans lesquels nous n'aurions pas du tout à penser à la mise en œuvre de l'index, mais nous pourrions simplement utiliser le type d'intervalle. Malheureusement, je ne peux pas appeler l'implémentation de ces constructions dans le code optimal, car ces constructions (et ces langages) ne sont pas destinées à l'optimisation au moment de l'exécution, mais c'est dommage.

Nous avons donc créé le bon module (quel nom fort pour la fonction inline) pour travailler avec l'index, et maintenant nous sommes prêts à commencer à implémenter le tampon en anneau lui-même.

Et pour commencer, nous devons décider ce que nous voulons exactement de cet objet programme. Il est absolument nécessaire de pouvoir mettre un élément de données dans un tampon et de l'extraire - deux méthodes principales, une sorte de getter et setter. Il est théoriquement possible d'imaginer un tampon sans l'une de ces méthodes, ou même sans les deux (peu peut être imaginé purement théoriquement), mais la valeur pratique d'une telle implémentation est une grande question. La prochaine fonctionnalité nécessaire - vérification des informations - peut être implémentée soit comme une méthode distincte, soit comme une valeur spéciale (ou attribut) retournée par la lecture. Habituellement, ils préfèrent la première méthode, car elle se révèle plus compréhensible et pas trop chère.
Mais vérifier l'exhaustivité du tampon est déjà une grande question - cette opération nécessitera du temps supplémentaire, qui sera toujours consacré à l'enregistrement, bien que personne ne nous oblige à l'utiliser - alors laissez-le. Nous n'avons besoin de rien d'autre du tampon, souvenons-nous de cette phrase pour l'avenir.

Retour à l'implémentation. Nous avons besoin d'un endroit pour stocker les éléments de la file d'attente et de deux index - un pour écrire dans le tampon et un pour lire à partir de celui-ci. Comment exactement nous obtiendrons cet endroit (et ces pointeurs) est un sujet pour une discussion séparée, pour l'instant, laissons ce moment entre crochets et croyons que nous les avons simplement. Certains (y compris les auteurs du livre "Programmation pour les mathématiciens" que je respecte, je le recommande pour la lecture) utilisent également le compteur de places remplies, mais nous ne le ferons pas et j'essaierai de montrer pourquoi c'est mal.

Tout d'abord, sur les indices - nous remarquons immédiatement que ce sont des indices, pas des pointeurs, bien que parfois je me permette d'être appelé ainsi.Pourquoi les index (stockage d'informations sur le numéro de l'élément de file d'attente) et non les pointeurs (stockage d'informations sur l'emplacement dans la mémoire de l'élément de file d'attente) est une question très difficile, il existe des situations où les pointeurs sont plus rentables, mais ce n'est clairement pas notre cas. Nos files d'attente seront courtes (même à 256, nous regardons avec prudence), donc les index prendront moins de place, les opérations élémentaires seront plus rapides pour eux, il n'y aura pas de problèmes d'atomicité des opérations (dans une architecture normale, il ne devrait pas y en avoir avec des pointeurs, mais avec Les index 8 bits ne se produiront tout simplement jamais, bien sûr, si vous n'avez pas de contrôleur 4 bits), les coûts supplémentaires associés au passage de l'index au pointeur ne seront pas trop importants (à condition que les éléments de la file d'attente soient petits).


De plus, de nombreuses astuces qui augmentent la vitesse d'obtention de la valeur suivante ne seront plus disponibles lors de l'utilisation du pointeur. Et si vous tenez également compte de l'opinion selon laquelle les pointeurs sont plus difficiles à comprendre (non pas que cette opinion me paraisse correcte, mais qu'elle existe), alors le choix est clair - les index.

Mais ce que les indices devraient montrer exactement - ici, la marge d'imagination est illimitée dans la taille du tampon Max (et même plus que cela), mais un très petit ensemble d'options a une signification pratique. Pour l'index d'enregistrement, ce sont deux possibilités: 1) indiquer l'endroit où le dernier élément a été enregistré et 2) indiquer l'endroit où l'élément suivant sera enregistré. Comme immédiatement après la création de la file d'attente, la première option semble un peu étrange, nous choisissons la seconde, d'autant plus que cela nous promet un gain tangible à l'avenir. Pour l'index de lecture, nous supposons immédiatement qu'il pointe vers l'élément qui sera lu la prochaine fois qu'il sera lu. Il existe immédiatement un critère simple (au sens de la vérification) selon lequel la file d'attente n'est pas vide - les indices ne sont pas égaux. Mais le deuxième problème se pose - si nous mettons en file d'attente exactement les éléments Mach,alors les indices coïncideront et nous ne pourrons pas distinguer cette situation d'une file d'attente vide.

La première solution à ce problème («une mauvaise solution évidente, compréhensible et simple») a été utilisée à plusieurs reprises et consiste à mettre en place un compteur pour le nombre d'éléments placés dans le buffer, ou dans le cas avancé l'indicateur d'exhaustivité. Pourquoi je ne l'approuve pas - c'est 1) de l'espace mémoire supplémentaire, 2) le temps passé à travailler avec (ils sont petits, mais il y en a) 3) jusqu'à ce que l'indice coïncide, la valeur du compteur est redondante, car elle coïncide avec la différence d'index, 4) dans le cas d'une taille de tampon de 256 éléments, le compteur doit être plus long que les indices et peut ne pas être de type natif, 5) il y a un autre inconvénient (presque fatal), mais plus à ce sujet plus tard. Comme mentionné ci-dessus, il est partiellement possible d'atténuer ces lacunes en organisant non pas un compteur, mais un indicateur complet, mais il existe une solution bien meilleure.

Nous devons simplement éviter une situation où les indices peuvent coïncider après l'enregistrement suivant (le fait qu'ils peuvent coïncider après la lecture est évident), et pour cela, nous devons limiter le nombre possible d'éléments dans le tampon à 1 de moins que possible. Voici sa mise en œuvre:

 #define NeedOverflowControl YES typedef uint8_t Data_t; static Data_t BufferData[Max]; static Counter_t BufferWriteCounter=0, BufferReadCounter=BufferWriteCounter; void BufferWrite(const data_t Data) { BufferData[BuffWriteCounter] = Data; register counter_t Tmp = NextCount(BufferWriteCounter); #if (NeedOverflowControl == YES) if (Tmp == BufferReadCounter) {BufferOverflow();} else #endif { BufferWriteCounter = Tmp; } }; 

Il y a une légère inexactitude dans la fonction précédente, je propose de la trouver et de la corriger par moi-même, bien que ... toujours là, mais nous allons continuer:

  inline int BufferIsEmpty(void) { return ( BufferReadCounter == BufferWriteCounter ); }; inline int BufferIsFull(void) { return ( BufferReadCounter == NextCounter(BufferWriteCounter) ); }; #define DataSizeIsSmaller (sizeof(data_t) < sizeof(counter_t)) data_t BufferRead(void) { #if DataSizeIsSmaller register data_t Tmp = BufferData[BufferReadCounter]; #else register counter_t Tmp = BufferReadCounter; #endif BufferReadCounter = NextCount(BufferReadCounter); #if DataSizeIsSmaller return Tmp; #else return BufferData[Tmp]; #endif }; 

Prenons attention à la situation dans laquelle nous avons appelé la procédure de traitement de débordement (si nous définissons l'indicateur pour le besoin de traitement) - lorsque nous avons essayé d'écrire le dernier octet inoccupé du tampon, nous ne l'avons pas signalé en déplaçant l'index d'écriture, nous ne pourrons donc pas le lire - comme moi et averti, avec l'option d'implémentation sélectionnée, la capacité tampon est réduite de un. Notez également que nous mettons d'abord l'élément suivant dans la file d'attente, et ensuite seulement en informant en déplaçant l'index, l'ordre inverse pourrait entraîner des conséquences très désagréables.

Avant de regarder le code avec l'indicateur, parlons un peu de débordement - cela se produit lorsque nous ne pouvons pas mettre l'élément suivant dans le tampon, et nous avons différentes façons de résoudre le problème, parmi lesquelles il y en a de bonnes et ainsi de suite.

Tout d'abord, la méthode (correcte et bonne) numéro

1) pour éviter une situation similaire en principe en choisissant la taille de tampon correcte (il existe une sous-option de cette méthode - augmentez la taille du tampon si nécessaire, mais dans le monde de la programmation intégrée, elle n'a pas pris racine, et en fait, cela semble douteux - parfois nous avons dû augmenter la taille du tampon, où il y a une garantie que nous n'aurons pas à le faire encore et encore).
La méthode suivante (correcte, mais pire, bien que toujours bonne) numéro

2) pour signaler l'occurrence d'un débordement avec une valeur de retour et pour suspendre l'écriture dans le tampon - le soi-disant enregistrement de blocage, mais il n'est pas toujours implémenté.

Et voici deux façons mauvaises et mauvaises:

3) et 4) ignorer le problème et prétendre que tout va bien («sourire et vague»). Pourquoi sont-ils mauvais - parce que nous prétendons seulement que tout va bien, en fait, le principe de Dirichlet (le problème des cellules N et des oiseaux N + 1) ne peut pas être violé et nous perdons l'élément de données, et pourquoi y a-t-il deux façons? que nous pouvons

3) perdre le dernier élément de données enregistré et

4) perdre le premier des éléments non encore transférés.

Laquelle de ces méthodes est pire - «les deux sont pires», même si certaines d'entre elles peuvent être plus acceptables pour une tâche spécifique, mais le principal inconvénient est inamovible - nous sommes obligés de perdre des informations. Par conséquent, la méthode 3 est le plus souvent utilisée, car elle est plus facile à implémenter (pour cela, il suffit de laisser l'index d'enregistrement inchangé), ce que j'ai fait dans l'exemple précédent si le traitement de dépassement est vide.

Il y a une autre façon - ne contrôlez pas du tout la situation (dans notre exemple, commentez la ligne avec la définition, mais pas la ligne avec le contrôle réel), tandis que nous

5) perdrons tout le tampon rempli - à première vue, cela semble être le pire, car les pertes sont les plus importantes grande, en fait, ce n'est pas entièrement vrai, car toute perte de données est mauvaise, mais elle a un avantage certain - cette méthode est plus rapide, car le débordement ne contrôle pas du tout.

Une observation intéressante - une recherche rapide sur Internet n'a pas trouvé d'algorithme de récupération de données en cas de perte d'élément, contrairement au cas d'une distorsion d'élément, où les codes de blocs fonctionnent parfaitement.

L'option avec le drapeau de débordement, étonnamment, perd un peu de vitesse si elle est écrite correctement, mais perd néanmoins, et de mémoire, nous gagnons bien sûr un élément, mais nous devons allouer de l'espace pour le drapeau, de sorte que les économies sont en question . Nous n'envisagerons tout simplement pas l'option avec le compteur, car j'ai déjà énuméré 4 de ses défauts et il est temps de rappeler le cinquième, comme je l'ai promis, en plus du fatal. Dans l'implémentation précédemment proposée, les index ont les propriétés de MRSW (Multi-Reader Single-Writer) selon la classification de "The Art of Mulpiprocessor Programming" (je recommande fortement la lecture, un travail absolument incroyable), et dans le cas des opérations atomiques, le changement d'index (pour le type natif) ne nécessite pas aucun moyen de synchronisation.Un point nécessaire et très important - la synchronisation n'est pas seulement requise du point de vue de l'interaction de l'écriture et de la lecture, les deux fonctions ne sont en aucun cas réutilisables et peu sûres de ce point de vue, qui est important à retenir.

Mais le compteur aura la propriété MRMW, et sans synchronisation, vous ne pouvez tout simplement pas travailler avec, à partir du mot «complètement» (à moins, bien sûr, que votre objectif soit de créer un programme «soudainement bogué»). Si nous prenons en compte le fait que nous écrivons un module pour travailler avec des périphériques et, par conséquent, l'écriture ou la lecture peut être appelée à partir d'une interruption, alors le problème de synchronisation est absolument nécessaire à considérer. Fait intéressant, le drapeau, qui semble avoir des propriétés similaires, lui permet néanmoins de travailler avec lui sans outils de synchronisation (drôle, n'est-ce pas, mais il a une explication complètement scientifique - l'opération de changement devient atomique, et la logique du drapeau permet, et même impose, le chevauchement enregistrements), qui est illustré par le fragment suivant du programme.

Veuillez noter qu'une telle approche (un indicateur sans outils de synchronisation) n'est possible que si certaines conditions sont remplies, ce qui doit être soigneusement vérifié dans votre cas. Des détails peuvent être trouvés dans la littérature, je ne les donnerai pas, car je considère que cette méthode d'organisation du tampon n'est pas trop bonne, et je ne la cite que pour montrer que la solution la plus réussie ne peut pas être mise en œuvre proprement, ainsi que pour démontrer un autre concept que je considère très utile et que j'ai l'intention d'adhérer.

 typedef uint8_t data_t; static data_t BufferData[Max]; static counter_t BufferWriteCounter=0, BufferReadCounter=WriteCounter; static int8_t BufferHaveData = 0; void BufferWrite(const data_t Data) { if ((BufferWriteCounter == BufferReadCounter) && (BufferHaveDataFlag == 1)) {BufferOverflow();} else { BufferData[BufferWriteCounter] = Data; BufferHaveDataFlag = 1; BufferWriteCounter = NextCounter(BufferWriteCounter); }; }; inline int BufferIsEmpty(void) { return ((BufferReadCounter==BufferWriteCounter) && (BufferHaveDataFlag == 0));}; data_t BufferRead(void) { register counter_t Tmp; Tmp = BufferReadCounter; BufferReadCounter = NextCount(BufferReadCounter); if (BufferReadCount == BufferWriteCounter) { BufferHaveDataFlag = 1; }; return BufferData[Tmp]; }; 

Notons à nouveau que dans la procédure d'écriture, nous définissons d'abord l'indicateur, puis modifions l'index, et dans la procédure de lecture, nous vérifions d'abord les index, puis contrôlons l'indicateur, ce qui nous évite à nouveau des problèmes et chevauche en quelque sorte la gestion des ressources pour éliminer le blocage mutuel .

De manière générale, ce fragment doit être réécrit dans le bon style (à l'exception des constantes magiques 0 et 1, si vous pensez que ce ne sont pas des constantes magiques, alors vous vous trompez), et si vous l'utilisez, faites-le, je cache le corrigé code dans le spoiler, non pas parce que je suis gêné, mais afin de ne pas inciter à un autre cycle de la guerre sainte (sans signification et sans pitié), haineux des transferts, vous ne devriez pas ouvrir ce bouton,


Fait intéressant, le code de cette approche sera exactement le même que pour les constantes directes 0 et 1, mais tout est extrêmement transparent et clair et ne laisse aucune place à l'interprétation. Je suis d'accord à l'avance que l'exemple semble farfelu et si seules les fonctions de travail sont sorties avec le drapeau, à l'intérieur, vous pouvez utiliser complètement les constantes 0 et 1. Tout cela est vrai, la seule chose sur laquelle j'insiste est précisément ce comportement du drapeau, vous pouvez appeler BufferFullFlag et changer la logique de travail avec, mais en aucun cas devrait être appelé BufferIsNotEmptyFlag avec ce qui suit il effectue un mystérieux opérations logiques. J'insiste à nouveau sur le fait que le principe KISS a démontré à plusieurs reprises sa fidélité inconditionnelle et, si nous voulons savoir si le tampon est vide, nous devons l'écrire directement dans le programme et ne pas poser la question «est-il incomplet».

Dans tous les cas, je ne pense pas que l'implémentation avec l'indicateur soit bonne, donc je recommande fortement de se réconcilier avec le tampon qui n'est pas pleinement utilisé et d'accepter l'implémentation avec deux index et sans champs supplémentaires.

En fait, un article d'une ampleur inattendue s'est avéré pour un sujet aussi simple, j'ai pensé à écrire davantage sur la synchronisation et les sections critiques, mais c'est la prochaine fois.

PS Et en conclusion, qu'est-ce que je n'ai pas aimé exactement dans la bibliothèque mentionnée, mais en même temps, les auteurs du RTOS domestique ont pris cela dans leur code sans le moindre doute:

1. Deux implémentations du tampon sont données - une pour la taille de la puissance de deux (j'espère avoir montré que cela est complètement inutile), et la seconde pour les cas restants, mais vous devrez choisir la version avec des stylos, bien sûr, ils ne feront pas d'erreur, il y a des contrôles partout.
2. Des méthodes complètement inutiles ont été créées, telles que la suppression du dernier élément ou l'accès direct à l'élément tampon.
3. Le tampon de données est aligné sur un entier.
4. Dans la mise en œuvre du degré 2, une erreur de vérification du taux d'occupation.
5. Dans la mise en œuvre d'une taille arbitraire, un compteur
6. Les sections critiques ne sont pas du tout organisées, ce qui dans la bonne mise en œuvre (avec deux indices) n'est tout simplement pas nécessaire, mais on ne peut pas s'en passer, l'utilisation d'opérations atomiques à la place n'est clairement pas suffisante.
7. Une certaine négligence de style, genre de lignes
   
   

    return ((_writeCount - Atomic::Fetch(&_readCount)) & (size_type)~(_mask)) != 0; 

   
   en particulier sa seconde moitié - c'est exactement ce que C est blâmé, et le langage lui-même n'est pas à blâmer, il vous permet seulement d'écrire ceci au lieu du plus compréhensible
   
   

    size_type(~(_mask)) 

   
   mais sans le forcer à le faire.

PPS J'espère que l'auteur de la bibliothèque accepte de considérer cette critique comme constructive et apportera les corrections appropriées.