Reemplazo de colas en RTOS

12

Para la comunicación entre tareas o para compartir datos entre dos tareas de RTOS, utilizamos colas. Pero el problema con las colas es que son lentas ... Copian datos en Buffer, luego Mutex Handling y luego Data Transfer. Es irritantemente lento si tiene que transferir grandes datos. Otro problema es si varias tareas acceden a la misma cola. Luego, la imagen se vuelve así: - Primero espere para tener acceso a The Queue, luego a la cola del manejo interno de Mutex y luego a la transferencia de datos.

Esto aumenta la sobrecarga en el sistema. ¿Cuál podría ser el reemplazo eficiente de las colas?

(Supongo que esta pregunta es independiente de RTOS que usamos. La mayoría de los RTOS manejan las colas solo de esta manera)

Swanand
fuente
¿Qué quiere decir con una cola a la que acceden varias tareas? ¿Te refieres a publicar en la cola o leer desde la cola? Múltiples tareas deberían poder publicar en una cola con una sobrecarga mínima. El RTOS debe manejar el mutexing para que una publicación sea una operación atómica. Para el 99% de las tareas, debe tener un bucle que se encuentre en una cola y procese el mensaje. Una cola debe (generalmente) ser leída solo por una tarea. Probablemente necesite ver su diseño y cómo está usando las colas en lugar de reemplazarlas.
Erik
@Erik: ¡Lo siento! Estoy usando el mecanismo que mencionaste ... Quería decir algo más y escribí diferente ... ¡Lo editaré! ¡Gracias por señalar el error! ¡Estoy esperando el acceso a la cola en mi código!
Swanand

Respuestas:

7

Las colas operan de esa manera porque es un modelo de transacción seguro para la comunicación entre tareas. Corre el riesgo de corrupción de datos y / o problemas de propiedad en cualquier esquema menos estricto.

¿Está copiando los datos en un búfer en la memoria y luego pasa un puntero con los elementos de la cola o intenta pasar todos los datos en los elementos de la cola? Si no está pasando punteros, obtendrá un aumento en el rendimiento al hacerlo en lugar de pasar un byte a la vez a través de elementos de la cola.

AngryEE
fuente
2
Yo iba a decir lo mismo. Si solo pasa punteros a los datos en las colas, puede aumentar la velocidad, pero asegúrese de no terminar con dos hilos tratando de usar y cambiar los datos.
Kortuk
Como dijo @Kortuk, necesito "asegurarme de que no termines con dos hilos tratando de usar y cambiar los datos" ... Lo que significa un aumento en la sobrecarga ... ¡No quiero mucho procesamiento! :(
Swanand
Por lo tanto, no hay un reemplazo como tal para las colas ... ¡En lugar de Data Queue, necesito usar Pointer Queue!
Swanand
1
@Swanand si planifica su aplicación de modo que las colas sean solo unidireccionales (es decir, nunca lea la misma cola en dos tareas) y procese los datos almacenados en el puntero inmediatamente y luego libérelos, no debería tener problemas para compartir los datos. Habrá un aumento de los gastos generales, ya que es posible que tenga que crear múltiples colas para pasar datos de manera confiable de un lado a otro, pero este es el costo de hacer negocios en un entorno multitarea.
AngryEE
7

Una manera fácil es poner un puntero a los datos en la cola y consumir los datos usando el puntero.

Tenga en cuenta que está intercambiando seguridad por rendimiento de esta manera, ya que debe asegurarse de que:

  1. el búfer permanece válido hasta que el consumidor haya consumido los datos
  2. alguien desasigna el búfer

Si no está utilizando memoria asignada dinámicamente, no tiene que desasignarla, pero aún debe asegurarse de que el área de memoria no se reutilice antes de que se hayan consumido los datos.

Trygve Laugstøl
fuente
6

Se pueden implementar colas sin bloqueo para el caso de productor único / consumidor único, y a menudo puede diseñar su software para minimizar el número de colas de productor múltiple o consumidor múltiple.

Se puede construir una cola sin bloqueo de la siguiente manera: Asigne una matriz de los elementos que se van a comunicar, y también dos enteros, llámelos Head y Tail. Head es un índice en la matriz, donde se agregará el siguiente elemento. La cola es un índice en la matriz, donde el siguiente elemento está disponible para ser eliminado. La tarea del productor lee H y T para determinar si hay espacio para agregar un elemento; escribe el elemento en el índice H, luego actualiza H. Las tareas del consumidor leen H y T para determinar si hay datos disponibles, lee los datos del índice T, luego actualiza T. Básicamente es un búfer en anillo al que acceden dos tareas, y el El orden de las operaciones (insertar, luego actualizar H; eliminar, luego actualizar T) asegura que no se produzcan daños en los datos.

Si tiene una situación con múltiples productores y un solo consumidor, o un solo productor y múltiples consumidores, efectivamente tiene una limitación de recursos de algún tipo, y no tiene nada más que usar la sincronización, ya que es más probable que el limitador de rendimiento ser el único productor / consumidor que una sobrecarga del sistema operativo con el mecanismo de bloqueo.

Pero si tiene múltiples productores Y consumidores, vale la pena pasar el tiempo (en el espacio de diseño) para ver si no puede obtener un mecanismo de comunicación más coordinado; En un caso como este, serializar todo a través de una sola cola definitivamente hace que la eficiencia de la cola sea el determinante central del rendimiento.

JustJeff
fuente
1
Iba a hacer +1 en esto, pero eres incorrecto: es posible implementar colas sin bloqueo para múltiples lectores y escritores, son simplemente más complicadas. (mire el documento de Michael + Scott sobre Colas sin bloqueo google.com/search?q=michael%20scott%20queue )
Jason S
1
@Jason S: ¿el documento de Scott afirma específicamente el reingreso por las operaciones de inserción y extracción sin bloqueo? Si es así, si puede extraerlo y publicarlo, hágalo, sería un activo invaluable para muchos. El lector debe tener en cuenta que el documento citado hace uso de instrucciones especiales de la máquina, mientras que mi posición en la publicación anterior no asumía tales instrucciones.
JustJeff
1
Sí, el costo de los algoritmos sin bloqueo suele depender de CAS o instrucciones equivalentes. ¿Pero cómo entra en juego aquí el reencuentro? Tiene sentido para mutexes + estructuras de bloqueo, pero no para operaciones de estructura de datos.
Jason S
2

Se puede obtener una operación eficiente en una cola de un solo consumidor multiproductor sin bloqueo si la cola en sí contiene elementos que son lo suficientemente pequeños como para funcionar con una primitiva exclusiva de carga-tienda, comparación-intercambio o similar, y uno puede usar un valor reservado o valores reservados para ranuras de cola vacías. Al escribir en la cola, el escritor realiza un intercambio de comparación para intentar almacenar sus datos en el siguiente espacio vacío; Si eso falla, el escritor intenta el siguiente espacio. Aunque la cola mantiene un puntero a la siguiente ranura vacía, el valor del puntero es "asesor". Tenga en cuenta que si un sistema usa compare-exchange en lugar de load-store-exclusive, puede ser necesario tener una 'familia' de diferentes valores de 'ranura vacía'. De lo contrario, si entre el momento el escritor encuentra un espacio de cola vacío e intenta escribir en él, otro escritor escribe el espacio y el lector lo lee, el primer escritor sin saberlo pondría sus datos en un lugar donde el lector no lo vería. Este problema no ocurre en los sistemas que usan load-store-exclusive, ya que store-exclusive detectaría que los datos se habían escrito aunque se volvieran a escribir en el valor anterior.

Super gato
fuente
1

Puede acceder a las colas de manera más eficiente escribiendo en la parte superior de la cola Normalmente, la mayoría de los RTOS ofrecen el soporte de agregar al frente de la cola que no requiere la adquisición de mutex. Pero asegúrese de usar agregar al inicio de la cola lo más mínimo posible donde solo desea ejecutar los datos más rápido. Normalmente, las estructuras de cola tienen un límite de tamaño máximo, por lo que es posible que no coloque todos los datos en cola, por lo tanto, pasar el puntero siempre es fácil.

¡¡salud!!

Sai
fuente
1

Las colas no son inherentemente lentas. La implementación de ellos puede ser.

Si está copiando datos ciegamente y está usando una cola sincrónica, verá un impacto en el rendimiento.

Como otros carteles han indicado, existen alternativas sin bloqueo. El caso del productor único / consumidor único es sencillo; Para múltiples productores y consumidores, el algoritmo de cola sin bloqueo de Michael y Scott (esos son sus apellidos) es el estándar y se utiliza como base para el ConcurrentLinkedQueue de Java .

Es posible optimizar la necesidad de colas en ciertos casos, pero brindan garantías de concurrencia que generalmente brindan enormes beneficios de simplificación a los sistemas al permitirle desacoplar tareas.

Jason S
fuente
Del artículo de Michael & Scott: "es el algoritmo de elección claro para las máquinas que proporcionan una primitiva atómica universal (por ejemplo, comparar e intercambiar o cargar condicional vinculado / almacenar)". Si bien esto puede no bloquear exactamente un subproceso, hay una forma de sincronización aquí.
JustJeff
usted tiene un punto; puede disminuir el requisito de concurrencia del acceso exclusivo a una barrera de memoria.
Jason S