La implementación de una cola de prioridad con una condición variable en C

Question

Mi comprensión actual de las variables de condición es que todos (en espera) hilos bloqueados se insertan en una cola FIFO básica, el primer elemento de la cual se despierta cuando la señal () se llama.

¿Hay alguna manera de modificar esta cola (o crear una nueva estructura) para llevar a cabo como una cola de prioridad en su lugar? He estado pensando en ello durante un tiempo, pero la mayoría de las soluciones Tengo terminan siendo obstaculizado por la estructura de cola existente inherente a C.V. y de mutex.

Gracias!

Answer 1

Creo que debería replantearse lo que estás tratando de hacer. Si usted está tratando de optimizar su rendimiento, es probable que ladrando al árbol equivocado.

pthread_cond_signal() ni siquiera está garantizado para desbloquear exactamente un hilo - está garantizado para desbloquear al menos un hilo, por lo que su código mejor que sea capaz de manejar la situación en la que múltiples hilos se desbloquean simultáneamente. La forma típica de hacer esto es para cada hilo para volver a comprobar el estado desbloqueado después de convertirse, y, si es falso, regresar a la espera de nuevo.

Se puede aplicar algún tipo de esquema en el que usted guardó su propia cola de prioridad de subprocesos en espera, y cada hilo se sumó a esa cola inmediatamente antes de que iba a comenzar de espera, y luego hará la verificación de la cola cuando el desbloqueo, pero esto añadir un montón de complejidad y un gran potencial para los problemas graves (condiciones de carrera, bloqueos, etc.). También se añade una cantidad no trivial de los gastos generales.

Además, ¿qué ocurre si un hilo de mayor prioridad se inicia esperando una condición variable en el mismo momento que la variable de condición está siendo señalizada? A quién le da, el hilo de alta prioridad recién llegado o no bloqueada la antigua subproceso de prioridad más alta?

El orden en que los hilos quedan desbloqueadas en depende por completo de programador de subprocesos del núcleo, por lo que está a su merced. Ni siquiera asumiría FIFO pedido, ya sea.

Answer 2

Dado que las variables de condición son, básicamente, sólo una barrera y no tiene control sobre la cola de subprocesos en espera no hay forma real de aplicar las prioridades. Es válido para asumir los subprocesos en espera actuará de una manera FIFO.

Con una combinación de atómicas, variables de condición adicionales, y pre-conocimiento de los hilos / prioridades involucrado usted podría construir una solución en la que un hilo señalado volverá a señalizar el CV maestro y luego volver a bloque en un CV prioridad pero ciertamente no sería una solución genérica. Eso es también la parte superior de mi cabeza así que también podría tener algún otro defecto.

Answer 3

Es el programador que determina cuál de ellos se ejecutará. Usted puede mirar en pthread_setschedparam y pthread_getschedparam y el violín con las políticas (SCHED_OTHER, SCHED_FIFO o SCHED_RR) y las prioridades. Pero es probable que no se llega a donde sospecho que desea ir.

Parece como si quieres hacer algo predecible a partir de la inherentemente no determinista. Como señala Andrew es posible piratear algo, pero mi conjetura es que esto dará lugar a dolores de cabeza o un código de lote te odiarás por escribir en seis meses (o ambos).