c - 按类型限制多对多的资源访问
问题描述
免责声明:这篇文章包含对以下答案所做的编辑,所有学分归其各自所有者所有。
我正在尝试实现一个问题,该问题指出资源可能被两种类型的线程使用。每种类型可以有更多的线程。(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
。
解决方案
考虑以下对John Bollingers answer的扩展评论。
OP 描述的规则是不完整的。例如,考虑这样一种情况,您有三个黑色线程与资源,一个白色线程等待资源,另一个黑色线程到达并希望获取资源。应该发生什么?如果黑色线程总是获取资源,那么黑色(或白色)线程可能会饿死其他类型的线程。如果所有权在可能的情况下立即更改为其他类型,我们将失去跨相同类型线程的并发性的大部分好处;如果传入线程类型的分布大致均匀,则可能一次只运行一种类型的一个线程,所有线程都是顺序的!
有几种可能的解决方案。似乎符合 OP 问题陈述的一个是允许最多N个黑色黑色线程与资源一起运行,然后切换到轮到白人(如果有的话);最多N个白色白色线程与资源一起运行,然后切换到黑色。(时间限制,即同一类型的其他线程也可能抢占资源的宽限期,可能是您在实践中实际使用的。)
我们可以用下面的结构来描述这种锁:
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 \
}
lock
互斥锁仅在检查字段时保留,而不是在资源访问期间。
(还要注意虽然black
初始为0,但当没有跑步者和服务员时,轮到会改变,所以没关系。如果初始black
为1,代码将完全一样。)
我们先看释放bwlock,因为它是更有趣的部分;它是控制转弯变化的东西。假设 lock 和 release 都有一个isblack
参数(0 或 1)。如果释放线程是它的最后一个颜色,而另一个颜色的线程正在等待,它会改变轮次,并在另一个颜色wait
条件变量上广播以唤醒它们:
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;
}
抓取块更复杂。该限制仅适用于没有其他类型的线程等待的情况(因为如果我们这样做,单一颜色的线程会在没有其他颜色的情况下死锁)。
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));
}
pthread_cond_wait(&(bwl->wait[black]), &(bwl->lock))
释放锁并等待条件变量上的信号或广播。收到信号后,它将在返回之前重新获取锁。(在释放锁和等待条件变量时没有竞争窗口;它在同一时间点以原子方式有效地发生。)
如果您考虑上面的逻辑,则bwlock_unlock()
当特定颜色的最后一个运行线程应将“接力棒”处理给另一个线程集时,处理的情况。确定bwlock_lock()
线程是否可以使用资源运行,还是需要等待。只有当没有其他颜色的线程在运行或等待轮到它们时,它才会改变轮到。
这是一个相当简单的方案,但您可能需要考虑几种情况才能理解它的行为。
当轮次started
改变时计数器被清除,并为在该轮次中启动的每个线程递增。当它达到limit
时,将不再启动该类型的线程;他们将等待轮到他们。
比方说limit
,{3, 3}
你每种类型都有四个线程,它们基本上都是同时冲向bwlock的。假设第一个获取锁的线程是黑色的。前三个黑色线程将与资源一起运行,一个黑色和四个白色线程将等待条件变量。当轮换时,三个白色线程开始运行;一个白色,一个随机的,将重新等到下一个白色转弯。
此外,正如 Craig Estey 在对 John Bollingers 回答的评论中指出的那样,这并不能保证同一类型线程之间的公平性。例如,如果 A 和 B 属于同一类型,A 在其回合中多次访问受 bwlock 保护的资源,而 B 只访问一次,则 B 可能必须无限期地等待才能获得回合,因为 A “贪婪”它的所有插槽。
为了保证公平,我们需要某种票证锁或有序等待队列,这样我们就可以唤醒limit
特定颜色的等待时间最长的线程,而不是随机等待的线程。
推荐阅读
- python - 如何在 google colaboratory 中旋转 3D 散点图?
- python - Freeze.py 上的 TensorFlow 简单音频识别错误
- hangfire - 执行 Hangfire 作业时引发“线程被中止”异常
- c# - 如何使用另一个数组和那个数组中存在的值在数组中找到索引?
- hadoop - 该示例如何在 Oozie 最佳案例中找到库?
- elasticsearch - Elasticsearch 汇总作业可以像 Logstash 那样动态创建索引吗?
- css - Bootstrap 3.3.1 间距选项不起作用。有谁知道可能出了什么问题?
- azure - Azure AD B2C - 无法调用 MS Graph API 或 Azure AD Grap API
- google-cloud-platform - 网络的 GCP 错误
- vba - 向每张幻灯片添加蓝色三角形 - 填充不起作用