c/c++マルチスレッドプログラミングとロックされていないデータ構造の漫談

本文は主にc/c++に対して、システムは主にlinuxに対して.本文は他人の資料を引用してすべて引用段落で声明する.
シーン:
thread...1...2...3...:マルチスレッド遍歴
thread...a...b...c...:マルチスレッド挿入削除の変更
周知のstlはマルチスレッドで安全ではない.なぜstlはスレッドの安全なデータ構造を提供しないのですか?この問題は、stlが性能の卓越性を追求している可能性があり、コンテナデータ構造のスレッドセキュリティが複雑すぎると推測するしかありません.
ネット上でよく見られるスレッドセキュリティの研究は、最もsimpleのqueueタイプに対するコンテナである.なぜよくあるshow理論の実力のブログはqueueタイプのデータ構造に対してですか?おそらくqueueは反復遍歴に関与しないので、この原因は頼りになると思います.マルチスレッドによるqueueの操作は、一般的にマルチスレッドがqueueに対してpopとpushを同時に行う.1つまたは複数のスレッド読み取り専用(query)、もう1つまたは複数のスレッド書き込み操作(更新、削除、挿入)には関与しません.後者の需要は、実現するのが難しい.
では、queueタイプのデータ構造がlock-free操作をどのようにしているかについてお話ししましょう.
lock-free queue
CAS操作文
lock-free queueはいずれもCAS操作に基づいてロックなしを実現している.CASはcompare-and-swapの略で、比較交換を意味します.CAS命令にはCPUとコンパイラのサポートが必要であり、現在のCPUの多くはCAS命令をサポートしている.GCCコンパイラの場合はGCC 4が必要です.1.0またはバージョンを更新します.CASのGCCでの実装には2つの原子操作がある.ほとんどのロックされていないデータ構造では、boolが現在の原子操作が成功したかどうかを示し、後者の戻り値が値タイプである次の2つの関数の前者が使用されています.

bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)

以下のマクロ定義で、独自のCAS関数を定義します.

/// @brief Compare And Swap
///        If the current value of *a_ptr is a_oldVal, then write a_newVal into *a_ptr
/// @return true if the comparison is successful and a_newVal was written
#define CAS(a_ptr, a_oldVal, a_newVal) __sync_bool_compare_and_swap(a_ptr, a_oldVal, a_newVal)

次の2つの段落は、このブログの説明を参照してください(元のブログを読むことをお勧めします.理解に役立ちます.しかし、このコードを商用化しないでください.バグがあり、map、listなどは適用されません)、CASキューの出入り操作については、読者に強くお勧めします.

EnQueue(x) //   
{
    //          
    q = new record();
    q->value = x;
    q->next = NULL;
 
    do {
        p = tail; //         
    } while( CAS(p->next, NULL, q) != TRUE); //             ，  
 
    CAS(tail, p, q); //    
}

プログラムのdo-whileのRe-try-Loopを見ることができます.つまり、キューの最後にノードを追加する準備をしている間に、他のスレッドが成功したので、tailポインタが変わった可能性が高いので、私のCASはfalseに戻り、プログラムは成功するまで再試行しました.これは私たちの電話ホットラインの再放送が止まらない状況に似ています.
なぜ私たちの「置尾結点」の操作(12行目)が成功したかどうかを判断しないのかを見ることができます.なぜなら、
1、スレッドT 1がある場合、そのwhileのCASが成功すれば、その後のスレッドのCASはすべて失敗し、再循環します.
2、このとき、T 1スレッドがtailポインタを更新していない場合、tail->nextがNULLではないため、他のスレッドは失敗し続けます.
3、T 1スレッドがtailポインタを更新するまで、他のスレッドのいずれかのスレッドが新しいtailポインタを得ることができ、下に進み続けます.
T 1スレッドがCASでtailポインタを更新する前にスレッドが停止または停止した場合、他のスレッドはデッドサイクルに入るという潜在的な問題があります.以下は改良版のEnQueue()

EnQueue(x) //      
{
    q = new record();
    q->value = x;
    q->next = NULL;
 
    p = tail;
    oldp = p
    do {
        while (p->next != NULL)
            p = p->next;
    } while( CAS(p.next, NULL, q) != TRUE); //           ，  
 
    CAS(tail, oldp, q); //    
}

各スレッドに、自分のfetchポインタpをチェーンテーブルの最後にします.しかし、このようなfetchは性能に影響します.実際の状況から見ると、99.9%の場合、スレッドが停止することはありません.そのため、上記の2つのバージョンに接続して、retryの回数が1つの値を超えた場合(例えば3回)、自分のfetchポインタを合わせることができます.
EnQueueを解決しました.DeQueueのコードを見てみましょう.

DeQueue() //   
{
    do{
        p = head;
        if (p->next == NULL){
            return ERR_EMPTY_QUEUE;
        }
    while( CAS(head, p, p->next) != TRUE );
    return p->next->value;
}

汎用ロックフリーデータ構造について
読者がc言語で実装されたカスタムチェーンテーブルなどの構造である場合、本節の内容はC++関連であるため、本節の汎用ロックフリーデータ構造に関する説明を参照する必要はありません.
シナリオ1:stl+ロック
stl/boost+ロックは最も一般的なスキームの1つです.要件が満たされている場合(1つのライトスレッド、複数のリードスレッド)、boost::shared_mutex.
方案二:TBB
TBBライブラリは他の多くのIntelのライブラリと同じように、有名ではありません.TBBはThreading BuildingBlocks@Intelの双曲線コサインを返します.
TBBの同時コンテナは以下の方法で高度な並列操作を行う:細粒度ロック(Fine-grained locking):細粒度ロックを使用して、コンテナ上のマルチスレッド操作は同じ位置に同時にアクセスする時だけロックされ、異なる位置に同時にアクセスする場合は並列に処理することができる.ロックフリーアルゴリズム(Lock-free algorithms):ロックフリーアルゴリズムを使用して、他のスレッドとの相互影響を評価し、修正します.std::mapと同様にconcurrent_hash_mapもstd::pairの容器です.競合を回避するために、ハッシュ・テーブルのセル・データを直接格納するのではなく、accessorまたはconst_を使用します.accessor. accessorはstd::pairのスマートポインタであり、ハッシュ・リスト内の各ユニットの更新を担当し、1つのユニットを指す限り、他のユニットに対する操作はaccessorが完了するまでロックされます.const_アクセスは似ていますが、読み取り専用で、複数のconst_accessorは同じユニットを指すことができ、これは頻繁な読み取りと少量の更新の場合に同時性を極めて向上させることができる.
以下のコードはTBBのsampleの中のconcurrent_ですhash_map使用例

/*
    Copyright 2005-2014 Intel Corporation.  All Rights Reserved.

    This file is part of Threading Building Blocks. Threading Building Blocks is free software;
    you can redistribute it and/or modify it under the terms of the GNU General Public License
    version 2  as  published  by  the  Free Software Foundation.  Threading Building Blocks is
    distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
    implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
    See  the GNU General Public License for more details.   You should have received a copy of
    the  GNU General Public License along with Threading Building Blocks; if not, write to the
    Free Software Foundation, Inc.,  51 Franklin St,  Fifth Floor,  Boston,  MA 02110-1301 USA

    As a special exception,  you may use this file  as part of a free software library without
    restriction.  Specifically,  if other files instantiate templates  or use macros or inline
    functions from this file, or you compile this file and link it with other files to produce
    an executable,  this file does not by itself cause the resulting executable to be covered
    by the GNU General Public License. This exception does not however invalidate any other
    reasons why the executable file might be covered by the GNU General Public License.
*/

// Workaround for ICC 11.0 not finding __sync_fetch_and_add_4 on some of the Linux platforms.
#if __linux__ && defined(__INTEL_COMPILER)
#define __sync_fetch_and_add(ptr,addend) _InterlockedExchangeAdd(const_cast(reinterpret_cast(ptr)), addend)
#endif
#include 
#include 
#include 
#include 
#include 
#include "tbb/concurrent_hash_map.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"
#include "tbb/tick_count.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/tbb_allocator.h"
#include "../../common/utility/utility.h"


//! String type with scalable allocator.
/** On platforms with non-scalable default memory allocators, the example scales 
    better if the string allocator is changed to tbb::tbb_allocator. */
typedef std::basic_string,tbb::tbb_allocator > MyString;

using namespace tbb;
using namespace std;

//! Set to true to counts.
static bool verbose = false;
static bool silent = false;
//! Problem size
long N = 1000000;
const int size_factor = 2;

//! A concurrent hash table that maps strings to ints.
typedef concurrent_hash_map StringTable;

//! Function object for counting occurrences of strings.
struct Tally {
    StringTable& table;
    Tally( StringTable& table_ ) : table(table_) {}
    void operator()( const blocked_range range ) const {
        for( MyString* p=range.begin(); p!=range.end(); ++p ) {
            StringTable::accessor a;
            table.insert( a, *p );
            a->second += 1;
        }
    }
};

static MyString* Data;

static void CountOccurrences(int nthreads) {
    StringTable table;

    tick_count t0 = tick_count::now();
    parallel_for( blocked_range( Data, Data+N, 1000 ), Tally(table) );
    tick_count t1 = tick_count::now();

    int n = 0;
    for( StringTable::iterator i=table.begin(); i!=table.end(); ++i ) {
        if( verbose && nthreads )
            printf("%s %d
",i->first.c_str(),i->second);
        n += i->second;
    }

    if ( !silent ) printf("total = %d  unique = %u  time = %g
", n, unsigned(table.size()), (t1-t0).seconds());
}

/// Generator of random words

struct Sound {
    const char *chars;
    int rates[3];// begining, middle, ending
};
Sound Vowels[] = {
    {"e", {445,6220,1762}}, {"a", {704,5262,514}}, {"i", {402,5224,162}}, {"o", {248,3726,191}},
    {"u", {155,1669,23}}, {"y", {4,400,989}}, {"io", {5,512,18}}, {"ia", {1,329,111}},
    {"ea", {21,370,16}}, {"ou", {32,298,4}}, {"ie", {0,177,140}}, {"ee", {2,183,57}},
    {"ai", {17,206,7}}, {"oo", {1,215,7}}, {"au", {40,111,2}}, {"ua", {0,102,4}},
    {"ui", {0,104,1}}, {"ei", {6,94,3}}, {"ue", {0,67,28}}, {"ay", {1,42,52}},
    {"ey", {1,14,80}}, {"oa", {5,84,3}}, {"oi", {2,81,1}}, {"eo", {1,71,5}},
    {"iou", {0,61,0}}, {"oe", {2,46,9}}, {"eu", {12,43,0}}, {"iu", {0,45,0}},
    {"ya", {12,19,5}}, {"ae", {7,18,10}}, {"oy", {0,10,13}}, {"ye", {8,7,7}},
    {"ion", {0,0,20}}, {"ing", {0,0,20}}, {"ium", {0,0,10}}, {"er", {0,0,20}}
};
Sound Consonants[] = {
    {"r", {483,1414,1110}}, {"n", {312,1548,1114}}, {"t", {363,1653,251}}, {"l", {424,1341,489}},
    {"c", {734,735,260}}, {"m", {732,785,161}}, {"d", {558,612,389}}, {"s", {574,570,405}},
    {"p", {519,361,98}}, {"b", {528,356,30}}, {"v", {197,598,16}}, {"ss", {3,191,567}},
    {"g", {285,430,42}}, {"st", {142,323,180}}, {"h", {470,89,30}}, {"nt", {0,350,231}},
    {"ng", {0,117,442}}, {"f", {319,194,19}}, {"ll", {1,414,83}}, {"w", {249,131,64}},
    {"k", {154,179,47}}, {"nd", {0,279,92}}, {"bl", {62,235,0}}, {"z", {35,223,16}},
    {"sh", {112,69,79}}, {"ch", {139,95,25}}, {"th", {70,143,39}}, {"tt", {0,219,19}},
    {"tr", {131,104,0}}, {"pr", {186,41,0}}, {"nc", {0,223,2}}, {"j", {184,32,1}},
    {"nn", {0,188,20}}, {"rt", {0,148,51}}, {"ct", {0,160,29}}, {"rr", {0,182,3}},
    {"gr", {98,87,0}}, {"ck", {0,92,86}}, {"rd", {0,81,88}}, {"x", {8,102,48}},
    {"ph", {47,101,10}}, {"br", {115,43,0}}, {"cr", {92,60,0}}, {"rm", {0,131,18}},
    {"ns", {0,124,18}}, {"sp", {81,55,4}}, {"sm", {25,29,85}}, {"sc", {53,83,1}},
    {"rn", {0,100,30}}, {"cl", {78,42,0}}, {"mm", {0,116,0}}, {"pp", {0,114,2}},
    {"mp", {0,99,14}}, {"rs", {0,96,16}}, /*{"q", {52,57,1}},*/ {"rl", {0,97,7}},
    {"rg", {0,81,15}}, {"pl", {56,39,0}}, {"sn", {32,62,1}}, {"str", {38,56,0}},
    {"dr", {47,44,0}}, {"fl", {77,13,1}}, {"fr", {77,11,0}}, {"ld", {0,47,38}},
    {"ff", {0,62,20}}, {"lt", {0,61,19}}, {"rb", {0,75,4}}, {"mb", {0,72,7}},
    {"rc", {0,76,1}}, {"gg", {0,74,1}}, {"pt", {1,56,10}}, {"bb", {0,64,1}},
    {"sl", {48,17,0}}, {"dd", {0,59,2}}, {"gn", {3,50,4}}, {"rk", {0,30,28}},
    {"nk", {0,35,20}}, {"gl", {40,14,0}}, {"wh", {45,6,0}}, {"ntr", {0,50,0}},
    {"rv", {0,47,1}}, {"ght", {0,19,29}}, {"sk", {23,17,5}}, {"nf", {0,46,0}},
    {"cc", {0,45,0}}, {"ln", {0,41,0}}, {"sw", {36,4,0}}, {"rp", {0,36,4}},
    {"dn", {0,38,0}}, {"ps", {14,19,5}}, {"nv", {0,38,0}}, {"tch", {0,21,16}},
    {"nch", {0,26,11}}, {"lv", {0,35,0}}, {"wn", {0,14,21}}, {"rf", {0,32,3}},
    {"lm", {0,30,5}}, {"dg", {0,34,0}}, {"ft", {0,18,15}}, {"scr", {23,10,0}},
    {"rch", {0,24,6}}, {"rth", {0,23,7}}, {"rh", {13,15,0}}, {"mpl", {0,29,0}},
    {"cs", {0,1,27}}, {"gh", {4,10,13}}, {"ls", {0,23,3}}, {"ndr", {0,25,0}},
    {"tl", {0,23,1}}, {"ngl", {0,25,0}}, {"lk", {0,15,9}}, {"rw", {0,23,0}},
    {"lb", {0,23,1}}, {"tw", {15,8,0}}, /*{"sq", {15,8,0}},*/ {"chr", {18,4,0}},
    {"dl", {0,23,0}}, {"ctr", {0,22,0}}, {"nst", {0,21,0}}, {"lc", {0,22,0}},
    {"sch", {16,4,0}}, {"ths", {0,1,20}}, {"nl", {0,21,0}}, {"lf", {0,15,6}},
    {"ssn", {0,20,0}}, {"xt", {0,18,1}}, {"xp", {0,20,0}}, {"rst", {0,15,5}},
    {"nh", {0,19,0}}, {"wr", {14,5,0}}
};
const int VowelsNumber = sizeof(Vowels)/sizeof(Sound);
const int ConsonantsNumber = sizeof(Consonants)/sizeof(Sound);
int VowelsRatesSum[3] = {0,0,0}, ConsonantsRatesSum[3] = {0,0,0};

int CountRateSum(Sound sounds[], const int num, const int part)
{
    int sum = 0;
    for(int i = 0; i < num; i++)
        sum += sounds[i].rates[part];
    return sum;
}

const char *GetLetters(int type, const int part)
{
    Sound *sounds; int rate, i = 0;
    if(type & 1)
        sounds = Vowels, rate = rand() % VowelsRatesSum[part];
    else
        sounds = Consonants, rate = rand() % ConsonantsRatesSum[part];
    do {
        rate -= sounds[i++].rates[part];
    } while(rate > 0);
    return sounds[--i].chars;
}

static void CreateData() {
    for(int i = 0; i < 3; i++) {
        ConsonantsRatesSum[i] = CountRateSum(Consonants, ConsonantsNumber, i);
        VowelsRatesSum[i] = CountRateSum(Vowels, VowelsNumber, i);
    }
    for( int i=0; i