Client/Server FIFO computer system analysis (sharpe software)

1

Università degli Studi di Messina

Computer system analysis

Queueing networks

2

Structure • A queueing network model is a collection of

service stations (aka service centers) connected via directed paths

• Each service station offers a service to customers

• Customers visit more stations in order to collect different services and complete a complex action

• A service station has a queue to hold customers waiting for service

3

Entities • Stations represent system resources

– CPU, disks, shared variables, ...

• Costumers represent active entities – jobs, processes

4

Dynamics • A customer arrives to a station asking

for a service

• It enters on a service (if free) or into a queue (if the service is busy)

• If more customers are waiting for the service the next customer is selected according to a scheduling discipline

• It leaves the station when it is served

5

Service center • Described by:

– Sequence of arrival times of customers

– Service time

– Number of servers

– Storage size (buffer size)

– Number of possible customers

– Order according to which the customers are served

6

A computer system

CPU

DISK1

DISK2

Exit

Enter

7

Graphical notation • A server is represented by a circle

• A buffer is represented by one open side rectangle

Servers and buffers are connected by oriented arcs

Server i

8

The computer system

CPU

DISK1

DISK2

Arriving jobs

Exit

Service centers are identified by dotted rectangles

9

Definitions • Interarrival time: time incurred between

two customer arrivals in the system

• Service time: time spent by the servers into a center to make the service

• Queueing delay: time spent by a customer waiting for the service

• Response time: time spent by a customer into the center service

10

Delays

CPU

Response time

Waiting time Service time

Arrival

11

Input parameters • Inter-arrival time (external)

• Service time (rate)

• Number of services

• Buffer size (it could be infinite)

• Population size (it could be infinite)

• Queueing discipline

• Routing probabilities

12

Kendal notation • A way to synthesize input parameters of

a service center (a queue)

A/B/c/d/e-x

13

Timing A/B/c/d/e - x

• A and B describe the customers arrival process (interarrival times) and service process (service times) – M - Poisson process (markovian) – Geom – geometric (discrete) process – D – deterministic – En – n-stage Erlang

– Hn – n-stage hiperexponential – G - general

14

Resources A/B/c/d/e - x

• Users and buffer dimension – c – number of servers in the station – d – maximum number of elements in the buffer (it could

be infinite) – e – maximum number of users in the system (also

considering users outside the station)

15

Queueing discipline A/B/c/d/e - x

• x can assume the classical values: – FIFO (FCFS)

– LIFO (LCFS)

– RO (Random Order)

– RR (Round Robin)

– PS (Processor sharing)

– Priority

16

Remarks • d and e are written only when different

by ∞

• x is written only when different by FIFO

*/*/* means */*/*/∞/∞ - FIFO

*/*/*/k means */*/*/k/∞

*/*/*/ /k means */*/*/∞/k

17

Characterization • Open queueing network:

– customers can arrive and depart

• Closed queueing network – No source of customers

– No customer departures

– Constant number of customers

18

Output parameters • Queue length

– distribution or expected value

• Response time

• Throughput

• Utilization

19

Analysis • Steady state analysis

– Transient analysis is difficult

• Avarege values

• Stochastic vs Operational – Same results

20

Remark • A server is characterized by an expected

work capacity r – CPU: number of instructions per time unit

• A customer need some work w – Number of instructions to be executed

• Mean service time: w/r

• Mean service rate: μ=r/w

21

Little's law • Let us consider a queueing system

– N: avarege number of customers

– λ: avarage arrival rate

– R: avarage time spent in the system (response time)

N = λ · R

Little's law has a general validity

22

M/M/1 queue • Parameters could depend on the number

of customers in the queue n

• Arrival rate: λ(n)

• Service rate: μ(n)

λ(n)

μ(n)

23

Stochastic analysis • State number of customers in the →

station

• State transitions – k → k+1: a customer arrives when k

customers are in the station (λ(k)) – k k-1→ : customer under service is served

(μ(k)) – μ(0) = 0

24

Birth and death process

0 1 2 k-1 k k+1

λ(0) λ(1) λ(2) λ(k-1) λ(k)

μ(1) μ(2) μ(3) μ(k) μ(k+1)

25

Q matrix

qn,n1=n

qn,n−1=n

qn,n=−nn

qi , j=0 ∣i− j∣1

26

Transient analysis

• A closed form solution is very difficult

• Numerical methods

d pt  dt

=ptQ p0={1,0,⋯,0}

d pnt 

dt =pn−1tn−1pn1tn1−pnt nn

d p0t 

dt =p1t1−p0t 0

27

Steady state analysis • Balance equation at equilibrium

p⋅Q=0

p⋅e=1 Q=[

−0 0 ⋯ ⋯ 1 −01 0 ⋯ 0 ⋯ ⋯ ⋯ ⋯ ⋯ ⋯ ⋯

]

28

Steady state analysis

−p00p11=0 ⇒ p11=p00

pnnn=pn−1n−1pn1n1 n0

0 1 2 k-1 k k+1

λ(0) λ(1) λ(2) λ(k-1) λ(k)

μ(1) μ(2) μ(3) μ(k) μ(k+1)

29

Steady state analysis • Repeated application of balance

equations p11=p00

p2μ(2)=p1λ(1)+ p1μ(1)−p0λ(0)= =p1λ(1)+ p0λ(0)−p0λ(0)=p1λ(1)

pnn=pn−1n−1

30

The solution

by iterating over the equations above

pnn=pn−1n−1=pn−2 n−2 n−1

n−1

pn−1n−1=pn−2n−2 ⇒ pn−1=pn−2 n−2 n−1

pn= 01⋯n−1 12⋯n

p0

31

… moreover

• A solution exists iff the series converges

• It is true when the chain is ergodic

∑ i=0

∞

pi=1 ⇒ p0= 1

1+∑ n≥1 ∏ i=0

n−1 λ(i) μ(i+1)

32

M/M/1 case • Constant transition rates

• λ(n) = λ

• μ(n) = μ

pn=( λ μ )

n

p0=ρ n p0

33

Convergence • Series

∑ n≥0

ρ n

converges iff ρ<1

The arrival rate must be less than the service rate

34

Costumers • pn : probability to have n customers in the

station

• Since ∑ n=0

∞

pn=1⇒ p0∑ n=0

∞

ρ n =1

p0= 1

∑ n≥0

ρ n =1−ρ ,iff λ<μ

• and pn=(1−ρ)ρ

n

35

Utilization • Probability that the server is busy

1−p0=ρ

36

Number of customers • The everage number of customers is

computed by the knowledge of pn E[Q]=∑

n⩾0

n pn=

(1−ρ)∑ n=0

∞

nρ n =

(1−ρ) ρ

(1−ρ)2 =

ρ

1−ρ

E [Q]= ρ

1−ρ

37

Response time • Application of Little's law

r= n λ =

1 μ(1−ρ)

= 1

μ−λ

λ=2sec −1 ;μ=2.5sec −1

ρ=0.8; p(0)=0.2;n=4 ;r=2sec

38

Summarizing

pn=(1−ρ)ρ n

1−p0=ρ

E [Q]= ρ

1−ρ

r= 1

μ−λ

• Probability to have n customers

• Utilization

• Queue length

• Response time

39

Response time distribution • M/M/1 queue response time is distributed

according to an negative exponential distribution

• The proof exploits the Laplace transform of the service time probability density

• Its expected time is

thus

1 μ(1−ρ)

FT(t)=1−e −μ(1−ρ)t

40

Open and closed queueing network • Costumers arrive from external sources

• Customers spend some time in the net

• Costumers depart

• Otherwise it is said closed

41

Single chain queueing network • The network is said single-chain queueing

network when all customers – behave identically with respect to the

workload

– the sequence of services is the same

– Otherwise it is said multi-chain queueing network

42

Burke's theorem •Stable M/M/k system

•Arrival rate equal to λ (load)

•The output process is a Poisson process with rate λ

•The number of users into the system at time t is independent by the sequence of departure times before t

43

Product form • The joint distribution of queue size is

the product of distributions for individual service centers

p(n)=∏ j=1

J

p j(n j)

n=(n1,n2,⋯,nJ)

p j(n j) steady state probabilities to have n j

customers in the j-th center

44

Sufficient conditions • The routing process from a station to another

is memoryless

• FCFS, PS (processor sharinh), IS (infinite server), LCFSPR (last-come-first-serve preeptive-resume)

• Service time distributions are differentiable except at FCFS centers where it is exponential

• External arrival streams for all open chains are Poissonian

45

Jackson networks • Open product-form queueing network

– open networks with feedback

• J centers

• mj servers at j-th center

• Exponentially distributed service time with μ

j

• External rate at j-th center equal to γj

46

Jackson result

Each station is considered as an M/M/m j

queue

μ j

γ j

q kj

p(n1,n2,⋯,nJ)=p1(n1) p2(n2)⋯pJ(nJ)

47

M/M/m j queue

• pj(nj) is steady state probability

• Service rate equal to μj

• Arrival rate equal to λj and

λ j=γ j+∑ k=1

J

λkqkj (λ=γ+λQ)

48

Tandem μ

2λ 1

μ 1

J=2

γ=[γ1,0] Q=[0 10 0]

49

Visit count • In the Jackson networks the customers visit

station j more than once

• (µj-λj) -1 is the expected time spent in the

station during one visit

• The expected visit time depends on the expected number of visits to the station (visit count) once a costumer enters the network

50

Visit count: computation • Probability to directly visit station j

from outside

• Each time a costumer visits station i it also will visit station j with probability pij

γ j

∑ i=1

J

γ j

= γ j Γ

ν j= γ j Γ +∑ i=1

J

pijνi ⇒ ν j= λ j Γ

51

M/M/m queue

• Poissonian arrival process

• m servers (service capacity)

• Exponentially distributed service time

λ

μ

μ

1

m

52

Analysis

• Its analysis is similar to the M/M/1 queue

• Take care to states m, m+1, m+2, …

0 1 2 m-1 m m+1

λ λ λ λ λ

μ 2μ 3μ m μ m μ(m-1)μ

λ

m μ

53

M/M/m queue: metrics • Stability

• State probability

λ m∗μ

<1 ≡ λ 1 μ <m

pn={ ( λ μ)

j 1 j! p0 j=1,2,…,m

( λ μ)

j 1 m!

1 m j−m

p0 j>m

p0= 1

1+∑ j=1

m−1

( λμ ) j 1 j ! +∑ j=m

∞

( λμ ) j 1 m!

1

m j−m

54

M/M/m queue: metrics (2) • Service time

• Number of customers

r=E[T ]= 1 μ+

mμ pm (mμ−λ)2

E[Q]=λμ+ mμ pm (mμ−λ)2

55

Exercise Let us suppose we have a system of two single server workstations in series: the first is a processing station, the second a test station. Pieces arrive at the first station according to a Poisson process of parameter λ = 10. The server service times are exponentially distributed with μ1=12 and μ2= 15 respectively

• Compute the expected response time and the mean number of pieces in the system.

56

Exercise A system is made by two nodes: the first node is a processing station, the second is an inspection-test station. Pieces come from the outside to station 1 according to a Poisson process with rate 10 pieces/hour, and, after the processing in station 1, they shall carry in the station 2 for the test. 10% of the tested pieces are defective and they return to the station 1 to be modified. The two stations are single service stations with exponentially distributed service times with parameters 12 pieces/hour and 15 pieces/hour respectively

• Which is the average number of pieces in the network and the mean sojourn time in the system?

57

Exercise Consider an open Jackson network made by 3 stations. Costumers arrive at the station 1 from the outside with an average frequency equal to 1 person per hour (Poisson arrivals). From station 1, users go to station 2 with probability 1/3 and to the station 3 with probability 2/3. From the station 2, users return at the entrance of the station 2 with probability 1/2, or leave the network. From the station 3, users go outside the network or they return to the station 1 with probability 1/3. The stations 2 and 3 are identical and are single server with exponentially distributed service times with μ2 = μ3 = 3/2 users/time. The station 1 is single server with exponentially distributed service time with μ1 = 2 users/hour. Check whether there is a stationary distribution and, if it is the case, compute the average number of users in the network and the mean sojourn time.

58

Closed product form networks • N fixed number of customers

• J centers

• qij is the routing probability from center

i to center j

• Exponentially distributed service time with μ

j

• No external rate at j-th center

59

Analysis

p(n1,n2,⋯,nJ)= 1

G(N ) x1 n1 x2

n2⋯xJ nJ

x j= v j μ j

v j=∑ k=1

J

vkqkj

G(N )= ∑ n1,n2, ... ,nm

n1+n2+...+nm=N

J

x1 n1 x2

n2...xJ nJ