Peterson的算法

我有以下的情况线程和链表（C语言）：Peterson的算法

首先，我创建了一个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算法来保证互斥。我该怎么做？

来源

2015-04-14 woz

你的问题太宽泛了，所以很难得到一个简洁的答案。但对于初学者来说：是的，你应该在threadBody内部添加/删除代码。您可能应该为生产者和消费者使用不同的threadBody代码（或者您可以使用相同的threadBody并在创建过程中将其传递给参数，以使其作为消费者或生产者）。为了互相排斥，我会将您引向pthread_mutex_lock和pthread_mutex_unlock手册页供初学者使用。 – kaylum

彼得森算法是80年代初开发的无锁多任务处理的一种形式。它在当时存在的处理器上运行良好。现代处理器具有许多功能，即使不是不可能，也很难正确实现无锁多任务。例如，请参阅[本文]（https://msdn.microsoft.com/en-us/library/windows/desktop/ee418650（v = vs.85）.aspx）。 – user3386109

你有两个线程，所以使用Peterson的算法不是问题。只需要'threadBodyAdd'和'threadBodyRemove'。在轮到你/你的轮流变量上同步它们，你就完成了。 – jiveturkey

谢谢大家。

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

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将是功能均添加/删除操作将被执行。

来源

2015-04-16 11:48:23 woz

我可以看到你对链表的操作很简单。在这种情况下，也许会更好地使用无锁编程。要阅读，请查看link。如果您使用的是GCC，请查看__sync_bool_compare_and_swap操作（link）。最后，广泛研究了编写无锁链表的问题。下一个链接可能会给你提示link。祝你好运！

来源

2015-04-15 16:33:41

回答

相关问题