Évitement des blocages en commandant std :: mutex
Existe-t-il une implémentation portable de la logique d'évitement de blocage ici (voir la section marquée `` NON PORTABLE ''):
#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;
}
Exécutable ici: https://ideone.com/hAUfhM
Les hypothèses sont (et je pense suffisantes - n'importe qui?) Qui intptr_texistent et que les opérateurs relationnels intptr_timpliquent un ordre strict total sur les valeurs de pointeur qu'ils représentent.
Cet ordre supposé n'est pas garanti et pourrait être moins portable que la non-portabilité de l'ordre des pointeurs (par exemple, si intptr_test plus large que le pointeur et que tous les bits ne sont pas écrits).
Je suis au courant de certains riffs différents sur ce modèle et d'autres. Je vais voter pour toutes les bonnes réponses, même si elles ne sont pas portables, qui identifient leurs hypothèses sur la mise en œuvre et idéalement une plate-forme sur laquelle elles s'appliquent et de préférence une où elles ne le sont pas!
Réponses
tl; dr - vous pouvez rendre votre comparaison de pointeur d'origine portative en C ++ 20. J'emballerais probablement ce code dans un scoped_ordered_lockou quelque chose comme ça, parce que le code est encore un peu velu.
Les hypothèses sont (et je crois suffisant - n'importe qui?) Que intptr_t existe et que les opérateurs relationnels sur intptr_t impliquent un ordre strict total sur les valeurs lorsque des valeurs sont converties à partir de pointeurs non nuls valides vers std :: mutex.
Pas précisément. Vous ne disposez toujours d' un ordre strict totale sur les valeurs intégrales. Le problème se pose lorsque le mappage de intptr_tvers pointeur est plusieurs à un (c'est le cas de l'exemple d'adresse segmentée ici - c'est-à-dire que TSO activé intptr_tn'est pas suffisant).
Le pointeur vers le intptr_tmappage doit également être injectif (il n'est pas nécessaire que ce soit une bijection, car nous ne nous soucions pas si certaines intptr_tvaleurs sont inutilisées / ne représentent pas des pointeurs valides).
Quoi qu'il en soit, il est évident qu'un ordre strict total sur les pointeurs peut exister: il est juste spécifique à l'implémentation. Les adresses segmentées peuvent être normalisées ou aplaties, etc.
Heureusement, un ordre strict total défini par l'implémentation est fourni: par le foncteur 3 voies std::compare_three_wayen C ++ 20, et par les foncteurs 2 voies less, greateretc. avant C ++ 20 (et peut - être aussi en C ++ 20 ).
Il n'y a pas de langage équivalent sur l' ordre total strict défini par l' implémentation sur les pointeurs dans le texte sur l' opérateur du vaisseau spatial - même s'il compare_three_wayest décrit comme l'appelant - ou sur les autres opérateurs relationnels.
Cela semble être délibérée, de sorte que les opérateurs de BUILTIN <, >,, <=, >=et <=>ne pas acquérir de nouvelles contraintes qui pourraient être coûteux sur une plate - forme. En effet, les opérateurs relationnels bidirectionnels sont explicitement décrits comme un ordre partiel sur les pointeurs.
Donc, cela devrait être identique à votre code d'origine, sauf portable:
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();
}
Remarque
à partir de C ++ 20 (et spécifiquement PDF: P1961R0 ), [ comparisons.general ] dit
Pour les modèles
less,greater,less_equaletgreater_equal, les spécialisations pour tout type de pointeur donnent un résultat cohérent avec le strict ordre total défini par l'implémentation des pointeurs surIl s'agit d'une exigence plus faible qui leur permet de fournir une commande partielle, à condition qu'elle ne soit jamais en désaccord avec la commande totale. Il n'est pas évident qu'il s'agisse d'un affaiblissement délibéré ou qu'il vise seulement à dire qu'ils doivent mettre en œuvre le même ordre total défini ailleurs.
avant C ++ 20
less, etc. ont fait besoin d' un ordre total pour ces foncteurs.
Dans tous les cas, si vous n'avez pas accès à C ++ 20 et compare_three_way, vos lessetc. sont garantis de fournir la commande totale dont vous avez besoin. Ne vous fiez simplement pas aux opérateurs relationnels bruts.
std :: lock () a un algorithme intégré pour éviter les interblocages.
https://en.cppreference.com/w/cpp/thread/lock
Une fois que vous commencez à avoir des conflits de verrouillage, vous avez perdu avec cette méthode et devez repenser l'ensemble de la solution. Et presque tous les verrous provoquent un changement de contexte qui coûtera environ 20000 cycles chacun.
Habituellement, la plupart des comptes ont soit de nombreux entrants (magasins, arrangements) ou sortants (pensions, indemnités, etc.)
Une fois que vous avez identifié le compte concurrent, vous pouvez mettre en file d'attente un grand nombre de transactions, puis verrouiller le compte satisfait et exécuter les transactions en try_lock l'autre compte, si le verrouillage réussit la transaction est effectuée. Essayez le try_lock plusieurs fois, puis effectuez le scope_lock avec les deux verrous pour le reste en prenant toutes les transactions communes pour ces deux.
Partie 2. Comment puis-je garantir un ordre sûr de mes serrures, car comparer des pointeurs qui ne sont pas dans la même zone est UB.
Vous ajoutez un identifiant unique au compte et comparez-le à la place!
Ceci est une auto-réponse pour montrer le code révisé. Le crédit est dû à la réponse acceptée ci-dessus. L'apprentissage pour moi est que depuis C ++ 14 std::less, std::greateretc. définissent un total strict sur les pointeurs qui est cohérent avec l'ordre partiel déjà défini par <et >etc.
En utilisant ces modèles, ce code est désormais garanti sans blocage. En C ++ 20, il peut être rendu plus net et potentiellement plus rapide avec 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;
}