Struttura dati generica concomitante senza deadlock o mancanza di risorse

Question

Ho recentemente fatto una serie di domande riguardanti TVar e ho ancora dubbi su livelock.

così ho pensato di questa struttura:

1. Ogni transazione ottiene una priorità unica (forse assegnate in ordine di creazione).
2. Le transazioni tentano di ottenere blocchi di lettura/scrittura sui dati a cui accedono. Naturalmente, le letture simultanee vanno bene, ma un blocco di scrittura esclude tutti gli altri (sia letti che scritti).
3. Dire che la transazione A ha priorità più alta della transazione B. Se A mantiene il blocco, B attende, ma se B mantiene il blocco e A lo vuole, B viene avviato dal blocco, A lo ottiene e la transazione B ricomincia (come con TVar). B mantiene comunque la sua attuale priorità per il tentativo.
4. Quando un blocco viene liberato e ci sono transazioni in attesa, passa alla transazione con priorità più alta e il resto continua ad attendere.

Questo sistema, credo, previene i deadlock, ma impedisce anche l'inedia (a differenza di TVar). Mi stavo chiedendo se qualcuno ha implementato un sistema del genere, dato che sembra abbastanza ovvio e non voglio reinventare la ruota.

Ovviamente, un simile approccio potrebbe essere facilmente esteso per consentire all'utente di specificare le priorità.

La priorità potrebbe essere la coppia (user_supplied_prio, auto_increment), con user_supplied_prio che ha la precedenza, ma le attività con priorità uguale che si risolvono nell'ordine FIFO.

Commento/Soluzione:

In realtà, quando ci penso, quello che ho descritto già esiste in Haskell, semplicemente utilizzando uno IORef avvolto intorno tutti i dati, e utilizzando solo atomicModifyIORef. Lo atomicModifyIORef assicurerà che le transazioni vengano applicate in sequenza. Tuttavia, si potrebbe pensare che questo significhi che la struttura dei dati sia sequenziale (cioè efficacemente limitata a un thread) ma in realtà è parallela a causa della pigrizia.

Per spiegare ciò, considerare una funzione costosa f. Applicheremo questo a Data.Map ai dati con il tasto "pippo".

Sostituisce (foo -> x) con (foo -> future(f x)). Questo thread deve continuare a capire cosa sia in realtà (f x), ma nel frattempo possiamo applicare g a "bar". Dato che applicare g a "bar" non ha bisogno del risultato di "foo", possiamo lavorarci allo stesso tempo.

Nessun deadlock, nessuna inedia, alla fine tutte le transazioni verranno elaborate (all'incirca nell'ordine in cui vengono ricevute).

Answer 1

È possibile impostare un thread di lavoro per elaborare tutte le richieste in modo deterministico, in modo che nessuno resti affamato. Questa strategia sarebbe ragionevolmente efficiente e immune al livelock.

-- yes, this is a horrible name 
createManagerFactory :: a -> IO ((IO a), IO (((a -> a) -> IO a))) 

IO a è un'azione che modo rapido e sicuro interroga il valore con una sola lettura azioni STM. (a -> a) è una funzione pura che modifica il valore, quindi ((a -> a) -> IO a) è un'azione che accetta una funzione modificatore, modifica il valore in modo sicuro e restituisce il nuovo valore.

Eseguire questa volta per inizializzare la fabbrica.

(query, modifierFactory) <- createManagerVactory initValue 

Quindi, per ogni thread, eseguire questo per generare un nuovo modificatore.

myModify <- modifierFactory 

createManagerFactory farebbe il seguente:

• Creare un Tvar contenente initValue (lo chiamano valueTVar).
• Creare un Tvar contenente un insieme vuoto di Tvar (O una (un -> a)) (lo chiamano il modifyTVarCollection)
• ritorno (atomicamente $ readTVar valueTVar) come il 'query' risultato
• cambio una modifierFactory che conosce il modifyTVarCollection

modifierFactory farebbe questo:

• Creare un nuovo Tvar (O un (a -> a)) (chiamarlo modifyTVar), inizializzare a un (a sinistra una) con il valore corrente del valoreTVar e aggiungerlo a modifyTVarCollection
• restituire un'azione modificatore che carica (Destra (a -> a)) nel modifyTVar in un'azione STM, quindi in un'altra azione STM riprova finché il modifyTVar non contiene a (A sinistra a) valore del risultato, quindi restituire quel valore.

Il thread di lavoro sarebbe in questo ciclo:

• In un'azione, afferrare tutte le TVars query dal modifyTVarCollection, e controllare i loro valori. Se tutti contengono valori (Left a), riprova (questo bloccherebbe fino a quando qualche altro thread caricherà il loro modifyTVar con una funzione modificatore, o il modificatoreFactory ha creato un nuovo modificatoreTV e l'ha aggiunto alla raccolta). Restituire un elenco di tutte le modificheTVars che contengono un diritto (a -> a)
• Iterate su tutte le restituzioni modificate. Per ogni TVar, eseguire un'azione che legge la funzione modificatore, eseguire la modifica in modo sicuro e reinserire il risultato nella modificaTVar (a sinistra)