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?) Que intptr_t existe et que les opérateurs relationnels sur intptr_t impliquent 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_t est 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!
4 Réponses :
std :: lock () a un algorithme intégré pour éviter les interblocages.
C'est le cas et c'est l'un des «autres modèles» que je mentionne dans la question. Dûment voté. std::lock() n'est pas une solution miracle. À grande échelle (avec des niveaux élevés de contention), il peut s'avérer contre-productif et présenter des performances médiocres. Mais c'est certainement une solution valable.
@Persixty - il est toujours vrai que si vous connaissez les particularités de l'utilisation de certaines ressources par votre application, vous pouvez écrire un gestionnaire de ressources qui fait un meilleur travail qu'un gestionnaire de ressources à usage général qui, par exemple, fait partie de la bibliothèque standard . La question de conception est de savoir si le travail supplémentaire pour écrire le vôtre vaut le gain que vous en retirez ou si le code à usage général est assez bon.
Je suis d'accord. Il y a une réponse bienvenue à ce sujet. À faible contention, std::lock gagne parce que try_lock fonctionne massivement la première fois! À un verrouillage de contention relativement inégal, le verrouillage de contention, puis try-lock fonctionne mieux et à un verrouillage de contention extrêmement élevé et inégal, le goulot d'étranglement fonctionne mieux parce que vous n'obtenez jamais un verrou improductif sur le goulot d'étranglement. Mais la commande de serrure garantit également aucun verrouillage non productif et cette question est un jouet pour un boîtier symétrique. Je l'ai transformé en "jouet" de compte car il n'a pas besoin de beaucoup de fond!
Une fois que vous commencez à avoir des conflits de verrouillage, vous avez perdu avec cette méthode et vous 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 essayant de verrouiller 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!
Je suis d'accord. J'ai voté pour. Quand on regarde un cas réel d'utilisation d'une application on peut souvent l'exploiter mais un traitement asymétrique. J'ai travaillé sur un vrai système qui permettait de verrouiller le compte de prélèvement automatique puis de suivre les instructions du jour. Cela a fonctionné jusqu'à ce qu'il passe 24 heures sur 24, 7 jours sur 7 et qu'il soit bloqué en ligne pendant 2 heures par nuit si vous interrogiez le solde du compte DD. Une autre stratégie consiste à verrouiller les comptes non sollicités, puis à minimiser strictement le verrouillage «à chaud», mais à donner la possibilité d'équilibrer les demandes afin que tout le monde obtienne un débit. Toujours à la recherche d'un moyen portable de commander std::mutex .
@Persixty a ajouté une partie 2 pour répondre à votre question initiale.
Aussi d'accord. La question existe précisément à cause de l'UB. Dans une application de comptabilité réelle, nous pourrions utiliser le type de compte pour identifier la banque comme contestée et le client comme moins finalement le numéro de compte (qui existerait!) Comme bris d'égalité. Mais un ordre strict est excellent car il fonctionne (en principe) et minimise pratiquement le verrouillage improductif (ce que std::lock ne fait pas) et maximise le débit et l'utilisation sans faire d'hypothèses concernant la demande de verrous asymétriques. Que ne pas aimer? (à part l'UB!)
tl; dr - vous pouvez rendre votre comparaison de pointeur d'origine portative en C ++ 20. scoped_ordered_lock probablement ce code dans un scoped_ordered_lock ou quelque chose comme ça, car le code est encore un peu velu.
Les hypothèses sont (et je crois suffisantes - n'importe qui?) Que intptr_t existe et que les opérateurs relationnels sur intptr_t impliquent un Ordre strict total sur les valeurs lors de la détention de valeurs transtypées de pointeurs non nuls valides vers std :: mutex.
Pas précisément. Vous n'avez toujours un ordre strict totale sur les valeurs intégrales. Le problème se pose lorsque le mappage de intptr_t au pointeur est plusieurs à un (c'est le cas de l'exemple d'adresse segmentée ici - c'est-à-dire que TSO sur intptr_t n'est pas suffisant).
Le pointeur vers le mappage intptr_t doit également être injectif (il n'est pas nécessaire que ce soit une bijection, car nous ne nous soucions pas si certaines valeurs intptr_t 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: c'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_way en C ++ 20, et par les foncteurs à 2 voies less , greater etc. avant C ++ 20 (et peut - être également 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 à propos de l' opérateur du vaisseau spatial - même si compare_three_way est décrit comme l'appelant - ou sur les autres opérateurs relationnels.
Cela semble être délibéré, de sorte que les opérateurs intégrés < , > ,, <= , >= et <=> n'acquièrent pas de nouvelles contraintes qui pourraient être coûteuses sur certaines plates-formes. 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();
}
à 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 l'ordre total strict défini par l'implémentation sur les pointeurs
Il 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. exigeait un ordre total pour ces foncteurs.
Dans tous les cas, si vous n'avez pas accès à C ++ 20 et compare_three_way , vos less etc. sont assurés de fournir la commande totale dont vous avez besoin. Ne vous fiez simplement pas aux opérateurs relationnels bruts.
C'est donc un défaut de la norme que le pointeur compare ne soit pas écrit dans la documentation std :: compare_three_way? Même si je préférerais que la langue changée pour la comparaison soit autorisée par la normalisation des pointeurs lors de la comparaison.
Je pense qu'il est intentionnel que compare_three_way ait une sémantique de pointeur spéciale qui est omise de l' operator <=> . L'ordre strict total défini par l'implémentation est décrit comme "cohérent avec l'ordre partiel imposé par les opérateurs intégrés ... <=>" . C'est peut-être pour éviter de rendre les opérateurs plus chers sur les plates-formes avec des modèles de mémoire non plate.
Réponse héroïque. Je vais éditer pour clarifier la commande devant être projetée à nouveau sur void* . Je pense que vous pouvez vouloir dire std::compare_three_way{}(&this->lock, &to.lock) parce que fi et ti sont mes valeurs intptr_t qui, je pense encore, peuvent ne pas fonctionner. Malheureusement, mon projet est bloqué sur C ++ 14 et a du mal à activer même C ++ 17 pour tester std::has_unique_object_representations afin que le problème puisse être détecté. Mais voici votre solution wandbox.org/permlink/KnhFA1n4FUWYA0tP .
Oh tu as tout à fait raison, merci. J'ai un peu trop réduit votre exemple!
Je suis sûr que vous avez raison au sujet des dépenses. Les restrictions préexistantes sur les comparaisons de pointeurs existent sûrement pour ne pas entraîner une gestion de pointeur dé-normalisée inutile (bien que == doive) et le vaisseau spatial devrait suivre ce modèle (il ressemble à The Joker pour moi). Et ce modèle existe quand il est nécessaire (rarement). Je voterais toujours pour un esprit de modèle std::normalize .
vous pouvez rendre votre comparaison de pointeurs d'origine portative en C ++ 20 std::less donne un ordre total sur les pointeurs et existe depuis C ++ 98. Qu'est-ce que je manque?
std::less est défini pour utiliser < qui est explicitement défini comme fournissant un ordre partiel sur les pointeurs. Il peut en pratique être total sur les plates-formes avec des modèles de mémoire plate, mais il n'est pas garanti par la norme.
Si vous voulez que je voie votre commentaire, vous devez me @mentionner. Et std::less est explicitement défini comme fournissant un ordre total strict sur les pointeurs.
@LanguageLawyer - intéressant, la version eel.is précise que ces foncteurs sont cohérents avec le TSO, mais cela leur permet quand même d'implémenter le classement partiel. Je vais devoir faire plus de recherches et mettre à jour la réponse
La différence entre C ++ 17 et la formulation actuelle est que «défini par l'implémentation» a été ajouté et «ordre total strict sur les pointeurs» a été déplacé du paragraphe vers une définition distincte. cela leur permet toujours de mettre en œuvre la commande partielle Uhm, que voulez-vous dire? Si std::less viole d'une manière ou d'une autre les règles strictes d'ordre total, comment cela serait-il cohérent avec l'ordre total strict défini par l'implémentation sur les pointeurs?
Un ordre partiel peut être cohérent avec un ordre total, tant qu'il correspond à l'ordre total sur chaque paire où l'ordre partiel est défini. Un ordre total n'est qu'une extension d'un ordre partiel qui est en fait défini sur toutes les paires.
Je ne vois pas le paragraphe disant «Pour les modèles ... les spécialisations pour tout type de pointeur, pour les arguments pour lesquels la comparaison ordinaire n'est pas non spécifiée , donnent un résultat cohérent avec ...», ce qui signifie qu'elles donneront un résultat compatible avec ordre total strict pour chaque paire d'arguments. Pourriez-vous montrer un exemple comment obtenir un résultat cohérent avec un ordre total strict pour n'importe quelle paire de pointeurs sans toutefois fournir un ordre total strict pour tous les pointeurs?
Continuons cette discussion en chat .
Ceci est une auto-réponse pour afficher le code révisé. Le crédit est dû à la réponse acceptée ci-dessus. L'apprentissage pour moi est que puisque C ++ 14 std::less , std::greater , etc. 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<> .
#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;
}
Est-ce que cela répond à votre question? Verrouiller plusieurs mutex
Êtes-vous sûr que c'est une question de langue-avocat? Cherchez-vous des citations de la norme?
@cigien Oui. J'invite des réponses qui identifient leurs hypothèses dans ma tête qui nécessitent un peu de droit du langage pour identifier ce que la norme ne promet pas, par exemple, alors que
intptr_ta une relation d'ordre, il est très clair que la norme ne fait aucune promesse sur la sémantique.Ok, cela semble raisonnable. Je vérifie juste :)
@PasserBy Cela a déjà été donné comme réponse et voté pour. Mais comme mentionné, ce n'est pas une solution miracle.
Alors votre question est extrêmement sous-spécifiée. Vous demandez aux gens de deviner ce qui, dans votre esprit, constitue une réponse acceptable.
@PasserBy Je pense que je fais le contraire.
std::scoped_lockest définitivement une réponse valide. J'ai déjà voté pour «std :: lock». Mais de nombreuses questions en génie logiciel ont de nombreuses réponses qui ont des caractéristiques différentes et conviennent à différentes situations. N'oubliez pas que je ne sais même pas quelles sont les restrictions / caractéristiques de votre proposition. Donc, plutôt que d'avoir de longues questions et réponses si vous les mettez dans la réponse, c'est une bonne réponse. Même si cela ne me convient pas, cela peut convenir à d'autres.Ce n'est pas ainsi que fonctionne le stackoverflow. Ce n'est pas un forum de discussion, un wiki, un manuel ou une conférence. Vous avez une question bien spécifiée, et les gens répondent avec une solution qui la résout réellement. Si vous voulez des techniques de génie logiciel, vous cherchez peut- être softwareengineering.stackexchange.com .
@Passant. C'est ainsi que les propriétaires veulent que cela fonctionne «nous travaillons ensemble pour construire une bibliothèque de réponses détaillées à toutes les questions sur la programmation». stackoverflow.com/tour Si je pose une question précise, les gens commencent à vous dire que vous devriez faire autre chose. Vous comprenez que je ne peux pas gagner! Il y a toujours quelqu'un qui n'aime pas la question et qui commence par dire que c'est un «problème X / Y». Vous ne pouvez pas plaire à tout le monde et aujourd'hui je ne vous ai pas plu. Mes excuses. Aucun mal prévu.
@PasserBy Chaque fois que je pose des questions, j'obtiens une réponse similaire. Certains disent trop vague, certains disent trop précis. Même avec tous les faits, certaines questions ont des réponses multiples. J'ai déjà voté pour
std::locket bien sûrstd::scoped_lockne convient pas car la question est étiquetée c ++ 14 bien que bien sûr, elle puisse êtrestd::scoped_lockou je pourrais utiliser la version Boost en supposant que je veux l'inclure Boost que je n'ai pas mentionné non plus car je pouvais l'envisager! Une autre réponse valable."Vous comprenez que je ne peux pas gagner" , je pense que vous avez mal compris. Lorsque vous avez une réponse qui correspond à votre question, mais qui ne correspond pas à ce que vous avez en tête , vous sous-spécifiez.
std::lockest C ++ 11, mais il ne correspond pas à ce que vous voulez car "il peut être contre-productif et peut montrer de mauvaises performances" .@PasserBy Oui, mais de nombreuses réponses pourraient correspondre à ma question. Je ne sais pas encore. Bien sûr, la ligne d'en-tête est 'ordering std :: mutex' donc
std::lock,std::scoped_lockne correspondent pas à la question (ils évitent de trier). Mais dans un acte de bonne foi et dans l'espoir d'éviter les débats improductifs sur les mérites et la formulation des questions dans lesquels je vois Stackoverflow descendre trop souvent, je suis prêt à les accepter. Évidemment, ma tentative d'éviter le terrier du lapin a complètement échoué.