invertire i buffer a thread singolo-scrittore-multiple-reader

StackOverflow https://stackoverflow.com/questions/7805957

Domanda

La Storia

C'è un thread di scrittura, raccogliendo periodicamente i dati da qualche parte (in tempo reale, ma che non importa molto in questione). Ci sono molti lettori che leggono quindi da questi dati. La soluzione più comune per questo è con la serratura di due lettore-scrittore e due tamponi in questo modo: 

Writer (case 1):
acquire lock 0                        
loop
    write to current buffer
    acquire other lock
    free this lock
    swap buffers
    wait for next period

o 

Writer (case 2):
acquire lock 0                        
loop
    acquire other lock
    free this lock
    swap buffers
    write to current buffer
    wait for next period

Il problema

In entrambi i metodi, se la acquisiscono altro blocco operazione non riesce, non di swap è fatto e scrittore avrebbe sovrascrivere i suoi dati precedente (perché chi scrive è in tempo reale, non può attendere per i lettori) Così in questo caso, tutti i lettori perderebbero quel lasso di dati.

Questo non è un grosso problema, però, i lettori sono il mio codice e sono brevi, quindi con doppio buffer, questo problema è risolto, e se ci fosse un problema che potrebbe rendere tampone tripla (o più).

Il problema è il ritardo che voglio minimizzare. Immaginate caso 1: 

writer writes to buffer0                reader is reading buffer1
writer can't acquire lock1              because reader is still reading buffer1
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)      <- **this point**
|
|
writer wakes up, and again writes to buffer0

A questo punto ** **, altri lettori in teoria avrebbero potuto leggere i dati di buffer0 se solo lo scrittore potrebbe fare lo scambio, dopo che il lettore finisce, invece di aspettare per il prossimo periodo. Quello che è successo in questo caso è che solo perché un lettore era un po 'tardi, tutti i lettori perso un fotogramma dei dati, mentre il problema avrebbe potuto essere completamente evitato.

Caso 2 è simile: 

writer writes to buffer0                reader is idle
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)
|
|                                       reader starts reading buffer1
writer wakes up                         |
it can't acquire lock0                  because reader is still reading buffer1
overwrites buffer0

Ho provato a mescolare le soluzioni, in modo che i tentativi scrittore scambiare i buffer subito dopo la scrittura, e se non è possibile, solo dopo il risveglio nel prossimo periodo. Quindi, qualcosa di simile a questo: 

Writer (case 3):
acquire lock 0                        
loop
    if last buffer swap failed
        acquire other lock
        free this lock
        swap buffers
    write to current buffer
    acquire other lock
    free this lock
    swap buffers
    wait for next period

Ora il problema con ritardo detiene ancora: 

writer writes to buffer0                reader is reading buffer1
writer can't acquire lock1              because reader is still reading buffer1
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)      <- **this point**
|
|
writer wakes up
swaps buffers
writes to buffer1

Ancora una volta a questo punto ** **, tutti i lettori potrebbero iniziare a leggere buffer0, che è un breve ritardo dopo buffer0 è stato scritto, ma invece hanno dovuto aspettare fino al prossimo periodo dello scrittore.

La questione

La domanda è, come faccio a gestire questo? Se voglio lo scrittore per eseguire con precisione al periodo desiderato, ha bisogno di attendere per il periodo usando la funzione RTAI e non posso fare come 

Writer (case 4):
acquire lock 0                        
loop
    write to current buffer
    loop a few times or until the buffer has been swapped
        sleep a little
        acquire other lock
        free this lock
        swap buffers
    wait for next period

Questo introduce jitter. perché i "poche volte" potrebbe accadere a diventare più lunga della "attesa per il prossimo periodo", così lo scrittore potrebbe perdere l'inizio del suo periodo.

Tanto per essere più chiaro, ecco quello che voglio che accada: 

writer writes to buffer0                reader is reading buffer1
|                                       |
|                                       reader finishes reading,
| (writer waiting for next period)      As soon as all readers finish reading,
|                                         the buffer is swapped
|                                       readers start reading buffer0
writer wakes up                         |
writes to buffer1

Quello che ho già trovato

-copia-update leggere che, per quanto ho capito continua l'allocazione della memoria per i buffer e li libera fino a quando i lettori sono fatti con loro, che è impossibile per me per molte ragioni. Uno, i fili sono condivisi tra il kernel e user space. In secondo luogo, con RTAI, non è possibile allocare la memoria in un thread in tempo reale (perché allora il tuo thread sarebbe chiamando chiamate di sistema di Linux e quindi rompere il real-time-itivity! (Per non parlare usando propria implementazione telecomando di Linux è dovuto inutile per le stesse ragioni)

Ho anche pensato di avere un filo in più che a un più alto tentativi di frequenza scambiare i buffer, ma che non suona come una buona idea. In primo luogo, non sarebbe in necessità di sincronizzare con lo scrittore, e la seconda, beh io ho molti di questi scrittori-lettori che lavorano in diverse parti in parallelo e un filo in più per ogni scrittore sembra proprio troppo. Un thread per tutti gli scrittori sembra molto complicato per quanto riguarda la sincronizzazione con ogni scrittore.

È stato utile?

Soluzione

Cosa API stai usando per serrature lettore-scrittore? Avete una serratura a tempo, come pthread_rwlock_timedwrlock ? Se sì, penso che la è una soluzione al tuo problema, come nel codice seguente: 

void *buf[2];

void
writer ()
{
  int lock = 0, next = 1;

  write_lock (lock);
  while (1)
    {
      abs_time tm = now() + period;

      fill (buf [lock]);
      if (timed_write_lock (next, tm))
        {
          unlock (lock);
          lock = next;
          next = (next + 1) & 1;
        }
      wait_period (tm);
    }
}


void
reader ()
{
  int lock = 0;
  while (1)
    {
      reade_lock (lock);
      process (buf [lock]);
      unlock (lock);
      lock = (lock + 1) & 1;
    }
}

Quello che succede qui, è che non ha molta importanza per lo scrittore se si attende un blocco o per il periodo successivo, fino a quando è sicuro di svegliarsi prima del prossimo periodo è venuto. Il timeout assoluto assicura questo.

Altri suggerimenti

Non è questo esattamente il problema dovrebbe triple buffering per risolvere. In modo da avere 3 tamponi, lascia li chiamano write1, write2, e leggere. Alterna filo scrivi tra iscritto e write1 write2 garantendo che essi non bloccano, e che l'ultimo frame completo sempre disponibile. Poi, i fili di lettura, ad un certo punto appropriato (per esempio, appena prima o dopo la lettura di un frame), il buffer di lettura è capovolto con il buffer di scrittura disponibile.

Anche se questo garantirebbe che gli scrittori non bloccano (il flipping buffer può essere fatto molto rapidamente semplicemente lanciando due puntatori, forse anche con un CAS atomica al posto di una serratura), c'è ancora la questione dei lettori dover attendere altri lettori per finire con il buffer di lettura prima del capovolgimento. Suppongo che questo potrebbe essere risolto un po 'RCU-esque con un pool di buffer di lettura in cui una disponibile può essere capovolto.

  • Usa una coda (FIFO lista collegata)
  • Lo scrittore in tempo reale sarà sempre append (accodamento) alla fine della coda
  • I lettori sarà sempre rimuovere (dequeue) dall'inizio della coda
  • I lettori bloccherà se la coda è vuota

Modifica per l'allocazione dinamica evitano

Io probabilmente usare una coda circolare ... Vorrei utilizzare il costruito in operazioni atomiche __sync. http://gcc.gnu.org /onlinedocs/gcc-4.1.0/gcc/Atomic-Builtins.html#Atomic-Builtins

  • coda circolare (FIFO 2d array)
    • es: byte [] [] Array = new byte [MAX_SIZE] [BUFFER_SIZE];
    • di inizio e fine indice puntatori
  • sovrascrive Writer tampone a Array [fine] []
    • Writer può incrementare Inizio se finisce in loop tutto intorno
  • Reader ottiene buffer dalla Array [Start] []
    • blocchi Reader Se Inizio == Fine

Se non si desidera allo scrittore di attesa, forse non dovrebbe acquisire un blocco che chiunque altro potrebbe attesa. Avrei che esegue una sorta di sincronizzazione, però, per fare in modo che ciò che scrive in realtà viene scritto - in genere, la maggior parte delle chiamate di sincronizzazione causerà un filo di memoria o istruzione ostacolo da eseguire, ma i dettagli dipenderà dal modello di memoria della CPU e l'attuazione del pacchetto fili.

Vorrei dare un'occhiata per vedere se c'è qualche altra primitiva di sincronizzazione in giro che si adatta meglio le cose, ma se arriva il momento critico avrei il blocco scrittore e sbloccare un blocco che nessun altro usa mai.

I lettori devono quindi essere pronto a cose di mancanza di tanto in tanto, e deve essere in grado di rilevare quando hanno perso roba. Vorrei associare una bandiera validità e una lunga sequenza di conteggio con ogni buffer, e hanno lo scrittore fare qualcosa di simile "bandiera chiaro validità, numero sequenza di incrementi, sync, scrittura di buffer, conteggio sequenza di incrementi, insieme flag, sincronizzazione." Se il lettore legge un conteggio delle sequenze, sincronizza, vede la bandiera validità vero, legge i dati fuori, sincronizza, e rilegge lo stesso numero di sequenza, quindi forse c'è qualche speranza che non ha ottenuto dati distorta.

Se avete intenzione di fare questo, vorrei provarlo in modo esaustivo. Sembra plausibile per me, ma potrebbe non funzionare con il vostro particolare implementazione di tutto, dal compilatore di modello di memoria.

Un'altra idea, o un modo per controllare questo, è quello di aggiungere un checksum per il buffer e scrivere l'ultimo di tutti.

Vedi anche le ricerche su algoritmi liberi di blocco, come http://www.rossbencina.com/code/lockfree

Per andare con questo, probabilmente si desidera un modo per lo scrittore di segnale per i lettori che dormono. Potreste essere in grado di utilizzare i semafori Posix per questo - per esempio hanno il lettore chiede allo scrittore di chiamare sem_post () su un particolare semaforo quando raggiunge un determinato numero di sequenza, o quando un buffer è valido.

Un'altra opzione è quella di attaccare con bloccaggio, ma assicurarsi che i lettori non appendere troppo a lungo in possesso di un blocco. I lettori possono tenere il tempo impiegato in possesso di un breve blocco e prevedibile facendo nient'altro mentre tengono che il blocco, ma la copia dei dati dal buffer dello scrittore. L'unico problema è quindi che un lettore bassa priorità può essere interrotto da un task priorità superiore a metà di una scrittura e la cura di ciò è http://en.wikipedia.org/wiki/Priority_ceiling_protocol .

Dato questo, se il filo scrittore ha un'alta priorità, il lavoro caso peggiore da fare a tampone è per il thread di scrittura per riempire il buffer e per ogni thread di lettura per copiare i dati su quel buffer in un altro buffer. Se si può permettere che in ogni ciclo, quindi il filo scrittore e una certa quantità di dati del lettore la copia verrà sempre essere completati, mentre i lettori elaborazione dei dati che hanno copiati può o non può ottenere il loro lavoro svolto. Se non lo fanno, essi saranno in ritardo rispetto e si nota questo quando la prossima afferrare un blocco e lo sguardo intorno per vedere quali tampone vogliono copiare.

FWIW, la mia esperienza con la lettura del codice in tempo reale (se necessario per dimostrare che i bug sono lì, e non nel nostro codice) è che è incredibilmente e volutamente ingenuo, molto chiaramente delineato, e non necessariamente più efficiente di quello che deve essere quello di soddisfare le sue scadenze, in modo da alcuni dati fotocopiatura in ordine apparentemente inutili per arrivare bloccaggio semplice per il lavoro potrebbe essere un buon affare, se lo può permettere.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top