Pergunta sobre threads e bloqueios

Atualmente, estou lendo Fuss, Futexes e Furwocks: Fast Userland Locking no Linux e me deparei com esta citação:

Em um esquema de bloqueio justo, o bloqueio é concedido na ordem em que foi solicitado. Isso pode ter um impacto negativo na taxa de transferência devido ao aumento do número de alternâncias de contexto. Ao mesmo tempo, pode levar ao chamado problema do comboio. Como os bloqueios são concedidos na ordem de chegada, todos prosseguem na velocidade do processo mais lento, diminuindo a velocidade de todos os processos em espera. Uma solução comum para o problema do comboio foi marcar o bloqueio disponível após a liberação, ativar todos os processos em espera e solicitá-los que recontendessem o bloqueio. Isso é chamado de justiça aleatória. No entanto, isso também leva ao problema do rebanho estrondoso. Apesar disso, ele pode funcionar bem em sistemas de processador único, se a primeira tarefa a ser ativada libera o bloqueio antes de ser antecipada ou agendada, permitindo que o segundo membro do rebanho obtenha o bloqueio, etc.

Eu tenho algumas perguntas sobre esta citação.

Primeiro, um esquema de bloqueio justo resulta em um número aumentado de alternâncias de contexto porque tarefas diferentes colocam processos na fila de espera em momentos diferentes e, portanto, servindo os processos na ordem em que foram recebidos, alternamos o contexto entre várias tarefas?

Segundo, como conceder bloqueios na ordem de chegada faz com que os processos prossigam na velocidade do processo mais lento? Esse não seria o caso apenas se o processo mais lento receber o bloqueio antes dos outros processos? Da mesma forma, como ter processos disputando aleatoriamente o bloqueio resolve o problema do comboio?

Finalmente, não entendo como a justiça aleatória é melhor em sistemas uni-processadores em comparação com sistemas multiprocessadores. Por exemplo, em ambos os casos, todos os processadores em espera são acordados, um fica com o cadeado e os outros precisam dormir novamente, certo? Então, como isso funciona bem em sistemas uni-processadores?

Deixe-me responder a última pergunta primeiro. Ele ressalta que o documento foi escrito em 2002, quando os processadores com vários núcleos eram muito mais caros. Eu acho que os autores estavam preocupados em otimizar para o caso de núcleo único.

... como é a justiça aleatória ... melhor nos sistemas uni-processadores em comparação com sistemas multiprocessadores.

Em um uniprocessador, apenas um processo pode ser agendado por vez. Então, todo mundo é "acordado", mas isso significa apenas que eles passam de um estado de espera para um estado pronto. Em seguida, o planejador é chamado e escolhe um dos processos prontos para execução, e permite que esse processo seja executado por algum período de tempo.

A primeira coisa que o processo recém-executado faz é adquirir o bloqueio. Em seguida, ele processa e (se você não tiver azar) libera o bloqueio. Nesse caso, na próxima vez em que o agendador do kernel obtiver o controle, ele escolherá outro processo "pronto" e o executará. Se o primeiro processo liberou o bloqueio, o segundo processo o adquiriu e assim por diante.

Em um multiprocessador, por outro lado, todos os processos podem ser "despertados" e, em seguida, o agendador inicia alguns / muitos / todos eles sendo executados simultaneamente em diferentes processadores. Um dos processos adquirirá o bloqueio, mas todos os outros processos tentarão obtê-lo, falharão imediatamente e voltarão a dormir na fila de espera. Então, em todos os processadores, exceto um, você acabou de desperdiçar várias chamadas de kernel e várias alternâncias de contexto, apenas para poder dizer a vários processos que não havia nada a fazer.

um esquema de bloqueio justo resulta em um número aumentado de alternâncias de contexto porque tarefas diferentes colocam processos na fila de espera em momentos diferentes e, portanto, servindo processos na ordem em que foram recebidos, alternaríamos o contexto entre várias tarefas?

Eu acho que o caso que eles têm em mente é se você tiver vários processos (em um processador), onde cada processo adquire o mesmo bloqueio repetidamente por curtos períodos de tempo. No caso injusto, o primeiro processo pode ser executado por um tempo e adquirir e liberar o bloqueio várias vezes sem fazer uma alternância de contexto. Em seguida, o segundo processo é executado por um tempo e adquire e libera o bloqueio várias vezes.

No caso "justo", o primeiro processo bloqueia / libera e, na segunda vez que tenta bloqueá-lo, deve ser colocado em suspensão, e o kernel precisa fazer uma troca de contexto e ativar o outro processo. Os processos de pingue-pongue para a frente e para trás "acordam, bloqueiam, desbloqueiam, trabalham um pouco, tentam bloquear, são adormecidos".

como conceder bloqueios na ordem de chegada faz com que os processos prossigam na velocidade do processo mais lento? Este não seria o caso apenas se o processo mais lento obtiver o bloqueio antes dos outros processos? Da mesma forma, como ter processos disputando aleatoriamente o bloqueio resolve o problema do comboio?

Eu acho que eles estão observando que, em um uniprocessador, o menor trabalho primeiro (injusto) tem tempos médios de espera mais curtos do que o round-robin (justo). Mas não entendo como o acaso diminui o tempo médio de espera em comparação com o round-robin.