Evitare il deadlock ordinando std :: mutex
Esiste un'implementazione portabile della logica di prevenzione dei deadlock qui (vedere la sezione contrassegnata come "NON PORTATILE"):
#include <cstdint>
#include <iostream>
#include <mutex>
#include <thread>
typedef long Money; //In minor unit.
class Account {
public:
bool transfer(Account& to,const Money amount);
Money get_balance() const;
Account(const Money deposit=0) : balance{deposit} {}
private:
mutable std::mutex lock;
Money balance;
};
bool Account::transfer(Account& to,const Money amount){
std::unique_lock<decltype(this->lock)> flock{this->lock,std::defer_lock};
std::unique_lock<decltype(to.lock)> tlock{to.lock,std::defer_lock};
//NON-PORTABLE:BEGIN: using intptr_t AND assuming Total Strict Order.
const auto fi{reinterpret_cast<const std::intptr_t>(static_cast<const void*>(&this->lock))};
const auto ti{reinterpret_cast<const std::intptr_t>(static_cast<const void*>(&to.lock))};
if(fi<ti){
flock.lock();
tlock.lock();
} else if (fi!=ti) {
tlock.lock();
flock.lock();
} else {
flock.lock();
}
//NON-PORTABLE:END
this->balance-=amount;
to.balance+=amount;
return true;
}
Money Account::get_balance() const{
const std::lock_guard<decltype(this->lock)> guard{this->lock};
return this->balance;
}
void hammer_transfer(Account& from,Account& to,const Money amount, const int tries){
for(int i{1};i<=tries;++i){
from.transfer(to,amount);
}
}
int main() {
constexpr Money open_a{ 200000L};
constexpr Money open_b{ 100000L};
constexpr Money tran_ab{10};
constexpr Money tran_ba{3};
constexpr Money tran_aa{7};
Account A{open_a};
Account B{open_b};
std::cout << "A Open:" << A.get_balance() << '\n';
std::cout << "B Open:" << B.get_balance() << '\n';
constexpr long tries{20000};
std::thread TAB{hammer_transfer,std::ref(A),std::ref(B),tran_ab,tries};
std::thread TBA{hammer_transfer,std::ref(B),std::ref(A),tran_ba,tries};
std::thread TAA{hammer_transfer,std::ref(A),std::ref(A),tran_aa,tries};
TAB.join();
TBA.join();
TAA.join();
const auto close_a{A.get_balance()};
const auto close_b{B.get_balance()};
std::cout << "A Close:" << close_a<< '\n';
std::cout << "B Close:" << close_b<< '\n';
int errors{0};
if((close_a+close_b)!=(open_a+open_b)){
std::cout << "ERROR: Money Leaked!\n";
++errors;
}
if(close_a!=(open_a+tries*(tran_ba-tran_ab)) ||
close_b!=(open_b+tries*(tran_ab-tran_ba))
){
std::cout << "ERROR: 'Lost' Transaction(s)\n";
++errors;
}
if(errors==0){
std::cout << "* SUCCESS *\n";
}else{
std::cout << "** FAILED **\n";
}
std::cout << std::endl;
return 0;
}
Eseguibile qui: https://ideone.com/hAUfhM
Le ipotesi sono (e credo sufficienti - chiunque?) Che intptr_tesiste e che gli operatori relazionali su intptr_timplicano un Total Strict Ordering sui valori del puntatore che rappresentano.
Questo presunto ordinamento non è garantito e potrebbe essere meno portabile della non portabilità dell'ordinamento dei puntatori (ad esempio, se intptr_tè più largo del puntatore e non tutti i bit sono scritti).
Sono a conoscenza di alcuni riff diversi su questo e altri progetti. Voterò a favore di tutte le buone risposte anche se non portabili che identificano le loro ipotesi sull'implementazione e idealmente una piattaforma in cui si applicano e preferibilmente una in cui non lo fanno!
Risposte
tl; dr - puoi rendere portabile il confronto del puntatore originale in C ++ 20. Probabilmente dovrei avvolgere quel codice in un scoped_ordered_locko qualcosa del genere, perché il codice è ancora un po 'peloso.
Le ipotesi sono (e credo sufficienti - chiunque?) Che intptr_t esista e che gli operatori relazionali su intptr_t implichino un Total Strict Ordering sui valori quando si mantengono valori espressi da puntatori non nulli validi a std :: mutex.
Non proprio. Si fa sempre un ordine rigoroso totale sui valori interi. Il problema sorge quando la mappatura da intptr_ta puntatore è molti-a-uno (questo è il caso dell'esempio di indirizzo segmentato qui - cioè, TSO attivo intptr_tnon è sufficiente).
Anche il puntatore alla intptr_tmappatura deve essere iniettivo (non deve essere una biiezione, perché non ci interessa se alcuni intptr_tvalori sono inutilizzati / non rappresentano puntatori validi).
Ad ogni modo, è ovvio che possa esistere un ordine rigoroso totale sui puntatori : è solo specifico dell'implementazione. Gli indirizzi segmentati possono essere normalizzati o appiattiti, ecc.
Fortunatamente, viene fornito un appropriato ordinamento rigoroso definito dall'implementazione: dal funtore std::compare_three_waya 3 vie in C ++ 20 e dai funtori a 2 vie less, greaterecc. Prima di C ++ 20 (e forse anche in C ++ 20 ).
Non esiste un linguaggio equivalente per l' ordine totale rigoroso definito dall'implementazione sui puntatori nel testo sull'operatore dell'astronave - anche se compare_three_wayviene descritto come chiamandolo - o sugli altri operatori relazionali.
Questo sembra essere deliberata, in modo che gli operatori incorporate <, >,, <=, >=, e <=>non acquisiscono nuovi vincoli che potrebbero essere costosi su qualche piattaforma. In effetti, gli operatori relazionali a 2 vie sono descritti esplicitamente come un ordine parziale sui puntatori.
Quindi, questo dovrebbe essere identico al tuo codice originale, eccetto portabile:
const auto order = std::compare_three_way{}(&this->lock, &to.lock);
if(order == std::strong_ordering::less){
flock.lock();
tlock.lock();
} else if (order == std::strong_ordering::greater) {
tlock.lock();
flock.lock();
} else {
flock.lock();
}
Nota
a partire da C ++ 20 (e in particolare PDF: P1961R0 ), dice [ comparisons.general ]
Per i modelli
less,greater,less_equal, egreater_equal, le specializzazioni per qualsiasi tipo di puntatore producono un risultato coerente con l'ordine totale rigorosa applicazione definiti sopra puntatoriQuesto è un requisito più debole che consente loro di fornire un ordine parziale, a condizione che non sia mai in disaccordo con l'ordine totale. Non è ovvio se si tratta di un indebolimento deliberato o se intende solo dire che devono implementare lo stesso ordine totale definito altrove.
prima C ++ 20
lessecc fatto richiederebbe un ordine totale per questi funtori.
In ogni caso, se non hai accesso a C ++ 20 e compare_three_way, il tuo lessecc. È garantito per fornire l'ordine totale di cui hai bisogno. Basta non fare affidamento sugli operatori relazionali grezzi.
std :: lock () ha un deadlock incorporato che evita l'algoritmo.
https://en.cppreference.com/w/cpp/thread/lock
Una volta che inizi ad avere conflitti di blocco, hai perso con questo metodo e devi ripensare all'intera soluzione. E quasi tutti i blocchi provocano un cambio di contesto che costerà circa 20000 cicli ciascuno.
Di solito la maggior parte dei conti ha molti in entrata (negozi, accordi) o in uscita (pensioni, disoccupazione ecc.)
Una volta identificato l'account conteso, è possibile mettere in coda molte transazioni e quindi bloccare l'account contento ed eseguire le transazioni try_lock l'altro account, se il blocco ha esito positivo, la transazione viene eseguita. Prova il try_lock un paio di volte, quindi esegui lo scope_lock con entrambi i blocchi per il restante prendendo tutte le transazioni comuni per quei due.
Parte 2. Come posso garantire un ordinamento sicuro dei miei lucchetti poiché il confronto di puntatori che non si trovano nella stessa area è UB.
Aggiungi un ID univoco all'account e confronta invece su quello!
Questa è una risposta automatica per mostrare il codice modificato. Il merito è dovuto alla risposta accettata sopra. L'apprendimento per me è che dal momento che C ++ 14 std::less, std::greaterecc. Definiscono un totale rigoroso sui puntatori che è coerente con l'ordine parziale già definito da <ed >ecc.
Utilizzando questi modelli, questo codice è ora garantito per essere privo di deadlock. In C ++ 20 può essere reso più ordinato e potenzialmente più veloce con std::compare_three_way<>.
https://ideone.com/ekuf2f
#include <functional>
#include <iostream>
#include <mutex>
#include <thread>
typedef long Money; //In minor unit.
class Account {
public:
bool transfer(Account& to,const Money amount);
Money get_balance() const;
Account(const Money deposit=0) : balance{deposit} {}
private:
mutable std::mutex lock;
Money balance;
};
namespace{
std::less<void*> less{};
std::equal_to<void*> equal_to{};
}
bool Account::transfer(Account& to,const Money amount){
std::unique_lock<decltype(this->lock)> flock{this->lock,std::defer_lock};
std::unique_lock<decltype(to.lock)> tlock{to.lock,std::defer_lock};
if(less(&this->lock,&to.lock)){
flock.lock();
tlock.lock();
} else if(equal_to(&this->lock,&to.lock)) {
flock.lock();
} else {
tlock.lock();
flock.lock();
}
this->balance-=amount;
to.balance+=amount;
return true;
}
Money Account::get_balance() const{
const std::lock_guard<decltype(this->lock)> guard{this->lock};
return this->balance;
}
void hammer_transfer(Account& from,Account& to,const Money amount, const int tries){
for(int i{1};i<=tries;++i){
from.transfer(to,amount);
}
}
int main() {
constexpr Money open_a{ 200000L};
constexpr Money open_b{ 100000L};
constexpr Money tran_ab{10};
constexpr Money tran_ba{3};
constexpr Money tran_aa{7};
Account A{open_a};
Account B{open_b};
std::cout << "A Open:" << A.get_balance() << '\n';
std::cout << "B Open:" << B.get_balance() << '\n';
constexpr long tries{20000};
std::thread TAB{hammer_transfer,std::ref(A),std::ref(B),tran_ab,tries};
std::thread TBA{hammer_transfer,std::ref(B),std::ref(A),tran_ba,tries};
std::thread TAA{hammer_transfer,std::ref(A),std::ref(A),tran_aa,tries};
TAB.join();
TBA.join();
TAA.join();
const auto close_a{A.get_balance()};
const auto close_b{B.get_balance()};
std::cout << "A Close:" << close_a<< '\n';
std::cout << "B Close:" << close_b<< '\n';
int errors{0};
if((close_a+close_b)!=(open_a+open_b)){
std::cout << "ERROR: Money Leaked!\n";
++errors;
}
if(close_a!=(open_a+tries*(tran_ba-tran_ab)) ||
close_b!=(open_b+tries*(tran_ab-tran_ba))
){
std::cout << "ERROR: 'Lost' Transaction(s)\n";
++errors;
}
if(errors==0){
std::cout << "* SUCCESS *\n";
}else{
std::cout << "** FAILED **\n";
}
std::cout << std::endl;
return 0;
}