Задача про 3 буфера

[Vaarallinen]

Есть следующая задача:

Имеется диспечер (Д1), который с определенными вероятностями $P_1,P_2,P_3$ соответственно на каждом шагу (такте) выбирает один из 3 буферов, чтобы поместить туда заявку. Ёмкость каждого буфера равна $n$. Так продолжается $n$ шагов. После чего в работу включается второй диспечер (Д2), который с определенными вероятностями $G_1,G_2,G_3$ безвозвратно забирает заявки из буферов. Требуется найти вероятность блокировки системы на $n+k$ - ом шагу, где $k > 1$. Блокировкой считается такое состояние системы, когда первый диспечер пытается положить заявку в уже заполненный буфер, а второй диспечер одновременно с этим пытается извлечь заявку из пустого буфера.

Например, для первого буфера можно записать:
$P^n_1 \cdot (G_2 + G_3) \cdot P^{k-1}_1 \cdot G^{k-1}_1$

Аналогично для остальных буферов.

Но это выглядит как какой-то сильно идеализированный случай. Как понимаю, для шагов выше $n+1$ нужно, чтобы для заполняемого до предела буфера извлечение заявок завершилось заранее. Не знаю, как еще объяснить что имею в виду, но попробую так: пусть на одном из следующих шагов за $n+1 $ шагом в одном из буферов ровно $n$ заявко. Тогда, если Д1 пытается поместить в этот буфер заявку, то он получит блокировку, а число заявок в буфере останется n. Тем временем, Д2 может на том же шагу забрать заявку из этого буфера, и заявок станет $n-1$. Таким образом, может случится так,что в заполняемом буфере на $n+k-1$ шаге в буфере $n-1$ заявка. Тогда на $n+k $не получим блокировки в указанном смысле. В общем, порядок событий имеет значение. И не понятно, как его учесть. Пожалуйста, посоветуйте что-нибудь.

[Vaarallinen]

[Vaarallinen]

Посоветуйте, пожалуйста, какую-нибудь стратегию.

[svv]

Vaarallinen в сообщении #1084489 писал(а):

Блокировкой считается такое состояние системы, когда первый диспечер пытается положить заявку в уже заполненный буфер, а второй диспечер одновременно с этим пытается извлечь заявку из пустого буфера.

1) А если первый диспетчер пытается положить заявку в уже заполненный буфер, а второй выполняет корректное действие, разве блокировка не возникает? Или, если первый выполняет корректное действие, но второй пытается извлечь заявку из пустого буфера, разве блокировка не возникает?

2) В последнем абзаце Вы ставите вопрос о корректной модели синхронной работы диспетчеров. Действительно, от малого временного сдвига действий может зависеть, наступит блокировка или нет.

Чтобы «гонок» не было, примите такую модель. Пусть в буферах было соответственно $a_1, a_2, a_3$ заявок. Допустим, первый диспетчер выбрал буфер 1, а второй — буфер 3. Находим состояние после действий обоих диспетчеров:
$a_1+1, a_2, a_3-1$
Если оно окажется некорректным ($a_1+1>n$ или $a_3-1<0$), тогда блокировка.

Пусть теперь оба выбирают первый буфер. Учитываем оба изменения и присваиваем каждому счетчику его новое значение после хода:
$a_1, a_2, a_3$,
где $a_1$ получено как $a_1+1-1$, либо как $a_1-1+1$, но результат от этого не зависит.

Иными словами, считаем, что нет такого момента, когда один диспетчер уже сделал своё действие, а второй нет. Состояние счетчика может измениться не более одного раза за дискретный шаг.

[Vaarallinen]

svv в сообщении #1091365 писал(а):

1) А если первый диспетчер пытается положить заявку в уже заполненный буфер, а второй выполняет корректное действие, разве блокировка не возникает? Или, если первый выполняет корректное действие, но второй пытается извлечь заявку из пустого буфера, разве блокировка не возникает?

Возникает, но только по одному диспечеру. А надо, чтобы блокировка наступала одновременно по обоим диспечерам.

[svv]

Тогда надо оговорить, что всё-таки происходит, когда первый пытается положить заявку в полный буфер или второй пытается взять из пустого, но не то и другое одновременно. Первый продолжает держать заявку в руках ( т.е. не кладёт её ни в какой буфер)? Скрепя сердце кладёт в другой буфер? А если остальные тоже заполнены? Возникает исключение и работа прерывается?

Вам подходит мой способ предотвращения race condition?

[Vaarallinen]

svv в сообщении #1091439 писал(а):

Первый продолжает держать заявку в руках ( т.е. не кладёт её ни в какой буфер)?

Да,именно так.

[svv]

А этот вопрос?

svv в сообщении #1091439 писал(а):

Вам подходит мой способ предотвращения race condition?

Я не напрашиваюсь на похвалу, мне надо знать, могу ли я принять свою модель, когда вклады от действий обоих диспетчеров суммируются и только потом прибавляются к счетчикам (что исключает гонки).

[Vaarallinen]

svv в сообщении #1091442 писал(а):

А этот вопрос?

В стартовом посте было такое описание:

Цитата:

пусть на одном из следующих шагов за $n+1 $ шагом в одном из буферов ровно $n$ заявок. Тогда, если Д1 пытается поместить в этот буфер заявку, то он получит блокировку, а число заявок в буфере останется n. Тем временем, Д2 может на том же шагу забрать заявку из этого буфера, и заявок станет $n-1$.

[svv]

Тогда почему это осталось проблемой?

Vaarallinen в сообщении #1084489 писал(а):

В общем, порядок событий имеет значение. И не понятно, как его учесть.

Вы предложили один способ учёта совместного доступа к буферу, я другой, выбирайте любой.

[Vaarallinen]

svv в сообщении #1091449 писал(а):

Тогда почему это осталось проблемой?

Как я понимаю, для рассмотрения этой модели лучше всего подходит полиноминальное распределение. Но коэффициент этого распределения учитывает все возможные варианты, а по условию задачи подходят далеко не все варианты. Вот я и не понимаю,как это учесть.

[svv]

Вас устроило бы найти вероятности численно, без явной формулы?

(Оффтоп)

Я заглянул в suomalais-venäläinen sanakirja — «опасный, рискованный».

[Vaarallinen]

svv в сообщении #1091486 писал(а):

Вас устроило бы найти вероятности численно, без явной формулы?

К сожалению, нет. Но,возможно, если Вы поделитесь знанием как получить численные оценки, то я смогу получить общий случай :)

(Оффтоп)

Цитата:

Я заглянул в suomalais-venäläinen sanakirja — «опасный, рискованный».

Знаю :) Где-то увидел это слово, и оно мне понравилось.

[svv]

Нет, оценок у меня как раз нет. Я знаю, как получить точные цифры, но численно, не с помощью явных формул (фактически, с помощью рекуррентных).

[Vaarallinen]

svv в сообщении #1091503 писал(а):

Нет, оценок у меня как раз нет. Я знаю, как получить точные цифры, но численно, не с помощью явных формул (фактически, с помощью рекуррентных).

Интересно было бы взглянуть на Ваши рассуждения (т.е., в чем Ваша идея).