Pthreads: Thread Starvation Caused by Quick Re-Locking

pthreads: thread starvation caused by quick re-locking

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.

Issue with Lock Ordering or Scheduling

It looks that you algorithm suffers from starvation, you should queue your access to the lock, see

pthreads: thread starvation caused by quick re-locking

or

Fair critical section (Linux)

As an answer to the comment, what is a mutex (pthread library)

A mutex is a lock (from Pthread library) that guarantees the following
three things:

Atomicity - Locking a mutex is an atomic operation,
meaning that the threads library assures you that if you lock a mutex,
no other thread can succeed in locking that mutex at the same time.

Singularity - If a thread managed to lock a mutex, it is assured that
no other thread will be able to lock the same mutex until the original
thread releases the lock.

Non-Busy Wait - If threadA attempts to lock a mutex that was locked
by threadB, the threadA will get suspended (and will not consume any
CPU resources) until the lock is freed by threadB. When threadB
unlocks the mutex, then the threadA will wake up and continue
execution, having the mutex locked by it.

It do not guaranty fairness.

If you are still interested in sort of reader writer fairness for pthread_rwlock_rdlock:
which are allowed to favour writers over readers to avoid writer starvation.

Why doesn't my mutex lock before my other thread locks it?

Your main thread is unlocking the mutex and then immediately locking it again. Try introducing a delay in your main loop (for testing purposes) to see if this is the issue.

Check out the answer to this question:
pthreads: thread starvation caused by quick re-locking

pthread_mutex_lock takes much time

Restating the problem: you have a worker thread in charge of processing some data, and a monitor thread which controls the worker's activity. You wish to know why there is a latency in stopping the worker thread through a mutex contention lock.

A mutex may block a thread only when this thread is trying to lock it. If that thread is going through some computation before reaching that point where it tries to lock the mutex, you will experience a latency. That latency will vary depending on where the thread execution is at when your monitoring thread locks the mutex.

The only way to reduce latency is to reduce the work load between mutex lock attempts, but this will also reduce throughput.

Why is another thread, say B running when pthread_mutex is being locked and unlocked inside thread A?

A mutex is a mechanism for implementing critical sections.

Any code between pthread_mutex_lock(x) and pthread_mutex_unlock(x) calls will execute in only one thread at any given time. That's all.

So ...

1. Can the other thread concurrently run when mtx is locked?

If it didn't lock the mtx, then of course.

2. What is the use of line 2 since newThread can only unlock mtx when line 4 has been executed, and thus makes line 2 redundant?

The mutex becomes useless, and you also get UB since you're unlocking it in the thread that didn't lock it:

If the mutex type is PTHREAD_MUTEX_DEFAULT...

Attempting to unlock the mutex if it was not locked by the calling thread results in undefined behavior.

(By default you get mutex type PTHREAD_MUTEX_DEFAULT)

3. What would happen if line 1 is uncommented?

You get thread starvation, since the mutex is locked almost all the time and is immediately re-locked after unlocking (POSIX doesn't guarantee mutex fairness).

A POSIX semaphore does provide fairness in some cases (when you use SCHED_FIFO or SCHED_RR schedulers), but is heavier.

I don't quite understand what you're trying to achieve (the application looks contrived). In a real application there's probably some logical ordering to the actions that either thread needs to take. So if the semaphore works for you, I'd keep it at that and remove the mutex.

Mutex takes a long while to unlock

Try changing pthread_yield() to usleep(10) or usleep(100) to determine if the yield is causing you problems, as I've seen cases where yield does nothing, which would cause your loop to unlock and relock a too quickly for the first thread to catch its lock most of the time. Then you might consider looking at condition variables in pthread if you want more control.

---

Related Topics