How do you delegate tasks for N threads such that the workload is evenly distributed?

Say we have a queue

[the] -> [quick] -> [brown] -> [fox] -> [jumps] -> [over] -> [the] -> [lazy] -> [dog]

And we have N threads to split up the workload of dequeuing the queue and output the words where at least one word is only printed by one thread.

Here's my attempt (Updated, fixed null printing):

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

#define threadCount 8    // Set number of threads

pthread_t* thread;
pthread_mutex_t lock;

//========= Setup for Queue =========
struct node
{
    char *key;
    struct node *next;
};

struct Q 
{
    struct node *front, *rear;
};

struct node* newNode(char *key)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->key = key;
    temp->next = NULL;
    return temp;
}

struct Q* q;

void enqueue(char* key)
{
    struct node* temp = newNode(key);

    if(q->rear == NULL)
    {
        q->front = q->rear = temp;
        return;
    }
    q->rear->next = temp;
    q->rear = temp;
}

char* dequeue()
{
    if (q->front == NULL)
    {
        return NULL;
    }

    struct node* temp = q->front;
    char *key = temp->key;

    q->front = q->front->next;

    if(q->front == NULL)
    {
        q->rear = NULL;
    }
    free(temp);

    return key;
}
//========= Setup for Queue =========

void *run(void* arg)
{
    int id = *(int*)arg;
    char* node;

    while(q->front != NULL)
    {
        pthread_mutex_lock(&lock);
        node = dequeue();
        pthread_mutex_unlock(&lock);

        if(node == NULL)
        {
            return NULL;
        }
        
        printf("Thread %d: %s\n", id, node);
    }

    return 0;
}

int main()
{
    q = (struct Q*)malloc(sizeof(struct Q));
    q->front = NULL;
    q->rear = NULL;

    enqueue("the");
    enqueue("quick");
    enqueue("brown");
    enqueue("fox");
    enqueue("jumps");
    enqueue("over");
    enqueue("the");
    enqueue("lazy");
    enqueue("dog");

    thread = malloc(sizeof(pthread_t)*threadCount);
    
    // Should output lines be only N-1 due to how the id is generated?
    for(int id = 0; id < threadCount; id  )
    {
        pthread_create(&thread[id], NULL, (void *) run, &id);
    }

    for(int id = 0; id < threadCount; id  )
    {
        pthread_join(thread[id], NULL);
    }

    free(thread);
    free(q);

    return 0;
}

Here is my unresolved problem:

• Sometimes there are lines also that print Thread N, but according to how I implemented (see main), max output for thread number should be N-1.

CodePudding user response：

1. Lock the mutex
2. Take an item from the queue
3. Unlock the mutex
4. Do the work with the item

You don't want to hold the mutex while doing the work (e.g. printf) because then only one thread can do work at a time - you aren't really using multiple threads.

The reason you get (null) printed is that your code checks q->front != NULL while it hasn't locked the mutex. Then by the time it locks the mutex, the queue is empty. The solution is that the thread should dequeue, and then after it dequeues and unlocks the mutex, check whether it dequeued NULL.

You can't expect the work to be done in the "correct" order when using threads. You use threads when you don't care about the order.

If some threads don't print any words, that's normal - your "work" is very quick and you have too many threads for the amount of work. It's understandable that some threads don't get any work because all the work is already done by the time they start up. You can fix this for the demonstration by putting a call like sleep(1) before or after the printf, to slow the thread down.

Sometimes your thread IDs are wrong. When each thread starts, it accesses the id variable in main. The pthread_create function doesn't wait for the thread to read the variable. main sets id to 0, and it starts a thread, and it sets id to 1, and it starts a thread, ..., and it sets id to N and stops looping. When does the thread read the variable? No idea, could be any time, so the number it reads could be higher than the right number.

You can fix this by either making a new variable per thread to hold its ID (with new or just with an array of 8 separate ints) or you can use a little trick, and cast the ID to a pointer since it doesn't have to be a real pointer:

// No &. Just take the number and use that number as a pointer.
//                                              vvvvvvvv
pthread_create(&thread[id], NULL, (void *) run, (void *)id);
//                                ^^^^^^^^
//     don't know why you wrote (void *) here

in the run function:

int id = (int)arg;
// no *. This isn't a pointer to an int, it's just an int hiding in a pointer variable