Problema produttore / consumatore con 2 mutex?

3

L'impostazione

Consideriamo una variante del classico problema di programmazione multithread: il problema produttore / consumatore. Abbiamo un numero finito di risorse (per semplicità, lascia che ci sia solo una singola risorsa). Il thread del produttore crea continuamente nuove unità di risorse, finché il buffer delle risorse non è pieno (nel nostro caso, può produrre solo un'unità di risorsa prima del blocco). Il thread del consumatore recupera le risorse dal buffer ed esegue alcuni lavori con esse.

Il problema

Il trucco consiste nell'usare una specie di primitiva di sincronizzazione (o più primitive) per impedire che il buffer entri in uno stato incoerente a causa delle condizioni di gara, ecc.

La domanda

Per quanto ne so, il problema potrebbe essere risolto utilizzando uno dei seguenti elementi:

  • Monitor
  • un mutex e una variabile di condizione
  • due semafori
  • tre mutex

Potrei usare l'algoritmo della soluzione semaforo per risolvere il problema usando solo due mutex, ma poiché il thread è autorizzato a sbloccare i propri mutex, questo algoritmo non può essere applicato qui. Non sono stato in grado di inventarne un altro finora.

Quindi, la mia domanda è:

È possibile risolvere la variante descritta del problema produttore / consumatore usando solo una coppia di mutex, senza alcuna altra primitiva di sincronizzazione? Se non lo è, perché? Potresti fornire una dimostrazione formale?

    
posta Dmitry Serov 09.10.2016 - 13:41
fonte

1 risposta

1

Sostanzialmente le architetture produttore / consumatore utilizzano una coda che viene alimentata dal / dai produttore / i e letta dal (i) consumatore (i):

Laconcorrenzaelecondizionidigarasonotuttecorrelateallagestionedellacoda.

Ilmodopiùsempliceperprocederesarebbequellodiproteggereogniaccessoallacodaconunsingolomutex,tenutoerilasciatodalproduttoreodalconsumatore.Ilproblemaneltuoscenarioècheilproduttorescrivecontinuamentenuoviarticolifinchéilbuffernonèpieno,quindic'èilrischiodifarmoriredifameiconsumatorifinchéilbuffernonèpieno,arrivandodifattoaunasequenzializzazionedell'elaborazione.

Levarianticheproponievitanol'inediagarantendounaccessopiùequilibratoallacodacondivisa(comeadesempio con il mutex ).

Ma è anche possibile condividere una coda usando due mutex! Uno di questi esempi consiste nell'utilizzare un mutex per la testa e un mutex per la coda (un cosiddetto blocco a grana fine come implementato qui)

    
risposta data 09.10.2016 - 19:10
fonte

Leggi altre domande sui tag