Qual è il numero di consenso per i semafori?

Question

(Penso che) numero di consenso Per un mutex è 2.

Qual è il numero di consenso per i semafori (come in pthread_sem_*)?

Qual è il numero di consenso per le variabili della condizione (come in pthread_cond_*)?

Answer 1

Il numero di consenso per un mutex sarebbe 1. È banalmente chiaro che un mutex sarà privo di attesa per un singolo thread. Dalla sua definizione, è anche chiaro che un mutex non è più libero per due thread. Il numero di consenso è quindi> = 1 e <2, quindi deve essere 1.

Allo stesso modo, altri meccanismi di sincronizzazione che funzionano fermando un thread a favore di un altro hanno anche il consenso numero 1, e quindi non possono essere utilizzati per costruire un oggetto privo di attesa condiviso da 2 thread.

Answer 2

La risposta dipende dalle operazioni supportate dal mutex o dal semaforo. Se sono supportati solo i blocchi di blocco, il numero di consenso è 1. Se un thread può provare a bloccare il mutex senza aspettare, il numero di consenso è 2. Questo perché se ci sono due thread, entrambi possono provare a bloccare il mutex, entrambi possono Concorda su quale abbia ottenuto, quindi c'è consenso. Se il mutex può inoltre determinare, per qualsiasi numero di thread, quale thread lo ha bloccato, il numero di consenso è infinito. Penso che la situazione per i semafori sia simile. I mutex sono equivalenti ai semafori con il contatore 1. Non credo che il consenso possa essere raggiunto solo con contatori più grandi, si riduce ancora alle stesse operazioni. Pthreads supporta blocchi non bloccanti ma non query, quindi la risposta sarebbe 2.

La segnalazione di una variabile di condizione non fa nulla se i thread non lo aspettano, quindi hanno il consenso numero 1.

Answer 3

Infinito, sicuramente? Ma non aspettano gratis.

Forse sto fraintendendo. Dici che un mutex ha un numero di consenso di 2 - qual è la tua fonte per questo? È progettato per consentire a qualsiasi numero di thread di condividere una risorsa, con il compromesso del blocco.

Atomico test-and-set Ha un numero di consenso di 2, ma non blocca.

---

Per chiarire: semafori, mutex, ecc. Sono primitivi che puoi semplicemente avvolgere una risorsa condivisa per renderlo al sicuro (fintanto che lo fai correttamente). Potrebbero bloccare, ma garantiranno che i tuoi dati siano sicuri.

Il documento che citi riguarda i primitivi necessari per proteggere i dati senza bloccare, che è difficile. Gli stessi primitivi possono essere utili anche per le serrature, ma è solo un bel extra.

Answer 4

Solo da questo articolo puoi concludere che un semaforo deve avere un numero di consenso inferiore o uguale a 2. Ecco perché:

Nella terza pagina dell'articolo affermano: "L'operazione Fetch & Aggiungi è abbastanza flessibile: può essere utilizzata per i semafori ...". Dal momento che sappiamo che Fetch & Add ha un numero di consenso pari a 2, il teorema 1 di quella carta può quindi essere usato per dimostrare che un semaforo deve avere un numero di consenso inferiore o uguale a 2. La prova va così:

Prova

Supponiamo che esista un'implementazione senza attesa di semafori da parte di Fetch & ADD. Supponiamo inoltre che un semaforo abbia un numero di consenso maggiore di 2. Sappiamo che Fetch & Add ha un numero di consenso di 2. Dal Teorema 1 possiamo concludere che non esiste un'implementazione senza attesa di un semaforo per fetch e aggiungi un sistema di più di 2 processi . Ciò contraddice il presupposto che esista un'implementazione di Fetch & ADD. Pertanto, un semaforo deve avere un numero di consenso inferiore o uguale a 2.

QED