Implementazione di una coda di priorità con una variabile di condizione in C

Question

Il mio attuale comprensione di variabili di condizione è che tutti bloccati (attesa) fili vengono inseriti in una coda di base FIFO, il primo elemento del quale è risvegliato quando il segnale () viene chiamato.

C'è un modo per modificare questa coda (o creare una nuova struttura) per eseguire come una coda di priorità, invece? Ci ho pensato su per un po ', ma la maggior parte delle soluzioni che ho finiscono per essere ostacolato dalla struttura coda esistente inerente alla C.V. e di mutex.

Grazie!

Answer 1

Credo che si dovrebbe ripensare quello che stai cercando di fare. Se stai cercando di ottimizzare le prestazioni, probabilmente stai abbaiare contro l'albero sbagliato.

pthread_cond_signal() non è nemmeno garantito per sbloccare esattamente un filo - è garantito per sbloccare almeno un thread, così il vostro codice di meglio essere in grado di gestire la situazione in cui più thread contemporaneamente siano sbloccati. Il modo tipico per farlo è per ciascun filo di ri-verificare la condizione dopo essere sbloccato, e, se falso, tornare nuovamente in attesa.

Si potrebbe attuare una sorta di schema in cui è tenuto il proprio coda di priorità dei thread in attesa, e ogni thread si aggiunge a quella della coda subito prima che fosse cominciare attesa, e poi sarebbe controllare la coda quando lo sblocco, ma questo sarebbe aggiungere un sacco di complessità e un sacco di potenziale di gravi problemi (condizioni di gara, deadlock, etc.). E 'stato anche aggiungere una quantità non trascurabile di spese generali.

Inoltre, cosa succede se un thread con priorità più alta inizia attesa su una variabile condizione nello stesso momento in cui variabile condizione viene segnalata? Chi ottiene sbloccato, il thread ad alta priorità appena arrivato o l'ex thread a priorità più alta?

L'ordine in cui le discussioni ottenere sbloccato nel dipende interamente dalla pianificazione dei thread del kernel, in modo che siano alla sua mercé. Non avrei neppure assumere FIFO ordinazione, sia.

Answer 2

Dal momento che le variabili di condizione sono fondamentalmente solo una barriera e si ha alcun controllo sulla coda di thread in attesa non c'è nessun vero modo per applicare le priorità. E 'valida per assumere le discussioni in attesa agirà in modo FIFO.

Con una combinazione di Atomics, variabili di condizione supplementari, e pre-conoscenza dei filati / priorità coinvolti si potrebbe costruire una soluzione in cui un filo segnalato si ri-segnale CV master e poi ri-blocco in un CV priorità ma certamente non sarebbe una soluzione generica. Questo è anche fuori dalla parte superiore della mia testa così potrebbe anche avere qualche altro difetto.

Answer 3

E 'lo scheduler che determina quale thread verrà eseguito. Potete guardare pthread_setschedparam e pthread_getschedparam e violino con le politiche (SCHED_OTHER, SCHED_FIFO o SCHED_RR) e le priorità. Ma probabilmente non si arrivare dove ho il sospetto che si vuole andare.

Sembra come se si vuole fare qualcosa di prevedibile dal intrinsecamente non-deterministico. Come Andrew note si potrebbe incidere qualcosa ma la mia ipotesi è che questo porterà a mal di cuore o di un codice lotto voi odiarti per la scrittura in sei mesi (o entrambi).