Evitación de interbloqueo ordenando std :: mutex
¿Existe una implementación portátil de la lógica de evitación de interbloqueo aquí (consulte la sección marcada como "NO PORTÁTIL"):
#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;
}
Ejecutable aquí: https://ideone.com/hAUfhM
Las suposiciones son (y creo que suficientes, ¿alguien?) Que intptr_texisten y que los operadores relacionales intptr_timplican un Orden estricto total en los valores de puntero que representan.
Esa ordenación asumida no está garantizada y podría ser menos portátil que la no portabilidad de la ordenación de punteros (por ejemplo, si intptr_tes más ancho que el puntero y no se escriben todos los bits).
Soy consciente de algunos riffs diferentes de este y otros diseños. ¡Votaré todas las buenas respuestas, incluso si no son portátiles, que identifiquen sus suposiciones sobre la implementación e idealmente una plataforma donde se apliquen y preferiblemente una donde no!
Respuestas
tl; dr : puede hacer que su comparación de punteros original sea portátil en C ++ 20. Probablemente envolvería ese código en un scoped_ordered_locko algo así, porque el código todavía es un poco complicado.
Las suposiciones son (y creo que suficientes, ¿alguien?) Que intptr_t existe y que los operadores relacionales en intptr_t implican un Orden estricto total en los valores cuando se mantienen valores emitidos desde punteros válidos no nulos a std :: mutex.
No precisamente. Usted no siempre tiene un orden estricto en el total de los valores integrales. El problema surge cuando la asignación de intptr_tun puntero es de varios a uno (este es el caso del ejemplo de dirección segmentada aquí , es decir, TSO activado intptr_tno es suficiente).
El puntero al intptr_tmapeo también debe ser inyectivo (no tiene que ser una biyección, porque no nos importa si algunos intptr_tvalores no se utilizan / no representan punteros válidos).
De todos modos, es obvio que puede existir un orden estricto total de punteros : es solo una implementación específica. Las direcciones segmentadas se pueden normalizar o aplanar, etc.
Afortunadamente, se proporciona un orden estricto total definido por la implementación adecuado: por el functor de 3 vías std::compare_three_wayen C ++ 20, y por los functores de 2 vías less, greateretc. antes de C ++ 20 (y tal vez también en C ++ 20 ).
No existe un lenguaje equivalente sobre el orden total estricto definido por la implementación sobre los punteros en el texto sobre el operador de la nave espacial , aunque compare_three_wayse describa como llamando a eso, o sobre los otros operadores relacionales.
Esto parece ser deliberada, de modo que los operadores incorporados <, >,, <=, >=, y <=>no adquieren nuevas restricciones que podrían ser caros en alguna plataforma. De hecho, los operadores relacionales bidireccionales se describen explícitamente como un orden parcial en los punteros.
Entonces, esto debería ser idéntico a su código original, excepto portátil:
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 partir de C ++ 20 (y específicamente PDF: P1961R0 ), [ comparisons.general ] dice
Para las plantillas
less,greater,less_equal, ygreater_equal, las especializaciones para cualquier tipo de puntero producen un resultado consistente con la orden total estricto definido por la implementación más punterosEste es un requisito más débil que les permite proporcionar un pedido parcial, siempre que nunca esté en desacuerdo con el pedido total. No es obvio si se trata de un debilitamiento deliberado o solo pretende decir que deben implementar el mismo orden total definido en otra parte.
antes de C ++ 20,
lessetc. , requería un orden total para estos functores.
En cualquier caso, si no tiene acceso a C ++ 20 y compare_three_way, se garantiza que su lessetc. proporcionará el pedido total que necesita. Simplemente no confíe en los operadores relacionales en bruto.
std :: lock () tiene un algoritmo de evitación de interbloqueo incorporado.
https://en.cppreference.com/w/cpp/thread/lock
Una vez que empiece a tener problemas de bloqueo, ha perdido con este método y necesita reconsiderar toda la solución. Y casi todos los bloqueos provocan un cambio de contexto que costará alrededor de 20000 ciclos cada uno.
Por lo general, la mayoría de las cuentas tienen muchos ingresos (tiendas, acuerdos) o salientes (pensiones, subsidios, etc.)
Una vez que haya identificado la cuenta en disputa, puede poner en cola muchas transacciones y luego bloquear la cuenta contenta y ejecutar las transacciones probando_bloquear la otra cuenta, si el bloqueo tiene éxito, la transacción se realiza. Pruebe el try_lock un par de veces y luego haga el scope_lock con ambos bloqueos para el resto tomando todas las transacciones comunes para esos dos.
Parte 2. ¿Cómo puedo asegurar un pedido seguro de mis candados si comparo punteros que no están en la misma área es UB?
¡Agrega una identificación única a la cuenta y compara en su lugar!
Esta es una auto-respuesta para mostrar el código revisado. El crédito se debe a la respuesta aceptada arriba. El aprendizaje para mí es que desde C ++ 14 std::less, std::greateretc., defina un total estricto en punteros que sea consistente con el orden parcial ya definido por <y >etc.
Al usar esas plantillas, ahora se garantiza que este código está libre de interbloqueos. En C ++ 20 se puede hacer más ordenado y potencialmente más rápido 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;
}