<<
>>

Определение основных событий

Анализ вероятностных систем такого рода полезно начать с определения основных событий и их вероятностей. Первое событие: для заданного процесса P и заданного кванта времени t событие A[i, t] обозначает попытку обращения P к базе данных

в кванте t.

Известно, что каждый процесс пытается обратиться к базе данных с веро- ятностью р, так что вероятность этого события для любых i и t равна Для каждого события также существует дополняющее событие, которое означает, что основное событие не произошло; в данном случае дополняющее событие Л [к f] означает, что процесс P не пытался обратиться к базе данных в кванте t, а его ве- роятность равна

Главный вопрос — удастся ли процессу обратиться к базе данных в заданном кванте. Обозначим это событие S[i, t].

Очевидно, процесс P должен хотя бы по- пытаться обратиться к базе данных в кванте t. Успешное обращение означает, что процесс Pi попытался обратиться к базе данных в кванте t, а все остальные про- цессы не пытались обращаться к базе данных в кванте t. Следовательно, S[i, t]

равно пересечению события А[i,t] с дополняющими событиями А[j, f\ для j Ф i:

Все события в этом пересечении независимы по определению протокола раз- решения конфликтов. Следовательно, вероятность S[i, t] вычисляется умножением вероятностей всех событий в пересечении:

Рr[⅜ t\] = Рr \А[i,?]]∙ПРr[Т[й]] = р(\-р)”-'.

j*i

Мы получили удобное выражение в замкнутой форме для вероятности того, что P успешно обратится к базе данных в кванте t; теперь уместно задаться во- просом, как выбрать р для максимизации вероятности успеха. Сначала заметим, что вероятность успеха равна 0 для крайних случаев р = 0 и р = 1 (в которых либо процессы вообще не пытаются обратиться к базе данных, либо каждый процесс пытается обратиться к базе данных в каждом кванте, так что в итоге все процессы блокируются).

Функция f(р) =р( 1 ~рУ 1 положительна для значенийр из диапазо- на от 0 до 1, а ее производная fiр) = {\-рY 1-- равна нулю только

в точке р = 1/n, где и достигается максимум. Таким образом, вероятность успеха максимизируется при выборе р = 1/n. (Стоит заметить, что 1/n — естественный и интуитивный вариант в том случае, если в каждом кванте попытка обращения должна исходить ровно от одного процесса.)

Выбирая р = \/п, получаем Рr[S[/, t]] = —

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

(13.1) (а) Функция |l— —1 монотонно сходится от — к - при увеличении ' 1 rt) 4 е '

начиная с 2.

(b) Функция I—I монотонно сходится от — к — при увеличении на-

о I n I

чиная с 2.

Из (13.1) следует, что I Цеп) < Рг[Щ /]]< \f(2п) , а следовательно, значение Рr[

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Определение основных событий:

  1. 2. Определение и основные признаки сделки
  2. 1. Определение ключевых понятий, основные проявления и анализ ядра характера
  3. ПЛАНИРУЯ КАКОЕ-ТО СОБЫТИЕ, ЗАДЕРЖИТЕ В СЕБЕ ЭНЕРГИЮ, А НЕ ВЫПЛЕСКИВАЙТЕ ЕЕ В ЭМОЦИИ ИЛИ В СЛОВА. ЭНЕРГИЯ НУЖНА ДЛЯ ФОРМИРОВАНИЯ ЭТОГО СОБЫТИЯ.
  4. 40. Основные теоретические подходы в определении классов. Немарксистские подходы
  5. Типология органов и основные типологические группы современной российской журналистики (качественные и массовые издания, каналы, программы; органы информации различной функционально-целевой, предметно-тематической, направленности; рассчитанные на определенные группы аудитории, разной периодичности).
  6. 5. События
  7. Статья 55. Лишение права занимать определенные должности или заниматься определенной деятельностью
  8. 3. Юридические факты - события
  9. От рассказа о событиях
  10. События
  11. Правило воспроизводства событий и действий
  12. Заключение по событиям (случаям) и состязаниям
  13. СОБЫТИЕ КАК ПРЕДМЕТ ОТОБРАЖЕНИЯ
  14. Возможность прошлого события.
  15. Секс как Событие
  16. Мобильность освещения событий.
  17. Исторические события.
  18. Историческое событие.
  19. ? Журналист не должен инициировать события.