13

I have a two threads, one which works in a tight loop, and the other which occasionally needs to perform a synchronization with the first:

// thread 1
while(1)
{
    lock(work);
    // perform work
    unlock(work);
}

// thread 2
while(1)
{
    // unrelated work that takes a while
    lock(work);
    // synchronizing step
    unlock(work);
}

My intention is that thread 2 can, by taking the lock, effectively pause thread 1 and perform the necessary synchronization. Thread 1 can also offer to pause, by unlocking, and if thread 2 is not waiting on lock, re-lock and return to work.

The problem I have encountered is that mutexes are not fair, so thread 1 quickly re-locks the mutex and starves thread 2. I have attempted to use pthread_yield, and so far it seems to run okay, but I am not sure it will work for all systems / number of cores. Is there a way to guarantee that thread 1 will always yield to thread 2, even on multi-core systems?

What is the most effective way of handling this synchronization process?

scientiaesthete
  • 919
  • 9
  • 20
  • What you have described in your question has no relation to fairness, If you want Thread 2 to be with higher priority then thread 1, one of the ways to achieve it , by using condition variables. – Michael Oct 02 '12 at 06:46
  • 2
    This question is very similar to [*Fair critical section (Linux)*](http://stackoverflow.com/q/6449732/134633). – caf Oct 02 '12 at 07:00

5 Answers5

9

You can build a FIFO "ticket lock" on top of pthreads mutexes, along these lines:

#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);
}

Under this kind of scheme, no low-level pthreads mutex is held while a thread is within the ticketlock protected critical section, allowing other threads to join the queue.

caf
  • 233,326
  • 40
  • 323
  • 462
  • Shouldn't `queue_head` be declared `volatile`? Otherwise in `ticket_lock()` the compiler might optimize it away... – lornova Feb 13 '19 at 16:33
  • 2
    @lornova: No. `pthread_cond_wait()` is one of the functions listed by POSIX as *["functions (that) synchronize memory with respect to other threads."](http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_12)*. The compiler can't cache the value across such function calls. – caf Feb 14 '19 at 00:56
5

In your case it is better to use condition variable to notify second thread when it is required to awake and perform all required operations.

Sergei Nikulov
  • 5,029
  • 23
  • 36
  • 1
    Please also mention semaphores as a potential solution to problems like these, they are often overlooked! – Marius Brendmoe Oct 02 '12 at 06:56
  • Any example or snippet about how semaphores can be used to this problem? – Atanu Oct 02 '12 at 06:57
  • [This answer of mine](http://stackoverflow.com/a/6453925/134633) might be useful, where I show how to use pthreads condition variables to implement a first-in-first-out ticket lock. – caf Oct 02 '12 at 06:59
  • @caf Your answer was exactly what I was looking for. You should post it here so I can accept it. If Sergey can complete his answer with including _how_ to use condition variables in this case, I can consider it as well. – scientiaesthete Oct 03 '12 at 04:16
  • @scientiaesthete the question provides a small amount of information to understand whole design of your system. My common advice is to take a look on Monitor object http://en.wikipedia.org/wiki/Monitor_%28synchronization%29 , http://www.cs.wustl.edu/~schmidt/PDF/monitor.pdf and review also a list concurrency patterns http://en.wikipedia.org/wiki/Concurrency_pattern to understand which is better for your needs. – Sergei Nikulov Oct 03 '12 at 06:41
4

pthread offers a notion of thread priority in its API. When two threads are competing over a mutex, the scheduling policy determines which one will get it. The function pthread_attr_setschedpolicy lets you set that, and pthread_attr_getschedpolicy permits retrieving the information.

Now the bad news:

  • When only two threads are locking / unlocking a mutex, I can’t see any sort of competition, the first who runs the atomic instruction takes it, the other blocks. I am not sure whether this attribute applies here.
  • The function can take different parameters (SCHED_FIFO, SCHED_RR, SCHED_OTHER and SCHED_SPORADIC), but in this question, it has been answered that only SCHED_OTHER was supported on linux)

So I would give it a shot if I were you, but not expect too much. pthread_yield seems more promising to me. More information available here.

Community
  • 1
  • 1
qdii
  • 12,505
  • 10
  • 59
  • 116
0

Ticket lock above looks like the best. However, to insure your pthread_yield works, you could have a bool waiting, which is set and reset by thread2. thread1 yields as long as bool waiting is set.

JayS
  • 2,057
  • 24
  • 16
0

Here's a simple solution which will work for your case (two threads). If you're using std::mutex then this class is a drop-in replacement. Change your mutex to this type and you are guaranteed that if one thread holds the lock and the other is waiting on it, once the first thread unlocks, the second thread will grab the lock before the first thread can lock it again.

If more than two threads happen to use the mutex simultaneously it will still function but there are no guarantees on fairness.

If you're using plain pthread_mutex_t you can easily change your locking code according to this example (unlock remains unchanged).

#include <mutex>

// Behaves the same as std::mutex but guarantees fairness as long as
// up to two threads are using (holding/waiting on) it.
// When one thread unlocks the mutex while another is waiting on it,
// the other is guaranteed to run before the first thread can lock it again.

class FairDualMutex : public std::mutex {
public:
    void lock() {
        _fairness_mutex.lock();
        std::mutex::lock();
        _fairness_mutex.unlock();
    }
private:
    std::mutex _fairness_mutex;
};
itaych
  • 644
  • 5
  • 18