ARTUR_article.DVI


Mathematical Problems of Computer Science 50, 104{106, 2018.

I mpr oved M odel of Scheduling Algor ithm

A r t u r P . V a r d a n ya n

Institute for Informatics and Automation Problems of NAS RA

e-mail: artvardanyan@asnet.am

Abstract

Cluster computing is becoming increasingly practical for high performance comput-
ing research and development. A computer cluster is a set of connected computers that
work together so that, they can be viewed as a single system. Clusters o®er a scalable
means of linking computers together to provide an expansive environment for hosting
enterprise applications. As the number of nodes in cluster con¯gurations grows, the
cluster administration becomes more challenging. We need to study the challenges of
cluster management and to provide a solution. To have an e®ective cluster management
we need to have an e®ective task scheduling algorithm. With the explosive growth of
information, the demand on computing is sharply increasing. Due to a large number of
computing tasks, the scheduling algorithm is an important part of cluster computing
and has a great in°uence on the quality of claster service. In cluster computing, some
large tasks may occupy too many resources and some small tasks may wait for a long
time based on First-In-First-Out (FIFO) scheduling algorithm. This paper provides
an overview of an improved scheduling algorithm that shortens the execution time of
tasks and increases the resource utilization.

Keywords: Cluster computing, Task scheduling, Scheduling algorithm.

1 . In t r o d u c t io n

Ta s k S c h e d u lin g is t o a s s ig n e d a t a s k t o a n a va ila b le r e s o u r c e fo r it s e xe c u t io n . Ta s k s c h e d u l-
in g is a n im p o r t a n t c o m p o n e n t o f c lu s t e r c o m p u t in g a n d h a s a g r e a t im p a c t o n t h e qu a lit y
o f c lu s t e r s e r vic e . Th e b a s ic p r o b le m o f t a s k s c h e d u lin g t h a t n e e d s t o b e s o lve d is a s s ig n -
in g t a s ks t o r e s o u r c e s . A s c h e d u le r is wh a t c a r r ie s o u t t h e s c h e d u lin g a c t ivit y. S c h e d u le r s
a r e o ft e n im p le m e n t e d s o t h e y ke e p a ll c lu s t e r r e s o u r c e s b u s y ( a s in lo a d b a la n c in g ) , a llo w
m u lt ip le u s e r s t o s h a r e c lu s t e r r e s o u r c e s e ®e c t ive ly, o r t o a c h ie ve a t a r g e t qu a lit y o f s e r vic e .
FIFO s c h e d u le r is a c o m m o n s c h e d u le r , a n d it c h o o s e s t h e t a s k t o e xe c u t e a c c o r d in g t o t a s k
a r r iva l t im e . B y d e fa u lt , FIFO s c h e d u le r d o e s n o t c o n s id e r a t a s ks p r io r it y.
U s u a lly, in t a s k s c h e d u lin g a lg o r it h m s , t a s ks a r e d e s c r ib e d b y t wo p a r a m e t e r s : t h e r e s o u r c e
u t iliz a t io n p a r a m e t e r a n d t a s k's e xe c u t io n t im e . Ta s k's r e s o u r c e u t iliz a t io n p a r a m e t e r is t h e
n u m b e r o f c lu s t e r n o d e s r e qu ir e d t o p e r fo r m t h is t a s k. Ta s k's e xe c u t io n t im e is t h e m a xim u m
t im e n e c e s s a r y t o c o m p le t e t h is t a s k. B u t in t h is p a p e r we p r o p o s e a t a s k s c h e d u lin g a lg o -
r it h m , in wh ic h t a s ks a r e d e s c r ib e d b y t h r e e p a r a m e t e r s : t h e r e s o u r c e u t iliz a t io n p a r a m e t e r ,
t a s k's e xe c u t io n t im e a n d t a s k's wa it in g t im e . W h a t is a t a s ks wa it in g t im e ? Ta s ks wa it in g
t im e is t h e m a xim u m t im e t h a t t h is t a s k c a n wa it b e fo r e a s s ig n in g t o r u n . To d e s c r ib e e a c h

1 0 4



A. Vardanyan 1 0 5

t a s k we u s e d ( º; ¯; ! ) t r ip le t , wh e r e º is t h e n u m b e r o f c lu s t e r n o d e s r e qu ir e d t o p e r fo r m
t h is t a s k, ¯ is t h e m a xim u m t im e n e c e s s a r y t o c o m p le t e t h is t a s k a n d ! is t h e m a xim u m
t im e t h a t t h is t a s k c a n wa it b e fo r e a s s ig n in g t o r u n . Fo r t h e va lu e t o t h e n u m b e r o f t h e
c lu s t e r n o d e s we t o o k m . Th e ¯ r s t m o m e n t o f t h e t im e we h a ve a qu e u e , in wh ic h t h e r e a r e
n t a s ks , t h a t is we h a ve a qu e u e wit h n t h r e e -d im e n s io n a l ve c t o r s .

2 . Mo d e l o f S c h e d u lin g A lg o r it h m fo r FIFO

Im p r o ve d a lg o r it h m d e s c r ip t io n :
In p u t :

n tree-dementional vectors: f ( ºi; ¯i; !i ) ; i = 1 ; 2 ; :::; ng;
the number of cluster nodes: m;

P r o c e s s :
S t e p 1 : declare the variables

the number of assigned tasks: k = 0 ;
the number of cluster occupied nodes:s = 0
the number of cluster idle nodes: f;

S t e p 2 : while s + ºk+1 · 0 then k = k + 1 ; s = s + ºk and serve kth task;
S t e p 3 : set f = m ¡ s;
S t e p 4 : sort ¯1; ¯2; :::; ¯k in non-decreasing order: ¯i1; ¯i2 ; :::; ¯ik ;
S t e p 5 : declare the variables

¿i
th moment of the time: ¿i; i = 1 ; 2 ; :::; k;

the number of cluster idle nodes at ¿i
th moment of the time:

mi; i = 1 ; 2 ; :::; k;
S t e p 6 : for j = 1 to k set ¿i = ¯ij and mj = f +

Pj
i=1 mi;

S t e p 7 : go through the queue and ¯nd which ( ºj ; ¯j; !j ) so that ºj · f; ¯j < ¿1
for j = k + 1 to n
if ºj · f; ¯j < ¿1 then serve jth task and break for;

S t e p 8 : check if there are tasks in queue that have the waiting time less than ¿1
for j = k + 1 to n
if !j < ¿1 then delete j

th task from the queue and rearrange the queue;
S t e p 9 : while the queue is not empty at each ¿i; i = 1 ; :::; k point do these cheeks

for j = k + i + 1 to n
if !j < ¿1 then delete j

th task from the queue and rearrange the queue;

if ºk+i · mi then serve ( k + i) th task;
else
for j = k + i + 1 to n
if ºj · mi and ¿i + ¯j < ¿i+1 then serve jth task and break for.

3 . Co n c lu s io n

W e p r e s e n t e d t h e im p r o ve d m o d e l o f t h e s c h e d u lin g a lg o r it h m , wh ic h d e c r e a s e s t h e e xe c u t io n
t im e o f t a s ks a n d in c r e a s e s t h e r e s o u r c e u t iliz a t io n o f t h e s ys t e m . In t h e a b o ve m e n t io n e d
a lg o r it h m e a c h t a s k is c h a r a c t e r iz e d b y p a r a m e t e r s ( º; ¯; ! ) , wh e r e º is t h e n u m b e r o f c lu s t e r
n o d e s r e qu ir e d t o p e r fo r m t h is t a s k, ¯ is t h e m a xim u m t im e n e c e s s a r y t o c o m p le t e t h is t a s k
a n d ! is t h e m a xim u m t im e t h a t t h is t a s k c a n wa it b e fo r e a s s ig n in g t o r u n . N o t e t h a t in



1 0 6 Improved Model of Scheduling Algorithm

t h e im p r o ve d a lg o r it h m we h a ve u s e d t h e b a c k¯ ll s c h e d u lin g m o d e l. B a c k¯ ll is a s c h e d u lin g
o p t im iz a t io n , wh ic h a llo ws t h e s c h e d u le r t o m a ke b e t t e r u s e o f a va ila b le r e s o u r c e s b y r u n n in g
jo b s o u t o f o r d e r .

Refer ences

[1 ] V . G. S a h a kya n , Y . H . S h o u ko u r ia n , H . V . 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 " , M athematical P roblems of Computer Science, Y e r e va n ,
A r m e n ia , 2 0 1 6 .

[2 ] M. L . P in e d o , S c h e d u lin g : Th e o r y, A lg o r it h m s , a n d S ys t e m s , Springer International
P ublishing, 5 t h e d ., 2 0 1 6 .

[3 ] P . B r u c ke r , S c h e d u lin g A lg o r it h m s , Springer International P ublishing, 5 t h e d ., 2 0 0 7 .

Submitted 10.04.2018, accepted 28.11.2018.

äɳݳíáñÙ³Ý ³É·áñÇÃÙÇ µ³ñ»É³íí³Í Ùá¹»É

². ì³ñ¹³ÝÛ³Ý

²Ù÷á÷áõÙ

Ðá¹í³ÍáõÙ Ý»ñϳ۳óíáõÙ åɳݳíáñÙ³Ý ³É·áñÇÃÙÇ Ùá¹»É, áñÁ Ýí³½»óÝáõÙ ¿ ³é³ç³-
¹Áñ³ÝùÇ Ï³ï³ñÙ³Ý Å³Ù³Ý³ÏÁ ¨ ٻͳóÝáõ٠ѳٳϳñ·Ç é»ëáõñëÝ»ñÇ û·ï³·áñÍáõÙÁ:
²É·áñÇÃÙáõÙ Ûáõñ³ù³ÝãÛáõñ ³é³ç³¹ñ³Ýù µÝáõó·ñíáõÙ ¿ ( º; ¯; ! ) å³ñ³Ù»ïñ»ñáí, áñ-
ï»Õ º-Ý ³Û¹ ËݹÇñÁ ëå³ë³ñÏ»Éáõ ѳٳñ å³Ñ³ÝçíáÕ Ïɳëï»ñ³ÛÇÝ Ñ³Ý·áõÛóÝ»ñÇ
ù³Ý³ÏÝ ¿, ¯-Ý ³Û¹ ËݹÇñÁ ëå³ë³ñÏ»Éáõ ѳٳñ å³Ñ³ÝçíáÕ ³é³í»É³·áõÛÝ Å³Ù³Ý³ÏÝ
¿, ÇëÏ ! - Ý ³ÛÝ ³é³í»É³·áõÛÝ Å³Ù³Ý³ÏÝ ¿, áñ ³Û¹ ³é³ç³¹ñ³ÝùÁ ϳñáÕ ¿ ëå³ë»É
ÙÇÝ㨠ëå³ë³ñÏÙ³Ý áõÕ³ñÏí»ÉÁ:

Óëó÷øåííàÿ ìîäåëü àëãîðèòìà ïëàíèðîâàíèÿ
À. Âàðäàíÿí

Àííîòàöèÿ

 ñòàòüå ââîäèòñÿ óëó÷øåííóþ ìîäåëü àëãîðèòìà ïëàíèðîâàíèÿ, êîòîðàÿ óìåíü-
øàåò âðåìÿ âûïîëíåíèÿ çàäà÷ è óâåëè÷èâàåò èñïîëüçîâàíèå ðåñóðñîâ ñèñòåìû. Â
âûøåóïîìÿíóòîì àëãîðèòìå êàæäàÿ çàäà÷à õàðàêòåðèçóåòñÿ ïàðàìåòðàìè ( º; ¯; ! ) ,
ãäå º-êîëè÷åñòâî óçëîâ êëàñòåðà, íåîáõîäèìûõ äëÿ âûïîëíåíèÿ ýòîé çàäà÷è, ¯-
ìàêñèìàëüíîå âðåìÿ, íåîáõîäèìîå äëÿ âûïîëíåíèÿ ýòîé çàäà÷è, à ! -ìàêñèìàëüíîå
âðåìÿ, ÷òî ýòà çàäà÷à ìîæåò ïîäîæäàòü äî íàçíà÷åíèÿ äëÿ çàïóñêà.