Mathematical Problems of Computer Science 51, 82–89, 2019.

UDC 519.872

The Queue Distribution in Multiprocessor Systems

with the Waiting Time Restriction

Artur P. Vardanyan and Vladimir G. Sahakyan

Institute for Informatics and Automation Problems of NAS RA

e-mail: artvardanyan@asnet.am, vladimir.sahakyan@sci.am

Abstract

A queueing system model is considered, consisting of m (m ≥ 1) servicing devices
and a maximum number of tasks with n (n ≥ 1) in the waiting queue. Each task is
characterized by three random parameters (ν,β,ω), where ν is the number of servicing
devices required to perform the task, β is the maximum time required to complete
the task and ω is the possible time that the task can wait before assigning to run,
after which it leaves the system without service. Tasks are accepted for service in
the order of their entry into the system, i.e., FIFO (First-In-First-Out) discipline is
used. In paper the equations are obtained for the state probabilities of the system in
the stationary mode, which can serve as an assessment for real multiprocessor systems
using MPI and OpenMP technologies.

Keywords: Multiprocessor cluster-type system, Cluster computing, Queueing the-
ory, Waiting time restriction.

The optimal use of processor time in multiprocessor cluster-type systems depends on many
factors: the method of receiving and queuing the task, determining the order of execution,
the possibility of dynamically distributing computing resources, the ability to move the task
during different phases of execution to the minimum necessary environment or stop the
execution with the possibility of continuing, etc.. The reception of a task in the system for
execution plays an important role in the organization of this process. The ability to interact
distributed processes in certain periods of time requires synchronization and simultaneous
execution both in one and different computer systems. Therefore, accepting a task from
the queue for execution imposes the responsibility on the scheduler for ensuring its timely
execution. At the same time, tasks arriving for execution may be ”impatient”, that is, they
leave the queue after a certain waiting time. In this paper, the probabilities of the queue
state are obtained for the exponential distributions of the task of receipt, execute, and failure
of service. Such models play an important role on multiprocessor systems using MPI and
OpenMP technologies [1].

Suppose that a task stream enters a computing system consisting of m processors (m ≥ 1).
Each task is characterized by three random parameters (ν,β,ω), where ν is the number of

82

1. Introduction



A. Vardanyan and V. Sahakyan 83

computational resources(processors, cores, cluster nodes, etc.,) required to perform the task,
β is the maximum time required to complete the task and ω is the possible time that the
task can wait before assigning to run, after which it leaves the system without service [2].

By using David Kendall’s notation(which is widely used to describe elementary queueing
systems)[3], the system under consideration can be represented as M|M|m|n. So, the system
parameters are described:

m - the maximum number of computational resources;
n - the maximum permissible number of tasks in the queue;
α - a random value of the time interval between neighboring entrances, which has the

probability distribution:

P(α < t) = 1 −e−at,

where a is the intensity of the incoming stream;
β - a random value of the task execution time, which has the probability distribution:

P(β < t) = 1 −e−bt,

where b is the intensity of service;
ω - a random value of the permissible waiting time for a task in the queue, which has

the probability distribution:

P(ω < t) = 1 −e−wt,

where w is the intensity of the failure of service for a task from the queue;
ν - a random value of the number of required computational resources for performing a

task, which has the probability distribution:

P(ν ≤ k) =
k

m
,k = 1, 2, ...,m.

Tasks will be accepted for service in the order of their entry into the system, i.e., FIFO
discipline is used (First-In-First-Out). Those tasks that arrive at the time of full occupation
of the queue (there are already n tasks in the queue) receive a denial of service.

To obtain a system of equations, we need the values of some probabilistic characteristics.
By P(i,k) is denoted the probability that k processors will be occupied by i tasks:

P(i,k) = P

(
i∑

j=1

νj = k

)
.

P(i,k) =
1

mi

(
k − 1
i− 1

)
, 1 ≤ i ≤ k ≤ m.

2. Basic Notations and Lemmas

Lemma 2.1:The probability that k processors will be occupied by i tasks, can be obtained in
the following way:



84 The Queue Distribution in Multiprocessor Systems with the Waiting Time Restriction

Proof. To prove the lemma we use the mathematical induction technique. The method
of induction requires two cases to be proved. The first case, called the base case, proves that
the property holds for i = 1:

P(1,k) =
1

m

(
k − 1

0

)
=

1

m
.

The statement is true because if i = 1, then

P(1,k) = P(ν = k) =
1

m
.

The second case, called the induction step, proves that if the property holds for number i−1,
then it holds for the next natural number i:

P(i,k) =
k−1∑

j=i−1

P(i− 1,j)P(1,k − j) =
1

m

k−1∑
j=i−1

1

mi−1

(
j − 1
i− 2

)
=

1

mi

k−1∑
j=i−1

(
j − 1
i− 2

)
(1)

from combinatorics we know this equality [4]:(
i

i

)
+

(
i + 1

i

)
+ ... +

(
i + k − 1

i

)
=

(
i + k

i + 1

)
(2)

considering (2) equality to count (1), we get the formula, which was mentioned in Lemma
2.1.:

P(i,k) =
1

mi

(
k − 1
i− 1

)
.

P

(
i∑

j=1

νj ≤ k

)
=

1

mi

(
k

i

)
, 1 ≤ i ≤ k ≤ m.

Proof. To prove the lemma we use the formula, which we got in Lemma 2.1.

P

(
i∑

j=1

νj ≤ k

)
=

k∑
j=i

P(i,j) =
k∑

j=i

1

mi

(
i− 1
j − 1

)
=

1

mi

k∑
j=i

(
i− 1
j − 1

)
to calculate the last sum, we again use the (2) equality and as a result we get that

P

(
i∑

j=1

νj ≤ k

)
=

1

mi

(
k

i

)
.

P

(
k∑

i=1

νi ≤ s <
k+1∑
i=1

νi

)
=

1

mk+1

(
m−

s−k
k + 1

)(
s

k

)
, 1 ≤ k ≤ s ≤ m.

Lemma 2.2: The probability that i tasks will occupy no more than k processors, can be
obtained in the following way:

Lemma 2.3:



A. Vardanyan and V. Sahakyan 85

Proof. It’s obvious that:

P

(
k∑

i=1

νi ≤ s <
k+1∑
i=1

νi

)
=

s∑
j=k

P

(
k∑

i=1

νi = j

)
P (νk+1 > s− j).

Primarily, we use the obvious fact that

P (νk+1 > s− j) =
m−s + j

m
,

and then we use the formula, which we got in Lemma 2.1. for the first probability in sum,
as a result we get:

P

(
k∑

i=1

νi ≤ s <
k+1∑
i=1

νi

)
=

1

mk+1

(
s∑

j=k

(m−s)
(
j − 1
k − 1

)
+

s∑
j=k

j

(
j − 1
k − 1

))
=

=
1

mk+1

(
(m−s)

(
s

k

)
+ k

(
s + 1

k + 1

))
=

1

mk+1

(
m−

s−k
k + 1

)(
s

k

)
.

To analyze our system we need to identify the following basic notation:
Pi,j(t) - the probability that at the moment of time t there are i tasks in service, and in

the queue j tasks wait for service;
Due to the finite number of possible states of the system (m∗n+1) with long-term operation,
the system goes into a steady mode of operation, i.e., in a stationary state [5]. In this case,
the limiting values Pi,j(t) are considered as t tends to infinity, which will be denoted by Pi,j.

By Li,j we denote the state of the system when i tasks are serviced and j tasks are waiting
in the queue. Cases when the system can pass Li,j state from the other state are presented
in the following scheme:

Li−k+1,j+k Li,j Li,j−1

Li,j+1 or Li−k,j+k+1

q(1)(i,j)

q(2)(i,j)

q(3)(i,j,k)

where q(1)(i,j), q(2)(i,j), q(3)(i,j) are probabilities for appropriate passing and when the
passing is from Li−k+1,j+k, then k = 1, 2, ...,min(i,n − j), but when the passing is from
Li−k,j+k+1, then k = 0, ..., i − 1. Note that if j = 0, then there won’t be the passing from
Li,j−1 and if j = n, then there won’t be the passing from Li,j+1 or Li−k,j+k+1. We also assume
that at the passing from Li−k,j+k+1 the first task from the queue leaves the queue and at the
passing from Li,j+1 not the first task, but another task from the queue leaves the queue.
Obviously,

q(1)(i,j) =

min(i,n−j)∑
k=0

(
(i−k + 1)b

a + (i−k + 1)b + (j + k)w
Pi−k+1,j+kP(i,k)

)
,

3. The Equations for System State



86 The Queue Distribution in Multiprocessor Systems with the Waiting Time Restriction

where P(i,k) = 0 if i = 0, but if 0 < i ≤ m, then P(i,k) is the following conditional
probability:

P(i,k) = P

(
i−k∑
s=1

νs +
i+1∑

s=i−k+2

νs ≤ m,
i−k∑
s=1

νs +
i+2∑

s=i−k+2

νs > m

/
i−k+1∑
s=1

νs ≤ m,
i−k+2∑
s=1

νs > m

)
,

where we consider that νi−k+1 is the number of required computational resources required to
service the task that was being left the system(it was serviced) and due to which the system
has changed its state,

q(2)(i,j) =
a

a + ib + (j − 1)w
Pi,j−1,

q(3)(i,j) =
jw

a + ib + (j + 1)w
Pi,j+1 +

i−1∑
k=0

(
w

a + (i−k)b + (j + k + 1)w
Pi−k,j+k+1P(i,k)

)
,

where P(i,k) = 0 if i = 0, but if 0 < i ≤ m, then P(i,k) is the following conditional
probability:

P(i,k) = P

(
i−k∑
s=1

νs +
i+1∑

s=i−k+2

νs ≤ m,
i−k∑
s=1

νs +
i+2∑

s=i−k+2

νs > m

/
i−k∑
s=1

νs ≤ m,
i−k+1∑
s=1

νs > m

)
,

where we consider that νi−k+1 is the number of required computational resources required
to service the task that was being left the system(it left the queue) and due to which the
system has changed its state.
In this case, the equations for system state are given in the following way:

Pi,j = ηjq
(1)(i,j) + θjq

(2)(i,j) + ηjq
(3)(i,j), (3)

where 0 ≤ i ≤ m, 0 ≤ j ≤ n and

ηj =

{
0, for j = n

1, for 0 ≤ j < n
,

θj =

{
0, for j = 0

1, for 0 < j ≤ n
.

Note that if i = 0, then P0,j = 0 for 0 ≤ j ≤ n.



A. Vardanyan and V. Sahakyan 87

To calculate P(i,k) probability, we first perform a simple transformation, then use the
conditional probability formula:

P(i,k) = P

(
i+1∑
s=1

νs ≤ m + νi−k+1 <
i+2∑
s=1

νs

/
i−k+1∑
s=1

νs ≤ m <
i−k+2∑
s=1

νs

)
=

=
P
(∑i+1

s=1 νs ≤ m + νi−k+1 <
∑i+2

s=1 νs,
∑i−k+1

s=1 νs ≤ m <
∑i−k+2

s=1 νs

)
P
(∑i−k+1

s=1 νs ≤ m <
∑i−k+2

s=1 νs

) .
By using Lemma 2.3. we can calculate the probability, which is in the denominator of the
last fraction:

P

(
i−k+1∑
s=1

νs ≤ m <
i−k+2∑
s=1

νs

)
=
i−k + 1
mi−k+2

(
m + 1

i−k + 2

)
.

Before the calculation of the probability, which is in the numerator of the fraction, it is
denoted by δk, then it is calculated in the following way:

δk =
m−k+1∑
u=i−k

P

(
i−k∑
s=1

νs = u

)
P̃u,

where k = 1, 2, ...,min(i,n− j) and

P̃u = P

(
i+1∑

s=i−k+2

νs ≤ m−u <
i+2∑

s=i−k+2

νs,νi−k+1 ≤ m−u < νi−k+1 + νi−k+2

)
.

Obviously, in the last probability we deal with independent probabilities and with the help
of Lemma 2.3. for P̃u we get the following formula:

P̃u =
(m−u)(m + u + 1)

(
(m + 1)k + u

)
2(k + 1)mk+3

(
m−u
k

)
. (4)

By using Lemma 2.1. as a result we get the following formula for δk:

δk =
1

mi−k

m−k+1∑
u=i−k

(
u− 1

i−k − 1

)
P̃u, (5)

where P̃u is calculated by formula (4). So, we get formula for P(i,k) probability:

P(i,k) =
mi−k+2

(i−k + 1)
(

m+1
i−k+2

)δi. (6)
Note that we can calculate the probability P(i,k) in the same way as P(i,k).
Thus, according to equation (3), probabilistic equation of the state of the system is given.
As we know, if i = 0 for all 0 ≤ j ≤ n

P0,j = 0,

and please note that
m∑
i=0

n∑
j=0

Pi,j = 1.

The probability that the system will refuse a new arrival task is denoted by R.



8 8 The Queue Distribution in Multiprocessor Systems with the Waiting Time Restriction

Corollary 3.1.

R =
mX

i=1

a

a + ib + nw
Pi;n:

4 . Co n c lu s io n

In c la s s ic a l qu e u e in g s ys t e m s , o n e t a s k d o e s n o t r e qu ir e m o r e t h a n o n e s e r vic in g d e vic e , b u t
in t h is p a p e r we s u g g e s t a qu e u e in g s ys t e m m o d e l t h a t d i®e r s fr o m o t h e r qu e u e in g s ys t e m s .
In t h e s u g g e s t e d n e w m o d e l it m a y t a ke m o r e t h a n o n e s e r vic in g d e vic e s t o p e r fo r m o n e
t a s k. S u c h a qu e u e in g s ys t e m m o d e l c a n p la y a n im p o r t a n t r o le o n m u lt ip r o c e s s o r s ys t e m s
u s in g MP I a n d Op e n MP t e c h n o lo g ie s . In p a p e r fo r t h e e xp o n e n t ia l d is t r ib u t io n s o f t h e t a s k
o f r e c e ip t , e xe c u t e , a n d fa ilu r e o f s e r vic e , t h e p r o b a b ilis t ic e qu a t io n o f s t a t e o f t h e s ys t e m is
o b t a in e d in t h e s t a t io n a r y m o d e .

[1 ] N . D a h n o u n , M ulticore D SP : F rom Algorithms to R eal-Time Implementation on the
TM S320C66x SoC, W IL E Y , B r is t o l, 2 0 1 8 .

[2 ] V . S a h a kya n , Y . S h o u ko u r ia n a n d H . A s t s a t r ya n ,\ A b o u t s o m e qu e u e in g m o d e ls fo r
c o m p u t a t io n a l g r id s ys t e m s " , Transactions of IIAP NAS R A, M athematical P roblems
of Computer Science, vo l. 4 6 , p p .5 5 -5 8 , 2 0 1 6 .

[3 ] L . K le in r o c k, Queueing Systems: Volume 1 - Theory, W ile y In t e r s c ie n c e , N e w Y o r k,
1 9 7 5 .

[4 ] Í. ß. Âèëåíêèí, Êîìáèíàòîðèêà, Íàóêà, Ìîñêâà, 1 9 6 9 .
[5 ] Á. Â. Ãíåäåíêî è È. Í. Êîâàëåíêî, Ââåäåíèå â òåîðèþ ìàññîâîãî

îáñëóæèâàíèÿ, Íàóêà, Ìîñêâà, 1 9 8 7 .

Submitted 04.02.2019, accepted 26.04.2019.

лñÃÇ µ³ßËáõÙÁ µ³½Ù³åñáó»ëáñ³ÛÇÝ Ñ³Ù³Ï³ñ·áõÙ

ëå³ëÙ³Ý Å³Ù³Ý³ÏÇ ë³Ñٳݳ÷³ÏÙ³Ý ¹»åùáõÙ

ìɳ¹ÇÙÇñ ¶. ê³Ñ³ÏÛ³Ý ¨ ²ñÃáõñ ä. ì³ñ¹³ÝÛ³Ý

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï

e-mail: vladimir.sahakyan@sci.am, artvardanyan@asnet.am

²Ù÷á÷áõÙ

¸Çï³ñÏí³Í ¿ ½³Ý·í³Í³ÛÇÝ ëå³ë³ñÏÙ³Ý Ñ³Ù³Ï³ñ·Ç Ùá¹»É, áñáõÙ áñå»ë
ëå³ë³ñÏáÕ ë³ñù»ñ í»ñóíáõÙ ¿ m ( m ¸ 1 ) åñáó»ëáñÇó µ³Õϳó³Í µ³½Ù³åñáó»ëáñ³ÛÇÝ

References



V. Sahakyan and A. Vardanyan 8 9

ѳٳϳñ·Á, Ñ»ñÃáõÙ å³Ñ³ÝçÝ»ñÇ ³é³í»É³·áõÛÝ ÃáõÛɳïñ»ÉÇ ù³Ý³ÏÁ n ( n ¸ 1 ) ¿:
гٳϳñ·áõÙ Ûáõñ³ù³ÝãÛáõñ å³Ñ³Ýç µÝáõó·ñíáõÙ ¿ ( º; ¯; ! ) å³ñ³Ù»ïñ»ñ, áñï»Õ º-
Ý å³Ñ³ÝçÇ ëå³ë³ñÏÙ³Ý Ñ³Ù³ñ ³ÝÑñ³Å»ßï é»ëáõñëÝ»ñÇ(åñáó»ëáñÝ»ñÇ) ù³Ý³ÏÝ ¿,
¯ - Ý å³Ñ³ÝçÇ ëå³ë³ñÏÙ³Ý ³é³í»É³·áõÛÝ Å³Ù³Ý³ÏÝ ¿, ÇëÏ ! - Ý ³ÛÝ ³é³í»É³·áõÛÝ
ųٳݳÏÝ ¿, áñ ³Û¹ å³Ñ³ÝçÁ ϳñáÕ ¿ Ñ»ñÃáõÙ ëå³ë»É ÙÇÝ㨠ëå³ë³ñÏÙ³Ý
áõÕ³ñÏí»ÉÁ: ²ñ¹ÛáõÝùáõÙ Ûáõñ³ù³ÝãÛáõñ å³Ñ³Ýç áõÝ»ÝáõÙ ¿ ëå³ëÙ³Ý Å³Ù³Ý³ÏÇ
ë³Ñٳݳ÷³ÏáõÙ: ²ß˳ï³ÝùáõÙ ëï³óí³Í »Ý ѳٳϳñ·Ç íÇ׳ÏÁ µÝáõó·ñáÕ
ѳí³Ý³Ï³Ý³ÛÇÝ Ñ³í³ë³ñáõÙÝ»ñ, »ñµ ѳٳϳñ·Á ϳÛáõÝ íÇ׳ÏáõÙ ¿:

Ðàñïðåäåëåíèå î÷åðåäè â ìíîãîïðîöåññîðíîé ñèñòåìå
ïðè îãðàíè÷åíèè íà âðåìÿ îæèäàíèÿ

Âëàäèìèð Ã. Ñààêÿí è Àðòóð Ï. Âàðäàíÿí

Èíñòèòóò ïðîáëåì èíôîðìàòèêè è àâòîìàòèçàöèè ÍÀÍ ÐÀ
e-mail: vladimir.sahakyan@sci.am, artvardanyan@asnet.am

Àííîòàöèÿ

Ðàññìîòðåíà ìîäåëü ñèñòåìû ìàññîâîãî îáñëóæèâàíèÿ, ñîñòîÿùàÿ èç m
( m ¸ 1 ) îáñëóæèâàþùèõ ïðèáîðîâ è ñ ìàêñèìàëüíûì êîëè÷åñòâîì çàäàíèé
â î÷åðåäè îæèäàíèÿ - n ( n ¸ 1 ) . Êàæäîå çàäàíèå õàðàêòåðèçóåòñÿ òðåìÿ
ñëó÷àéíûìè ïàðàìåòðàìè ( º; ¯; ! ) , ãäå º - ÷èñëî òðåáóåìûõ îáñëóæèâàþùèõ
ïðèáîðîâ, íåîáõîäèìûõ äëÿ âûïîëíåíèÿ çàäàíèÿ, ¯ -âðåìÿ, òðåáóåìîå äëÿ
âûïîëíåíèÿ çàäàíèÿ, ! - äîïóñòèìîå âðåìÿ ïðåáûâàíèÿ çàäàíèÿ â î÷åðåäè äî
íà÷àëà åãî âûïîëíåíèÿ, ïîñëå êîòîðîãî îíî ïîêèäàåò ñèñòåìó áåç îáñëóæèâàíèÿ.
Çàäàíèÿ ïðèíèìàòüñÿ íà îáñëóæèâàíèå â ïîðÿäêå ïîñòóïëåíèÿ èõ â ñèñòåìó, ò.å.
èñïîëüçóåòñÿ äèñöèïëèíà FIFO (First-In, First-Out).  ðàáîòå ïîëó÷åíû óðàâíåíèÿ
äëÿ âåðîÿòíîñòåé ñîñòîÿíèÿ ñèñòåìû â ñòàöèîíàðíîì ðåæèìå, êîòîðûå ìîãóò
ñëóæèòü îöåíêîé äëÿ ðåàëüíûõ ìíîãîïðîöåññîðíûõ ñèñòåì, èñïîëüçóþùèõ
òåõíîëîãèè MPI è OpenMp.

Êëþ÷åâûå ñëîâà: ìíîãîïðîöåññîðíàÿ ñèñòåìà êëàñòåðíîãî òèïà, êëàñòåðíûå
âû÷èñëåíèÿ, òåîðèÿ ìàññîâîãî îáñëóæèâàíèÿ, îãðàíè÷åíèå âðåìåíè îæèäàíèÿ.

´³Ý³ÉÇ µ³é»ñ՝ µ³½Ù³åñáó»ëáñ³ÛÇÝ Ïɳëï»ñ³ÛÇÝ ïÇåÇ Ñ³Ù³Ï³ñ·, Ïɳëï»ñ³ÛÇÝ
ѳßí³ñÏ, Ù³ëë³Û³Ï³Ý ëå³ë³ñÏÙ³Ý ï»ëáõÃÛáõÝ, ëå³ëÙ³Ý Å³Ù³Ý³ÏÇ ë³Ñٳݳ÷³-
ÏáõÙ:


	Sbornik_Karen
	abstract_Artur