c - 通过类型限制多对多资源访问

Question

免责声明：这篇文章包含对以下答案的编辑，所有的信用证都归各自的所有者所有。
我正在尝试实现一个问题，它指出一个资源可能被两种类型的线程使用。每种类型的线程可以更多。（4根白色螺纹，6根黑色螺纹）。任何数量的黑人都可以同时使用这个资源。白人也一样。我还是不能把我的头缠在这。。。
我试着用互斥体实现这个。我还想考虑这个实现可能会出现的饥饿，因此我决定检查是否达到了某个类型的服务线程数，从而允许另一个类型工作。我似乎无法实施最新的计划。
我还想考虑到，每当其他类型想要使用资源时，它必须等待轮到它，以及其他类型完成使用资源。
编辑：我试着用@Nominal Animal的解决方案，但有时也会出现这种僵局。此外，我还在结构中添加了缺少的转向。现在，我还有一个问题：
这似乎是对的，但不起作用，为什么？
为什么需要对isBLack内的bwlock_lock()参数进行双反运算
现在，对于一些代码：

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

#define WHITES 31
#define BLACKS 33
#define TYPES 2
#define W_ID 0
#define B_ID 1

struct bwlock
{
    pthread_mutex_t lock;    /* Protects the rest of the fields */
    pthread_cond_t wait[2];  /* To wait for their turn */
    volatile int waiting[2]; /* Number of threads waiting */
    volatile int running[2]; /* Number of threads running */
    volatile int started[2]; /* Number of threads started in this turn */
    const int limit[2];      /* Maximum number of starts per turn */
    volatile int black;      /* Black threads' turn */
    volatile int turn;       /*The turn */
};

#define BWLOCK_INIT(whites, blacks, turn)                         \
    {                                                             \
        PTHREAD_MUTEX_INITIALIZER,                                \
            {PTHREAD_COND_INITIALIZER, PTHREAD_COND_INITIALIZER}, \
            {0, 0}, {0, 0}, {0, 0}, {whites, blacks}, 0, turn     \
    }

struct bwlock resource = BWLOCK_INIT(4, 5, W_ID);

void bwlock_unlock(struct bwlock *bwl, const int isblack)
{
    const int black = !!isblack; /* 0 if white, 1 if black */

    pthread_mutex_lock(&(bwl->lock));

    /* This thread is no longer using the resource. */
    bwl->running[black]--;

    /* Was this the last of this color, with others waiting? */
    if (bwl->running[black] <= 0 && bwl->waiting[!black])
    {
        /* Yes. It's their turn. */
        if (bwl->turn == black)
        {
            bwl->turn = !black;
            /* Clear their started counter. */
            bwl->started[!black] = 0;
        }
        /* Wake them all up. */
        pthread_cond_broadcast(&(bwl->wait[!black]));
    }

    pthread_mutex_unlock(&(bwl->lock));
}

void bwlock_lock(struct bwlock *bwl, const int isblack)
{
    const int black = !!isblack; /* 0 if white, 1 if black */

    pthread_mutex_lock(&(bwl->lock));
    while (1)
    {

        /* No runners or waiters of the other color? */
        if (!(bwl->waiting[!black] < 1) && bwl->running[!black] < 1)
        {
            /* No; we can run. Does this change the turn? */
            if (bwl->turn != black)
            {
                bwl->turn = black;
                /* Clear started counter. */
                bwl->started[black] = 0;
            }
            break;
        }

        /* Still our turn, and not too many started threads? */
        if (bwl->turn == black && bwl->started[black] < bwl->limit[black])
            break;

        /* We must wait. */
        bwl->waiting[black]++;
        pthread_cond_wait(&(bwl->wait[black]), &(bwl->lock));
        bwl->waiting[black]--;
    }

    bwl->started[black]++;
    bwl->running[black]++;

    pthread_mutex_unlock(&(bwl->lock));
}

typedef struct
{
    int thread_id;
    char *type;
    int type_id;
} data;

void use_resource(int thread_id, char *type)
{
    printf("U: Thread %d of type %s is using the resource!\n", thread_id, type);
}

void take_resource(int thread_id, char *type, int type_id)
{
    printf("W:Thread %d of type %s is trying to get the resource!\n", thread_id, type);
    bwlock_lock(&resource, type_id);
    printf("W:Thread %d of type %sB got resource!\n", thread_id, type);
}

void release_resource(int thread_id, char *type, int type_id)
{
    bwlock_unlock(&resource, type_id);
    printf("R:Thread %d of type %s has released the resource!\n", thread_id, type);
}

void *doWork(void *arg)
{
    data thread_data = *((data *)arg);

    int thread_id = thread_data.thread_id;
    char *type = thread_data.type;
    int type_id = thread_data.type_id;
    take_resource(thread_id, type, type_id);
    use_resource(thread_id, type);
    release_resource(thread_id, type, type_id);

    return NULL;
}

data *initialize(pthread_t threads[], int size, char *type, int type_id)
{
    data *args = malloc(sizeof(data) * size);
    for (int i = 0; i < size; i++)
    {
        args[i].type = type;
        args[i].thread_id = i;
        args[i].type_id = type_id;
        pthread_create(&threads[i], NULL, doWork, (void **)&args[i]);
    }
    return args;
}

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

int main()
{
    pthread_t whites[WHITES];
    pthread_t blacks[BLACKS];
    char *white = "WHITE";
    char *black = "BLACK";
    data *w_args = initialize(whites, WHITES, white, W_ID);
    data *b_args = initialize(blacks, BLACKS, black, B_ID);

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

    free(w_args);
    free(b_args);

    return 0;
}

这是使用 gcc -g -o ba blacks_whites.c -Wall -Wextra -pthread编译的。

Answer 1

考虑以下对John Bollingers answer的扩展注释。
所描述的规则不完整。例如，假设您有三个黑色线程与资源，一个白色线程等待资源，另一个黑色线程到达，希望获取资源。会发生什么？如果黑色线程总是获得资源，那么黑色（或白色）线程可能会耗尽其他类型的线程。如果在可能的情况下立即将所有权更改为另一种类型，我们将失去跨同一类型线程并发的大部分好处；如果传入线程类型的分布大致均匀，则可能一次只运行一种类型的线程，所有线程都是连续的！
有几种可能的解决办法。最适合OP的问题陈述是，在切换到white s'turn（如果有的话）之前，允许多达Nblack的黑色线程与资源一起运行；在切换到blacks'turn之前，允许多达Nwhite的白色线程与资源一起运行。（一个时间限制，一个宽限期，在这个宽限期内，同一类型的其他线程也可能获取资源，这可能是您在实践中实际使用的。）
我们可以使用以下结构来描述这种锁：

struct bwlock {
    pthread_mutex_t    lock;        /* Protects the rest of the fields */
    pthread_cond_t     wait[2];     /* To wait for their turn */
    volatile int       waiting[2];  /* Number of threads waiting */
    volatile int       running[2];  /* Number of threads running */
    volatile int       started[2];  /* Number of threads started in this turn */
    const int          limit[2];    /* Maximum number of starts per turn */
    volatile int       black;       /* Black threads' turn */
};
#define BWLOCK_INIT(whites, blacks) \
    { PTHREAD_MUTEX_INITIALIZER, \
      { PTHREAD_COND_INITIALIZER, PTHREAD_COND_INITIALIZER }, \
      { 0, 0 }, { 0, 0 }, { 0, 0 }, { whites, blacks }, 0 \
    }

mutex只在检查字段时保持，而不是在资源访问期间。
（还要注意，虽然 lock最初是0，但是当没有跑步者和服务员时，转弯会改变，所以这无关紧要。如果初始值 black为1，则代码的工作原理将完全相同
让我们先看看释放bwlock，因为它是更有趣的部分；它控制着转弯的变化。假设lock和release都有一个 black参数（可以是0或1）。如果释放线程是它的最后一个颜色，而另一个颜色的线程正在等待，则它将改变转向，并在另一个颜色 isblack条件变量上广播以唤醒它们：

void bwlock_unlock(struct bwlock *bwl, const int isblack)
{
    const int black = !!isblack;  /* 0 if white, 1 if black */

    pthread_mutex_lock(&(bwl->lock));

    /* This thread is no longer using the resource. */
    bwl->running[black]--;

    /* Was this the last of this color, with others waiting? */
    if ((bwl->running[black] <= 0) && (bwl->waiting[!black] > 0)) {
        /* Yes. It's their turn. */
        if (bwl->black == black) {
            bwl->black = !black;
            /* Clear their started counter. */
            bwl->started[!black] = 0;
        }
        /* Wake them all up. */
        pthread_cond_broadcast(&(bwl->wait[!black]));
    }

    pthread_mutex_unlock(&(bwl->lock));
    return;
}

抓取bwlock要复杂得多。只有在没有其他类型的线程在等待时才应用此限制（因为如果我们这样做了，单一颜色的线程将在没有其他颜色的情况下死锁）。

void bwlock_lock(struct bwlock *bwl, const int isblack)
{
    const int  black = !!isblack; /* 0 if white, 1 if black */

    pthread_mutex_lock(&(bwl->lock));
    while (1) {

        /* No runners or waiters of the other color? */
        if ((bwl->waiting[!black] < 1) && (bwl->running[!black] < 1)) {
            /* No; we can run. Does this change the turn? */
            if (bwl->black != black) {
                bwl->black = black;
                /* Clear started counter. */
                bwl->started[black] = 0;
            }
            break;
        }

        /* Still our turn, and not too many started threads? */
        if ((bwl->black == black) && (bwl->started[black] < bwl->limit[black]))
            break;

        /* We must wait. */
        bwl->waiting[black]++;
        pthread_cond_wait(&(bwl->wait[black]), &(bwl->lock));
        bwl->waiting[black]--;
    }

    bwl->started[black]++;
    bwl->running[black]++;

    pthread_mutex_unlock(&(bwl->lock));
}

wait释放锁并等待条件变量上的信号或广播。当发出信号时，它将在返回之前重新获取锁。（在释放锁并等待条件变量时没有race窗口；它是原子式的，有效地在同一时间点发生的。）
如果考虑到上面的逻辑， pthread_cond_wait(&(bwl->wait[black]), &(bwl->lock))会处理最后一个运行的特定颜色的线程应该处理另一个线程集的“指挥棒”的情况。 bwlock_unlock()决定线程是可以使用资源运行，还是需要等待。只有当没有其他颜色的线程在运行或等待它们的回合时，它才会改变回合。
这是一个相当简单的计划，但您可能需要考虑几个案例来了解它的行为。
当圈数改变时， bwlock_lock()计数器被清除，并且在该圈中启动的每个线程的计数器都会递增。当它达到 started时，不再启动该类型的线程；它们将等待轮到它们。
假设 limit是 limit，每种类型有四个线程，它们基本上都同时冲到bwlock。假设第一个抓住锁的线程是黑色的。前三个黑色线程将与资源一起运行，一个黑色线程和四个白色线程将等待条件变量。当转弯改变时，三条白色线开始运行；一条白色线，一条随机线，将重新等待下一个白色转弯。
而且，正如克雷格·埃斯蒂在给约翰·博林格斯的回复中指出的那样，这并不能保证同一类型的线程之间的公平性。例如，如果A和B是同一类型，A在它们的回合中多次访问bwlock受保护的资源，而B只有一次，则B可能在获得回合之前必须无限期地等待，因为A“hogs”了它的所有时隙。
为了保证公平性，我们需要某种类型的票锁或顺序等待队列，这样我们就可以唤醒特定颜色的最长等待线程，而不是随机等待线程。