Peterson的线程链表算法（C语言）

Question

我有以下情况：

首先，我创建了一个 int 链表（已经可以使用，没有问题），我需要执行以下任务：

使用 2 个线程，一个线程将删除我的列表的第一个元素，然后同一个线程必须在列表的末尾添加一个新元素（列表遵循 FIFO 结构）。

第二个线程将执行相同的操作：删除第一个元素并在列表末尾添加另一个元素。

我需要多次执行此操作，这显然是使用循环完成的。

当我创建线程时，我使用了以下函数：

for(i=0, i<NUM_THREADS; i++)
    pthread_create (&thread[i], NULL, threadBody, (void *) i);

其中 NUM_THREADS 是一个变量，其中包含我将使用的线程数（在本例中为 2），线程声明为：

pthread_t thread [NUM_THREADS] ;

那么，我的问题是：

我是否需要在我的 threadBody 函数上执行我之前提到的操作（添加和删除列表中的元素），否则此函数将为空？

如果我的 threadBody 函数不打算执行此操作，我该如何使用我创建的线程来执行这些操作？是用pthread_join函数完成的吗？

还有一点，我需要使用Peterson算法来保证互斥。我该怎么做？

Answer 1

看得出来你对链表的操作很简单。在这种情况下，也许使用无锁编程会更好。要阅读，请查看此 link. If you are using GCC, please review the __sync_bool_compare_and_swap operations (link). Finally, the problem of programming a lock-free linked list has been broadly studied. The next link may give you hints about it link。祝你好运！

Answer 2

谢谢大家

我的最终实现（和工作）是：

void *threadBody (void *id){
    long threadId = (long) id;
    int k=0;
    while(k<N){
        if(threadId == 0){
             flag[0] = 1;
             turn = 1;
             while(flag[1]==1 && turn==1);
         }
         else{
             flag[1] = 1;
             turn = 0;
             while(flag[0]==1 && turn==0);
         }
         critSection(id);
         if(threadId==0) 
            flag[0] = 0;
         else if(threadId==1) 
            flag[1] = 0;
         k++;
    }
    pthread_exit (NULL) ;   
}

其中 critSection 将是执行 add/remove 操作的函数。

Peterson的线程链表算法（C语言）

Peterson's Algorithm with Threads and Linked List (C language)

c

algorithm

multithreading

mutual-exclusion