Имитационная модель многопользовательской работы в ФБП



Posted by Аркадий Водяник on July 28, 1999 at 07:05:37:

Модель выполнена в виде программы на Паскале. Ее исходный текст полностью показан ниже.

Пользователи представлены массивом Users из N элементов. Каталог обмена сообщениями
представлен массивом Box.

Сервер выглядит здесь как переменная ServerP, указывающая на обрабатываемый
запрос в массиве Box, и переменной ServerT, в которой запоминается номер тика,
при котором начинается обработка очередного запроса.

В массиве D строится гистограмма: i-й элемент этого массива увеличивается на единицу
если округленное время ожидания пользователем ответа (время отклика) равно i.

Главная процедура модели - DoTicks. Каждый виток ее цикла - это тик - очередной шаг
во времени. Длительность тика задана константой dt.

На каждом витке своего цикла процедура DoTicks делает следующее:

1) обходит всех пользователей; если при обходе встречаются пользователи, которые МОГУТ
и ХОТЯТ послать запрос, то производятся соответствующие изменения в массивах Box и Users;

2) Если Сервер занимался обработкой запроса в Box, то выясняется, не пора ли завершить
обработку; если пора - то необходимым образом модифицируются Box и Users,
увеличивается счетчик в гистограмме D, Сервер ищет следующий запрос в Box.

ОСНОВНЫЕ ДОПУЩЕНИЯ ЭТОЙ ВЕРСИИ МОДЕЛИ:

a) Сервер выполняет любой запрос за фиксированное время st.

b) Каждый пользователь НЕ МОЖЕТ послать запрос, пока не пришел ответ на предыдущий запрос;
другими словами, он взаимодействует с Сервером по одному каналу (поэтому массивы
Users и Box имеют одинаковое количество элементов)

c) Каждый пользователь стремится выполнить план по запросам. Например, если указано,
что среднее время между запросами пользователя ut = 60с, это значит, что на 6000-й
секунде модельного времени пользователь j будет считать, что он укладывается в план,
если Users[j].R >= 6000/60 (Users[j].R - сделанное количество запросов).
Если пользователь не укладыватеся в план и если он МОЖЕТ, то он ХОЧЕТ послать запрос.
А если укладывается, то его желание или нежелание определяется псевдослучайным образом,
который также обеспечивает заданный средний интервал между запросами : см. подробности
в функции UserWant.

Были проведены эксперименты для N = 10, 20, 28, 30, 31 при st = 2с; ut = 60с.
Каждый эксперимент длился 360000 тиков при dt = 0.1с - т.e. 10 часов модельного времени.
Вот что получилось:

Видно, что при N=10 (красная линия) почти 80% всех времен ожидания ответа укладываются
в интервал 2-3 с, а худшее время не превосходит 8 с.

Для N=20 (синяя линия) в интервал 2-3с укладываются уже чуть более 40% всех случаев,
но результат по-прежнему отличный, так как худшее время менее 15с.

При N=28 (зеленая линия) ситуация еще приемлема.

Значение N=30 (фиолетовая линия) является критическим. В самом деле:
30 пользователей за 10 часов должны сделать 30*10*(3600/60) = 18000 запросов.
Сервер каждый запрос выполняет за st=2с, то есть для выполнения всех этих запросов
требуется 18000*2 = 36000 с, что и есть 10 часов.
График для N=30 имеет какой-то критический, пограничный вид: примерно равномерное
распределение от 20 до 60 с.

И вот уже при N=31 (светло-синяя линия) наступает "коллапс"; при этом все пользователи
почти всегда ждут чуть больше минуты, с планом ни один из них не справляется.

Несколько слов о случае N=600 (предложенном Владимиром Секретевым).
Эксперимент на этой модели показал, что
при dt=0.01c, ut=60с, Mt=3600с потребуется st = 0.05с, чтобы обеспечить время отклика
менее 1с в 86% случаев, и 1..2с - в 5%.

Конечно, допущения в этой версии модели сделаны грубые, и на показанные
результаты не стоит особенно полагаться. Здесь предложен только "каркас"
имитационной модели, который можно дополнять реалистичными подробностями.

{ Исходный тескст имитационной модели версии 0.1
Mногопользовательская работа в ФБП }

(C) 1999 А.Водяник

const N = 10; { кол-во пользователей }
dt = 0.1; { шаг моделиpования - тик }
ut = 60.0; { сpеднее вpемя между запpосами пользователя, с }
st = 2.0; { вpемя выполнения запpоса сеpвеpом, с }
Mt = 36000; { моделиpуемый пеpиод, с }

var Users :array [1..N] of record
Wait :boolean; { ждет ли ответ ? }
T :longint; { тик, когда начал ждать ответ }
R :longint; { сколько он уже послал запpосов }
end;

var Box :array [1..N] of record
Active :boolean; { это еще необpаботанный *.in }
User :integer; { чей запpос }
end;

var ServerP :integer; { позиция в каталоге Box }
ServerT :longint; { тик, когда Сеpвеp начал обpаботку этого запpоса }
ServerN :longint; { общее количество обpаботанных запpосов }

const Dlimit = 10000;
var D :array [0..Dlimit] of longint; { pаспpеделение вpемен, сек - индекс }

var Tick :longint;
LastTick :longint;

function UserWant(n :integer) :boolean;
var r :double;
begin
if not Users[n].Wait
then begin
if Users[n].R < Tick*dt / ut then UserWant:=true { выбиваемся из плана }
else begin
r:=Random(60000);
UserWant:=(r <= 60000*(dt/ut));
{ еще не выбиваемся, но зачем этого дожидаться }
end;
end
else UserWant:=false;
end;


function ServerDone :boolean;
begin ServerDone:=(Tick - ServerT)*dt >= st; end;


procedure DoTicks;
label 1, NextTick;
var i,j,k :integer;
begin
for Tick:=1 to LastTick
do begin
for i:=1 to N
do if UserWant(i)
then begin
Users[i].Wait:=true; Users[i].T:=Tick; inc(Users[i].R);
for j:=1 to N
do if not Box[j].Active
then begin Box[j].Active:=true; Box[j].User:=i; goto 1; end;
writeln('так не должно быть - не нашлось место в каталоге!'); halt;
1:
end;

if Box[ServerP].Active
then if ServerDone
then begin
Box[ServerP].Active:=false;
k:=round((Tick - Users[Box[ServerP].User].T)*dt);
Users[Box[ServerP].User].Wait:=false;
inc(D[k]); inc(ServerN);
end
else goto NextTick;

for i:=ServerP+1 to N
do if Box[i].Active
then begin ServerP:=i; ServerT:=Tick; goto NextTick; end;

for i:=1 to ServerP-1
do if Box[i].Active
then begin ServerP:=i; ServerT:=Tick; goto NextTick; end;

ServerT:=Tick;

NextTick:
end;
end;


procedure Init;
begin
LastTick:=round(Mt / dt);
ServerP:=1; ServerT:=0; ServerN:=0;
FillChar(Users, sizeof(Users), 0);
FillChar(Box, sizeof(Box), 0);
FillChar(D, sizeof(D), 0);
end;


procedure PrintD;
var i :integer;
begin
for i:=1 to N
do begin
if Users[i].R < LastTick*dt / ut
then writeln(i, ' не выполнил план');
end;
writeln;

writeln('ServerN=', ServerN);

for i:=0 to 180 do writeln(100.0*D[i]/ServerN:5:2);
end;

begin Init; DoTicks; PrintD; end.




Пpишедшие ответы: