Fairness: Where can it be better handled?

I would like to share one of my practical experience with multiprogramming here.

Yesterday I had written a multiprogram. Modifications to sharable resources were put under critical sections protected by P(mutex) and V(mutex) and those critical section code were put in a common library. T开发者_StackOverflow社区he library will be used by concurrent applications (of my own).

I had three applications that will use the common code from library and do their stuff independently.

 my library
 ---------
 work_on_shared_resource
 {
  P(mutex)
  get_shared_resource
  work_with_it
  V(mutex)
 }
     ---------

 my application
 -----------
 application1
 {
   *[
      work_on_shared_resource
      do_something_else_non_ctitical
    ]
 }


 application2
 {
   *[
      work_on_shared_resource
      do_something_else_non_ctitical
    ]
 }


 application3
 {
   *[
      work_on_shared_resource
    ]
 }

 *[...] denote a loop.
 ------------

I had to run the applications on Linux OS. I had a thought in my mind, hanging over years, that, OS shall schedule all the processes running under him with all fairness. In other words, it will give all the processes, their pie of resource-usage equally well.

When first two applications were put to work, they run perfectly well without deadlock. But when the third application started running, always the third one got the resources, but since it is not doing anything in its non-critical region, it gets the shared resource more often when other tasks are doing something else. So the other two applications were found almost totally halted. When the third application got terminated forcefully, the previous two applications resumed their work as before.

I think, this is a case of starvation, first two applications had to starve.

Now how can we ensure fairness?

Now I started believing that OS scheduler is innocent and blind. It depends upon who won the race; he got the largest pie of CPU and resource.

Shall we attempt to ensure fairness of resource users in the critical-section code in library?

Or shall we leave it up to the applications to ensure fairness by being liberal, not greedy?

To my knowledge, adding code to ensure fairness to the common library shall be an overwhelming task. On the other hand, believing on the applications will also never ensure 100% fairness. The application which does a very little task after working with shared resources shall win the race where as the application which does heavy processing after their work with shared resources shall always starve.

What is the best practice in this case? Where we ensure fairness and how?

Sincerely,

Srinivas Nayak

The problem arises because the "application 3" process continues running after it unlocks the mutex, so it is able to immediately acquire it again.

You can implement a fair queuing system where each thread is added to a queue when it blocks, and the first thread on the queue always gets the resource when it becomes available. You can use condition variables to build this. Such a "fair" ticket lock built on pthreads primitives might look like this:

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

There has been research done on revoking ownership of mutexes in order to ensure equal sharing or to detect and avert deadlock. However, this really is overkill and not worth the effort, especially since it opens up a whole new can of worms such as how a program should behave if it was in the midst of some computation and it lost ownership of its resources. It's really up to the application to ensure that its various threads play fair with with each other and consume resources in a way that won't deadlock.

I should point out that there is another option, albeit of a slightly different variety, and that is the use of the message passing style of parallel programming. With message passing, the synchronization is all implicit in the communication; no explicit synchronization is required, which helps to avert such errors.