Se utilizzo i blocchi, il mio algoritmo può ancora essere bloccato?

Questa non è una definizione per lock-free.

Se puoi garantire il progresso, allora hai deadlock-free e se hai il completamento finale di ogni richiesta, allora hai starvation-free , ma non bloccare -free.

Mi domando se il tuo semplice esempio in realtà lo fornisce comunque. Hai bisogno di gerarchie di lock e così via per ottenere garanzie di progresso quando sono coinvolti più blocchi.

Ho studiato l'arte della programmazione multiprocessore ¹ e il loro testo è privo di chiarezza, proprio come il libro a cui fai riferimento. Ecco alcune citazioni da TAMPP:

Citazione 1 (Definizione di lock-free)

A method is lock-free if it guarantees that infinitely often some method call finishes in a finite number of steps.

Citazione 2 (Definizione di non blocco)

a pending invocation of a total method is never required to wait for another pending invocation to complete.

Quota 3 (afferma che il blocco è senza blocchi)

The wait-free and lock-free nonblocking progress conditions guarantee that the computation as a whole makes progress, independently of how the system schedules threads.

Il problema è che il reclamo in Quota 3 non segue ovviamente la definizione in Citazione 1. Come già accennato, una coda sincronizzata sembra soddisfare la Citazione 1: infinitamente spesso alcuni metodi acquisiscono con successo il blocco e lo completano.

Si noti in particolare la frase abbastanza vaga in Quota 3: "indipendentemente da come il sistema pianifica i thread". Questo non è preceduto da alcun tipo di descrizione formale del "sistema di schedatura del thread", quindi siamo lasciati a ricostruire le sue proprietà sulla base dei nostri preconcetti su cosa significano le definizioni dovrebbero :

1. il sistema esegue sempre le istruzioni di alcuni thread;
2. potrebbe non eseguire mai le istruzioni di alcun dato thread;
3. tutti i thread stanno invocando il metodo preso in considerazione.

Su un sistema di questo tipo, un metodo di blocco non può essere bloccato: se il thread che blocca il blocco non viene mai più pianificato per l'esecuzione, non ci sarà nessun altro thread che può completare l'invocazione del metodo in un numero finito di passaggi, eppure ci saranno alcuni thread che stanno eseguendo passi del metodo. Per un sistema più realistico, che garantisce di dare tempo CPU a ogni thread, la definizione deve includere esplicitamente la proprietà non bloccante:

Definizione corretta di lock-free

A method is lock-free if it is non-blocking and, additionally, guarantees that infinitely often some method call finishes in a finite number of steps.

¹ Maurice Herlihy, Nir Shavit, L'arte della programmazione multiprocessore, Elsevier 2008, pp. 58-60

La terminologia non è sempre coerente, ma penso che l'importante è porre le seguenti domande su un algoritmo o sistema proposto:

1. Esiste una sequenza di eventi in cui i thread potrebbero rimanere bloccati in attesa l'uno dell'altro anche se a tutti i thread è stato concesso tutto il tempo della CPU che potevano usare [se così fosse, non è deadlock libero]
2. Se un thread è stato bloccato per un tempo arbitrario, potrebbe bloccare altri thread o compromettere il funzionamento del sistema per un tempo arbitrariamente lungo [in tal caso, non è non bloccante].
3. Esiste una qualche combinazione teoricamente possibile di scheduling dei thread che potrebbe far ripetere ripetutamente le stesse operazioni a tutti i thread, invalidando il lavoro degli altri, senza che nessuno faccia progressi [se è così, non è lock-free]
4. Se ad alcuni thread viene dato un tempo CPU sufficiente rispetto ad un altro, potrebbero forzare quest'ultimo thread a continuare a ripetere le sue operazioni a tempo indefinito [se così fosse, non è senza attesa].

Gran parte dell'importanza degli algoritmi lock-free non è che siano più veloci degli algoritmi non lock-free, ma piuttosto il fatto che non sono inclini a morire se un thread viene waylaid [nota che tale la garanzia richiede semplicemente che gli algoritmi siano non-bloccanti, ma tutti gli algoritmi lock-free sono]. È possibile che un algoritmo lock-free utilizzi i blocchi, ma solo se i tentativi di acquisizione dei blocchi includono timeout insieme agli algoritmi per garantire che sia sempre possibile per qualcuno progredire (ad esempio, un algoritmo potrebbe utilizzare un ciclo CompareExchange come metodo di arbitraggio primario, ma utilizzare i blocchi per arbitrare l'accesso quando il conflitto sembra elevato, se un blocco sembra essere trattenuto troppo a lungo, altri thread potrebbero decidere di abbandonare gli sforzi per utilizzare quel blocco e crearne uno nuovo. è garantito tramite CompareExchange , in quanto i clienti che abbandonano la serratura non metterebbero a repentaglio la coerenza del sistema, sebbene ciò potrebbe significare che il codice che aveva bloccato la vecchia serratura non avrebbe funzionato fino a quando non abbandonasse troppo la vecchia serratura e si mettesse in coda per il nuovo.

Devi guardare la "definizione" che citi in contesto :

The traditional way to implement shared data structures is to use mutual exclusion (locks) to ensure that concurrent operations do not interfere with one another. Locking has a number of disadvantages with respect to software engineering,fault-tolerance, and scalability (see [8]). In response,researchers have investigated a variety of alternative synchronization techniques that do not employ mutual exclusion. A synchronization technique is wait-free if it ensures that every thread will continue to make progress in the face of arbitrary delay (or even failure) of other threads. It is lock-free if it ensures only that some thread always makes progress.

Stai usando i blocchi per l'esclusione reciproca, quindi non è una tecnica lock-free di cui stanno parlando.

If I use locks, can my algorithm still be lock-free?

Potrebbe essere, ma dipende dall'algoritmo.

If I have a simple data structure such as a queue, protected by a lock, then one process can always make progress, as one process can acquire the lock, do what it wants, and release it.

So does it meet the definition of lock-free?

Nota di per sé .

Se il passaggio "fa ciò che vuole" non implica l'acquisizione di altri blocchi, e si garantisce che venga completato in un tempo finito, allora questa parte particolare del tuo algoritmo non ha deadlock.

Tuttavia, se queste precondizioni non sono soddisfatte, c'è almeno il potenziale di deadlock ...

L'esempio che fornisci non è privo di blocco per il seguente motivo.

Il supporto di un thread acquisisce il blocco e lo scheduler del SO sospende il thread per un periodo di tempo infinito, quindi tutto il thread non può avanzare perché nessun può acquisire il blocco acquisito dal thread sospeso.

In generale, gli algoritmi che utilizzano i blocchi non sono bloccati.

Si noti che deadlock-free e lock-free sono due concetti diversi. senza deadlock significa che non vi è alcuna possibilità di stallo, ma potrebbe esserci un livelock che può impedire a tutto il sistema di fare progressi. Lock-freedom è più strong di così perché significa che alcuni thread nel sistema fanno sempre progressi con un numero finito di passi.