c - 无锁队列和指针问题

Question

有人要求我使用比较和交换在 C 语言中实现无锁队列，但是我对指针的了解相当有限。

我一直在使用以下代码来测试我的(尚未完成的)出队实现，但我相信它正在无限循环，因为我不太确定如何正确使用运算符的指针/地址。

由于我对汇编程序一无所知，所以我得到了这个 CAS 函数的使用。

long __cdecl compare_exchange(long *flag, long oldvalue, long newvalue)
{
    __asm
    {
        mov ecx, flag
        mov eax, oldvalue
        mov ebx, newvalue
        lock cmpxchg [ecx], ebx
        jz iftrue
    }
    return 0;
    iftrue: return 1;
}

我当前的(相关)代码如下...

typedef struct QueueItem
{
    int data;
    struct QueueItem* next;
}item;

struct Queue
{
    item *head;
    item *tail;
}*queue;

int Dequeue()
{
    item *head;

    do
    {
        head = queue->head;
        if(head == NULL)
            return NULL_ITEM;
        printf("%d, %d, %d\n", (long *)queue->head, (long)&head, (long)&head->next);
    }
    while(!compare_exchange((long *)queue->head, (long)&head, (long)&head->next)); // Infinite loop.

    return head->data;
}

int main(int argc, char *argv[])
{
    item i, j;

    queue = (struct Queue *) malloc(sizeof(struct Queue));

    // Manually enqueue some data for testing dequeue.
    i.data = 5;
    j.data = 10;
    i.next = &j;
    j.next = NULL;

    queue->head = &i;

    printf("Dequeued: %d\n", Dequeue());
    printf("Dequeued: %d\n", Dequeue());
}

我应该在 do while 循环中使用 not 运算符吗？如果我不使用该运算符，我会得到“Dequeued 5”x2 的输出，这表明交换没有发生，我应该使用 not。如果是这样，我哪里出错了？我认为这是一个指针/地址运算符问题。

Answer 1

指针和值存在混淆。这是更正后的代码:

 do
 {
    head = queue->head;
    if(head == NULL)
        return 0;
    printf("%d, %d, %d %d\n", (long *)queue->head, (long)head, (long)head->next, head->data);
  }  while (!compare_exchange((long *)&queue->head,   (long)head, (long)head->next));

您试图写入queue->head所指向的内容，而不是queue->head本身的值。

此外，为了使其在多核上正常工作，我相信您需要将头部定义为 volatile 。

struct Queue
{
   volatile item *head;
   item *tail;
}*queue;