Титул
Цель
Обзор
Послед. предст-е
Связ-ое предст-е
Результаты
Заключение
Последовательное представление двух циклических FIFO очередей
Под последовательной реализации очередей обычно понимают циклическую организацию, так как в противном случае очередь быстро уходит в бесконечность. Учитывая, что в нашем случае память ограниченного размера m, то использование циклических очередей более чем целесообразно (иначе бы мы за малое количество шагов получили переполнение).
Известны некоторые вероятностные характеристики очередей. Пусть p1, q1 обозначают вероятности включения и исключения элементов в первую очередь, p2, q2 - во вторую, а r обозначает вероятность операции, не изменяющей длины очередей (например, только чтение), где p1+q1+p2+q2+r=1. Предполагается, что в очередях хранятся данные фиксированного размера.
Обозначим через x1 и x2 текущие длины очередей, через s максимальный размер первой очереди. В реализации циклической очереди принято один элемент памяти всегда оставлять свободным. Это делается для того, чтобы удобно было отличать пустую очередь от переполненной. А так как у нас 2 очереди, то максимальный размер двух очередей будет n=m-2.
Рис.1 Область блуждания:
Тогда в качестве модели мы будем иметь двумерное блуждание по целочисленной решетке в области , с вероятностями переходов: p1 - вправо, q1 - влево, p2 - вверх, q2 - вниз, r - остаться на месте (Рис 1.1). Блуждание начинается в точке x1=x2=0. При попытке исключения из пустой (первой или второй) очереди попадаем соответственно на прямую x1=-1 или x2=-1. Эти прямые называются отражающими экранами. При переполнении первой или второй очереди попадаем соответственно на прямую x1=s+1 или x2=n-s+1 - это поглощающие экраны.
Ставится задача выбрать такое s, чтобы математическое ожидание времени блуждания до поглощения было максимальным.
Петрозаводск - 2006
