公平的关键部分(Linux)

在一个multithreading的Linux应用程序中,我使用了一个用于关键部分互斥锁。 除了公平性问题,这个工作很好。 可能发生的情况是,离开关键部分并立即重新进入的线程不会给其他线程一个机会。 例如

while(true) { critsect.enter(); ... do calculations ... ... maybe call a blocking operation so we sleep ... critsect.leave(); } 

可能很可能会阻止任何其他线程进入相同的关键部分。 Mutexe不公平。

是否有一个解决scheme来制定一个公正的关键部分? 我正在考虑添加一个队列,以便按照“到达”顺序执行关键部分。 或者至less有一个计数器可能做一个pthread_yield()后解锁,如果其他线程正在等待。

这种要求是否有推荐的做法?

Solutions Collecting From Web of "公平的关键部分(Linux)"

您可以在pthreads互斥体之上构建一个FIFO“票证锁定”,如下所示:

 #include <pthread.h> typedef struct ticket_lock { pthread_cond_t cond; pthread_mutex_t mutex; unsigned long queue_head, queue_tail; } ticket_lock_t; #define TICKET_LOCK_INITIALIZER { PTHREAD_COND_INITIALIZER, PTHREAD_MUTEX_INITIALIZER } void ticket_lock(ticket_lock_t *ticket) { unsigned long queue_me; pthread_mutex_lock(&ticket->mutex); queue_me = ticket->queue_tail++; while (queue_me != ticket->queue_head) { pthread_cond_wait(&ticket->cond, &ticket->mutex); } pthread_mutex_unlock(&ticket->mutex); } void ticket_unlock(ticket_lock_t *ticket) { pthread_mutex_lock(&ticket->mutex); ticket->queue_head++; pthread_cond_broadcast(&ticket->cond); pthread_mutex_unlock(&ticket->mutex); } 

在这种方案下,当一个线程在ticketlock保护临界区内时,没有低级别的pthreads互斥体,允许其他线程加入队列。

即使有一个公平的关键部分,代码可能会有可怕的表现,因为如果关键部分被长时间保存,线程将经常等待它。

所以我建议你尝试重组代码,这样就不需要长时间锁定关键部分。 要么通过完全使用不同的方法(通常建议在消息队列上传递对象,因为它很容易获得),或者至少通过对局部变量进行大部分计算而不锁定锁定,并且仅用锁来存储结果。 如果锁保持较短的时间,线程将花更少的时间等待,这通常会提高性能,并使公平性不成问题。 您还可以尝试增加锁定粒度(分别锁定较小的对象),这也会减少争用。

编辑:好吧,考虑一下,我相信Linux中的每个关键部分都是公平的。 每当有睡眠者,解锁操作必须进入内核告诉它唤醒。 在从内核返回时,调度程序运行并选择具有最高优先级的进程。 在等待的时候,睡眠者会优先上升,所以在某些时候他们会高到足以释放任务。

如果你的声明是真实的(我没有时间阅读,而且看起来好像你在发布这个问题之前已经研究过),我建议

  sleep(0); 

在关键部分之间明确地屈服。

 while(true) { critsect.enter(); ... do calculations ... ... maybe call a blocking operation so we sleep ... critsect.leave(); sleep(0); } 

好的,这个怎么样:

 while(true) { sema.wait; critsect.enter(); sema.post; ... do calculations ... ... maybe call a blocking operation so we sleep ... critsect.leave(); } 

在里面。 信号计数为1.让其他线程等待信号量,然后再尝试获取CS并在完成时发出信号。 如果'calculate'线程获得sema,它可以到达CS并锁定它。 一旦进入锁定,但在长时间的分离之前,sema发出信号,另一个线程可以到达CS但不进入。 当'calculate'线程退出锁定时,由于sema,它不能循环并重新锁定它。 计数为零,所以另一个线程获得锁定。 'calculate'线程必须在sema上等待,直到进入的另一个线程完成访问并发出sema命令。

通过这种方式,另一个线程可以“保留”对数据的访问,尽管它实际上还没有得到。

Rgds,Martin