Как избежать голодания при попытке использовать реализацию "многие ко многим"

Question

Я пытаюсь предоставить доступ к общему ресурсу двум типам потоков. Доступ к нему может быть получен более чем одним потоком, если и только если этот поток относится к одному и тому же типу. Давайте рассмотрим черные и белые. Когда ресурс используется белыми, он не может использоваться черными и наоборот.

Я попытался реализовать это с помощью семафоров. Как только черный пытается получить доступ к ресурсу, он увеличивает количество черных, и если это число равно 1, он блокирует доступ белых к нему.

Проблема: существует заметное голодание, когда существует более 1 потока каждого типа (в моем случае потоки с идентификатором 0 никогда не использовали его). Я попытался исправить это, добавив дополнительный семафор, чтобы служить в качестве очереди.

Наблюдение: это очень похоже на проблему читателей-писателей, за исключением того, что существует множество критериев доступа. (он может использоваться несколькими потоками одного типа). В последнее время я довольно часто ломаю голову над этой проблемой, и я не могу понять, как мне к этому подойти.

Теперь для некоторого кода:

#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

Если вы хотите принудительно чередовать два типа потоков, обращающихся к одной вещи, вы можете использовать два семафора. Сделайте так, чтобы у черных и белых были свои собственные семафоры, начните один семафор с 0 клавиш, а другой - с 10 или чем-то еще, затем сделайте так, чтобы у белых был ключ к черному семафору, а у черных - ключ к белый семафор, таким образом, если у вас есть 10 белых нитей, когда одна из них разблокируется, вы не сможете вставить 10-ю белую нить, но вы сможете вставить черную нить, чтобы, когда все белые нити отпускают свои ключи, у вас не будет белых нитей, которые сейчас обращаются к этой вещи.

TL; DR: два семафора, которые публикуют друг друга, а не сами по себе, позволяют чередовать группы, однако независимо от этой операции вам также нужно следить за тем, чтобы белые не уходили, пока черные еще находятся.