ロックベースのプログラムが正しいスレッドセーフフラグメントを構成しないのはなぜですか？

Question

ティム・ハリスは言った：

https://en.wikipedia.org/wiki/Software_transactional_memory#Composable_operations

をおそらく最も基本的な反論[...]は、ロックベース プログラムが構成されていないということです：組み合わせたときに正しいフラグメントが失敗することがあります。 の例では、スレッドセーフの挿入と削除を伴うハッシュテーブルを考えて、 オペレーションを削除してください。テーブル t1から1つのアイテムAを削除し、それをテーブルt2に挿入するとします。中間状態（ のどちらのテーブルにも項目が含まれていない）は、他のスレッドから見えてはならない。 ハッシュテーブルの実装者がこの必要性を予期しない限り、 は単にこの要件を満たす方法ではありません。 [...]簡潔に言えば、 の操作は個別に正しい（挿入、削除）ことはできません より大きな正しい操作に構成されています。 - Tim Harris他、 「合成可能メモリトランザクション」、セクション2：背景、ページ2 [6]

この意味は？私は2つのハッシュマップstd::unordered_mapと2つのミューテックスstd::mutex（各ハッシュマップに1つ）を持っている場合は

その後、私は単純にロックすることができ、その両方：http://ideone.com/6RSNyN

#include <iostream> 
#include <string> 
#include <mutex> 
#include <thread> 
#include <chrono> 
#include <unordered_map> 

std::unordered_map<std::string, std::string> map1 ({{"apple","red"},{"lemon","yellow"}}); 
std::mutex mtx1; 

std::unordered_map<std::string, std::string> map2 ({{"orange","orange"},{"strawberry","red"}}); 
std::mutex mtx2; 

void func() { 
    std::lock_guard<std::mutex> lock1(mtx1); 
    std::lock_guard<std::mutex> lock2(mtx2); 

    std::cout << "map1: "; 
    for (auto& x: map1) std::cout << " " << x.first << " => " << x.second << ", "; 
    std::cout << std::endl << "map2: "; 
    for (auto& x: map2) std::cout << " " << x.first << " => " << x.second << ", "; 
    std::cout << std::endl << std::endl; 

    auto it1 = map1.find("apple"); 
    if(it1 != map1.end()) { 
     auto val = *it1; 
     map1.erase(it1); 
     std::this_thread::sleep_for(std::chrono::duration<double, std::milli>(1000)); 
     map2[val.first] = val.second; 
    } 
} 

int main() 
{ 
    std::thread t1(func); 
    std::this_thread::sleep_for(std::chrono::duration<double, std::milli>(500)); 
    std::thread t2(func); 
    t1.join(); 
    t2.join(); 

    return 0; 
} 

私は自分自身、スレッドセーフなハッシュマップmy_unordered_mapを実装する場合その後、私はそのようなことを実施します：

template<typename key, template val> 
class my_unordered_map { 
    std::recursive_mutex mtx_ptr; 
    void lock() { mtx_ptr->lock(); } 
    void unlock() { mtx_ptr->unlock(); } 
    template<typename mutex_type> friend class std::lock_guard; 
public: 
// .. all required public methods which lock recursive mutex before do anything 
    void insert(key k, val v) { std::lock_guard<std::recursive_mutex> lock(mtx); /* do insert ... */ } 
    // ... 
}; 

そして、このような使用します。

my_unordered_map<std::string, std::string> map1 ({{"apple","red"},{"lemon","yellow"}}); 

my_unordered_map<std::string, std::string> map2 ({{"orange","orange"},{"strawberry","red"}}); 

void func() { 
    std::lock_guard<my_unordered_map> lock1(map1); 
    std::lock_guard<my_unordered_map> lock2(map2); 

    // work with map1 and map2 
    // recursive_mutex allow multiple locks in: lock1(map1) and map1->at(key) 
} 

を

同様にmap1とmap2の両方に対して、スレッドセーフなコードと完全にシーケンシャルな一貫性が得られます。

しかし、これはどのような場合に言われましたか？

おそらく最も基本的な反論[...]は、ロックベース プログラムが構成されていないということです：組み合わせたときに正しいフラグメントが失敗することがあります。

Answer 1

あなた自身のプログラムは完全に上質です。

別のプログラムは、別のスレッドで別のタスクのために、

void func_other() { 
    std::lock_guard<my_unordered_map> lock2(map2); 
    std::lock_guard<my_unordered_map> lock1(map1); 

    // work with map1 and map2 
} 

のようなものはやはり、これは自分自身で、結構です代わりに使用する場合があります。

しかし、両方のプログラムを同時に実行すると、デッドロックが発生する可能性があります。スレッド1はマップ1をロックし、スレッド2はマップ2をロックし、両方のスレッドの次のロックは永遠に待機します。

私たちは2つのプログラムを簡単に構成することはできません。

ロックの代わりにSTMを使用すると、そのような種類の構成が（あるパフォーマンス価格で）常に許可されます。

Answer 2

挿入と消去のスレッドセーフアトミック操作は、通常、それらの内部にミューテックスを隠します。これにより、ロックしないでアクセスできなくなります。

あなたのケースでは、代わりにミューテックスを公開します。これには、すべてのユーザが適切にmutexを争奪する必要があります。

mutexesに完全にアクセスすると、安全に中間の状態を見ることができます。std::lockを使用しないためコードが失敗するため、mutexのロック順序がグローバルに一貫しています。異なるロック順序。

この種の問題は、あなたのトランザクションに必要なミューテックスを常に把握しておかなければならない場合、小さくて簡単に正しい部分を特定することができます。正しさは非ローカルになり、複雑さが爆発し、バグがたくさんあります。