Chapitre 10 • Simulation
386
arme un délai d’attente de l’acquit te ment (accusé de récep tion) par le client, au bout
duquel ce ser veur, en cas d’échec, ré émet la réponse.
Dans ce pro to cole, tous ces envois ou récep tions ou pertes de mes sage sont des
évé ne ments. Dans un cas réel, le pro to cole serait plus com plexe, et par consé quent,
le graphe d’états pour rait être très grand (plu sieurs mil lions d’états). Une simu la tion
du fonc tion ne ment du pro to cole per met un réglage adé quat des délais de garde afin
de res pec ter des prop rié tés requises de bon fonc tion ne ment, spé ci fiées dans un cahier
des charges ; par exemple : la requête ne doit pas être exé cu tée plus d’une fois.
10.2 défi ni tionS
Il est donc essen tiel, pour effec tuer une simu la tion, d’engen drer des séquences d’évé
ne ments, à cha cun étant asso cié une date d’occur rence. Les évé ne ments sont ordon
nan cés (lis tés), sui vant leur date d’occur rence, dans un « échéancier ».
10.2.1 Notion d’échéan cier et de noyau de syn chro ni sa tion
Un échéan cier est donc repré senté par une struc ture de don nées qui per met de sto cker
les évé ne ments, leur date d’occur rence ainsi que le trai te ment asso cié. L’ensemble
des pro cé dures qui entre tiennent et mani pulent l’échéan cier lors de chaque occur rence
d’évé ne ment (insé rer, sup pri mer des évé ne ments, etc.) s’appelle le « noyau de syn
chro ni sa tion ». L’effi ca cité de celui ci dépend beau coup de la struc ture de don nées
choi sie, des algo rithmes d’entre tien de l’échéan cier, du nombre d’évé ne ments et de la
dis tri bu tion des inter valles de temps entre évé ne ments consé cu tifs dans l’échéan cier.
10.2.2 Méthodes de ges tion de l’échéan cier
Com ment évo lue le temps dans une simu la tion ? Il y a deux sché mas pos sibles.
Simu la tion diri gée par évé ne ments
Les seuls temps acces sibles lors de la simu la tion à évé ne ments dis crets sont les dates
d’occur rences d’évé ne ments, l’incrémentation du temps se fait d’une date à la sui
vante (« next event scheduling »). L’échéan cier est ordon nancé dans une struc ture de
don nées qui peut être une liste ou un arbre binaire équi li bré.
Dans le cas d’une « liste », les évé ne ments sont sto ckés par ordre crois sant de
date d’occur rence. Le pro chain évé ne ment à trai ter dans le temps est tou jours en tête
de liste. Lors de l’exé cu tion de la simu la tion, chaque fois qu’un nou vel évé ne ment
inter vient, la liste est par cou rue pour l’insé rer à sa place (déter mi née par sa date
d’occur rence) ; la com plexité de cette recherche pour une liste com por tant Ν évé ne
ments est de Ο(N).
Dans le cas de la struc ture de don nées « arbre binaire équi li bré », les évé ne ments
sont orga ni sés comme suit : chaque évé ne ment a au plus deux fils, cor res pon dant
res pec ti ve ment l’un à une date infé rieure et l’autre à une date supé rieure à la date de
cet évé ne ment (père). On éli mine à chaque test toute une par tie des pos si bi li tés res
386
arme un délai d’attente de l’acquit te ment (accusé de récep tion) par le client, au bout
duquel ce ser veur, en cas d’échec, ré émet la réponse.
Dans ce pro to cole, tous ces envois ou récep tions ou pertes de mes sage sont des
évé ne ments. Dans un cas réel, le pro to cole serait plus com plexe, et par consé quent,
le graphe d’états pour rait être très grand (plu sieurs mil lions d’états). Une simu la tion
du fonc tion ne ment du pro to cole per met un réglage adé quat des délais de garde afin
de res pec ter des prop rié tés requises de bon fonc tion ne ment, spé ci fiées dans un cahier
des charges ; par exemple : la requête ne doit pas être exé cu tée plus d’une fois.
10.2 défi ni tionS
Il est donc essen tiel, pour effec tuer une simu la tion, d’engen drer des séquences d’évé
ne ments, à cha cun étant asso cié une date d’occur rence. Les évé ne ments sont ordon
nan cés (lis tés), sui vant leur date d’occur rence, dans un « échéancier ».
10.2.1 Notion d’échéan cier et de noyau de syn chro ni sa tion
Un échéan cier est donc repré senté par une struc ture de don nées qui per met de sto cker
les évé ne ments, leur date d’occur rence ainsi que le trai te ment asso cié. L’ensemble
des pro cé dures qui entre tiennent et mani pulent l’échéan cier lors de chaque occur rence
d’évé ne ment (insé rer, sup pri mer des évé ne ments, etc.) s’appelle le « noyau de syn
chro ni sa tion ». L’effi ca cité de celui ci dépend beau coup de la struc ture de don nées
choi sie, des algo rithmes d’entre tien de l’échéan cier, du nombre d’évé ne ments et de la
dis tri bu tion des inter valles de temps entre évé ne ments consé cu tifs dans l’échéan cier.
10.2.2 Méthodes de ges tion de l’échéan cier
Com ment évo lue le temps dans une simu la tion ? Il y a deux sché mas pos sibles.
Simu la tion diri gée par évé ne ments
Les seuls temps acces sibles lors de la simu la tion à évé ne ments dis crets sont les dates
d’occur rences d’évé ne ments, l’incrémentation du temps se fait d’une date à la sui
vante (« next event scheduling »). L’échéan cier est ordon nancé dans une struc ture de
don nées qui peut être une liste ou un arbre binaire équi li bré.
Dans le cas d’une « liste », les évé ne ments sont sto ckés par ordre crois sant de
date d’occur rence. Le pro chain évé ne ment à trai ter dans le temps est tou jours en tête
de liste. Lors de l’exé cu tion de la simu la tion, chaque fois qu’un nou vel évé ne ment
inter vient, la liste est par cou rue pour l’insé rer à sa place (déter mi née par sa date
d’occur rence) ; la com plexité de cette recherche pour une liste com por tant Ν évé ne
ments est de Ο(N).
Dans le cas de la struc ture de don nées « arbre binaire équi li bré », les évé ne ments
sont orga ni sés comme suit : chaque évé ne ment a au plus deux fils, cor res pon dant
res pec ti ve ment l’un à une date infé rieure et l’autre à une date supé rieure à la date de
cet évé ne ment (père). On éli mine à chaque test toute une par tie des pos si bi li tés res