有人要求我使用比较和交换在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, %dn", (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: %dn", Dequeue());
printf("Dequeued: %dn", Dequeue());
}
我应该在do while循环中使用not运算符吗?如果我不使用该运算符,我会得到"Dequeued 5"x2的输出,这表明交换没有发生,我应该使用not。如果是这样,我哪里错了?我会把钱花在指针/地址运算符的问题上。
指针和值之间存在混淆。这是更正后的代码:
do
{
head = queue->head;
if(head == NULL)
return 0;
printf("%d, %d, %d %dn", (long *)queue->head, (long)head, (long)head->next, head->data);
} while (!compare_exchange((long *)&queue->head, (long)head, (long)head->next));
您试图写入queue->head所指向的内容,而不是queue->header本身的值。
此外,为了使它在多核上正常工作,我认为您需要将head定义为volatile。
struct Queue
{
volatile item *head;
item *tail;
}*queue;