¿Por qué la mayoría de las implementaciones de mutex son injustas?

Tengo entendido que las implementaciones más populares de un mutex (p. Ej., Std :: mutex en C ++) no garantizan la equidad , es decir, no garantizan que, en casos de contención, el bloqueo sea adquirido por hilos en el orden en que llamado lock (). De hecho, incluso es posible (aunque con suerte poco común) que en casos de alta contención, algunos de los hilos que esperan adquirir el mutex nunca lo adquieran.

Esto me parece un comportamiento inútil, me parece que un mutex justo produciría un comportamiento más acorde con lo que un programador querría / esperaría.

La razón dada por la cual los mutexes generalmente no se implementan para ser justos es el "rendimiento", pero me gustaría entender mejor lo que eso significa, en particular, ¿cómo la relajación del requisito de equidad de mutex mejora el rendimiento? Parece que un mutex "justo" sería trivial de implementar: simplemente haga que lock () agregue el hilo de llamada a la cola de la lista vinculada de mutex antes de poner el hilo a dormir, y luego haga desbloquear () pop el siguiente hilo de la cabeza de esa misma lista y despiértala.

¿Qué idea de implementación de mutex me estoy perdiendo aquí, que explicaría por qué se consideró que valía la pena sacrificar la justicia por un mejor rendimiento?

La respuesta de Jim Sawyer apunta a una respuesta: cuando tiene hilos con diferentes prioridades, el comportamiento "justo" sería incorrecto. Cuando tiene varios subprocesos que podrían ejecutarse, el subproceso de mayor prioridad generalmente es el que debe ejecutarse.

Sin embargo, hay un secreto poco discutido sobre la implementación del sistema operativo que debe tener en cuenta, que es que ocasionalmente los sistemas operativos ejecutan código como el usuario al secuestrar un hilo de usuario. Por razones de seguridad, la mayoría de los sistemas operativos que hacen esto solo lo hacen mientras un hilo está bloqueado. Cuando finaliza el sistema operativo, el subproceso se vuelve a suspender, y esto normalmente tiene el efecto de mover el subproceso al final de la cola de espera.

Un ejemplo típico es un controlador de señal en Unix, una trampa de sistema asíncrono en VMS o una llamada a procedimiento asíncrono en Windows NT. Todos estos son esencialmente lo mismo: el sistema operativo debe notificar al proceso del usuario que sucedió algún evento, y esto se maneja ejecutando código en el espacio del usuario.

Muchos servicios del sistema operativo, como la E / S asíncrona, a menudo se implementan sobre esta instalación.

Otro ejemplo es si el proceso está bajo el control de un depurador. En ese caso, el sistema de depuración puede ejecutar código como tarea del usuario por varias razones.

La 'inversión prioritaria' es una de las razones por las que la equidad puede ser indeseable. Un proceso de baja prioridad golpea el mutex bloqueado y duerme. Luego, un proceso de mayor prioridad lo golpea, y también duerme. Cuando se desbloquea el mutex, ¿qué proceso debería obtener el bloqueo después?

Un mutex justo pasará más de su vida bloqueado que un mutex injusto, todo lo demás es igual. Porque un hilo que libera un mutex injusto siempre puede desbloquearlo. Pero un hilo que libera un mutex justo solo puede desbloquearlo cuando la cola del camarero está vacía. De lo contrario, el subproceso de liberación debe dejar el mutex bloqueado por el siguiente subproceso, también conocido como el primer subproceso en la cola del camarero, que luego se retira y se despierta. El mutex permanece bloqueado al menos hasta que el subproceso recién despertado esté programado en una CPU, lo que podría llevar mucho tiempo si actualmente hay muchos subprocesos ejecutables.

Y si el hilo de liberación intenta rápidamente volver a adquirir el mismo mutex, debe colocarse en la parte posterior de la cola del camarero e irse a dormir. Esto no habría sucedido si el hilo no liberara el mutex para empezar. Por lo tanto, esto incentiva secciones críticas más "más codiciosas".