sched_yield considered harmful

According to recent discussions sched_yield can cause performance problems with some code.

The essence of the problem is that if you call pthread_cond_signal it doesn't actually relinquish control from the current thread to the thread (if any) that has been signaled. The thread that has been signalled has to wait for its next time slice before it will realise it has been woken up. Thus a common idiom is to call pthread_cond_signal and then sched_yield to relinquish control from your thread to the waiting thread.

As discussed, this can lead to very bad performance under certain circumstances since sched_yeild on Linux is saying to the scheduler "I have nothing important to do". This is in fact the opposite of what is really happening, as the thread has lots of work to do, but just wants to get some out of the way! This is especially bad on a SMP machine, where you probably don't want to relinquish control at all since your thread probably has time to be running on another processor. On some other systems sched_yield will relinquish control to another thread in your thread group, but this is not specified by the standard so you can not depend on it.

One solution to such a problem is presented below. This is a fairly standard situation where are request is made and needs to be handled. To avoid using sched_yield one needs to queue the requests and take an extra lock. When requests are flooding in so fast that the dispatcher thread doesn't get a chance to run, we will relinquish control after queing up 10 requests. You will notice if you include the usleep that everything happens nice and sequentially; this is because the dispatcher gets a chance to run as we go to sleep.

Compile this once as

$ gcc -Wall -o server server.c -lpthread

to see the problem, then once as

$ gcc -Wall -o server-resched server.c -lpthread -DRESCHED 

to see the dispatcher handling the batched requests. I belive this is a good solution to minimise latency below a CPU timeslice when requests are flooding, without having to "fool" the scheduler with sched_yield.

server.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <pthread.h>
#include <errno.h>

struct request_tag_t {
        struct request_tag_t *next;
        int operation;
};

struct dispatcher_tag_t {
        struct request_tag_t *first;
        struct request_tag_t *last;
        int running;
        pthread_mutex_t mutex;
        pthread_cond_t request;
        pthread_mutex_t resched;
};

struct dispatcher_tag_t dispatcher = {
        .first = NULL,
        .last = NULL,
        .running = 0,
        .mutex = PTHREAD_MUTEX_INITIALIZER,
        .request = PTHREAD_COND_INITIALIZER,
        .resched = PTHREAD_MUTEX_INITIALIZER,
};

int rand_num(int range)
{
        return (int)((range)*1.0*rand()/(RAND_MAX+1.0));
}

void *dispatcher_routine(void *arg)
{
        struct request_tag_t *request;

        printf("dispatcher starting\n");

        while (1)
        {
                /* take the dispatcher queue mutex */
                pthread_mutex_lock(&dispatcher.mutex);

                /* if nothing to do, wait on the dispatcher queue
                 * condition variable until there is */
                while (dispatcher.first == NULL)
                        pthread_cond_wait(&dispatcher.request, &dispatcher.mutex);

                /* take a request from the queue */
                request = dispatcher.first;
                dispatcher.first = request->next;
                if (dispatcher.first == NULL)
                        dispatcher.last = NULL;

                /* handle request, maybe by handling it in a new thread. */
                printf("I'm dispatching request %d\n", request->operation);

                /* free request we have just finished with */
                free(request);

                /* release queue lock */
                pthread_mutex_unlock(&dispatcher.mutex);
#ifdef RESCHED
                /* release the resched lock to signal we've seen the queue */
                pthread_mutex_unlock(&dispatcher.resched);
#endif
        }
}

int tries = 1;

void request(int operation)
{
        struct request_tag_t *request;

        /* take the dispatcher queue mutex */
        pthread_mutex_lock(&dispatcher.mutex);

        /* start the thread if it isn't */
        if (!dispatcher.running)
        {
                pthread_t thread;
                printf("dispatcher not running, starting\n");
                dispatcher.running = 1;
                pthread_create(&thread, NULL, dispatcher_routine, NULL);
        }

        /* allocate a new request */
        request = malloc(sizeof(struct request_tag_t));
        if (request == NULL)
                exit(1);
        request->next = NULL;
        request->operation = operation;

        /* add to the queue, maintaing first and last */
        if (dispatcher.first == NULL) {
                dispatcher.first = request;
                dispatcher.last = request;
        } else {
                (dispatcher.last)->next = request;
                dispatcher.last = request;
        }

        /* signal something to do */
        pthread_cond_signal(&dispatcher.request);

        /* free the queue lock */
        pthread_mutex_unlock(&dispatcher.mutex);

#ifdef RESCHED
        /* try the resched lock.  if we can't have it, that means
         * we've already got it and the dispatch thread hasn't had a
         * chance to run and unlock it.  We queue up to this 10 times
         * before allowing the dispatcher to run by sleeping on the
         * mutex
         */
        if (pthread_mutex_trylock(&dispatcher.resched) == EBUSY) {
                if (tries++ == 10) {
                        pthread_mutex_lock(&dispatcher.resched);
                        tries = 1;
                }
        } else 
                tries = 1;
#endif
}

int main(void) {
        while(1)
        {
                int n = rand_num(3);
                printf("requesting %d\n", n);
                request(n);

                /* if you uncomment this, everything should play
                nicely with one dispatch per request, because other
                threads get a chance to run. */
                /*usleep(500000);*/
        }
}

IA64wiki: sched yieldConsideredHarmful (last edited 2009-12-10 03:13:48 by localhost)

Gelato@UNSW is sponsored by
the University of New South Wales National ICT Australia The Gelato Federation Hewlett-Packard Company Australian Research Council
Please contact us with any questions or comments.