質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
マルチスレッド

マルチスレッドは、どのように機能がコンピュータによって実行したのかを、(一般的にはスレッドとして参照される)実行の複合的な共同作用するストリームへ区分することが出来ます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

544閲覧

c++でLock-free stackの仕組みを実装したがうまくいかない

tanakanata

総合スコア4

マルチスレッド

マルチスレッドは、どのように機能がコンピュータによって実行したのかを、(一般的にはスレッドとして参照される)実行の複合的な共同作用するストリームへ区分することが出来ます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

1クリップ

投稿2021/02/02 15:03

編集2021/02/03 09:10

c++11以降の標準ライブラリを用いてLock-free stackを実装したく、コードを書きましたが
どうもどこかでスタック構造が破綻しメモリアクセスエラーが発生してしまいます。
どこに問題があるのかご教授いただければと思います。

出力例

4 Segmentation fault

発生個所はコード中にコメントで示しています。
高確率で発生しますがたまに成功することにご注意ください。

該当のソースコード

c++

1#include <thread> 2#include <random> 3#include <atomic> 4#include <iostream> 5#include <vector> 6using namespace std; 7 8int main() 9{ 10 auto size = thread::hardware_concurrency(); 11 cout << size << endl; 12 vector<thread> worker(size); 13 union Item { 14 Item* next{}; 15 intptr_t value; 16 }; 17 18 atomic<Item*> pool; 19 for (auto& w : worker) { 20 w = thread{ [&] { 21 mt19937 engien(random_device{}()); 22 uniform_int_distribution<uint32_t> random; 23 for (int i = 0; i < 10000; ++i) { 24 // プールから未使用アイテムを取得もしくは新規作成 25 auto top = pool.load(memory_order_acquire); 26 Item* next; 27 do { 28 if (!top) { 29 top = new Item; 30 break; 31 } 32 next = top->next; // !ここでセグメンテーション違反! 33 } while (!pool.compare_exchange_weak(top, next)); 34 // 取得したアイテムを使用 35 top->value = random(engien); 36 // 使用済みアイテムをプールへ返却 37 auto old = pool.load(memory_order_relaxed); 38 do { 39 top->next = old; 40 } while (!pool.compare_exchange_weak(old, top)); 41 } 42 } }; 43 } 44 for (auto& w : worker) { 45 if (w.joinable())w.join(); 46 } 47 for (auto h = pool.load(); h;) { 48 auto tmp = h->next; 49 delete h; 50 h = tmp; 51 } 52 return 0; 53}

試したこと

  1. プールからアイテムを取得せずに毎回newした場合問題ありません。
  2. シングルスレッドで動かした場合問題ありません。
  3. Itemをstructにした場合エラーの発生位置がメモリ解放処理になります。

  ただし、その前にスタック構造が破綻しています。(自身を指すItemが現れる)
4. Item*ではなくただの整数値で同様に処理してちゃんと破綻しないか確認したが問題なかった。

c++

1int main() 2{ 3 auto size = thread::hardware_concurrency(); 4 cout << size << endl; 5 vector<thread> worker(size); 6 for (int i = 0; i < 12; ++i) { 7 atomic<intptr_t> pool; 8 for (auto& w : worker) { 9 w = thread{ [&] { 10 for (int i = 0; i < 10000; ++i) { 11 auto h = pool.load(memory_order_consume); 12 intptr_t next; 13 do { 14 next = h + 1; 15 } while (!pool.compare_exchange_weak(h, next)); 16 auto o = pool.load(memory_order_relaxed); 17 do { 18 h = o - 1; 19 } while (!pool.compare_exchange_weak(o, h)); 20 } 21 } }; 22 } 23 for (auto& w : worker) { 24 if (w.joinable())w.join(); 25 } 26 cout << pool << endl; // 0であること 27 } 28 return 0; 29}

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

yohhoy

2021/02/03 07:18

FYI: 本題から外れますが、memory_order_consumeは非推奨となっており利用は避けたほうがよいです。MemoryOrder指定をしたければココはacquireで代替可能です。https://ja.cppreference.com/w/cpp/atomic/memory_order#Release-Consume_ordering (CPUアーキテクチャによっては、どれを指定しても結局は同じ命令になることもありますケド)
tanakanata

2021/02/03 09:10

ありがとうございます。
guest

回答1

0

自己解決

ポインタ単体だけでなく追加データとセットでCAS操作することで解決しました。

投稿2021/02/02 19:19

tanakanata

総合スコア4

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問