A implementação de uma fila de prioridade com uma variável de condição em C

Question

O meu entendimento atual de variáveis ??de condição é que todos (espera) tópicos bloqueados são inseridos em uma fila básica FIFO, o primeiro item da qual é despertado quando o sinal () é chamado.

Existe alguma maneira de modificar essa fila (ou criar uma nova estrutura) para executar como uma fila de prioridade em vez disso? Eu estive pensando sobre isso por um tempo, mas a maioria das soluções que eu acabar sendo prejudicado pela estrutura fila existente inerente à C.V. de e semáforos.

Obrigado!

Answer 1

Eu acho que você deveria repensar o que você está tentando fazer. Se você está tentando otimizar o seu desempenho, você provavelmente está latindo para a árvore errada.

pthread_cond_signal() nem sequer é garantido para desbloquear exatamente um fio - é garantido para desbloquear , pelo menos uma thread, para que o seu código melhor ser capaz de lidar com a situação em que vários tópicos são desbloqueados simultaneamente. A maneira comum de fazer isso é para cada thread para re-verificar a condição depois de se tornar desbloqueado, e, se for falso, retorno à espera novamente.

Você poderia implementar algum tipo de esquema em que você manteve sua própria fila de prioridade de segmentos de espera, e cada thread acrescentou-se a essa fila imediatamente antes que fosse para começar a espera, e em seguida, ele iria verificar a fila quando desbloqueio, mas isso adicionar um monte de complexidade e um grande potencial para problemas graves (condições de corrida, deadlocks, etc.). Foi também adicionar uma quantidade não trivial de sobrecarga.

Além disso, o que acontece se um de maior prioridade de rosca começa à espera de uma variável de condição no mesmo momento em que a variável de condição está sendo sinalizado? Quem fica desbloqueado, o segmento de alta prioridade recém-chegado ou da antiga thread de prioridade mais alta?

A fim de que threads ficar desbloqueado em é inteiramente dependente do programador thread do kernel, então você está à sua mercê. Eu nem assumir FIFO ordenação, qualquer um.

Answer 2

Desde variáveis ??de condição são basicamente apenas uma barreira e você não tem controle sobre a fila de segmentos de espera não há nenhuma maneira real para aplicar prioridades. É nulo assumir esperando tópicos irá agir de forma FIFO.

Com uma combinação de Atomics, variáveis ??de condição adicionais e pré-conhecimento dos fios / prioridades envolvida você poderia construir uma solução onde um fio sinalizou vai voltar a sinalizar o CV mestre e então re-block em um CV prioridade mas certamente não seria uma solução genérica. Isso também é em cima da minha cabeça para que também pode ter alguma outra falha.

Answer 3

É o programador que determina qual segmento será executado. Você pode olhar para pthread_setschedparam e pthread_getschedparam e mexer com as políticas (SCHED_OTHER, SCHED_FIFO, ou SCHED_RR) e as prioridades. Mas provavelmente não vai chegar até onde eu suspeito que você quer ir.

Soa como se você quiser fazer algo previsível do intrinsecamente não-determinista. Como Andrew observa que você pode cortar alguma coisa, mas meu palpite é que isso vai levar a dor de cabeça ou um código de lote que você irá se odiar para escrever em seis meses (ou ambos).