ロックレスキューC実装

エンキュー

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に戻り、プログラムは成功するまで再試行しました.これは私たちの電話ホットラインの再放送が止まらない状況に似ています.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); //    
}

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

ABA問題
ABA(ウィキペディアのABAの見出しを参照)とは、問題の基本はこのようなものです.

プロセスP 1は、共有変数において値A

を読み出す.

2 P 1がプリエンプトされ、プロセスP 2は

を実行する.

P 2共有変数の値をAからBに変更してAに戻すと、P 1に奪われます.

4 P 1が戻ってきて、共有変数の値が変更されていないのを見て、実行を続けます.

P 1は変数値が変化していないと考えて実行を続けたが,これはいくつかの潜在的な問題を引き起こす.ABA問題はlock freeのアルゴリズムで最も起こりやすい.CASはポインタのアドレスを判断しているからだ.もしこのアドレスが再利用されたら、問題は大きいです.(アドレスの再利用はよくありますが、1つのメモリが割り当てられて解放され、再割り当てされ、元のアドレスになる可能性が高いです)
たとえば、上記のDeQueue()関数は、headとtailを分離するため、headにdummyポインタを導入しています.CASをする前に、headのメモリが回収されて再利用され、再利用されたメモリがEnQueue()に入ってくると、大きな問題があります.(メモリ管理でメモリを再利用するのは基本的によくある動作です)
シンプルな実装
次に、チェーンテーブルデータ構造を使用し、ABAの問題を考慮しない簡単なロックレスキューを実現する.

/*lock_free.h*/
#ifndef _LOCK_FREE_H_
#define _LOCK_FREE_H_    
#include 
#include 
#include 
typedef struct node_s node_t;
struct node_s {
    node_t *next;
    void *data;
};
node_t *create_queue();
node_t *enqueue(void * d);
void* dequeue();
#endif

/*lock_free.c*/
#include "lock_free.h"
node_t *head = NULL;
node_t *tail = NULL;
node_t *create_queue()
{
    if (head != NULL)
        return head;
    head = (node_t*)malloc(sizeof(node_t));
    if (!head) {
        fprintf(stderr, "malloc error
");
        return NULL;
    }
    head->next = NULL;
    head->data = NULL;
    tail = head;
    return head;
}
node_t* enqueue(void *d)
{
    node_t *p = (node_t*)malloc(sizeof(node_t));
    if (!p) {
        fprintf(stderr, "malloc error
");
        return NULL;
    }
    p->next = NULL;
    p->data = d;
    node_t *q;
    do {
        q = tail;
    } while (!__sync_bool_compare_and_swap(&(q->next), NULL, p));
    __sync_bool_compare_and_swap(&tail, q, p);
    return p;
}
void* dequeue()
{
    node_t *p;
    void *res;
    do {
        p = head;
        if (p->next == NULL)
            return NULL;
         res = p->next->data;
    } while(!__sync_bool_compare_and_swap(&head, p, p->next));
    /* 
                   ，
             ，    1    head         ，
                 ，     1            
    */
    if (p) {
        free(p);
        p = NULL;
    }
    return res;
}

/*main.c*/
#include "lock_free.h"
#include 
#include 
void *entry(void *data);
int main()
{
    if (!create_queue()) {
        fprintf(stderr, "create queue error
");
        exit(1);
    }
    int i;
    pthread_t pid;
    for (i = 0; i < 4; i ++) {
        if (0 != pthread_create(&pid, NULL, entry, NULL)) {
            perror("pthread create error
");
        }
    }
    getchar();
    return 0;
}
void *entry(void *data)
{
    char str[64] = {0};
    char *dst = NULL;
    sprintf(str, "%lu", pthread_self());
    int i;
    for (i = 0; i < 4; i ++) {
        dst = (char*)malloc(128);
        memset(dst, 0, 128);
        sprintf(dst, "%s-%c", str, i + 65);
        if (!enqueue((void *)(dst))) {
            fprintf(stderr, "enqueue error
");
            break;
        }   
    }
    void *res = dequeue();
    for (; res ;) {
        fprintf(stdout, "%s
", (char*)(res));
        free(res);
        res = NULL;
        res = dequeue();    
    }
    return NULL;
}

参照
Implementing Lock-Free Queesロックレスキューの実装-COOLSHEL