Рассмотрим следующий расширенный комментарий к Ответ Джона Боллинджера .
Описанные правила 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;
}
Захватить 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));
}
pthread_cond_wait(&(bwl->wait[black]), &(bwl->lock)) снимает блокировку и ждетдля сигнала или трансляции по условной переменной.При получении сигнала он снова получит блокировку перед возвратом.(При снятии блокировки и ожидании переменной условия нет окна гонки; это происходит атомарно, эффективно в один и тот же момент времени.)
Если вы рассмотрите логику выше, bwlock_unlock() обрабатывает случайкогда последняя запущенная нить определенного цвета должна обрабатывать «жезл» для другого набора нитей.bwlock_lock() определяет, может ли поток работать с ресурсом или должен ждать.Он изменит ход, только когда нет нитей другого цвета, бегущих или ожидающих своего хода.
Это довольно простая схема, но вам, возможно, придется подумать о нескольких случаях, чтобы понять его поведение.
Счетчик started очищается при изменении хода и увеличивается для каждого потока, который был запущен в течение этого хода.Когда он достигает limit, потоки этого типа больше не запускаются;они будут ждать своей очереди.
Допустим, limit - это {3, 3}, и у вас есть четыре нити каждого типа, и они в основном все устремляются к bwlock одновременно.Допустим, первая нить, которая захватит замок, черная.Три первых черных потока будут работать с ресурсом, а один черный и четыре белых потока будут ожидать переменную условия.Когда ход меняется, три белых потока начинают работать;один белый, случайный, будет ждать до следующего хода белых.
Кроме того, как указывает Крейг Эстей в комментарии к ответу Джона Боллинджера, это не гарантирует справедливости среди потоков одного типа.Например, если A и B относятся к одному и тому же типу, A обращается к ресурсу, защищенному от bwlock, несколько раз в течение своего хода, а B - только один раз, B может ждать неопределенное время, прежде чем получить ход, потому что A "боровает"все его слоты.
Чтобы гарантировать справедливость, нам понадобится какая-то блокировка билета или упорядоченные очереди ожидания, чтобы мы могли пробуждать limit дольше ожидающих потоков определенного цвета вместослучайные ожидающие.