Avoiding starvation when attempting to use a many-to-many implementation

Question

I am trying to grant access to a shared resource to two types of threads. It can be accessed by more than one threads, if, and only if, that thread is of the same type. Let us consider blacks & whites. When the resource is used by whites, it cannot be used by blacks and vice-versa.

I attempted to implement this using semaphores. Once a black tries to access the resource, it will increment the number of blacks and if that number is 1, it will block the whites from accessing it.

Issue: there is a noticeable starvation when there are more than 1 thread of each type (in my case threads with id 0 never used it). I attempted to fix this by adding an extra semaphore to serve as a queue.

Observation: this resembles very well to the readers-writers problem, except there is a many to many access criteria. (it can be used by multiple threads of the same type) I have been bashing my head quite a lot around this problem lately and I cannot seem to understand how should I approach this.

Now, for some code:

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <wait.h>
#include <pthread.h>
#include <semaphore.h>

#define MAX_RAND 100
#define TRUE 1
#define FALSE 0

#define WHITES 3
#define BLACKS 2

#define MAX_WORLOAD 10

sem_t semaphore;
sem_t resource_semaphore;
sem_t service_queue;
volatile int resource = 0;
volatile int currentWhites = 0;
volatile int currentBlacks = 0;

typedef struct
{
    char *type;
    int *id;
} data;

void *white(void *args)
{
    data *thread_data = (data *)args;
    int id = *(thread_data->id);
    char *type = thread_data->type;

    for (int i = 0; i < MAX_WORLOAD; i++)
    {
        sem_wait(&service_queue);
        sem_wait(&semaphore);
        sem_post(&service_queue);

        currentWhites++;
        if (currentWhites == 1)
        {
            sem_wait(&resource_semaphore);
        }
        sem_post(&semaphore);

        sem_wait(&semaphore);

        currentBlacks--;
        resource = rand() % MAX_RAND;
        printf("Thread %d of type %s has updated resource to %d\n\n", id, type, resource);

        if (currentWhites == 0)
        {
            sem_post(&resource_semaphore);
        }

        sem_post(&semaphore);
    }
}

void *black(void *args)
{
    data *thread_data = (data *)args;
    int id = *(thread_data->id);
    char *type = thread_data->type;

    for (int i = 0; i < MAX_WORLOAD; i++)
    {
        sem_wait(&service_queue);
        sem_wait(&semaphore);
        sem_post(&service_queue);
        currentBlacks++;
        if (currentBlacks == 1)
        {
            sem_wait(&resource_semaphore);
        }
        sem_post(&semaphore);

        sem_wait(&semaphore);

        currentBlacks--;
        resource = rand() % MAX_RAND;
        printf("Thread %d of type %s has updated resource to %d\n\n", id, type, resource);

        if (currentBlacks == 0)
        {
            sem_post(&resource_semaphore);
        }

        sem_post(&semaphore);
    }
}

data *initialize(pthread_t threads[], int size, char *type)
{
    data *args = malloc(sizeof(data) * size);
    int *id = malloc(sizeof(int));
    void *function;

    if (type == "WHITE")
    {
        function = white;
    }
    else
    {
        function = black;
    }

    for (int i = 0; i < size; i++)
    {
        *id = i;
        args[i].type = type;
        args[i].id = id;
        printf("Initializing %d of type %s\n", *args[i].id, args[i].type);
        pthread_create(&threads[i], NULL, function, (void **)&args[i]);
    }

    return args;
}

void join(pthread_t threads[], int size)
{
    for (int i = 0; i < size; i++)
    {
        pthread_join(threads[i], NULL);
    }
}

void initialize_locks()
{
    sem_init(&semaphore, 0, 1);
    sem_init(&resource_semaphore, 0, 1);
    sem_init(&service_queue, 0, 1);
}

int main()
{
    initialize_locks();
    pthread_t whites[WHITES];
    pthread_t blacks[BLACKS];
    char *white = "white";
    char *black = "black";
    data *whites_arg = initialize(whites, WHITES, white);
    data *blacks_arg = initialize(blacks, BLACKS, black);

    join(whites, WHITES);
    join(blacks, BLACKS);

    free(whites_arg);
    free(blacks_arg);
    return 0;
}

Answer 1

If you want to force alternation between two types of threads accessing a single thing you can use two semaphores. Make it so the blacks and whites each have their own semaphores, start one semaphore with 0 keys and the other with 10 or something, then make it so that the whites release a key to the black semaphore, and the blacks release a key to the white semaphore, this way if you have 10 white threads in, when one of them unlocks you won't be able to put a 10th white thread in, but you will be able to put a black thread in, so that when all of the white threads release their keys you will have no white threads currently accessing the thing.

TL;DR: two semaphores that post to each other instead of themselves will allow alternation between groups, however independent of this operation you need to also make sure that whites don't go while blacks are still in.