Appunti di Sistemi Operativi Enzo Mumolo e-mail address ...Capitolo 1 Sistemi a code d'attesa 1.1...

Appunti di Sistemi Operativi

Enzo Mumolo

e-mail address :[email protected] address :www.units.it/mumolo

Indice

1 Sistemi a code d'attesa 11.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Richiami sulle variabili aleatorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2.1 La distribuzione esponenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.2.2 La distribuzione di Poisson . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2.3 La distribuzione gaussiana . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.2.4 La distribuzione geometrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3 Applicazione delle distribuzioni statistiche . . . . . . . . . . . . . . . . . . . . . . . . 91.3.1 Modello a coda semplice: M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.2 Modello di coda ciclica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4 Modello a uido continuo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.5 Esempi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.5.1 Esempio 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.5.2 Esempio 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.5.3 Esempio 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.5.4 Esempio 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.5.5 Esempio 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.5.6 Esempio 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.5.7 Esempio 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.5.8 Esempio 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.5.9 Esempio 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.5.10 Esempio 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.5.11 Esempio 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.5.12 esempio 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

1.6 Un modello a code d'attesa della multiprogrammazione . . . . . . . . . . . . . . . . . 251.6.1 Primo problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251.6.2 Secondo problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261.6.3 Terzo problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261.6.4 Un esempio applicativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

i

Capitolo 1

Sistemi a code d'attesa

1.1 Introduzione

In questo capitolo sono riportati alcuni richiami su concetti fondamentali sulla analisi analitica deisistemi di coda d'attesa per applicazioni nella analisi e dimensionamento di alcuni aspetti dei SistemiOperativi.

1.2 Richiami sulle variabili aleatorie

Il discorso sulle variabili aleatorie parte dal concetto di esperimento casuale: ossia un esperimentodal quale si ottiene in risultato incerto (ovvero un risultato non regolato da relazioni deterministiche,quindi non è possibile calcolare il risultato ma quest'ultimo soddisfa delle caratterisiche di media).Il risultato dell'esperimento sarà dunque un ω ∈ Ω con Ω spazio dei campioni.

Esempi:

- Se l'esperimento casuale è il lancio di un dado allora Ω = 1, 2, 3, 4, 5, 6

- Se l'esperimento casuale è il lancio di una moneta allora Ω = T,C

- Se l'esperimento casuale è la misurazione della temperatura allora Ω ⊂ R

Nel nostro caso, al ne di semplicare il discorso, possiamo sempre far riferimento al camporeale in quanto nulla ci vieta di considerare una variabile X(ω) : Ω → R che è una variabile cheprende i valori da Ω e fornisce valori in R (Es.: lanciando un dado l'evento 5 ∈ N diventa 5 ∈ R).Così facendo X è una variabile aleatoria reale; in queste note si farà sempre riferimento a variabilialeatorie appartenenti ad un sottoinsieme di R.

Supponiamo che una variabile aleatoria x, tra 0 e 4, sia il risultato di una serie di esperimenticasuali. Gli esperimenti casuali forniscono i seguenti risultati: 1 3 4 2 1 3 3 1 2 2 3 2 0 2 1 2, cioèvengono fatti 16 esperimenti, dai quali il numero 3 esce quattro volte, il numero 2 esce sei volte ecosì via. Ciò vuol dire che il numero 3 è associato alla probabilità 4/16, il numero 2 è associatoalla probabilità 6/16 e così via. Questo può essere visualizzato con l'istogramma delle probabilitàdi g. 2.1. L'altezza di ciascun rettangolo è la probabilità associata alla variabile aleatoria x.Rappresentando x = 0 con l'intervallo da -0.5 a 0.5, x = 1 con l'intervallo da 0.5 a 1 e così via,è possibile associare le probabilità alle aree dei rettangoli. Ci sono diversi vantaggi nell'associarel'area dell'istogramma - o distribuzione delle probabilità - alla probabilità. Per esempio, quando siapprossima l'istogramma con curve continue, la probabilità può essere calcolata mediante integrali,che comportano una maggiore semplicità degli sviluppi analitici.

1

1.2 Richiami sulle variabili aleatorie 2

Denotiamo con P (A) e P (B) le probabilità degli eventi A e B. Se l'avverarsi di A è condizionatoall'avverarsi di B, si parla di probabilità di A condizionata a B, e si indica con

P (A | B)

Nel caso di indipendenza statistica si ha che

P (A ∩ B) = P (A)P (B)

Nel caso invece in cui ci sia dipendenza si ha che

P (A ∩ B) = P (A)P (B | A) = P (B)P (A | B)

da cui segue la nota Formula di Byes

P (A) =P (A | B)P (B | A)

P (B)

Parlando dell'insieme dei numeri reali, l'evento P (X = x) è un evento che normalmente hauna probabilità di valore innitesimo; per ovviare a questo problema ha più senso parlare dellaprobabilità che X ≤ x: questo evento ha così una probabilità che non è più innitesimale. Questoevento viene chiamato funzione cumulatiba di distribuzione di probabilità e si denota con:

F(X) = ProbX ≤ x

Ora diremo che la variabile aleatoria X ha densità f se

F(X) =∫ x

−∞f(ξ) dξ

Naturalmente queste due funzioni sono legate dalla relazione:

f(x) =∂F(X)∂x

A questo punto possiamo valutare:

Probx1 ≤ X ≤ x2 =∫ x2

x1

f(ξ) dξ

Ne consegue che∫ +∞−∞ f(ξ) dξ = 1.

Possiamo anche vedere che:∫ x2

x1

f(ξ) dξ =∫ x2

−∞f(ξ) dξ −

∫ x1

−∞f(ξ) dξ = F(X2)− F(X1)

Per descrivere meglio queste funzioni si utilizzano dei momenti statistici; la descrizione statisticadelle variabili aleatorie (denita dai momenti) serve a mettere in luce alcune loro caratteristicheparticolari che possono essere utilizzate in questo contesto.

Denizione 1 Si denisce momento del k-esimo ordine attorno alla variabile w il valore∫ +∞

−∞(x− w)kf(x) dx

A questo punto siamo pronti per denire altri due concetti fondamentali.


Denizione 2 Si denisce speranza matematica della variabile x il valore

E(X) =∫ +∞

−∞x f(x) dx = λx

La speranza matematica altro non è il momento del primo ordine attorno allo zero. Appare subito

chiaro, mettendo la denizione della speranza matematica in questa forma: E(X) =R +∞−∞ x f(x) dxR +∞−∞ f(x) dx

,

che il parametro λx può essere interpretato come centro di gravità o baricentro della distribuzione(vedi gura 2.2).

Denizione 3 Si denisce momento del secondo ordine attorno a λx il valore

var2(X) =∫ +∞

−∞(x− λx)2f(x) dx = σ2

X

La radice quadrata di questa quantità è lo scarto quadratico medio, σX .Questi due momenti sono i più semplici e i più usati per descrivere queste distribuzioni e sono

quelle che bastano per delineare moltissime caratteristiche delle variabili aleatorie.Un primo esempio riguarda il noto signicato sico dello scarto quadratico medio di una dis-

tribuzione, cioè quello di dispersione della probabilità intorno alla media. In altri termini possiamodire che più lo scarto quadratico medio è piccolo, più la densità è concentrata intorno alla me-dia. Questo può essere subito visto mediante il seguente Teorema, che vale per qualsiasi tipo didistribuzione.

Teorema di Bienaymé-Chebyshev 1.2.1

Prob| x− λx |≥ kσ ≤ 1k2

Distinguiamo i due casi:

- Se | x− λx |> 0 ⇒ x− λx ≥ kσ ⇒ x ≥ λx + kσ- Se | x− λx |< 0 ⇒ −(x− λx) ≥ kσ ⇒ x ≤ λx − kσ

Questo signica che se rappresentiamo la funzione di distribuzione secondo una curva qualsiasi(vedi gura 2.3) allora la somma delle aree tratteggiate (le 'code' della distribuzione) è minore ouguale a 1/k2. Infatti, se moltiplichiamo la relazione presentata nella enunciazione del Teorema per-1 e se sommiamo 1 ad entrambi i termini, si ottiene

Prob| x− λx |< kσ > k2 − 1k2

ovvero Probλx − kσ < x < λx + kσ > k2−1k2 . Cioè, l'area della zona centrale in gura 2.3 è

maggiore di una costante. Questo vuol dire che se σ diminuisce, l'altezza della curva aumenta.Quindi il signicato dello scarto quadratico medio è quello di dispersione intorno alla media.

Ora, tornando alla varianza:

var2(X) = σ2(X) =∫ +∞

−∞(x2 + λ2

x − 2xλx)f(x) dx

=∫ +∞

−∞x2 f(x) dx+ λ2

x

∫ +∞

−∞f(x) dx︸︷︷︸=1

− 2λx

∫ +∞

−∞x f(x) dx︸︷︷︸=λx

=∫ +∞

−∞x2 f(x) dx+ λ2

x − 2λ2x = E(X2)− E2(X)


ovvero: var2(X) = E(X2)− E2(X)

A questo punto complichiamo le cose; introduciamo un'altra variabile:

ProbX ≤ x, Y ≤ y = F(X,Y ) =∫ x

−∞

∫ y

−∞f(ξ1, ξ2) dξ1 dξ2

Questa è un'estensione del caso a una sola variabile, di conseguenza le considerazioni fatte inprecedenza valgono anche in questo caso: per esempio esiste un valor medio attorno allo zero, ovveroesiste una

E(φ(x, y)) =∫∫ +∞

−∞φ(x, y)f(x, y) dx dy

così come esiste una varianza:

σ2φ(x,y) =

∫∫ +∞

−∞[φ(x, y)− E(φ(x, y))]2(f(x, y) dx dy

Il fatto di avere a che fare con due variabili aleatorie introduce due possibilità che riguardanola dipendenza o l'indipendenza tra le due variabili; per parlare di indipendenza bisogna anzituttointrodurre delle descrizioni statistiche di due variabili aleatorie; una descrizione usuale è quella dellacovarianza:

cov(X,Y ) =∫∫ +∞

−∞(x− λx)(t− λy)f(x, y) dx dy

Sviluppando i conti troviamo che:

cov(X,Y ) =∫∫ +∞

−∞(x− λx)(t− λy)f(x, y) dx dy

=∫∫ +∞

−∞(xy − xλy − yλx + λxλy)f(x, y) dx dy

=∫∫ +∞

−∞xyf(x, y) dx dy − λy

∫∫ +∞

−∞xf(x, y) dx dy +

−λx

∫∫ +∞

−∞yf(x, y) dx dy + λxλy

∫∫ +∞

−∞f(x, y) dx dy︸︷︷︸

=1

= E(X,Y )− λy

∫ +∞

−∞x

(∫ +∞

−∞f(x, y) dy

)︸︷︷︸h(x)=densita marginale

dx− λx

∫ +∞

−∞yg(x) dy︸︷︷︸λy

+E(X)E(Y )

= E(X,Y )− E(X)E(Y )

Ovvero possiamo sottolineare la seguente

Proprietà 1 cov(X,Y ) = E(X,Y )− E(X)E(Y )

A questo punto diamo una denizione di variabili aleatorie indipendenti

Denizione 4 Due variabili aleatorie sono indipendenti se le loro distribuzioni sono fattorizzabili:

f(x, y) = h(x)g(y).


Abbiamo visto che cov(X,Y ) = E(X,Y )− E(X)E(Y ). Ora

E(X,Y ) =∫∫ +∞

−∞xy f(x, y) dx dy

Se le due variabili aleatorie sono indipendenti si ha che

E(X,Y ) =∫∫ +∞

−∞xy g(x)h(y) dx dy

=∫ +∞

−∞x g(x) dx ·

∫ +∞

−∞y h(y) dy

= E(X) · E(Y )

Di conseguenza abbiamo vericato la seguente proprietà:

Proprietà 2 Per variabili indipendenti si ha che cov(X,Y ) = 0

Esempio. Nel caso seguente le due variabili x e y sono indipendenti perchè:

f(x, y) = e−(x+y) = e−x · e−y

La covarianza in generale vale zero se variabili sono indipendenti. In realtà la covarianza èuna quantità importante per misurare il livello di indipendenza di due variabili. Il particolare lacorrelazione normalizza questa misura:

corr(X,Y ) =cov(X,Y )σxσy

Il suo valore è compreso tra -1 e +1. Per variabili indipendenti, la correlazione è nulla. Se tuttaviala correlazione è nulla, non è necessariamente vero che le variabli sono indipendenti. Infatti percorr = 0 le due variabili sono non correlate, mentre per corr = 1 o corr = −1 sono assolutamentedipendenti (dipendenza lineare positiva o negativa).

Finora abbiamo analizzato il caso in cui φ(x, y) = (x − λx)(y − λy), che in qualche modo è unmomento statistico che ha delle relazioni con la varianza. è interessante ora vedere cosa succede secambio la funzione φ(x, y); per esempio se

φ(x, y) = x+ y

quanto vale E(x+ y)?

E(X,Y ) =∫∫ +∞

−∞(x+ y) f(x, y) dx dy

=∫ +∞

−∞x f(x, y) dx ·

∫ +∞

−∞y f(x, y) dy

= E(X) + E(Y )

In generale vale la seguente proprietà:

Proprietà 3 La speranza matematica della combinazione lineare di due variabili aleatorie è data

dalla combinazione lineare delle rispettive speranze matematiche:

E(aX + bY ) = aE(X) + bE(Y )


Ora che abbiamo calcolato la E(x + y) vediamo come risulta la σ2(x + y) (ovvero la varianzadella somma di due variabili aleatorie).

σ2(x+ y) =∫∫ +∞

−∞

[(x+ y)− E(x+ y)

]2f(x, y) dxdy

=∫∫ +∞

−∞

[x+ y −

(E(X) + E(Y )

)]2f(x, y) dxdy

=∫∫ +∞

−∞

[(x− E(X)

)+(y − E(Y )

)]2f(x, y) dxdy

=∫∫ +∞

−∞

(x− E(X)

)2f(x, y) dxdy +

∫∫ +∞

−∞

(y − E(Y )

)2f(x, y) dxdy +

+2∫∫ +∞

−∞

(x− E(X)

)(y − E(Y )

)f(x, y) dxdy

ovvero

σ2(x+ y) = σ2x + σ2

y + 2∫∫ +∞

−∞(x− λx)(y − λy) f(x, y) dxdy

= σ2x + σ2

y + 2 cov(X,Y )

Nel caso in cui le due variabili siano indipendenti la varianza della somma è uguale alla somma dellevarianze (infatti in questo caso si annulla il termine legato alla covarianza: 2 cov(X,Y )).

A questo punto facciamo qualche esempio di alcune distribuzioni usate in pratica.

1.2.1 La distribuzione esponenziale

La distribuzione esponenziale ha densità:

f(x) = λe−λx

Di conseguenza

F(X) =∫ x

−∞f(ξ) dξ

(∗)=∫ x

0f(ξ) dξ =

∫ x

0λe−λx dξ = x

[− e−λ

x

]x

0

= −e−λx + 1 = 1− e−λx

Ovvero F(X) = 1− e−λx

(*) Ipotesi legata all'utilizzo pratico di questa distribuzione: la distribuzione esponenziale viene in genere

usata per descrivere un tempo; il tempo pertanto non può essere −∞, ma viene preso x = 0 come

istante iniziale.

Con questa distribuzione si descrive generalmente il tempo tra due arrivi consecutivi, ovvero iltempo di interarrivo. Si può vedere che se gli interarrivi sono esponenziali, allora la probabilità diavere n arrivi in un tempo t è una variabile aleatoria discreta distribuita secondo una distribuzionedi Poisson, che verrà richiamata tra breve. Per ora è importante ricordare il seguente Teorema.

Teorema 1.2.1 La distribuzione esponenziale è l'unica distribuzione continua che gode della pro-

prietà markoviana, ovvero la distribuzione dipende solo dall'istante iniziale.


Dim. Dimostriamo nelle prossime righe la proprietà Markoviana. Supponiamo che la dis-tribuzione degli interarrivi sia esponenziale con frequenza λ. Dopo aver aspettato l'arrivo aspettan-do t secondi dopo l'ultimo arrivo, ci si chiede qual'è la probabilità che l'arrivo cada nei prossimi xsecondi, cioè qual'è la probabilità della che in prossimo interarrivo (variabile aleatoria T) sia minoredi t+ x. Se gli interarrivi sono esponenziali:

ProbT ≤ t+ x | T > t =Probt < T < t+ x

ProbT > t=

∫ t+xt λe−λξ dξ∫∞t λe−λξ dξ

= 1− e−λx

che è indipendente dal tempo d'attesa t ed uguale alla distribuzione iniziale.

1.2.2 La distribuzione di Poisson

Per quanto riguarda gli arrivi consideriamo la distribuzione discreta di Poisson che descrive laprobabilità di avere n arrivi all'istante t nel seguente modo:

Pn(t) =(λt)n

n!e−λt

Questa distribuzione si dimostra, in questo contesto, un compromesso molto ragionevole trasemplicità analitica e rigore descrittivo grazie a due caratteristiche importanti (come mostra lagura 2.5a):

1. pet t piccoli si hanno pochi arrivi;

2. la distribuzione presenta un certo massimo, ma per n che tende a innito il valore tende viavia a diminuire.

Associata a questa probabilità viene introdotto l'evento interrarrivo che descrive la distanza τtra due arrivi; l'interrarrivo è chiaramente una variabile aleatoria, una quantità non certa che puòessere vista come risultato di un esperimento casuale: come tale avrà una distribuzione denita da1

F(t) = Prob (T ≤ t) = 1− e−λt

e una certa densitàf(t) = λe−λt

che risulta semplice come forma analitica e gode della proprietà markoviana.Deniamo ora il tempo medio di interarrivo

E(T ) =1λ

essendo λ la frequenza degli arrivi, misurata in arrivi al secondo.Notiamo a questo punto due proprietà piuttosto importanti nella pratica.

Proprietà 4 La conuenza di n arrivi Poissoniani con frequenze d'arrivo λ1, λ2, . . . , λn è ancora

Poissoniana con frequenza∑n

i=1 λi.

Dim. La situazione è visualizzata nella seguente gura:

La probabilità di avere 1 arrivo in ∆t dopo la conuenza è dato dall'unione dei seguenti eventi:

1Nota: in questo contesto T è la variabile aleatoria, τ è un caso particolare.


prob(1arrivoin∆t) = prob(1arrivoin∆tnelprimoramo) ∪∪ prob(1arrivoin∆tnelsecondoramo ∪∪ . . . ∪ prob(1arrivoin∆tnelramon− esimo =

= λ1∆t+ λ2∆t+ . . .+ λn∆t =n∑

i=1

λi∆t

dove si è usata l'approssimazione e−x = 1− x che vale per x piccoli (vedi oltre).

D'altra parte

prob(0arriviin∆t) = prob(0arriviin∆tnelprimoramo) ∩∩ prob(0arriviin∆tnelsecondoramo) ∩∩ . . . ∩ prob(0arriviin∆tnelramon− esimo) =

= (1− λ1∆t)(1− λ2∆t) . . . (1− λn∆t) = 1−n∑

i=1

λi∆t

In modo analogo si può mostrare che la decomposizione di un processo Poissoniano con frequenzaλ in n rami dà luogo a n processi Poissoniani con frequenza p1λ per il primo ramo, p2λ per il secondoramo e pnλ per il ramo n-esimo, dove p1, p2, ...pn sono le probabilità che l'arrivo sia assegnatorispettivamente al ramo 1, 2, ... n.

Basta notare come la probabilità di avere 1 arrivo sul primo ramo in ∆t è data dalla proba-bilità di avere un arrivo sul ramo principale in ∆t e che l'arrivo sia assegnato al primo ramo, cioèprob(1arrivosulprimoramo) = λ∆tp1.

1.2.3 La distribuzione gaussiana

La densità di questa distribuzione è la seguente:

f(x) =1√2πσ

e−12(x−λx

σ)2

Questa distribuzione è molto importante per l'esistenza di un teorema:

Teorema del limite centrale 1.2.1 Siano X1, X2, ...Xn delle variabili aleatorie indipendenti con

la stessa distribuzione. Siano λ e σ2 rispettivamente la media e la varianza della sequenza. Allora

per n che tende a innito (nella pratica per n sucientemente grande) S =∑

iXi è una variabile

aleatoria con distribuzione gaussiana, con media nλ e varianza nσ2. Inoltre S0 = S−nλnσ è una

variabile aleatoria gaussiana con media nulla e varianza unitaria (variabile aleatoria normalizzata).

Purtroppo questa funzione non è integrabile, quindi non ammette la distribuzione in formachiusa, l'unico modo è eettuare una tabulazione.

Le due distribuzioni appena viste sono due distribuzioni di variabili aleatorie continue. Un casoimportante parlando di variabili aleatorie discrete è la distribuzione geometrica.

1.2.4 La distribuzione geometrica

La distribuzione geometrica si descrive con

Prob(X = n) = Pn = ρn(1− ρ) 0 < ρ < 1

1.3 Applicazione delle distribuzioni statistiche 9

Di questa variabile è interessante calcolare la speranza matematica

E(n) =∞∑

n=0

nPn =∞∑

n=0

nρn(1− ρ) = (1− ρ)∞∑

n=0

nρn = (1− ρ)ρ∞∑

n=0

nρn−1

= (1− ρ)ρ∞∑

n=0

∂ρn

∂ρ= (1− ρ)ρ

∂

∂ρ

∞∑n=0

ρn

︸︷︷︸=1/(1−ρ)

= (1− ρ)ρ∂

∂ρ

[1

1− ρ

]= (1− ρ)ρ

1(1− ρ)2

=ρ

1− ρ

che rappresenta il valor medio di una distribuzione geometrica.

Apriamo ora una parentesi per denire un concetto molto improtante.

1.3 Applicazione delle distribuzioni statistiche

1.3.1 Modello a coda semplice: M/M/1

Prendiamo in considerazione un modello estremamente semplicato: un sistema a coda semplicecome quello mostrato in gura 2.4; questo modello potrebbe rappresentare un sistema operativodedicato, ovvero (per i nostri scopi) un sistema operativo senza disco (diskless) e privo di interazionicon l'utente.

Per decidere quale distribuzione utilizzare per modellizzare il sistema bisogna saper conciliaredue esigenze tra loro contrastanti:

1. dovendo fare calcoli analitici con un sistemi sempre più complessi bisogna utilizzare delledistribuzioni che risultino analiticamente accessibili;

2. il modello deve comunque essere il più aderente possibile alla realtà.

Tornando al modello iniziale, per semplicità consideriamo sia gli arrivi che i tempi di esecuzionevariabili aleatorie distribuite esponenzialmente: facendo così si giunge a quella che viene chiamatacoda M/M/1 (M sta per Makov, 1 sta per una CPU).

Lo scopo è quello di vedere (note le caratteristiche statistiche degli arrivi e dei servizi) qual èil numero medio di processi e il tempo di attesa medio. Per giungere a queste conclusioni serveun'altra proprietà:

Formula di Little 1.3.1 Il numero medio di processi nel sistema operativo è uguale alla frequenza

degli arrivi moltiplicata per il tempo di attesa medio:

n = λw

NB: Questa è una proprietà che non dipende dalla particolare distribuzione (o dal particolaresistema a coda).


Da n = λw si può ricavare immediatamente il tempo di attesa medio:

w =1λn

Ora per calcolare il numero medio di processi bisogna considerare le proprietà di stazionarietà: sisfrutterà in particolare il fatto che le derivate temporali sono nulle (e per questo motivo si faràricorso ai limiti).

Stazionarietà: Non potendo fare delle stime sul bootstrap si considera il sistema quando è a regime;questa è un'enorme semplicazione: al boot si potrebbe infatti avere una grande quantità diprocessi che inuenzano l'andamento futuro del sistema.

I modelli che verranno usati saranno basati sul paragone di un sistema a coda con un sistema auido (gura 2.7)

A dierenza del sistema a code (discreto) questo è un sistema continuo: quest'approssimazioneconsente di utilizzare degli strumenti matematici che danno alcune informazioni non calcolabili nelcaso discreto.

Deniamo il coeciente di utilizzazione del sistema coda

coeff. utilizzazione =E(CPU)

E(interarrivi)=

tempo medio di CPU

tempo medio di interarrivi= ρ < 1

ρ < 1: ovvero la frequenza di CPU dev'essere superiore alla frequenza con la quale arrivano i nuoviprocassi: se così non fosse la lunghezza della coda tenderebbe a crescere (la CPU non riuscirebbe asmaltire i processi) no a diventare innita.

NB: Il nostro modello al momento non ha limiti per quanto riguarda l'arrivo dei processi in coda.Nella pratica questo non succede in quanto un sistema reale ha delle caratteristiche di nitezza(ovvero la coda avrà sempre una lunghezza nita).

Domanda: Qual è la probabilità che ci siano n processi nel sistema all'istante t+ ∆t?

Prima di tutto deniamo:

- PnE(t) = Prob (n processi eseguiti in t)

- PnA(t) = Prob (n processi arrivati in t)

Quindi

Pn(t+ ∆t) = Pn(t) ∩ P0A(∆t) ∩ P0E(∆t) (1.1)

∪ Pn(t) ∩ P1A(∆t) ∩ P1E(∆t)∪ Pn+1(t) ∩ P0A(∆t) ∩ P1E(∆t)∪ Pn−1(t) ∩ P1A(∆t) ∩ P0E(∆t)∪ ecc . . .

Si potrebbe continuare, ma gli eventuali termini aggiuntivi sono termini innitesimali (verrà fattoun processo di limite per ∆t→∞)

Ipotesi: arrivi ed esecuzioni in CPU sono eventi indipendenti.


· Prob (n processi in t) =(λt)n

n!e−λt

· Prob (0 processi arrivati in ∆t) =(λ∆t)0

0!e−λ∆t = e−λ∆t

· Prob (1 processo arrivato in ∆t) =(λ∆t)1

1!e−λ∆t = λ∆t e−λ∆t

A questo punto semplichiamo le cose considerando lo sviluppo in serie di Taylor attorno all'origine:

f(t) = f(0) + f ′(0)t+ f ′′(0)t2 + . . .

se considero f(t) = e−λ∆t allora ho che f ′ = −λe−λ∆t e f ′′ = λ2e−λ∆t e di conseguenza si ha che

e−λ∆t = 1− λ∆t+ λ2∆t2 + . . .

ora facendo tendere ∆t→ 0 è possibile troncare al secondo termine, e quindi

e−λ∆t = 1− λ∆t

A questo punto si ha che

· Prob (0 processi arrivati in ∆t) = 1− λ∆t· Prob (1 processo arrivato in ∆t) = λ∆t (1− λ∆t) = λ∆t

quindi si sostituiscono i valori appena trovati nella 1.1 specicando con λ la frequenza di arrivo deiprocessi e con µ quella di esecuzione:

Pn(t+ ∆t) = Pn(t) ∩ (1− λ∆t)(1− µ∆t)∪ Pn(t) ∩ λ∆t ∩ µ∆t∪ Pn+1(t) ∩ (1− λ∆t) ∩ λ∆t∪ Pn−1(t) ∩ λ∆t ∩ (1− µ∆t)

Ora si utilizza l'ipotesi di indipendenza: se le probabilità sono indipendenti allora le intersezionidiventano prodotti e le unioni diventano somme. Trascurando tutto ciò che svolgendo i conti diventaun innitesimo di ordine suoeriore si ottiene

Pn(t+ ∆t) = Pn(t)[1− (λ+ µ)∆t] + Pn+1(t)µ∆t+ Pn−1(t)λ∆t

da questa relazione si può ricavare un rapporto incrementale:

Pn(t+ ∆t)− Pn(t)∆t

= Pn+1(t)µ− (λ+ µ) + Pn−1(t)λ

facendo il limite per ∆t→ 0 si ottiene

P ′n(t) = µPn+1(t)− (λ+ µ) + λPn−1(t)

↓= 0 (1.2)

derivata che viene posta a zero in quanto interessa una soluzione stazionaria.Ora il coeciente di utilizzazione è dato da

ρ =tempo attesa unita centrale

media interarrivi=

1µ1λ

=λ

µ

dividendo la (1.2) per µ si giunge alla relazione:

Pn+1(t)− (1 + ρ)Pn(t) + ρPn−1(t) = 0


Con questa relazione è possibile denire delle iterazioni (n dev'essere ≥ 1)

n = 1 P2(t) = (1 + ρ)P1(t)− ρP0(t) (1.3)

n = 2 P3(t) = (1 + ρ)P2(t)− ρP1(t)n = 3 ecc . . .

In queste formule compare il termine P0(t) che bisogna calcolare.

Domanda: Quanto vale P0(t)?

P0(t+ ∆t) = P0(t) ∩ P0A(∆t) (*)

∪ P1(t) ∩ P1E(∆t) ∩ P0A(∆t)

(*) vengono trascurati i termini che non hanno senso: avendo 0 processi nel sistema non ci possono essere

processi in via di esecuzione.

P0(t+ ∆t) = P0(t)(1− λ∆t) + P1(t)µ∆t= P0(t)− λ∆tP0(t) + µP1(t)∆t

Come prima ci si conduce al rapporto incrementale, quindi si fa il limite per ∆t→ 0 e si ricava

P ′0(t) = µP1(t)− λP0(t) = 0

da cui segue immediatamenteP1(t) = ρP0(t)

valida solo nel caso in cui ci siano 0 processi all'interno del sistema.Tornando alle equazioni (1.3) troviamo che

n = 1 ρ2P0(t)n = 2 ρ3P0(t)

In generale Pn(t) = ρnP0(t)

Da note proprietà statistiche si osserva che

∞∑n=0

Pn(t) = 1 ⇒∞∑

n=0

ρnP0(t) = 1

⇒ P0(t)∞∑

n=0

ρn (*)= P0(t)1

1− ρ= 1

⇒ P0(t) = 1− ρ

(*) la sommatoria in questione rappresenta una serie geometrica di ragione ρ < 1

A questo punto è possibile dare una stima alla probabilità che all'istante t ci siano n processinel sistema: Pn(t) = ρn(1− ρ) ovvero é possibile stimare il numero medio di processi in questo tipodi sistema operativo, da

E(n) =∞∑

n=0

nPn(t) =∞∑

n=0

nρnP0(t) =∞∑

n=0

nρn(1− ρ) = (1− ρ)∞∑

n=0

nρn = (1− ρ)ρ

(1− ρ)2


si ricava che E(n) = ρ(1−ρ) A questo punto è possibile calcolare il tempo d'attesa medio dei processi

in questo sistema; da

w =1λ

ρ

1− ρ=

1λ

λµ

1− ρ

si ottiene w = 1µ(1−ρ) tempo medio di attesa dei processi (espresso in secondi).

Applicazione: questa formula viene tipicamente usata nei problemi di dimensionamento del tipo:qual è la potenza della CPU necessaria per far girare una data applicazione al ne di riuscirea smaltire i processi in coda?

1.3.2 Modello di coda ciclica

Prendiamo ora in considerazione il modello di coda ciclica mostrato in gura 2.8: per il momentotrascuriamo la possibilità di terminare qualche processo o di introdurne di nuovi.

Caratteristica: all'interno di questo sistema ci sono un numero costante (J) di processi: diconseguenza non si presenta il problema della coda che può raggiungere una lunghezza innita.

In generale avevamo denito

ρ =E(CPU)

E(interarrivi)=

tempo medio di CPU

tempo medio di interarrivi

e si aveva posto ρ < 1 per motivi di stabilità. In questo contesto ρ non è limitato da questa quantità:in linea teorica può assumere anche valori maggiori dell'unità.

Quello che ci interessa calcolare di questo modello è

1. il numero medio di processi in coda;

2. il tempo di attesa medio dei processi in coda;

3. il coeciente di utilizzazione della CPU;

Quest'ultimo indica la probabilità che l'unità centrale sia attiva (utilizzata): è auspicabile cheil sistema sia progettato in modo che l'utilizzo della CPU tenda al 100%.

Naturalmente esistono diversi modi per calcolare queste quantità, ciascuno con un diverso livello diprecisione.

Numero di processi e tempo di attesa medi

Per calcolare i primi due parametri si usa lo stesso metodo usato in precedenza nel caso del sistemaa coda semplice, ovvero, considerando µ1 la frequenza delle esecuzioni dei processi da parte dellaCPU e µ2 la frequenza delle richieste servite dal disco, i passi da fare sono:

• Si calcola Pn(t+ ∆t), ovvero la probabilità di avere n processi nel sistema all'istante t+ ∆t;si ricava

Pn(t+ ∆t) = Pn(t)[1− (µ1 + µ2)∆t] + Pn+1(t)µ1∆t+ Pn−1(t)µ2∆t

• Da questa espressione si trova il rapporto incrementale:

Pn(t+ ∆t)− Pn(t)∆t

= µ1Pn+1(t)− (µ1 + µ2) + µ2Pn−1(t)


• Quindi si ricava la derivata facendo il limite per ∆t → 0 e, considerando il sistema a regime(quindi una situazione stazionaria), la si pone uguale a zero:

P ′n(t) = µ1Pn+1(t)− (µ1 + µ2) + µ2Pn−1(t) = 0 (1.4)

• Da questa relazione è possibile ricavare un'iterazione, a condizione di avere un punto inizialeda cui partire; si va pertanto a cercare P0(t + ∆t), per poi ricavare un ulteriore rapportoincrementale (⇒ P ′

0(t) = µ1P1(t)−µ2P0(t)) da annullare per la stazionarietà e quindi trovare

P0(t) =µ1

µ2P1(t) =

1ρP1(t) ⇒ P1(t) = ρP0(t) (1.5)

• Dalla (1.4) e dalla (1.5) si ottiene la seguente relazione generale

Pn(t) = ρnP0(t)

che descrive la probabilità di avere n processi presenti in un sistema a coda ciclica.

Quest'ultima relazione è esattamente uguale a quella del caso M/M/1 (è ovvio, perchè anche questosistema può essere visto come un sistema a coda M/M/1 in cui gli arrivi sono rappresentati dalservizio di disco).

Attenzione: Le cose cambiano grazie a una dierenza sostanziale; qui il numero di processi èlimitato!

Quello che a questo punto bisogna fare è valutare P0(t). Come fatto in precedenza (vedi pagina12) si può dire che

J∑n=0

Pn(t) = 1 ⇒J∑

n=0

ρnP0(t) = 1 ⇒ P0(t) =

(J∑

n=0

ρn

)−1

L'ultimo termine di ques'equazione non è più una serie geometrica, bensì una somma geometrica e,considerando che ρ non è più < 1 si ha:

J∑n=0

ρn =1− ρJ+1

1− ρ

e di conseguenza

P0(t) =1− ρ

1− ρJ+1

Quindi generalizzando si trova che in un sistema a coda la probabilità di avere n processi incoda all'istante t è pari a: Pn(t) = ρn 1−ρ

1−ρJ+1 Ora è bene ricordare il nostro obiettivo: quello che si

sta cercando è

1. il numero medio di processi in coda;

2. il tempo di attesa medio dei processi in coda;

Per quanto riguarda il primo punto, ricordiamo che qui siamo siamo in un contesto di distribuzionediscreta, quindi si può dire che


da cui deriva che E(n) = ρ1−ρ

J ρJ+1−(J+1) ρJ+11−ρJ+1

Ora calcoliamo il secondo punto, ovvero il tempo di attesa medio: la formula di Little dice cheil numero medio di processi nel sistema è dato dalle due quantità frequenza di arrivo e tempo diattesa medio, ovvero n = λw che nel nostro caso si traduce con

E(n) = λw

da questa si ricava

w =1

freq. arrivi in coda· E(n)

Dunque manca da calcolare la frequenza con cui arrivano i processi in coda.Facciamo un passo avanti: ora non trascuriamo più la possibilità di terminare qualche processo

o di introdurne di nuovi: anche con questa modica il numero di processi nel sistema non cambiacol tempo in quanto viene imposto il vincolo che un nuovo processo non possa entrare prima che unaltro non sia terminato.

Figura 1.1

La frequenza di partenza dei processi dalla coda (vedi gura 1.1 (?)) è data dalla probabilitàdi avere dei processi in coda ∩ la probabilità di avere un'esecuzione da parte dell'unità centrale,ovvero

freq. partenza processi da coda = Prob(n processi in coda 6= 0)µ1

= (1− P0(t))µ1 =(1− 1− ρ

1− ρJ+1

)µ1

=1− ρJ+1 − 1 + ρ

1− ρJ+1· µ1

= ρ1− ρJ

1− ρJ+1· µ1

se si considerano le condizioni di stazionarietà, ovvero la situazione in cui a regime le dimensionidelle singole code sono uguali, allora deve valere:

freq. arrivi = freq. partenze

A questo punto abbiamo tutti i dati per poter ripartire dalla formula di Little:

w =1

freq. arrivi in coda· E(n) =

1ρµ1

· 1− ρJ+1

1− ρJ· ρ

1− ρ· J ρ

J+1 − (J + 1) ρJ + 11− ρJ+1

quindi il tempo di attesa medio in coda ciclica si può esprimere come: w = 1µ1(1−ρ) ·

J ρJ+1−(J+1) ρJ+11−ρJ

Ora resta solo da determinare il coeciente di utilizzazione della CPU.Qual è la probabilità che la CPU sia attiva? Quest'ultimo è un parametro non immediato da


calcolare, però di importanza fondamentale; con il tipo di modello in questione è possibile risponderein modo approssimativo.

Supponiamo di avere J molto alto, ovvero supponiamo di avere un elevato livello di multipro-grammazione. J non può tendere a innito (altrimenti P0(t) → (1 − ρ)) ma dev'essere suciente-mente grande da fare in modo che la probabilità che la CPU sia attiva equivalga alla probabilità diavere dei processi in coda (ovvero se J è elevato trascuro il singolo processo in esecuzione rispettoai J processi che sono in coda).

Prob(CPU attiva)]J↑

= Prob(n processi in coda CPU 6= 0)

con questa approssimazione, chiamato µ il coeciente di utilizzazione della CPU, si ha che

µ]J↑

= 1− P0(t) = 1− 1− ρ

1− ρJ+1

ovvero µ]J↑

= ρ · 1−ρJ

1−ρJ+1

Discussione dei risultati

Per quanto riguarda l'approssimazione è importantissimo il modo in cui si valuta questo coeciente;sono state fatte delle analisi sperimentali e si è visto che questa approssimazione è insuciente,ovvero ha un grande margine d'errore. A causa di questo margine si è costretti a passare al sistemacontinuo (che rappresenta un'altra approssimazione): qui si è in presenza di un processo stocasticodiscreto rappresentato dal numero di arrivi di processi in coda e dal numero di processi usciti dallacoda, processi che possiamo indicare con α(t) e δ(t):

In questo modello non verranno usate le statistiche usate no a questo momento (µ1, µ2 sonostatistiche) ma verrà utilizzato un numero in funzione del tempo: questo permetterà di andaread indagare in modo più puntuale e in particolare consentirà di vedere quello che succede comeandamento temporale (quindi ad esempio i transitori. . . ). I procssi stocastici in gioco sono del tipo:

Introduciamo ora la variabile N(t) che descrive il numero di processi nel sistema coda ed è datoda:

N(t) = α(t)− δ(t)

A questo punto, se ci si trova in condizioni di altro traco, i due numeri α(t) e δ(t) sono moltopiù elevati, quindi le discontinuità sono molto piccole rispetto il sistema nel suo complesso e diconseguenza i graci tendono ad assomigliare sempre di più a curve continue.

Approssimazione: a questo punto non consideriamo più un α(t) e un δ(t), bensì dei valori medi:α(t) e δ(t) che rappresentano le medie temporali degli arrivi e delle partenze. Ovviamente siha:

N(t) = α(t)− δ(t)

Osservazione: In questo caso le medie tendono (sempre in condizioni di alto traco) al valoremedio, ma localmente i valori possono discostarsi di molto. . .

In sintesi: si considerano processi stocastici continui che tendono (come limite estremo) a quellidiscreti.

Il fatto di passare da un sistema stocastico discreto ad uno continuo se da un lato introduce un'ul-teriore approssimazione (un modello continuo è diverso da modello reale che è discreto), dall'altrocomporta il vantaggio di poter rappresentare le code d'attesa con un sistema a uido continuo.

1.4 Modello a uido continuo 17

1.4 Modello a uido continuo

L'approssimazione consiste nel descrivere il sistema a coda d'atesa con un modello a uido continuo.Riprendendo quanto detto in precedenza si ha

N(t) = α(t)− δ(t)

con N(t) numero di processi nel sistema coda, α(t) e δ(t) che rappresentano le medie temporalidegli arrivi e delle partenze.

A questo punto vengono introdotte due nuove variabili

che rappresentano rispettivamente la frequenza degli arrivi e la frequenza delle partenze.A questo punto possiamo dire che

α(t) = α(0) +∫ t

0λ(ξ) dξ δ(t) = δ(0) +

∫ t

0µ(ξ) dξ

Diamo ora un'occhiata qualitativa a cosa può succedere a un sistema di questo tipo. Possiamorappresentare ad esempio una variazione di λ(t) come rappresentato in gura:

,sopra:frequenze di arrivo e partenza, sotto: numero di arrivi epartenze] Analizziamo la gura accanto: a. λ = µ; b. eccesso di arrivi che il sistema non riesce asmaltire; c. saturazione dei processi in esecuzione; d. gli arrivi sono ritornati a regime ma la CPUsta ancora lavorando a pieno carico; e. la CPU è riuscita a smaltire i processi in coda (le due areesi equivalgono); f. le due curve (frequenza d'ingresso e d'uscita) tornano a sovrapporsi.La cosa che emerge da questa rappresentazione è che comunque viene fatta l'ipotesi che il numerodi processo nel sistema sia la dierenza tra la media degli arrivi e la media ddelle partenze.

Calcoliamo ora la probabilità che il numero di arrivi all'istante t sia almeno n:

Prob[α(t) ≥ n ] = Prob[Tn ≤ t ]

con Tn istante (assoluto, non interarrivo) di arrivo dell'n-esimo processo.Se consideriamo gli interarrivi ti indipendenti, allora

Tn =n∑

i=1

ti

e applicando il teorema del limite centrale si può dire che l'istante assoluto di arrivo è distribuitonormalmente (ovvero la distribuzione degli istanti di arrivo è una variabile gaussiana). A questopunto anche la distribuzione del numero di arrivi nell'istante t è una variabile gaussiana. Quindi,riassumendo:


- α(t), α(t) sono delle variabilio gaussiane;

- quindi anche δ(t), δ(t) e di conseguenza N(t) sono variabili aleatorie gaussiane.

Si può dunque dire che α(t) e δ(t) sono normali con la media e con la varianza che le caratterizzano:

α(t) = N(λα, σ2α) δ(t) = N(λδ, σ

2δ)

Per capire quanto valgono queste variabili torniamo al sistema di coda ciclica mostrato nellagura successiva; si può dimostrare che:

λα ≈ µ2 λδ ≈ µ1

rappresentano delle buone approssimazioni.Allo stesso modo si può ricavare σ in funzione di λ:

σ2α = f(λα) σ2

δ= f(λδ)

A questo punto, come annunciato in precedenza, N(t) = α(t) − δ(t) è una variabile aleatoriagaussiana con un certo valor medio µ = µ2 − µ1 e una certa σ2 = f(σ2

α, σ2δ).

Osservazione: Essendo una variabile continua possiamo introdurre l'uso di strumenti dierenziali.Osserviamo come l'approssimazione con un sistema continuo venga compensata dal fatto chela funzione continua venga espressa in funzione di media e di varianza, che descrivono moltomeglio la variabile aleatoria di quanto possa farlo la sola frequenza.

Osservazione: Poniamo in evidenza una stranezza: nel sistema a coda semplice era possibilericavare un fattore di traco:

ρ =E(CPU)E(disco)

=µ2

µ1< 1

Ora, però, nel sistema a coda ciclica (in cui i processi sono al più J) ρ può essere anche > 1:al massimo si satureranno alcune code ma non potrà succedere nulla di. . . irreparabile!

Tornando sulle relazioni del valor medio (denotando con µN(t) una media) si ha:

µN(t) = µ2 − µ1 = µ1

(µ2

N− 1

)= µ1(ρ− 1)

In realtà vediamo che è buona norma avere anche in questo caso ρ < 1 :infatti per ρ < 1 abbiamoche µN(t) è un valore negativo (questo deriva dall'approssimazione che abbiamo fatto). Questoproblema viene mitigato introducendo alcune condizioni.

Condizioni di riessione: N(t) ≥ 0

Queste condizioni stanno a signicare che il valore ef-fettivo N(t) è positivo: ovvero la distribuzione gaus-siana ha un valore medio µ negativo ma a noi interessasolo (vedi graco) il quadrante positivo.


I casi che tratteremo avranno tipicamente un valore µ < 0 anche se abbastanza vicino all'origine.Introduciamo a questo punto la funzione distribuzione:

F(x, t) = Prob[N(t) ≤ x] = Probn processi nel sistema in T sia < x

Possono a questo punto seguire delle considerazioni molto complesse che si possono riassumereintuitivamente nel seguente modo: consideriamo una funzione denita come segue

ψ(x) =∂F∂t

questa funzione ora la sviluppiamo in serie di Taylor troncando al secondo termine:

ψ(x) = F′(0) · ∂F∂x

+ F′′(0) · ∂2F∂x2

si può dimostrare che

F′(0) = −µF′′(0) = σ2

2

= −µ · ∂F∂x

+σ2

2· ∂

2F∂x2

giungendo così all'equazione di diusione:∂F∂t = −µ · ∂F

∂x + σ2

2 · ∂2F∂x2

Questa è un'equazione dierenziale che descrive un determinato fenomeno sico; in questo con-testo viene utilizzato per descrivere un sistema di code d'attesa: qui infatti µ e σ2 sono proprio leµ e σ2 di N(t).

Quest'equazione viene qui usata in un contesto di stazionarietà rispetto al tempo, per cui avremo

−µ · ∂F∂x

+σ2

2· ∂

2F∂x2

= 0

Questa è un'equazione dierenziale la cui soluzione è

F(x) = A(1−Be2µ

σ2 x) con A e B costanti

Questa soluzione descrive Prob[N ≤ x] (trascurando i transitori, ovvero prendendo la situazione aregime).

Il problema ora è calcolare le costanti A e B; queste si trovano con le condizioni al contornoconsiderando due punti limite come x = 0 e x = J :

F(J) = 1 F(0) ≥ 0

con F(J) probabilità che il numero di processi nel sistema sia ≤ J .

Dalla prima condizione si ricava

F(J) = A(1−Be2µ

σ2 J) ⇒ A =1

1−Be2µ

σ2 J

quindi ottengo che la F(x) si può rappresentare come

F(x) =1−Be

2µ

σ2 x

1−Be2µ

σ2 J

Lavorando invece sulla seconda condizione al contorno si vede che

F(0) ≥ 0 ⇒ Prob[N ≤ 0] = Prob[N = 0] ≥ 0

non potendo essere N segativo.


Osservazione: Ora abbiamo che

F (0) =1−B

1−Be2µ

σ2 J(1.6)

è un'espressione ancora troppo complicata al ne di ricavare B. A questo punto introduciamoun'ulteriore:

Ipotesi: J → ∞, ovvero ipotizziamo un livello di multiprogrammazione molto elevato. Non èl'unica soluzione, ma è quella che ci interessa maggiormente. Dalla (1.6) si possono ricavarediverse soluzioni in base al livello di multiprogrammazione. Nella pratica conviene analizzareil sistema nei casi più critici, come quello di un livello di multiprogrammazione elevato.

Ora, ricordando che µ < 0, si ha che

J →∞ ⇒ F(0) = 1−B

Quanto vale questo 1 − B? In realtà si può far ricorso ad un altro modello, ovvero a quello dellacoda ciclica dove la probabilità di avere i processi in coda era data da (vedi pagina 14):

Pi(t) = ρi · 1− ρ

1− ρJ+1

A questo punto si pone

F(0) = P0(t) = ρ0 · 1− ρ

1− ρJ+1

con, ricordiamolo, ρ < 1 e con J →∞; quindi

limJ→∞

P0(t) = limJ→∞

1− ρ

1− ρJ+1= 1− ρ

da cui si ricava nalmente che B = ρ

A questo punto si giunge alla soluzione corretta:

F(x) = 1−ρ·e2µ

σ2 x

1−ρ·e2µ

σ2 J

Quello che ora rimane da determinare è il coeciente di utilizzazione della CPU:

µCPU = Prob[ci sia qualche processo in coda] = Prob[N 6= 0] = 1− F(0)

e dato che

F(0) =1− ρ

1− ρ e2µ

σ2 J

allora

1− F(0) =1− ρ · e

2µ

σ2 J − 1 + ρ

1− ρ · e2µ

σ2 J

da cui si ricava il coeciente di utilizzazione:

µCPU = ρ−ρ·e2µ

σ2 J

1−ρ·e2µ

σ2 J

in questa formula il coeciente di utilizzazione è denito in termini di valor medio e di varianzadi N . Questa è una soluzione che si accompagna a quella vista in precedenza che teneva conto solodelle valutazioni della probabilità. Si aveva visto che

µ = 1− P0 = 1− 1− ρ

1− ρJ+1

da cui si era giunti alla soluzione precedente:

µCPU = ρ−ρJ+1

1−ρJ+1

Esiste una somiglianza formale tra questi due risultati. Anche se più rudimentale in molti casi,per motivi di semplicità, conviene usare quest'ultima.

1.5 Esempi 21

1.5 Esempi

In questa sezione vengono descritte alcune applicazioni pratiche della teoria delle code nella analisie dimensionamento dei sistemi operativi.

1.5.1 Esempio 1

Si consideri un S.O. non pre-emptive, senza iterazioni di I/O. Supponendo che il tempo medio diesecuzione dei processi sia di 0.2 secondi, trovare la frequenza massima di arrivo dei processi taleche il tempo di attesa nel sistema sia minore di 0.5 secondi.

Sol. Il modello e' quello della coda M/M/1. Il tempo d'attesa nel sistema e' w = 1µ(1−ρ) ,

dove µ e' la frequenza di elaborazione, µ = 1te

= 5, dove te e' il tempo medio di elaborazione.

Inoltre λ e' la frequenza di arrivo, e ρ e' il coeciente di traco, ed e' uguale a ρ = λµ . Dunque:

w = 1µ(1−ρ) = 1

µ−µρ = 1µ−λ < 0.5. Quindi µ− λ > 1/0.5 ovvero λ < µ− 2. Quindi λ < 3.

1.5.2 Esempio 2

Si consideri un S.O. non pre-emptive, senza iterazioni di I/O. Si supponga che da alcune misurerisulti che il tempo medio di esecuzione dei processi sia pari a 100/(frequenza clock CPU in MHz).Se il tempo medio di interarrivo e' di 3 secondi, qual'e' il clock minimo della CPU tale che il tempod'attesa nel sistema sia minore di 0.5 secondi?

Sol. Il modello e' quello della coda M/M/1. Il tempo d'attesa nel sistema e' w = 1µ(1−ρ) =

1µ−λ < 0.5. Cioe' µ− λ > 2, cioe' µ > 2 + λ. Visto che λ = 1/3, µ > 7/3. Dato che µ = clock/100,ne risulta che clock > 233.

1.5.3 Esempio 3

Si consideri un S.O. di tipo batch, con un dispositivo di I/O. Supponendo che la CPU lavori alritmo di 3 elaborazioni al secondo e l'unita' di I/O soddis 2 richieste al secondo, qual'e' il livello(minimo) di multiprogrammazione tale che l'utilizzazione della CPU sia maggiore del 60% ?

Sol. Il modello e' quello della coda ciclica. Dato che la utilizzazione della CPU, U, e': U =ρ 1−ρN

1−ρN+1 , dove N è il numero di processi concorrenti, ovvero il livello di multiprogrammazione, dai

dati del problema ottengo ρ = 2/3 , cioe' U = 23

1− 23

N

1− 23

N+1 . Provando con alcuni N , si vede che il

minimo N che da' una utilizzazione della CPU maggiore del 60% e' N = 4.

1.5.4 Esempio 4

Un grosso Centro di Elaborazione Dati funziona nel seguente modo: a. Riceve da rete un bloccodi processi da eseguire da parte di N utenti b. Una volta ricevuti, esegue gli N processi in multi-programmazione c. Raccoglie i risultati e li invia agli utenti, assieme alla fattura con il costo delservizio. Sapendo che: - il tempo medio per ricevere un blocco di N richieste è T1 = 500 secondi- il tempo medio richiesto da un processo è T2 = 10 secondi - il costo sso del centro è CS = 100euro/secondo - il costo del tempo d'attesa di un utente è CU = 50 euro/secondo si determini ilnumero ottimale di utenti del blocco, cioe' il numero N che minimizza il costo totale per utente.

[suggerimento: il costo totale per utente è (tempo totale per eseguire i programmi)(costo totaleal secondo)/N cioè (T1 +NT2)(CS +NCU)/N

Sol. Come suggerito, il costo totale C è dato da C = (T1+NT2)(CS+NCU)N . Volendo minimizzare

C, possiamo annullare la derivata prima di C rispetto a N. Cioe': dCdN = (T1CU+T2CS+2NT2CU)N−(T1+NT2)(CS+NCU)

N2=

0 Cioè : T1CUN + T2CSN + 2N2T2CU = T1CS + T1CUN + T2CSN + N2T2CU Ovvero :

1.5 Esempi 22

N2T2CU = T1CS cioè N = SQRT (T1CS/T2CU) = SQRT (500x100/10x50) = 10 Cioè, il costototale per utente viene minimizzato se ci sono 10 utenti del centro di elaborazione.

1.5.5 Esempio 5

Un Sistema Operativo è rappresentabile nel seguente modo:La frequenza di elaborazione della 2 CPU è di 1 processo/s. La probabilità che ci sia 1 processo

nella coda della 2 CPU è del 25%. Sapendo che la prima CPU è utilizzata al 50%, determinare ilnumero di processi in attesa della prima CPU. [ricorda: la probabilità di avere n processi in coda èρn(1− ρ) ]

Sol. Con i dati del problema, basta avere le informazioni sulla prima CPU. Le informazioni sullaseconda CPU sono irrilevanti. Infatti: utilizzazione CPU = ρ = 0, 5. Visto che E[N ] =

∑n np(n) =

ρ(1−ρ) , il numero medio di processi in attesa della prima CPU è pari a 1.

1.5.6 Esempio 6

Un Sistema Operativo possiede una CPU (che esegue in media di 50 processi al secondo) ed un disco(in media esegue 40 richieste al secondo). Sapendo che un processo ha uno spazio di indirizzamentomedio di 500KB, che il Sistema Operativo non usa memoria virtuale, e che la CPU è utilizzata al60%, determinare la minima quantità di memoria di cui il Sistema Operativo deve disporre. [ricorda:la probabilità di avere n processi in coda in un sistema a coda ciclica è ρn 1−ρ

1−ρN+1 dove ρ è (frequenza

esecuzione disco)/(frequenza elaborazione CPU)]Sol. Visto che ρn(t) = ρn 1−ρ

1−ρN+1 , e che il coeciente di utilizzazione è U = 1 − p0(t)=1 −1−ρ

1−ρN+1=ρ1−ρN

1−ρN+1 . Quindi, visto che ρ = 40/50 = 0.8, possiamo calcolare il coeciente di utiliz-

zazione: U = 0.8 1−0.8N

1−0.8N+1 = 0.6. Sviluppando questa relazione si ha che 0.5 = 0.8N+1 da cui,facendo il logaritmo dei due membri, N = ln 0.5/ ln 0.8− 1, quindi N=2. Cioe' ci sono due processinel sistema operativo. La memoria minima richiesta è quindi di 1 Mbyte.

1.5.7 Esempio 7

In una biblioteca c'è un calcolatore dotato di un unico terminale mediante il quale gli utenti fannoricerche sulla disponibilità e collocazione dei libri. Se un nuovo utente arriva per consultare ilterminale in media ogni 3 minuti, ed il tempo medio di attesa che gli utenti aspettano prima diusare il terminale è di 8 minuti, qual è il numero medio di utenti che aspetta in coda?

Sol. Secondo Little, NumeroMedioDiUtentiInCoda = freq.arrivo*TempoAttesaInCoda cioè n =λ ∗W = 1/3 ∗ 8 = 2.66 utenti medi in attesa.

1.5.8 Esempio 8

I processi che arrivano ad un sistema operativo provengono da varie sorgenti, tutte poissoniane,come si vede in gura:

I tempi medi di interarrivo sono di 10, 5, 3.33 e 2.5 secondi rispettivamente per le varie sorgenti.Qual è la probabilità che nel processo degli arrivi risultante arrivino 5 processi in 10 secondi?

Sol. Le varie sorgenti hanno evidentemente le seguenti frequenze d'arrivo (λ = 1/T ): rispetti-vamente λ1 = 0.1, λ2 = 0.2, λ3 = 0.3, λ4 = 0.4. La conuenza è sempre di Poisson con λ =

∑n λi,

cioè λ = 1. In accordo alla distribuzione di Poisson, la probabilità che ci siano 5 processi arrivatiin 10 secondi è pari a (λt)5e−λt/5! con t=10 s. E' cioè pari a 105e−10/120 = 0.037.

1.5 Esempi 23

1.5.9 Esempio 9

Un sistema operativo è modellabile come una coda ciclica. Il tempo medio di CPU è di 2 secondi,quello di I/O è di 3 secondi. Il numero di processi nel sottosistema CPU, N(t), è una variabilealeatoria con media pari a -1/6 e varianza pari a 1. Usando l'approssimazione del uido continuo,determinare il numero minimo di processi nel sistema tale che il coeciente di utilizzazione dellaCPU sia maggiore dell'80%.

Sol. Si vuole cioè trovare il valore di J tale che U(J)>0.8. Dato che U = ρ(1− e−2mJ/var)/(1−ρe−2mJ/var), con i dati del problema (ρ = 2/3, µ = −1/6evar = 1) si ha che (1 − e−J/3)/(1.5 −e−J/3) > 0.8. Questa disuguaglianza porta a −1 > e−J/3 che non ha soluzioni nel campo reale. Ineetti con i valori assegnati non si troverà mai una probabilità maggiore di 0.8. Infatti, per J chetende a innito, il coeciente di utilizzazione tende a 2/3=0.6666.

1.5.10 Esempio 10

Si consideri un sistema di calcolo modellabile come in gura:dove il tempo medio di elaborazione della seconda CPU è di 10 secondi. Se si vuole che il tempo

d'attesa medio nell'intero sistema sia minore di 0.8 secondi, determinare la frequenza massimad'arrivo sapendo che l'utilizzazione della prima CPU è del 65%.

Sol. Intanto, U1 = ρ1 = λ1/µ1 = 0.65, cioè λ1 = 0.65µ1. Dato che il tempo d'attesa mediocomplessivo è la somma dei due tempi d'attesa medi nei due sistemi, si ha: W = W1 +W2 < 0.8.Inoltre

W1 = 1/(µ1 − λ1)=1/(0.35µ1),W2=1/(µ2 − λ2)=1/(0.1− λ2) = 1/(0.1− µ1)Quindi W = 1/(0.35µ1) + 1/(0.1 − µ1) = (0.1 − 0.65µ1)/(0.035µ1 − 0.35µ2

1) < 0.8 ovvero0.1 − 0.65µ1 < 0.028µ1 − 0.28µ2

1 ⇒ 0.28µ21 − 0.678µ1 + 0.1 < 0. Risolvendo l'equazione si ha che

la frequenza di esecuzione della prima CPU deve essere maggiore di 0.1589 e minore di 2.2625,cioè i tempi medi di esecuzione devono essere tra 0.44 e 6.29 secondi. La frequenza massimad'arrivo all'intero sistema e' dunque 0.65*2.2625 = 1.47 processi al secondo. Da notare che se siimponesse la condizione riportata sopra in funzione di λ1, si otterrebbe la seguente diseguaglianza:0.6627λ2

1 − 1.04λ1 + 0.1 < 0 con gli stessi risultati.Consideriamo ora la congruenza dei risultati ottenuti. Si è ottenuto λ1 = [0.1, 1.47] arrivi al

secondo e µ1 = [0.15, 2.26] elaborazioni al secondo. In tutti i casi, l'utilizzazione della prima CPUè del 65%. La frequenza d'arrivo alla seconda coda è quindi [0.1538, 2.26] mentre la frequenzadi elaborazione della seconda CPU è per ipotesi pari a 0.1. In tutti i casi, cioè il coeciente diutilizzazione risulta maggiore di 1, il che comporta instabilità della seconda coda.

1.5.11 Esempio 11

Si consideri un sistema di calcolo modellabile come in gura:I processi arrivano al sistema e si biforcano con probabilità α e 1−α sui due sottosistemi di CPU1

e CPU2. Quando i processi terminano l'elaborazione sulle due CPU, conuiscono sulla terza CPUper l'elaborazione nale. Sapendo che la frequenza d'arrivo al sistema è di 1.5 processi al secondo eche la frequenza di esecuzione della terza CPU è di 2 processi al secondo, e che l'utilizzazione dellaCPU1 e CPU2 sono del 90% e 80% rispettivamente, calcolare l'utilizzazione di CPU3 nel caso cheα = 0.5.

Sol. Se λ = 1.5, per α = 0.5 si ha che la frequenza d'arrivo sulle due code è di 0.75. Visto cheU1 = ρ1 = λ1/µ1 = 0.9 si ha che la frequenza di esecuzione della prima CPU è di 0.8333 processi alsecondo. Ugualmente, da U2 = ρ2 = λ2/µ2 = 0.8 si ha che la frequenza di esecuzione della secondaCPU è di 0.9374 processi al secondo. La frequenza di arrivo nella terza coda è la somma dellafrequenza di esecuzione delle prime due CPU, cioè λ3 = µ1 +µ2, cioè λ3 = 1.7708. Da cui si ha cheU3 = λ3/µ3 = 0.8854 cioè 88.54 %

1.5 Esempi 24

1.5.12 esempio 12

Un utente di un sistema operativo scrive una applicazione che risponde al paradigma del produt-tore/consumatore. L'applicazione è composta da due processi, uno dei quali - il produttore - scrivecontinuamente messaggi in un buer di 100 byte. Si consideri che:

1. Ogni messaggio richiede 5 byte

2. Il buer di 100 byte non è circolare: dopo che il buer si riempie i messaggi ulteriormenteprodotti non sovrascrivono altri messaggi, semplicemente vengono persi se non vengono letti.

L'altro processo - il consumatore - legge il buer con degli intertempi aleatori distribuiti secondouna distribuzione esponenziale con frequenza pari a 2 [letture/s]. Tenendo conto dei valori medi,trovare la frequenza massima alla quale il processo produttore scrive messaggi in modo tale che nonvenga perso nessun messaggio.

Sol. Il problema si può descrivere con una coda M/M/1 con µ = 2 e λ da determinare inmodo tale che la lunghezza della coda non superi mai 100 byte. Questo vuol dire che, considerando

i valori medi e chiamando n il numero medio di messaggi in coda, 5*n <100 ovvero 5 ρ2

1−ρ < 100ovvero 5ρ2 + 100ρ− 100 < 0 che ha due soluzioni: ρ1 = 0, 954 e ρ2 = −20, 954. Dal che risulta cheρ < 0, 954 ovvero, visto che ρ = λ/µ = λ/2, la frequenza media con la quale il processo scrittorescrive messaggi deve essere minore di 1,9 messaggi al secondo.

1.6 Un modello a code d'attesa della multiprogrammazione 25

1.6 Un modello a code d'attesa della multiprogrammazione

L'ipotesi è di avere un sistema chiuso, cioè con un numero costante di processi, pari a N , nelsistema. I processi sono distriobuiti fra le M code d'attesa, che fanno riferimento ad una CPU eM − 1 dispositivi di I/O. Tutte le distribuzioni sono esponenziali. Il sistema è visualizzato nellaseguente gura, dove le probabilità pi sono delle probabilità costanti di arrivo sulle varie code e µ1,µ2, ... µM sono le frequenze relative alla CPU e ai dispositivi di I/O rispettivamente.

In queste ipotesi semplicativi si può dimostrare con una tecnca simile a quella utilizzata prece-dentemente, che la probabilità che congiunta che ci siano n1 processi nella prima coda, n2 processinella seconda coda e così via è data dalla seguente relazione:

p(n1, n2, . . . , nM ) =1

G(N)

M∏i=1

Xnii (1.7)

dove G(N) è una costante relativa ad un sistema con N processi e M code. Inoltre, si dimostra cheX1 = 1 e Xi = µ1pi

µi.

Naturalmente in un sistema con N processi,∑M

i=1 ni = N .

1.6.1 Primo problema

In quanti modi si possono distribuire N processi su M code? Questo è ovviamente un problemacombinatorio. Per trovare la soluzione e per visualizzare il problema, è bene enumerare alcunepossibili casi semplici. Se nel sistema ci sono due code e due processi, cioè una CPU e un dispositivodi I/O, ci sono solo tre possibilità, cioè il caso in cui un processo è nella coda CPU ed un processoè nella coda di I/O, il caso in cui i due processi sono entrambi nella coda CPU e il caso in cui i dueprocessi sono entrambi nella coda nella coda di I/O. Analogamente si può vedere che se ci sono treprocessi, ci sono 4 possibili distribuzioni sulle due code, e se ci sono 4 processi le possibilità salgonoa 5. Se ci sono 3 code nel sistema, cioè una CPU e due I/O, allora le possibilità sono visualizzatenella seguente tabella per 2, 3 e 4 processi.

2processi 3 processi 4 processi

nr. code 1 2 3 1 2 3 1 2 3

nr. proc. 0 0 2 0 0 3 0 0 4

0 2 0 0 3 0 0 4 0

2 0 0 3 0 0 0 2 2

0 1 1 1 1 1 0 3 1

1 0 1 1 0 2 0 1 3

1 1 0 1 2 0 1 0 3

2 1 0 1 3 0

2 0 1 1 1 2

0 2 1 2 2 1

0 1 2 2 1 1

2 0 2

2 2 0

3 0 1

3 1 0

4 0 0

Le sequenze (2, 2) → 3, (2, 3) → 4, (2, 4) → 5, (3, 2) → 6, (3, 3) → 10, (3, 4) → 15 possonoessere ottenute con la formula delle combinazioni di N-M-1 elementi su N. Quindi: N processi si


possono distribuire su M code in

(M +N − 1

N

)modi. Sia S l'insieme delle possibili combinazioni

(n1, n2, . . . , nM ); per esempio per N=2, M=2, S = (02), (20), (11). Allora∑

S p(n1, n2, . . . , nM ) = 1.Data la relazione precedente, si ha:

G(N) =∑S

M∏i=1

Xnii (1.8)

1.6.2 Secondo problema

Come calcolare la costante G(N)? J.P.Buzen propone una soluzione risorsiva a questo problema,introducendo la funzione ausiliaria g(n,m) =

∑F

∏mi=1X

nii che è cioè riferita ad un sistema con

m code e n processi, cioè un sistema per il quale ci sono

(m+ n− 1

n

)possibili combinazioni dei

processi sulle code. Data la denizione, G(N) = g(N,M). Per arrivare alla ricorsione si divide lasommatoria in due termini, uno per le congurazioni di (n1, n2, . . . , nM ) per cui nm = 0 e l'altroper le congurazioni per cui nm > 0. Facendo riferimento alla tabella precedente, se ho 3 code e 2processi, e per quanto riguarda la costante G(N) ciò corrisponde a :

G(N) =∑S

M∏i=1

Xnii =

∑(020),(200),(110)

M∏i=1

Xnii +

∑(002),(011),(101)

M∏i=1

Xnii (1.9)

Dato che nel primo insieme nm = 0, la produttoria del primo termine della sommatoria può esserelimitata a (m-1), quindi la prima sommatoria descrive la costante in un sistema don m − 1 code.Per quanto riguarda la seconda sommatoria, mettiamo a fattore comune Xm. L'esponente di Xm

diventa allora nm−1 e quindi la sommatoria descrive un sistema con n− 1 processi perchè la sommadegli esponenti è n− 1. In denitiva:

g(n,m) = g(n,m− 1) +Xmg(n− 1,m) (1.10)

Inoltre g(n, 1) =∑

F,m=1

∏mi=1X

nii = Xn1

1 per tutti gli N da 0 a N e, dalla ricorsione, g(0,m)=1

per tutti gli m da 1 a M. La ricorsione consente di calcolare g(N,M) in NM passi, partendo da(1, 2) in avanti. Un esempio di determinazione è dato nella seguente tabella.

g(1,2)=g(1,1)+X2*g(0,2); g(1,3)=g(1,2)+X3*g(0,3); ...

g(1,M)=g(1,M-1)+XM*g(0,M) g(2,2)=g(2,1)+X2*g(1,2);

g(2,3)=g(2,2)+X3*g(1,3); ... g(2,M)=g(2,M-1)+XM*g(1,M)

g(3,2)=g(3,1)+X2*g(2,2); g(3,3)=g(3,2)+X3*g(2,3); ...

g(3,M)=g(3,M-1)+XM*g(2,M) ... g(N,2)=g(N,1)+X2*g(N-1,2);

g(N,3)=g(N,2)+X3*g(N-1,3); ... g(N,M)=g(N,M-1)+XM*g(N-1,M)

alla ne G(N) = g(N,M). Da osservare che g(0,M) = G(0), g(1,M) = G(1), g(2,M) =G(2),..., g(N,M) = G(N).

1.6.3 Terzo problema

Un'altra cosa interessante riguarda la determinazione della probabilità pni ≥ k.Chiaramente è p(ni ≥ k) =

∑S∩ni≥k p(n1, n2, . . . nM ) =

∑S∩ni≥k

1G(N)

∏MniXni

i = 1G(N)

∑S∩ni≥k

∏MniXni

i =Xk

iG(N)

∑Xn1

1 Xn22 . . . Xni−k

i . . . XnMM = Xk

iG(N−k)

G(N) .

Ora, si osservi che p(ni ≥ 1) è il coeciente di utilizzazione della coda i. Quindi i coecientidi utilizzazione (cioè la probabilità che stiano eseguendo o processando richieste) delle varie code

sono: UCPU = G(N−1G(N) , UI/O1

= X2G(N−1G(N) , . . . , UI/OM−1

= XMG(N−1G(N) dove Xi = µ1pi

µi).


1.6.4 Un esempio applicativo

Si consideri un sistema operativo multiprogrammato con una CPU, e due dispositivi di I/O. Ilnumero di processi concorrenti nel sistema è due. Misure sul sistema evidenziano che: µ1 = 100, µ2 =25, µ3 = 40, p1 = 0.1, p2 = 0.2ep3 = 0.7. Ci si chiede: se si vuole aumentare l'utilizzazione dellaCPU di almeno 10% in termini assoluti, è suciente aumentare la memoria in modo che il numerodi processi concorrenti raddoppi? (da 2 passa a 4)

Con i dati si ottiene: X1 = 1, X2 = 0.8, X3 = 1.75. Inoltre G(0) = 1, G(1) = 3.55, G(2) = 8.65.Quindi l'utilizzazione della CPU è U = G(1)/G(2) = 41%. Se i processi concorrenti passano da 2 aquattro, si ottiene: G(3) = 18, G(4) = 35. Quindi il nuovo coeciente di utilizzazione della CPU èU = 52%. Quindi aumenta più del 10% come si voleva.

Appunti di Sistemi Operativi Enzo Mumolo e-mail address ...Capitolo 1 Sistemi a code d'attesa 1.1...

Documents

Transcript of Appunti di Sistemi Operativi Enzo Mumolo e-mail address ...Capitolo 1 Sistemi a code d'attesa 1.1...