Com calcular les mides de les cues en un RTOS

A entrades anteriors hem parlat de que es poden comunicar tasques entre elles mitjançant cues. Aquestes estructures emmagatzemen un seguit de dades de manera que una tasca les pot enviar cap a la cua i una altra tasca les va agafant quan li faci falta. El ritme d’enviar dades a la cua i de treure-les pot ser diferent, fent que les dues tasques vagin “desincronitzades” entre elles.

Però, com saber quants elements cal atorgar a una cua en la seva creació? Aquest paràmetre serà clau, ja que si creem una cua amb pocs elements disponibles, la tasca productora potser es quedi bloquejada si la tasca consumidora no va prou de pressa. Tot i que es pot triar aquest valor d’una forma empírica, començant per un valor prou baix i fent proves i via successives aproximacions arribar a un valor prou bo.

Aquest mètode, però, no ens assegura que en qualsevol cas el sistema no acabi amb una cua plena. Per això, cal un anàlisi més analític del problema per trobar una solució.

Model M/M/1

Aquest model de cues és dels models estadístics més senzills però que ens pot donar informació important només amb les dades més bàsiques del nostre sistema. Aquest model fa certes suposicions que podem donar per bones pels nostres sistemes:

  • El productor genera noves entrades a la cua seguint una distribució de Poisson.
  • El consumidor processa dades a la cua seguint una distribució exponencial.
  • Només hi ha un productor.
  • La cua és de tipus FIFO

Amb aquestes suposicions ens cal trobar els paràmetres λ i μ pel productor i el consumidor respectivament, ara es veurà com.

Si la nostra tasca consumidora genera un element nou a la cua de mitjana (seguint una distribució de Poisson) cada cert Pr temps tindrem

Pr = temps mitjà a generar una dada

i llavors tindrem que
λ = 1 / Pr

El mateix càlcul el podem fer pel temps de la tasca consumidora (que segueix una distribució exponencial):

C = temps mitjà a processar una dada

i llavors tindrem que

μ = 1 / C

Amb aquestes dades, tenim les següents fórmules:
ρ =C / Pr = λ / μ

Aquesta primer valor ρ ens indica si el sistema és factible o no: si ρ és més petit d’1 (ρ < 1), la cua té sentit, en cas contrari, el ritme de inserir elements a la cua és més ràpid que el ritme de treure’ls i, per tant. la cua s’acabarà omplint en algun moment o altre i el productor haurà de llençar dades que no podrà inserir a la cua.

Amb aquest valor ρ (o amb Pr i C) podem obtenir els següents càlculs:

Nombre mitjà d’elements a la cua

Temps mitjà de vida a la cua:

Temps total d’estada en el sistema (procés més espera a la cua):

Nombre mitjà d’elements al sistema:

Probabilitat que la cua tingui més de K elements:

Un exemple

Anem a proposar un exemple per tal d’entendre millor aquestes fórmules i el què signifiquen.

Així si, per exemple, tenim una tasca productora que genera una dada cada 50 ms i una tasca consumidora que processa una dada en uns 30 ms de mitjana, tenim els següents resultats:

Pr = 50 ms
C = 30 ms

i per tant

ρ = C / Pr = 30 / 50 = 0.6

Nombre mitjà d’elements a la cua

Temps mitjà de vida a la cua

Temps total de vida d’una dada

Nombre mitjà d’elements a la cua

Probabilitat que la cua tingui més de 10 elements

Aquestes equacions ens indiquen que durant bona part del temps de funcionament del sistema, la cua entre els dos processos tindrà tant sols 1 element, i que la probabilitat que tingui més de 10 elements en algun moment és de només el 0,60%. Cal fer notar que aquest valor probabilístic té en compte que els processos que generen dades es comporten com una variable aleatòria tipus Poisson i els temps de processat les dades s’ajusta a una variable aleatòria exponencial. Si algun dels dos processos no es comporta com a tal, si no que el seu temps de procés o de generació de dades és fix, els valors Lq , W q, W i L seran certs en tot moment.

Manipulant una mica les fórmules, també podem esbrinar quin temps màxim de procés podem tenir per una tasca que genera dades cada 25 ms i volem menys d’un 0.1% de probabilitats que la cua arribi a tenir 8 elements.

Tenim, doncs:

Pr = 25 ms
K = 8

I segons les fórmules anteriors:

Probabilitat que la cua tingui més de K elements

per tant tenim

Això ens indica que el temps de processar una dada per part el consumidor (C) ha de ser més petit de 10.54 mil·lisegons de mitjana per assegurar els requeriments donats.

Anuncis

Deixa un comentari

Fill in your details below or click an icon to log in:

WordPress.com Logo

Esteu comentant fent servir el compte WordPress.com. Log Out /  Canvia )

Google photo

Esteu comentant fent servir el compte Google. Log Out /  Canvia )

Twitter picture

Esteu comentant fent servir el compte Twitter. Log Out /  Canvia )

Facebook photo

Esteu comentant fent servir el compte Facebook. Log Out /  Canvia )

S'està connectant a %s

Aquest lloc utilitza Akismet per reduir els comentaris brossa. Apreneu com es processen les dades dels comentaris.