domanda di riesame: Filetto di coda di sicurezza (parallela spinta pop)
-
30-09-2019 - |
Domanda
Ecco un'implementazione di un filo di coda di sicurezza. La spinta e pop non bloccherà l'un l'altro. Tuttavia, pop attenderà fino a quando un oggetto viene spinto, se la coda è vuota. produttori multiple e consumatori possono utilizzare la coda. Ti prego, dimmi se si vede alcun problema.
Aggiornamento: A cura secondo le risposte 1) risolto la questione della situazione "Queue Full". 2) Non v'è BlockingCollection<T>
e ConcurrentQueue<T>
in .NET4. Quindi non c'è bisogno di reinventare la ruota (per .NET4)
public class CustomQueue<T> where T: class
{
class Node
{
public Node()
{
Value = null;
NextNode = null;
}
public Node(T value)
{
Value = value;
NextNode = null;
}
public T Value;
public Node NextNode;
}
object PushLocker = new object();
object PopLocker = new object();
Semaphore QueueSemaphore;
volatile int PushIncrement;
volatile int PopIncrement;
int MaxItems;
Node FirstNode;
Node LastNode;
public CustomQueue(int maxItems)
{
QueueSemaphore = new Semaphore(0, maxItems);
MaxItems = maxItems;
FirstNode = LastNode = new Node();
PushIncrement = 0;
PopIncrement = 0;
}
public int Size()
{
return PushIncrement - PopIncrement;
}
public bool Push(T value)
{
lock(PushLocker)
{
if((Size()) >= MaxItems)
{
lock(PopLocker)
{
PushIncrement = PushIncrement - PopIncrement;
PopIncrement = 0;
return false;
}
}
Node newNode = new Node(value);
LastNode.NextNode = newNode;
LastNode = newNode;
PushIncrement++;
QueueSemaphore.Release();
return true;
}
}
public T Pop()
{
QueueSemaphore.WaitOne();
lock(PopLocker)
{
Node tempFirst = FirstNode;
Node tempNext = FirstNode.NextNode;
T value = tempNext.Value;
tempNext.Value = null;
FirstNode = tempNext;
PopIncrement++;
return value;
}
}
}
Soluzione
Si presenta come un'implementazione bravo a colpo d'occhio. Usando diverse serrature è sempre una bandiera rossa per me così ho preso un buon difficile guardare alcuni dei casi limite che coinvolgono simultaneamente chiamate a Pop
e Push
e sembra sicura. Ho il sospetto che probabilmente te istruiti sulla lista implemenation collegata di una coda di blocco eh? Il motivo per cui questo è sicuro perché solo sei mai LastNode
riferimento dal Push
e FirstNode
dal Pop
altrimenti l'intero trucco sarebbe cadere a pezzi.
L'unica cosa che si conficca fuori a me in questo momento è che quando si tenta di rilasciare un conteggio da un Semaphore
sarà un'eccezione se è già pieno così si potrebbe desiderare in guardia contro questo. 1 in caso contrario, si finirà con nodi in più nella lista collegata e la coda sarà 1) hanno più del numero massimo di elementi e 2) si otterrà live-locked.
Aggiornamento:
Ho dato questo un po 'di pensiero. Quella chiamata Release
nel metodo Push
sta per essere molto problematico. Vedo solo una possibile soluzione. Rimuovere il parametro maxItems
dal costruttore e consentire il semaforo di contare a Int.MaxValue
. In caso contrario, si sta andando ad avere per cambiare radicalmente il vostro approccio con conseguente un'implementazione che non è dove vicino a quello che si ha attualmente.
1 Penso che troverete che questo sarà più difficile di quello che si potrebbe subito conto.
Altri suggerimenti
1.
Considerare l'aggiunta di un secondo costruttore Node:
public Node(T value)
{
Value = value;
}
allora il vostro codice client:
Node newNode = new Node();
newNode.Value = value;
può considerare il valore come un invariante:
Node newNode = new Node(value);
2.
poi fatevi campi pubblici:
public T Value;
public Node NextNode;
nelle proprietà auto:
public T Value { get; private set; };
public Node NextNode { get; set; };
Così si può astrarre l'utilizzo con l'applicazione e aggiungere la validazione, altre lavorazioni, ecc dopo il fatto con il minimo disturbo al codice client.
Se si sta facendo questo per l'auto-educazione, grande - altrimenti BlockingCollection<T>
o ConcurrentQueue<T>
sono buone alternative.
Un problema che vedo è che non v'è alcun modo per Pop
interrupt una volta che inizia - assume un oggetto è in attesa quando si risveglia. Come si deselezionare questa verso il basso al termine? Un TryPop
che i rendimenti true
(con un elemento) o false
(se non ci sono dati) potrebbe essere migliore, allora si potrebbe segnalare le discussioni in attesa di chiudere in modo pulito una volta che la coda è drenato.
Vai a questa se si dispone di .Net 4
Come io sono un fan di oggetti immutabili, ecco un'alternativa alla mia precedente risposta che vorrei prendere in considerazione un po 'più pulito:
public sealed class CustomQueue<T> where T : class
{
private readonly object pushLocker = new object();
private readonly object popLocker = new object();
private readonly Semaphore queueSemaphore;
private readonly int maxItems;
private volatile int pushIncrement;
private volatile int popIncrement;
private Node firstNode = new Node();
private Node lastNode;
public CustomQueue(int maxItems)
{
this.maxItems = maxItems;
this.lastNode = this.firstNode;
this.queueSemaphore = new Semaphore(0, this.maxItems);
}
public int Size
{
get
{
return this.pushIncrement - this.popIncrement;
}
}
public bool Push(T value)
{
lock (this.pushLocker)
{
if (this.Size >= this.maxItems)
{
lock (this.popLocker)
{
this.pushIncrement = this.pushIncrement - this.popIncrement;
this.popIncrement = 0;
return false;
}
}
Node newNode = new Node(value, this.lastNode.NextNode);
this.lastNode = new Node(this.lastNode.Value, newNode);
this.firstNode = new Node(null, newNode);
this.pushIncrement++;
this.queueSemaphore.Release();
return true;
}
}
public T Pop()
{
this.queueSemaphore.WaitOne();
lock (this.popLocker)
{
Node tempNext = this.firstNode.NextNode;
T value = tempNext.Value;
this.firstNode = tempNext;
this.popIncrement++;
return value;
}
}
private sealed class Node
{
private readonly T value;
private readonly Node nextNode;
public Node()
{
}
public Node(T value, Node nextNode)
{
this.value = value;
this.nextNode = nextNode;
}
public T Value
{
get
{
return this.value;
}
}
public Node NextNode
{
get
{
return this.nextNode;
}
}
}
}