A la cuesti贸n de los tampones (anillo)

"Si encuentra que los costos de desarrollo de la arquitectura son excesivos, considere cu谩nto puede costarle la arquitectura incorrecta"


- No puedo recordar exactamente la fuente

Una vez, "hace mucho tiempo, en una galaxia distante", compr茅 el maravilloso libro de Charles Weatherly "Etudes for Programmers", en la introducci贸n a la cual el autor confirm贸 la necesidad de estudiar ejemplos educativos y tareas antes de comenzar una programaci贸n independiente. Le recomiendo que encuentre este libro, lea el prefacio (y sin detenerse en 茅l, lea el resto y resuelva los problemas que contiene), ya que no puedo justificar mejor la necesidad de tal pr谩ctica. Incluso si sigue mi recomendaci贸n y adquiere muchos conocimientos y habilidades pr谩cticas al leer el libro, puede regresar y leer esta publicaci贸n, ya que est谩 dedicada a varios otros temas. Y si no sigues mis recomendaciones, tanto m谩s debes ir debajo del gato.

No hace mucho tiempo, en una publicaci贸n en la que lo rega帽茅, expres茅 mi opini贸n sobre un RTOS dom茅stico, mencion茅 que la implementaci贸n del b煤fer de anillo en la conocida biblioteca mcucpp (y en ciertos aspectos, absolutamente maravillosa) no puede considerarse ideal. Tratar茅 de explicar mi punto de vista e imaginar la implementaci贸n ideal (en la medida de lo posible en el mundo real). Nota: el texto ofrecido a su atenci贸n estuvo en "inacabado" durante bastante tiempo, y luego apareci贸 un caso tan conveniente.

Continuamos desarrollando una biblioteca para trabajar con un dispositivo perif茅rico, y somos los siguientes en la l铆nea de gesti贸n de memoria y almacenamiento en b煤fer (s铆, todav铆a continuamos las operaciones preparatorias, pero sin ellas de ninguna manera). 驴De d贸nde viene la necesidad de organizar amortiguadores y qu茅 tipo de animal es? El hecho es que una parte importante de la periferia tiene una velocidad limitada y el proceso de transmisi贸n, que se inicia de una forma u otra, lleva un tiempo determinado, y a veces muy significativo, en comparaci贸n con la creaci贸n de otra porci贸n de informaci贸n para la transmisi贸n. Por supuesto, antes de que este tiempo haya pasado, la siguiente transmisi贸n no se puede realizar y, en consecuencia, no se puede iniciar.

Tenemos un caso cl谩sico de un par escritor-lector con diferentes velocidades. Es simplemente imposible resolver este problema de manera general, ya que "con un exceso arbitrariamente peque帽o, pero no cero, del flujo de solicitudes sobre el flujo de servicio, el tama帽o de la cola tiende al infinito", y el infinito es fundamentalmente imposible. Pero un caso especial del problema, cuando tenemos r谩fagas locales de solicitudes, pero en promedio el flujo de servicio puede hacer frente a la carga, se puede resolver una memoria intermedia de capacidad suficiente. Prestemos atenci贸n a la frase "capacidad suficiente", luego aprenderemos c贸mo calcularla, siempre y cuando el hecho de que esto sea fundamentalmente posible sea suficiente para nosotros.

Por supuesto, si la memoria intermedia es un requisito absoluto, no lo es. Para la informaci贸n transmitida, puede usar un registro de bloqueo, pero con la informaci贸n recibida es algo peor, tendr谩 que agregarse en alg煤n lugar antes del procesamiento, si no toma las medidas apropiadas en el protocolo de nivel superior (la expresi贸n m谩gica xon / xoff no naci贸 desde cero), lo que no siempre es posible y, en cualquier caso, generalmente conduce a una limitaci贸n significativa de la velocidad de transmisi贸n. Tambi茅n hay una implementaci贸n de hardware de memorias intermedias internas en dispositivos perif茅ricos (al menos para un elemento), pero esto no siempre se hace y el tama帽o de la memoria intermedia est谩 estrictamente limitado desde arriba.

Por lo tanto, a煤n implementaremos el b煤fer de programa, para lo cual ser铆a natural usar el m茅todo FIFO (es decir, la cola) para organizar dicho b煤fer, y la cola, a su vez, se implementa mejor en un b煤fer en anillo con dos punteros. Cuando escribo "mejor", esto no significa en absoluto que otras implementaciones (por ejemplo, una cola de referencia) sean imposibles o tengan fallas fatales que no sean fatales. Esta expresi贸n solo significa que la implementaci贸n no ser谩 demasiado complicada y bastante efectiva, aunque otros pueden tener ventajas innegables sobre ella, por lo que tendr谩n que pagar por algo, porque DarZaNeBy.

Dado que es muy poco probable que su modelo MK tenga una implementaci贸n de hardware de un dispositivo de uso tan general (los m贸dulos perif茅ricos individuales pueden tener sus propios buffers de anillo, pero no tienen nada que ver con el tema de esta publicaci贸n), tendremos que crear un buffer de anillo en la memoria lineal (implementar en vector, este es, de hecho, el 煤nico objeto natural en la memoria direccionable), y para esto, se requerir谩 un 铆ndice de b煤fer (o tal vez incluso dos 铆ndices, pero m谩s sobre eso m谩s adelante). En mi opini贸n, un b煤fer circular con dos punteros (铆ndices) es la 煤nica forma aceptable de implementar una cola en un vector, pero hay diferentes puntos de vista sobre este tema y vi con mis propios ojos una implementaci贸n en el estilo de "x1 = x2; x2 = x3; ... x8 = nuevo s铆mbolo ", si quieres, no lo considerar茅 tan ex贸tico. El hecho de que el fragmento dado pueda tener derecho a existir en una situaci贸n espec铆fica y muy limitada no lo hace aceptable en general.

Consideraremos la implementaci贸n correcta del m贸dulo del programa para organizar el puntero y, para comenzar, prestaremos atenci贸n a la primera palabra en la definici贸n. La diferencia entre un c贸digo correcto y uno incorrecto no es solo porque el c贸digo correcto no contiene errores, aunque este es un requisito absoluto. Incluso el c贸digo que realiza completamente sus funciones puede ser incorrecto si es incomprensible, o si hay una opci贸n que no es menos clara, pero se ejecuta m谩s r谩pido o se ejecuta tan r谩pido, pero m谩s claramente escrito, por lo que el concepto de correcci贸n es algo relativo. Continuamos considerando nuestro ejemplo de implementaci贸n de b煤fer, que nos permitir谩 demostrar la diferencia entre diferentes grados de correcci贸n.

Antes de pasar a la esencia, un punto importante sobre la discusi贸n adicional. Quiero decir que su compilador siempre est谩 activado en un nivel de optimizaci贸n diferente de cero (-O2), por lo que no tenemos que pensar en mejoras menores como 1) modificaci贸n del prefijo versus postfix, o 2) usar los resultados de la operaci贸n anterior, o 3) la diferencia entre el incremento y la suma unidades, etc., suponemos que el compilador har谩 mucho por nosotros. Por supuesto, esto no es una suposici贸n estricta, pero de lo contrario tendremos que sumergirnos en las entra帽as del ensamblador, que en nuestro tiempo no es la corriente principal.

Perm铆tame recordarle que se nos indic贸 que implementemos el 铆ndice (puntero) del b煤fer en anillo, es decir, necesitamos crear el comportamiento de una variable que se ejecuta secuencialmente a trav茅s de una serie de valores, desde algunos iniciales hasta otros finales . Suponga de inmediato que el valor inicial ser谩 cero, de lo contrario tendremos que escribir un c贸digo m谩s o menos correcto, y esto contradice los objetivos educativos y no tenemos prisa, y el 煤ltimo es Max.

Este comportamiento de la variable se puede implementar utilizando la siguiente construcci贸n:

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

y es precisamente ese c贸digo el que podemos ver en muchos (es decir, muy a menudo) casos. Lo que est谩 mal: bueno, en primer lugar, durante alg煤n tiempo (desde la realizaci贸n de la operaci贸n de incremento hasta la asignaci贸n del resultado) nuestra variable ser谩 mayor que el valor m谩ximo permitido y, si en ese momento se produce una interrupci贸n que debe tener en cuenta el valor de esta variable, entonces predigo personalmente No presumo los resultados. Por lo tanto, reescribimos el programa:

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

Hemos eliminado un error, y el c贸digo (en adelante me referir茅 al c贸digo "c贸digo" significa que el c贸digo ejecutable generado por el compilador) no se ha alargado y ya no se ejecuta (de hecho, se ejecuta m谩s r谩pido, sino solo porque en la primera versi贸n la palabra vol谩til se usa completamente redundante en este caso), y no se ha vuelto menos clara (m谩s bien, a煤n m谩s clara, pero esto es cuesti贸n de gustos).

Nota necesaria sobre vol谩til: esta directiva es necesaria si queremos evitar la optimizaci贸n del c贸digo que conduce a una ejecuci贸n incorrecta, y en este caso particular (cuando el valor de la variable no cambia fuera del alcance del m贸dulo y no hay entradas secuenciales en 茅l) (directiva ) completamente redundante. Le recomiendo que mire el c贸digo generado para ambas opciones en godbolt.org. Por qu茅 no debe abusar de la directiva vol谩til, a diferencia de la palabra clave est谩tica, que se recomienda utilizar siempre que sea posible. Bueno, en primer lugar, prohibimos la optimizaci贸n, es decir, el c贸digo definitivamente no ser谩 m谩s r谩pido (lo m谩s probable es que se haga m谩s grande y m谩s lento, pero preferimos formulaciones estrictas). Y en segundo lugar, en este caso particular, esta palabra es enga帽osa, ya que en relaci贸n con nuestro programa, el valor del contador no puede cambiar de ninguna manera fuera de nuestro control. En un programa que lee su valor, es decir, en la implementaci贸n del b煤fer en anillo, puede considerar el contador como mutable fuera del m贸dulo, y all铆 es cuestionable, por lo tanto, este atributo simplemente no es aplicable al contador. Si una variable se debe interpretar de manera diferente en diferentes m贸dulos, nuestros servicios se deben combinar, si estamos hablando de organizar una secci贸n cr铆tica, por ejemplo, al implementar una transacci贸n u operaciones at贸micas, entonces esta directiva no da nada en absoluto.

Volvemos al c贸digo y vemos que el programa todav铆a est谩 mal, lo que pasa, y el hecho es que no es lo que necesitamos (ver la descripci贸n de la tarea), sino algo m谩s (calcula el resto de la divisi贸n), solo los resultados emparejar Bueno, creemos que s铆 (no lo creo, pero los autores del c贸digo ciertamente), que los resultados coinciden, de hecho, en el caso general, no coinciden, solo tuvimos suerte con el rango de la variable (valores positivos). Adem谩s, el proceso de ejecuci贸n del c贸digo es m谩s largo de lo que podr铆a hacerse, ya que en el mejor de los casos tenemos la operaci贸n de divisi贸n de enteros (si es parte de los comandos de nuestra arquitectura), y no se realiza de ninguna manera en un ciclo de procesador (un valor caracter铆stico de 10 ciclos para arquitectura de 8 bits), y en el peor de los casos, veremos la llamada al procedimiento de divisi贸n desde la biblioteca est谩ndar (y bueno, si es una divisi贸n corta), el tiempo de ejecuci贸n ser谩 de decenas de ciclos de reloj.

Entonces, 驴por qu茅 todav铆a es posible encontrar un enfoque tan completamente equivocado tan a menudo? Aqu铆, desde la audiencia, me dicen que con el valor de Max + 1, que es una potencia de dos, el compilador adivinar谩 en lugar de la operaci贸n de divisi贸n, colocar谩 la operaci贸n de multiplicaci贸n bit a bit en la m谩scara correspondiente (igual a Max), que se realizar谩 muy r谩pidamente y todo estar谩 bien.

Estoy de acuerdo con esta declaraci贸n y adopto este enfoque, si no fuera por las siguientes circunstancias:

  • esto solo es posible para Mach est谩ticamente definido en la etapa de compilaci贸n,
  • esto solo sucede cuando la optimizaci贸n est谩 habilitada,
  • esto solo sucede cuando Mach cumple esta condici贸n,
  • Esto no ocurre para todos los tipos cardinales.

Adem谩s, es en este caso particular (cuando la variable se define como un signo), adem谩s del comando de multiplicar (l贸gico) por la m谩scara, se generar谩 un comando de comparaci贸n con cero y una rama para valores negativos, y aunque esta rama nunca ser谩 para nuestro rango se ejecutar谩, ocupar谩 espacio en la memoria (y en el caso de una funci贸n sustituible, tomar谩 varias veces) y llevar谩 tiempo realizar la operaci贸n de comparaci贸n, si no lo cree, nuevamente vamos al sitio especificado y lo veremos por usted mismo. Otro argumento a favor de los cardenales sin firmar, al que recientemente dediqu茅 una publicaci贸n completa.

Por lo tanto, si queremos usar la multiplicaci贸n l贸gica con una m谩scara (obtenida al optimizar el c谩lculo del resto), entonces deber铆amos reescribir el m贸dulo en consecuencia:

 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 }; 

En esta versi贸n, todo es completamente claro y controlable y todo es cierto (aunque persisten algunas deficiencias, pero ahora son obvias y no est谩n enmascaradas), por lo tanto, es correcto, aunque es m谩s correcto y ahora las buscaremos. El principal inconveniente, en mi opini贸n, es una violaci贸n del principio KISS, ya que el uso de la operaci贸n restante por divisi贸n descuida completamente este principio. Por lo tanto, ahora destruiremos todas las deficiencias de un solo golpe (no te preocupes por su destino, renacer谩n 100,500 veces, porque no todos los programadores de Arduino leen mis publicaciones).

Pero primero, una ligera desviaci贸n hacia un lado. 驴C贸mo podemos implementar una verificaci贸n de la potencia de dos (un n煤mero binario se puede representar como {0} 1 {0}) que acabamos de usar

no espiar
#define IS_POWER2 (N) ((((((N) - 1) & (N)) == 0)

驴Y c贸mo podemos implementar la verificaci贸n de que un n煤mero es una secuencia correcta de unidades {0} 1 {1} en notaci贸n binaria? Una opci贸n es obvia

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

y el segundo es trivial

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

Nota: no puedo evitar recordar el magn铆fico teorema: "Un n煤mero trascendental en un grado trascendental siempre es trascendental, a menos que lo contrario sea obvio o trivial".

驴Y c贸mo podemos verificar que un n煤mero sea una secuencia de unidades {0} 1 {1} {0}

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

Y finalmente, c贸mo seleccionar el n煤mero menos significativo de un n煤mero (no s茅 por qu茅 esto podr铆a ser necesario, pero ser谩 煤til)

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


Pero se le ocurri贸 lo que puede ser 煤til
 #define IsRightSequence(N) (IsSequence(N) && (LowerBit(N) == 1)) 

Una observaci贸n curiosa: estas macros no son del todo correctas, resulta que 0 es una potencia de dos y una secuencia correcta (por supuesto, una secuencia tambi茅n), lo cual es un poco extra帽o. Pero 1 es todos estos objetos con bastante raz贸n, por lo que parece que cero solo debe considerarse por separado. Otra propiedad interesante de estas macros es que no hacemos suposiciones sobre la longitud del argumento, es decir, funcionan correctamente con cualquier tipo cardinal.

Hay un libro maravilloso, Trucos para programadores, donde puede encontrar las macros mencionadas y muchas otras tareas igualmente divertidas e instructivas, le recomiendo leerlo, especialmente porque no contiene demasiadas letras.

Pero volvamos a nuestro 铆ndice de b煤fer en anillo. Dimos la soluci贸n correcta, pero prometimos a煤n m谩s correctamente, lo que significa que nuestra 煤ltima soluci贸n tiene fallas (qui茅n lo dudar铆a). Uno de ellos, la longitud del b煤fer debe determinarse est谩ticamente en la etapa de compilaci贸n, el segundo, en caso de una longitud fallida, el tiempo de ejecuci贸n es muy largo y todav铆a hay un cierto n煤mero de errores en una parte relativamente peque帽a del programa, lo que nos hace recordar un chiste sobre 4 errores al escribir la palabra "m谩s". Los eliminaremos a todos (algunos se dejar谩n para m谩s adelante) e inmediatamente, para lo cual, finalmente, escribiremos la soluci贸n al problema original como es:

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

(Como ya entendi贸, soy partidario de los corchetes egipcios y no hay nada que hacer al respecto).

Prestemos atenci贸n al hecho de que simplemente reescribimos la condici贸n del problema desde un lenguaje natural en el lenguaje de programaci贸n elegido, por lo que resulta extremadamente claro y comprensible. 驴Es posible mejorarlo? Sin duda, pero solo desde el punto de vista de la velocidad del c贸digo, ya que simplemente no hay otras deficiencias para esta soluci贸n (no hay deficiencias obvias, de hecho existen y las eliminaremos con 茅xito).

Evaluemos la complejidad computacional de esta soluci贸n: suma con unidad (1) y comparaci贸n (2) siempre, luego asignando cero (1) (raramente) o sumando (1) (casi siempre), lo que da 1 + 2 + 1 + 螖 ~ 4 elemental operaciones y memoria cero. Es posible que un buen compilador en el modo correcto haga ciertas optimizaciones y reduzca el tiempo de ejecuci贸n del c贸digo, pero es mejor que lo hagamos expl铆citamente. Aqu铆 est谩 la siguiente opci贸n:

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

Evaluamos la complejidad - suma y comparaci贸n siempre, asignando cero (raramente) - aproximadamente 3 operaciones y un elemento de memoria. De hecho, la versi贸n anterior tambi茅n ten铆a un elemento de memoria (impl铆cito), por lo que tenemos una ganancia neta en una operaci贸n elemental. Adem谩s, la versi贸n anterior ten铆a dos inconvenientes m谩s: 1) viol贸 el principio DRY (calcul贸 el aumento en uno dos veces) y 2) tuvo m谩s de un punto de salida, lo que no es bueno. Tampoco perdimos la comprensi贸n, es decir, logramos matar a un mont贸n de conejos de un disparo, y tampoco gastamos ning煤n cartucho, es solo una historia al estilo del Bar贸n Munchausen.

Tenga en cuenta que no if ( (Tmp = Counter + 1) > Max) construcci贸n if ( (Tmp = Counter + 1) > Max) , aunque contiene una instrucci贸n expl铆cita para el compilador para tratar de no hacer transferencias redundantes. Esto es aromatizante en la forma m谩s flagrante, simplemente no me gusta el valor devuelto por el operador de asignaci贸n e intento evitar usarlo. No puedo explicar la raz贸n de este fuerte sentimiento, seg煤n Freud, es muy probable que sea un trauma psicol贸gico en la infancia. Los compiladores modernos son bastante capaces de llevar a cabo una optimizaci贸n simple por s铆 mismos, y adem谩s, tambi茅n agregu茅 un calificador de registro, por lo que el c贸digo de mi versi贸n y el correcto (desde el punto de vista del lenguaje C) coincidir谩n. Sin embargo, no limito en absoluto su libertad para usar el m茅todo que le parezca preferible.

Continuamos mejorando, porque no hay l铆mite para la perfecci贸n y todav铆a no la hemos alcanzado. Para lograrlo, reformulamos un poco el problema original y dejamos solo que el requisito de la variable est茅 en el rango de valores, sin indicar la direcci贸n del cambio. Este enfoque le permite reescribir el programa de la siguiente manera

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

A primera vista, nada ha cambiado mucho, pero, sin embargo, obtenemos una ganancia en el tiempo. Por supuesto, no debido al hecho de que la operaci贸n de disminuir por uno funciona m谩s r谩pido que la operaci贸n de aumentar por 茅l (aunque escuch茅 una versi贸n similar), sino debido a las peculiaridades de la comparaci贸n. Si en las versiones anteriores consideraba la comparaci贸n como 2 operaciones elementales (primero restamos y luego tomamos una decisi贸n), entonces en este caso el resultado de la operaci贸n anterior se usa para tomar una decisi贸n directamente y la comparaci贸n toma una operaci贸n elemental, lo que lleva a dos operaciones siempre y una asignaci贸n (raramente) y guardamos una operaci贸n (sin perder nada), como dice el refr谩n, "un poco, pero agradable". 驴Es la soluci贸n resultante ideal? Desafortunadamente, no. Es ligeramente inferior a la soluci贸n con una m谩scara (que requiere exactamente 2 operaciones elementales) en t茅rminos de velocidad y este es quiz谩s su 煤nico inconveniente.

Existe una soluci贸n a煤n m谩s r谩pida: simplemente aumente (disminuya) el valor del contador y no haga nada m谩s, pero solo es posible en el caso en que el valor m谩ximo coincida con el valor m谩s representativo en el tipo aceptado. Para un contador de 8 bits (es decir, como uint8_t), ser谩 255, luego escribimos Counter = Counter + 1 y conf铆o en que escribir Counter + = 1 o ++ Counter es completamente opcional, aunque muchos son y escribir谩n y tendr谩n toda la raz贸n. Si no consideramos seriamente la versi贸n sobre la necesidad de guardar caracteres (ya que la primera opci贸n es la m谩s larga), entonces esto no tiene sentido, al menos si estamos escribiendo un programa para arquitectura ARM o AVR (para otros que simplemente no verifiqu茅, sospecho que el resultado ser谩 lo mismo) bajo el compilador GCC (el autor entiende que est谩 escribiendo el programa en el editor del entorno de programaci贸n integrado, esto es solo una revoluci贸n del habla del pasado cuando las computadoras eran grandes y la memoria peque帽a), y con la optimizaci贸n activada en cualquier nivel, porque El c贸digo dado ser谩 absolutamente id茅ntico.

Los compiladores modernos son muy, muy avanzados en t茅rminos de optimizaci贸n y generan un c贸digo realmente muy bueno, por supuesto, si ha habilitado el modo correspondiente. Aunque estoy dispuesto a aceptar que tales construcciones de lenguaje no hacen da帽o y pueden ser 煤tiles bajo ciertas condiciones, lo 煤nico que noto es que las expresiones de Counter ++ (en este caso particular, por supuesto) deben evitarse sin ambig眉edad, ya que est谩 destinado a situaciones completamente diferentes y puede dar lugar a c贸digo m谩s lento, aunque opcional.

Otra pregunta es que un b煤fer de 256 elementos no siempre es aceptable, pero si tiene suficiente memoria, 驴por qu茅 no? Con esta implementaci贸n, si puede alinear el b煤fer con el borde de la p谩gina, entonces el acceso a los elementos se puede hacer muy r谩pido al eliminar la operaci贸n de cambiar de 铆ndice a 铆ndice (la palabra clave de uni贸n le indicar谩 la implementaci贸n de dicha funci贸n, no la traer茅 para no aprender malo), pero esta es una decisi贸n muy, muy espec铆fica con un fuerte apego a la arquitectura, que est谩 peligrosamente cerca de trucos en el peor sentido de la palabra, y este no es nuestro estilo.

Por supuesto, nadie nos proh铆be escribir un contenedor que llame a este o aquel m茅todo dependiendo del valor de los valores de contador m谩ximos (y m铆nimos, ya que muchos m茅todos simplemente no funcionan con un m铆nimo distinto de cero), ya he propuesto los principios b谩sicos de tal soluci贸n, por lo que Vamos a ofrecer esto como un ejercicio.

En resumen, para resumir, reuniremos diferentes implementaciones de trabajo con un 铆ndice de anillo y evaluaremos sus propiedades.
M茅todoVersatilidadPlazo de entrega
0 (1)1
卤%1 (7)2
+ si3 (cualquiera)3.x
- si3 (cualquiera)2.x

La segunda l铆nea entre par茅ntesis muestra el n煤mero de valores de tama帽o del b煤fer (no superior a 256) para los que esta implementaci贸n est谩 disponible, pero queremos decir que un b煤fer de tama帽o 0 no nos interesa.

Como puede ver en esta tabla, DarZaNeBy (mi expresi贸n favorita, como puede haber notado), y las ventajas se compran a costa de desventajas, lo 煤nico que se puede afirmar inequ铆vocamente es que el incremento con la verificaci贸n tiene un competidor m谩s exitoso en forma de disminuci贸n con verificaci贸n y no pasa a la siguiente ronda bajo ninguna circunstancia

Una nota necesaria: hay lenguajes de programaci贸n en los que no tendr铆amos que pensar en la implementaci贸n del 铆ndice, sino que simplemente podr铆amos usar el tipo de intervalo. Desafortunadamente, no puedo considerar 贸ptima la implementaci贸n de estas construcciones en el c贸digo, ya que estas construcciones (y estos lenguajes) no est谩n destinados a la optimizaci贸n en tiempo de ejecuci贸n, pero es una pena.

Entonces, hicimos el m贸dulo correcto (qu茅 nombre tan fuerte para la funci贸n en l铆nea) para trabajar con el 铆ndice, y ahora estamos listos para comenzar a implementar el b煤fer en anillo.

Y para empezar, debemos decidir qu茅 queremos exactamente de este objeto de programa. Es absolutamente necesario poder colocar un elemento de datos en un b煤fer y extraerlo: dos m茅todos principales, una especie de captador y definidor. Es te贸ricamente posible imaginar un b煤fer sin uno de estos m茅todos, o incluso sin ambos (se puede imaginar poco te贸ricamente), pero el valor pr谩ctico de tal implementaci贸n es una gran pregunta. La siguiente funcionalidad necesaria, verificar la informaci贸n, se puede implementar como un m茅todo separado o como un valor especial (o atributo) devuelto por la lectura. Por lo general, prefieren el primer m茅todo, ya que resulta m谩s comprensible y no demasiado caro.
Pero verificar que el b煤fer est茅 completo ya es una gran pregunta: esta operaci贸n requerir谩 tiempo adicional, que siempre se dedicar谩 a la grabaci贸n, aunque nadie nos obliga a usarlo, as铆 que d茅jelo. No necesitamos nada m谩s del b煤fer, recordemos esta frase para el futuro.

Volver a la implementaci贸n. Necesitamos un lugar para almacenar los elementos de la cola y dos 铆ndices: uno para escribir en el b煤fer y otro para leerlo. C贸mo exactamente obtendremos este lugar (y estos indicadores) es un tema para una discusi贸n por separado, por ahora dejamos este momento fuera de par茅ntesis y creemos que simplemente los tenemos. Algunos (incluidos los autores del libro "Programaci贸n para matem谩ticos", que respeto, recomiendo leerlo) tambi茅n usan el contador de lugares rellenos, pero no haremos esto e intentar茅 mostrar por qu茅 esto es malo.

Primero, sobre los 铆ndices: notamos de inmediato que estos son 铆ndices, no indicadores, aunque a veces me permit铆 llamarme as铆. ( ), ( )- , , , . ( 256 ), , , ( , 8 , , 4- ), , , ( , ).

, 51 ( ) 2 ( ) 3 ( ), , , . , , GCC x51, AVR .

Adem谩s, muchos trucos que aumentan la velocidad para obtener el siguiente valor no estar谩n disponibles al usar el puntero. Y si tambi茅n tiene en cuenta la opini贸n de que los punteros son m谩s dif铆ciles de entender (no es que esta opini贸n me pareciera correcta, pero existe), entonces la elecci贸n es clara: 铆ndices.

Pero, 驴qu茅 deben mostrar exactamente los 铆ndices? Aqu铆, el alcance de la imaginaci贸n es ilimitado dentro del tama帽o del b煤fer Max (e incluso m谩s que eso), pero un conjunto muy peque帽o de opciones tiene un significado pr谩ctico. Para el 铆ndice de grabaci贸n, hay dos posibilidades: 1) indicar el lugar donde se grab贸 el 煤ltimo elemento y 2) indicar el lugar donde se grabar谩 el siguiente elemento. Dado que inmediatamente despu茅s de crear la cola, la primera opci贸n parece un poco extra帽a, luego elegimos la segunda, especialmente porque esto nos promete una ganancia tangible en el futuro. Para el 铆ndice de lectura, asumimos de inmediato que apunta al elemento que se leer谩 la pr贸xima vez que se lea. Inmediatamente hay un criterio simple (en el sentido de verificaci贸n) de que la cola no est谩 vac铆a: los 铆ndices no son iguales. Pero surge el segundo problema: si ponemos en cola exactamente los elementos de Mach,entonces los 铆ndices coincidir谩n y no podremos distinguir esta situaci贸n de una cola vac铆a.

(芦, 禄) , . 鈥 1) , 2) ( , ) 3) , , 4) 256 , 5) ( ), . , , , , .

Solo necesitamos evitar una situaci贸n en la que los 铆ndices puedan coincidir despu茅s del pr贸ximo registro (el hecho de que puedan coincidir despu茅s de la lectura es obvio), y para esto necesitamos limitar el n煤mero posible de elementos en el b煤fer a 1 menos de lo posible. Aqu铆 est谩 su implementaci贸n:

 #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; } }; 

Hay una ligera incorrecci贸n en la funci贸n anterior, propongo encontrarla y arreglarla por mi cuenta, aunque ... todav铆a la hay, pero continuaremos:

  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 }; 

, ( ) 鈥 , , , 鈥 , . , , , .

, , 鈥 , , , .

, ( )

1) ( 鈥 , , 鈥 , , ).
(, , )

2) 鈥 , .

:

3) 4) , (芦 禄). 鈥 , , ( N N+1 ) , ?

3) ,

4) .

鈥 芦 禄, - , 鈥 . 3, ( ), , .

鈥 , ( , ),

5) 鈥 , , , , 鈥 , .

鈥 , , .

, , , , , , , , , , , . , 4 , , . MRSW (Multi-Reader Single-Writer) 芦The Art of Mulpiprocessor Programming禄 ( , ) ( ) . 鈥 , , .

MRMW , 芦禄 (, , 芦 禄 ). , , , , . , , , (, , 鈥 , , , ), .

, ( ) , . , , , , , , , .

 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]; }; 

, , , , , .

, ( 0 1, , , ), , , , , , ( ), , ,

-
 typedef (NoBufferHaveData= 0, BufferHaveData =1) BufferHave DataFlag_t; BufferHaveData_t BufferYaveDataFlag; inline void BufferHaveDataFlagSet(void) {BufferHaveDataFlag = NoBufferHaveData;}; inline void BufferHaveDataFlagClr(void) {BufferHaveDataFlag = BufferHaveData;}; inline int BufferHaveDataFlagIsSet(void) {return (int)(BufferHaveDataFlag == BufferHaveData);}; 


, , 0 1, . , , , 0 1. , , , , BufferFullFlag , BufferIsNotEmptyFlag . , KISS , , , , , 芦 禄.

, , .

, , .

PS , , :

  1. 鈥 (, , ), 鈥 , , , , .
  2. .
  3. .
  4. 2 .
  5. , ( ) , , .
  6. ,

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

    鈥 , , ,

     size_type(~(_mask)) 

    .

PPS , .

Source: https://habr.com/ru/post/438476/


All Articles