I n t e r n a t i o n a l   J o u r n a l   o f   E l e c t r i c a l   a n d   C o m p u t e r   E n g i n e e r i n g   ( I J E C E )   V o l .   9 ,   N o .   1 ,   F e b r u a r y   2 0 1 9 ,   p p .   1 9 0 ~ 2 0 2   I S S N :   2 0 8 8 - 8 7 0 8 ,   D O I :   1 0 . 1 1 5 9 1 / i j e c e . v 9 i 1 . p p 1 9 0 - 2 0 2             1 9 0       J o u r n a l   h o m e p a g e :   h t t p : / / i a e s c o r e . c o m / j o u r n a l s / i n d e x . p h p / I J E C E   P r i o r i t y   b a s e d   r o u n d   r o b i n   ( P B R R )   C P U   s c h e d u l i n g   a l g o r i t h m       S o n i a   Z o u a o u i 1 ,   L o t f i   B o u s s a i d 2 ,   A b d e l l a t i f   M t i b a a 3   1 , 2 , 3 L a b o r a t o r y   o f   E l e c t r o n i c s   a n d   M i c r o - e l e c t r o n i c s ,   U n i v e r s i t y   o f   M o n a s t i r ,   T u n i s i a   2 , 3 N a t i o n a l   E n g i n e e r i n g   S c h o o l   o f   M o n a s t i r ,   U n i v e r s i t y   o f   M o n a s t i r ,   T u n i s i a   1 N a t i o n a l   E n g i n e e r i n g   S c h o o l   o f   S o u s s e ,   T u n i s i a       A r t i c l e   I n f o     A B S T R A C T     A r t i c l e   h i s t o r y :   R e c e i v e d   O c t   2 1 ,   2 0 1 7   R e v i s e d   J u l   1 0 ,   2 0 1 8   A c c e p t e d   J u l   2 4 ,   2 0 1 8       T h i s   p a p e r   i n t r o d u c e   a   n e w   a p p r o a c h   f o r   s c h e d u l i n g   a l g o r i t h m s   w h i c h   a i m   t o   i m p r o v e   r e a l   t i m e   o p e r a t i n g   s y s t e m   C P U   p e r f o r m a n c e .   T h i s   n e w   a p p r o a c h   o f   C P U   S c h e d u l i n g   a l g o r i t h m   i s   b a s e d   o n   t h e   c o m b i n a t i o n   o f   r o u n d - r o b i n   ( R R )   a n d   P r i o r i t y   b a s e d   ( P B )   s c h e d u l i n g   a l g o r i t h m s .   T h i s   s o l u t i o n   m a i n t a i n s   t h e   a d v a n t a g e   o f   s i m p l e   r o u n d   r o b i n   s c h e d u l i n g   a l g o r i t h m ,   w h i c h   i s   r e d u c i n g   s t a r v a t i o n   a n d   i n t e g r a t e s   t h e   a d v a n t a g e   o f   p r i o r i t y   s c h e d u l i n g .   T h e   p r o p o s e d   a l g o r i t h m   i m p l e m e n t s   t h e   c o n c e p t   o f   t i m e   q u a n t u m   a n d   a s s i g n i n g   a s   w e l l   p r i o r i t y   i n d e x   t o   t h e   p r o c e s s e s .   E x i s t i n g   r o u n d   r o b i n   C P U   s c h e d u l i n g   a l g o r i t h m   c a n n o t   b e   d e d i c a t e d   t o   r e a l   t i m e   o p e r a t i n g   s y s t e m   d u e   t o   t h e i r   l a r g e   w a i t i n g   t i m e ,   l a r g e   r e s p o n s e   t i m e ,   a n d   l a r g e   t u r n a r o u n d   t i m e   a n d   l e s s   t h r o u g h p u t .   T h i s   n e w   a l g o r i t h m   i m p r o v e s   a l l   t h e   d r a w b a c k s   o f   r o u n d   r o b i n   C P U   s c h e d u l i n g   a l g o r i t h m .   I n   a d d i t i o n ,   t h i s   p a p e r   p r e s e n t s   a n a l y s i s   c o m p a r i n g   p r o p o s e d   a l g o r i t h m   w i t h   e x i s t i n g   r o u n d   r o b i n   s c h e d u l i n g   a l g o r i t h m   f o c u s i n g   o n   a v e r a g e   w a i t i n g   t i m e   a n d   a v e r a g e   t u r n a r o u n d   t i m e .   K e y w o r d s :   A v e r a g e   t u r n a r o u n d   t i m e   A v e r a g e   w a i t i n g   t i m e   P r i o r i t y   b a s e d   R o u n d   r o b i n   ( R R )   S c h e d u l i n g   a l g o r i t h m s   C o p y r i g h t   ©   2 0 1 9   I n s t i t u t e   o f   A d v a n c e d   E n g i n e e r i n g   a n d   S c i e n c e .     A l l   r i g h t s   r e s e r v e d .   C o r r e s p o n d i n g   A u t h o r :   S o n i a   Z o u a o u i ,     L a b o r a t o r y   o f   E l e c t r o n i c s   a n d   M i c r o - e l e c t r o n i c s ,     U n i v e r s i t y   o f   M o n a s t i r ,   T u n i s i a .   E m a i l :   s o n i a . z o u a o u i 8 7 @ g m a i l . c o m       1 .   I N T R O D U C T I O N     S c h e d u l i n g   i s   t h e   m o s t   i m p o r t a n t   s e r v i c e   o f   a n   o p e r a t i n g   s y s t e m ;   i t   g i v e s   p r o c e s s e s   a c c e s s   t o   s y s t e m   r e s o u r c e s .   M a n y   r e q u i r e m e n t s   l i k e   f a s t   c o m p u t i n g ,   m u l t i t a s k i n g   ( e x e c u t e   m o r e   t h a n   o n e   p r o c e s s   a t   a   t i m e )   a n d   m u l t i p l e x i n g   ( t r a n s m i t   m u l t i p l e   f l o w s   s i m u l t a n e o u s l y )   a r i s e   t h e   n e e d   o f   s c h e d u l i n g   a l g o r i t h m s   [ 1 ] .   S c h e d u l i n g   i s   i n   t h e   h e a r t   o f   a n   o p e r a t i n g   s y s t e m .   I t   p r e s e n t s   a   f u n d a m e n t a l   f u n c t i o n ,   w h i c h   s e l e c t s   t h e   p r o c e s s   t o   r u n   w h e n   t h e r e   a r e   m u l t i p l e   r u n n a b l e   p r o c e s s e s .   T h e r e   a r e   v a r i e t i e s   o f   s c h e d u l i n g   a l g o r i t h m s   s u c h   a s   F i r s t   C o m e   F i r s t   S e r v e d   ( F C F S ) ,   S h o r t e s t   J o b   F i r s t   ( S J F ) ,   R o u n d   R o b i n   ( R R ) ,   P r i o r i t y   B a s e d   S c h e d u l i n g ,   e t c .   [ 2 ,   3 ] .     D u e   t o   t h e i r   p o o r   p e r f o r m a n c e ,   t h e   m a j o r i t y   o f   t h e s e   a l g o r i t h m s   a r e   r a r e l y   u s e d   i n   r e a l   t i m e   o p e r a t i n g   s y s t e m s   e x c e p t   f o r   t h e   R o u n d   R o b i n   s c h e d u l i n g .   I n   C P U   s c h e d u l i n g ,   a   n u m b e r   o f   a s s u m p t i o n   a r e   t a k e n   i n t o   c o n s i d e r a t i o n ,   w h i c h   a r e   a s   f o l l o w s   [ 4 ,   5 ] :   a .   J o b   p o o l   c o n s i s t s   o f   r u n n a b l e   p r o c e s s e s   w a i t i n g   f o r   t h e   C P U .     b .   A l l   p r o c e s s e s   a r e   i n d e p e n d e n t   a n d   c o m p e t e   f o r   r e s o u r c e s .     c .   T h e   f u n c t i o n   o f   t h e   s c h e d u l e r   i s   t o   f a i r l y   a l l o c a t e   t h e   l i m i t e d   r e s o u r c e s   o f   C P U   t o   t h e   d i f f e r e n t   p r o c e s s e s   a n d   i n   a   w a y   t h a t   o p t i m i z e s   s o m e   p e r f o r m a n c e   c r i t e r i a .   T h e   s c h e d u l e r ,   w h i c h   c o n s t i t u t e s   t h e   h e a r t   o f   t h e   k e r n e l ,   p l a y s   a   f u n d a m e n t a l   r o l e   i n   s e l e c t i n g   t h e   a p p r o p r i a t e   p r o c e s s   t o   b e   r u n .   I n   t h i s   c o n t e x t ,   a n   o p e r a t i n g   s y s t e m   c a n   b e   c h a r a c t e r i z e d   a c c o r d i n g   t o   t h r e e   d i f f e r e n t   t y p e s   o f   s c h e d u l e r s :   a   l o n g   t e r m ,   a   m i d - t e r m   o r   m e d i u m   t e r m   a n d   a   s h o r t - t e r m   s c h e d u l e r   a s   s h o w n   i n   F i g u r e   1 .   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t   J   E l e c   &   C o m p   E n g     I S S N :   2 0 8 8 - 8 7 0 8       P r i o r i t y   b a s e d   r o u n d   r o b i n   ( P B R R )   C P U   s c h e d u l i n g   a l g o r i t h m   ( S o n i a   Z o u a o u i )   1 9 1     F i g u r e   1 .   V a r i o u s   t y p e s   o f   s c h e d u l e r s       F o r   l o n g - t e r m   s c h e d u l e r ,   i t   l o a d s   p r o c e s s e s   i n   m e m o r y   f o r   e x e c u t i o n   a f t e r   s e l e c t i n g   t h e m   f r o m   t h e   j o b   p o o l .   C o n c e r n i n g   t h e   s h o r t - t e r m   s c h e d u l e r ,   i t   a l l o c a t e s   t h e   C P U   t o   o n e   p r o c e s s   f r o m   t h o s e   r e a d y   t o   b e   e x e c u t e d .   F o r   m e d i u m - t e r m   s c h e d u l e r ,   i t   t a k e s   o f f   p r o c e s s e s   f r o m   m a i n   m e m o r y   a n d   p l a c e   t h e m   o n   s e c o n d a r y   m e m o r y   ( s u c h   a s   a   d i s k   d r i v e )   o r   v i c e   v e r s a .   T h i s   i s   c o m m o n l y   r e f e r r e d   t o   a s   S w a p p i n g   o f   p r o c e s s e s   i n   m e m o r y   [ 2 ] .   T h e   e f f i c i e n c y   o f   t h e   R o u n d   R o b i n   S c h e d u l i n g   A l g o r i t h m   d e p e n d s   o n   t h e   t i m e   q u a n t u m   s i z e .   F i r s t l y ,   i f   t h e   q u a n t u m   o f   t i m e   i s   e x t r e m e l y   l a r g e ,   i t   d e c r e a s e s   t h e   r e s p o n s e   t i m e   a n d   i t   b e h a v e s   s i m i l a r   t o   F C F S   a l g o r i t h m .   I n   t h e   o t h e r   h a n d ,   i f   t h e   q u a n t u m   o f   t i m e   i s   e x t r e m e l y   s m a l l   t h i s   c a u s e s   m a n y   c o n t e x t   s w i t c h e s ,   w h i c h   d e c r e a s e s   t h e   C P U   e f f i c i e n c y .       2 .   R E L A T E D   W O R K S   I n   t h e   r e c e n t   y e a r s ,   a   n u m b e r   o f   C P U   s c h e d u l i n g   m e c h a n i s m s   h a v e   b e e n   d e v e l o p e d   f o r   p r e d i c t a b l e   a l l o c a t i o n   o f   p r o c e s s o r .   E x t r a c t i n g   a d v a n t a g e s   o f   e a c h   a l g o r i t h m   a n d   t r y   t o   m i x   t h e m   t o   l e a d   t o   t h e   p e r f e c t   a l g o r i t h m   a c c o r d i n g   t o   a   s p e c i f i c   s i t u a t i o n .   I n   M i s h r a ,   a n   i m p r o v e d   R o u n d   R o b i n   s c h e d u l e r   i s   d e v e l o p e d   n a m e d   I m p r o v e d   R o u n d   R o b i n   ( I R R )   C P U   s c h e d u l i n g   a l g o r i t h m .   I t   w o r k s   s i m i l a r   t o   R o u n d   R o b i n   ( R R )   w i t h   a   s m a l l   i m p r o v e m e n t   [ 6 ] .   I R R   p i c k s   t h e   f i r s t   p r o c e s s   f r o m   t h e   r e a d y   q u e u e   a n d   a l l o c a t e   t h e   C P U   t o   i t   f o r   a   t i m e   i n t e r v a l   o f   u p   t o   o n e   Q T .   E v e r y   t i m e   a   p r o c e s s   a c c o m p l i s h   i t s   Q T ,   i t   c h e c k s   t h e   r e m a i n i n g   C P U   b u r s t   t i m e   o f   t h e   c u r r e n t l y   r u n n i n g   p r o c e s s .   I f   t h e   r e m a i n i n g   C P U   b u r s t   t i m e   o f   t h e   c u r r e n t l y   r u n n i n g   p r o c e s s   i s   l e s s   t h a n   o n e   Q T ,   t h e   C P U   a g a i n   a l l o c a t e d   t o   t h e   c u r r e n t l y   r u n n i n g   p r o c e s s   f o r   r e m a i n i n g   C P U   b u r s t   t i m e .     T o   e v a l u a t e   t h e   p e r f o r m a n c e ,   l e t ' s   c o n s i d e r   t h e   f o l l o w i n g   r e a d y   q u e u e   a s   s h o w n   i n   T a b l e   1 .   F o r   s i m p l e   R o u n d   R o b i n   a l g o r i t h m ,   t h e   G a n t t   c h a r t   i s   s h o w n   i n   F i g u r e   2   f o r   Q T = 1 0   m s .   C o n c e r n i n g   I m p r o v e d   R o u n d   R o b i n   a l g o r i t h m   ( I R R ) ,   t h e   G a n t t   c h a r t   w i l l   b e   a s   f o l l o w   a s   s h o w n   i n   F i g u r e   3 .   P e r f o r m a n c e s   o f   t h e   t w o   a l g o r i t h m s   a r e   r e s u m e d   i n   T a b l e   2   r e g a r d i n g   t o   A v e r a g e   W T   a n d   A v e r a g e   T T .       T a b l e   1 .   P r o c e s s ' s   I d   a n d   B u r s t   T i m e   P r o c e s s   I D   B u r s t   T i m e   ( m s )   P 1   5   P 2   1 2   P 3   2 3   P 4   2 6   P 5   3 4     T a b l e   2 .   C o m p a r i s o n   o f   R R   a n d   I R R   A l g o r i t h m     A v e r a g e   W T   ( m s )     A v e r a g e   T T   ( m s )     R R     3 8 . 4     5 7 . 8     I R R     3 0 . 4     4 9 . 8           Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I n t   J   E l e c   &   C o m p   E n g ,   V o l .   9 ,   N o .   1 ,   F e b r u a r y   2 0 1 9   :     1 9 0   -   2 0 2   1 9 2     F i g u r e   2 .   G a n t t   c h a r t   f o r   s i m p l e   R R       F i g u r e   3 .   G a n t t   c h a r t   f o r   I R R       T h e   p r o p o s e d   I R R   i n   C P U   s c h e d u l i n g   a l g o r i t h m   i s   g i v i n g   b e t t e r   p e r f o r m a n c e s   t h a n   R R .   A f t e r   i m p r o v e m e n t   i n   R R ,   i t   h a s   b e e n   f o u n d   t h a t   t h e   W T   a n d   T T   h a v e   b e e n   r e d u c e d   d r a s t i c a l l y   [ 6 ] .   A   m o d i f i e d   r o u n d   r o b i n   a l g o r i t h m ,   p r o p o s e d   b y   [ 7 ] ,   c o n s i s t s   o f   a   m i x t u r e   b e t w e e n   s h o r t e s t   j o b   f i r s t   a n d   r o u n d   r o b i n   a l g o r i t h m s .   I n   t h i s   n e w   a l g o r i t h m ,   t h e   Q T   t a k e s   t h e   b u r s t   t i m e   o f   m i d   p r o c e s s   w h e n   t h e   n u m b e r   o f   p r o c e s s e s   i s   o d d   e l s e ,   i t   t a k e s   t h e   a v e r a g e   t i m e   o f   b u r s t   t i m e   o f   a l l   p r o c e s s e s .     T o   e v a l u a t e   t h e   p e r f o r m a n c e ,   l e t ' s   c o n s i d e r   t h e   f o l l o w i n g   r e a d y   q u e u e   a s   s h o w n   i n   T a b l e   3 .   F o r   s i m p l e   R o u n d   R o b i n   a l g o r i t h m ,   t h e   G a n t t   c h a r t   i s   s h o w n   i n   F i g u r e   4   w i t h   Q T = 2 5   m s .   C o n c e r n i n g   M o d i f i e d   R o u n d   R o b i n   a l g o r i t h m   ( M R R ) ,   t h e   G a n t t   c h a r t   w i l l   b e   a s   f o l l o w   a s   s h o w n   i n   F i g u r e   5 .   P e r f o r m a n c e s   o f   t h e   t w o   a l g o r i t h m s   a r e   r e s u m e d   i n   T a b l e   4 .   r e g a r d i n g   t o   a v e r a g e   W T   a n d   a v e r a g e   T T .       T a b l e   3 .   P r o c e s s ' s   I d   a n d   B u r s t   T i m e   P r o c e s s   I D   B u r s t   T i m e   ( m s )   P 1   1 4   P 2   4 5   P 3   3 6   P 4   2 5   P 5   7 7     T a b l e   4 .   C o m p a r i s o n   o f   R R   a n d   M R R   A l g o r i t h m     A v e r a g e   W T   ( m s )     A v e r a g e   T T   ( m s )     R R     7 0 . 2     1 0 9 . 6   M R R     5 6 . 8   9 6 . 2               F i g u r e   4 .   G a n t t   c h a r t   f o r   s i m p l e   R R     P 1   P 2   P 3   P 4   P 5   P 2   P 5   P 5   0   1 4   5 0   8 6   1 1 1   1 4 7   1 5 6   1 9 2   1 9 7     F i g u r e   5 .   G a n t t   c h a r t   f o r   M R R       I t   i s   c o n c l u d e d   f r o m   t h e   a b o v e   e x p e r i m e n t s   t h a t   t h e   p r o p o s e d   a l g o r i t h m   M R R   p e r f o r m s   b e t t e r   t h a n   s i m p l e   R R   i n   t e r m s   o f   p e r f o r m a n c e   m e t r i c s   s u c h   a s   a v e r a g e   W T   a n d   a v e r a g e   T T .   I n   t h e   w o r k   o f   [ 8 ] ,   t h e   p r o p o s e d   a l g o r i t h m   i s   b a s e d   o n   t h e   i n t e g r a t i o n   o f   R o u n d   R o b i n   a n d   p r i o r i t y   s c h e d u l i n g   a l g o r i t h m   a n d   a l s o   i m p l e m e n t s   t h e   c o n c e p t   o f   a g i n g   b y   a t t r i b u t i n g   n e w   p r o c e s s   p r i o r i t i e s .   F i r s t ,   t h e   C P U   i s   a l l o c a t e d   t o   e v e r y   p r o c e s s   i n   r o u n d   r o b i n   f a s h i o n   w i t h   a   g i v e n   p r i o r i t y   a n d   q u a n t u m .   T h e n ,   p r o c e s s e s   a r e   s o r t e d   i n   i n c r e a s i n g   o r d e r   a c c o r d i n g   t o   t h e i r   r e m a i n i n g   C P U   b u r s t   t i m e   i n   t h e   r e a d y   q u e u e .   C o n s e q u e n t l y ,   n e w   p r i o r i t i e s   a r e   a s s i g n e d ;   t h e   p r o c e s s   w i t h   s h o r t e s t   r e m a i n i n g   C P U   b u r s t   i s   a s s i g n e d   w i t h   h i g h e s t   p r i o r i t y .   E a c h   p r o c e s s   g e t s   t h e   c o n t r o l   o f   t h e   C P U   u n t i l   t h e y   f i n i s h e d   t h e i r   e x e c u t i o n .   T h i s   n e w   a p p r o a c h   i m p r o v e s   t h e   p e r f o r m a n c e   o f   C P U   i n   r e a l   t i m e   o p e r a t i n g   s y s t e m .     T o   e v a l u a t e   t h e   p e r f o r m a n c e ,   l e t ' s   c o n s i d e r   t h e   f o l l o w i n g   r e a d y   q u e u e   a s   s h o w n   i n   T a b l e   5 .   F o r   s i m p l e   R o u n d   R o b i n   a l g o r i t h m   w i t h   Q T = 5 m s ,   w e   o b t a i n   t h e   f o l l o w i n g   G a n t t   c h a r t   a s   s h o w n   i n   F i g u r e   6 .   C o n c e r n i n g   P r i o r i t y   b a s e d   R o u n d   R o b i n   a l g o r i t h m   ( P R R ) ,   t a s k s   a r e   e x e c u t e d   a c c o r d i n g   t o   t h e i r   p r i o r i t y ,   a n d   t h e   G a n t t   c h a r t   w i l l   b e   a s   f o l l o w   a s   s h o w n   i n   F i g u r e   7 .   P e r f o r m a n c e s   o f   t h e   t w o   a l g o r i t h m s   a r e   r e s u m e d   i n   T a b l e   6 .   r e g a r d i n g   t o   a v e r a g e   W T   a n d   A v e r a g e   T T .       T a b l e   5 .   P r o c e s s ' s   I d   a n d   B u r s t   T i m e     P r o c e s s   I D   B u r s t   T i m e   ( m s )   P r i o r i t y   P 1   2 2   4   P 2   1 8   2   P 3   9   1   P 4   1 0   3   P 5   4   5   T a b l e   6 .   C o m p a r i s o n   o f   R R   a n d   P R R   A l g o r i t h m     A v e r a g e   W T   ( m s )     A v e r a g e   T T   ( m s )     R R     3 3 . 2   4 5 . 8   P R R     2 6 . 2   3 8 . 8           Evaluation Warning : The document was created with Spire.PDF for Python.
I n t   J   E l e c   &   C o m p   E n g     I S S N :   2 0 8 8 - 8 7 0 8       P r i o r i t y   b a s e d   r o u n d   r o b i n   ( P B R R )   C P U   s c h e d u l i n g   a l g o r i t h m   ( S o n i a   Z o u a o u i )   1 9 3     F i g u r e   6 .   G a n t t   c h a r t   f o r   s i m p l e   R R       F i g u r e   7 .   G a n t t   c h a r t   f o r   P R R       T h e   p r o p o s e d   a l g o r i t h m   i m p r o v e s   a l l   t h e   d r a w b a c k s   o f   r o u n d   r o b i n   C P U   s c h e d u l i n g   a l g o r i t h m .   I t   r e t a i n s   t h e   a d v a n t a g e   o f   r o u n d   r o b i n   i n   r e d u c i n g   s t a r v a t i o n   a n d   a l s o   i n t e g r a t e s   t h e   a d v a n t a g e   o f   p r i o r i t y   s c h e d u l i n g .   I n   A b d u l r a h i m   e t   a l .   a   N e w   I m p r o v e d   R o u n d   R o b i n   ( N I R R )   w a s   d e v e l o p e d   [ 9 ] .   T h i s   a l g o r i t h m   i s   a n   i m p r o v e d   v e r s i o n   o f   I m p r o v e d   R o u n d   R o b i n   ( I R R )   a l g o r i t h m   m e n t i o n e d   a b o v e   i n   [ 6 ] .   T h i s   a l g o r i t h m   h o l d s   p r o c e s s e s   a c c o r d i n g   t o   t h e i r   a r r i v a l   t i m e s   i n   a   q u e u e   n a m e d   A R R I V E   q u e u e .   I n   t h e   o t h e r   h a n d ,   o t h e r   p r o c e s s e s   a r e   i n   a   q u e u e   c a l l e d   R E Q U E S T   q u e u e   w a i t i n g   t h e i r   t u r n   t o   o c c u p y   t h e   C P U .   T h e   t i m e   q u a n t u m   i s   c o n s i d e r e d   a s   t h e   a v e r a g e   o f   b u r s t   t i m e s   o f   t h e   p r o c e s s e s   i n   t h e   R E Q U E S T   q u e u e .   T o   e v a l u a t e   t h e   p e r f o r m a n c e ,   l e t ' s   c o n s i d e r   t h e   f o l l o w i n g   r e a d y   q u e u e   a s   s h o w n   i n   T a b l e   7 .   F o r   s i m p l e   R o u n d   R o b i n   a l g o r i t h m   w i t h   Q T = 5 0 m s ,   w e   o b t a i n   t h e   f o l l o w i n g   G a n t t   c h a r t   a s   s h o w n   i n   F i g u r e   8 .   C o n c e r n i n g   N e w   I m p r o v e d   R o u n d   R o b i n   a l g o r i t h m   ( N I R R ) ,   t h e   G a n t t   c h a r t   i s   a s   f o l l o w s   a s   s h o w n   i n   F i g u r e   9 .   P e r f o r m a n c e s   o f   t h e   t w o   a l g o r i t h m s   a r e   r e s u m e d   i n   T a b l e   8   r e g a r d i n g   t o   t h e   a v e r a g e   W T   a n d   t h e   a v e r a g e   T T .       T a b l e   7 .   P r o c e s s ' s   w i t h   I t s   I d   a n d   B u r s t   T i m e   P r o c e s s   I D   B u r s t   T i m e   ( m s )   P 1   2 3   P 2   7 5   P 3   9 3   P 4   4 8   P 5   2     T a b l e   8 .   C o m p a r i s o n   o f   R R   a n d   N I R R   A l g o r i t h m     A v e r a g e   W T   ( m s )     A v e r a g e   T T   ( m s )     R R     1 1 3   1 6 1 . 2   N I R R     5 3 . 8   1 0 2             F i g u r e   8 .   G a n t t   c h a r t   f o r   s i m p l e   R R       F i g u r e   9 .   G a n t t   c h a r t   f o r   N I R R       I n   E m i l i o   a n   a l g o r i t h m   c a l l e d   M o d u l o   B a s e d   R o u n d   R o b i n   A l g o r i t h m   i s   p r o p o s e d .   T h i s   a l g o r i t h m   i s   b a s e d   o n   R o u n d   R o b i n   f a s h i o n   a n   i n t e l l i g e n t   t i m e   q u a n t u m   a n d   t h e n   a s s i g n s   p r i o r i t y   t o   t h e   p r o c e s s e s   [ 1 0 ] .   T h i s   a l g o r i t h m   s t a r t   b y   c a l c u l a t i n g   t h e   a v e r a g e   o f   C P U   b u r s t   o f   a l l   t h e   p r o c e s s e s   ( P )   a n d   t h e n   c o m p u t e   f o r   e a c h   p r o c e s s   t h e   b u r s t   t i m e   m o d u l o   P   w h i c h   i s   n a m e d   ( M ) .   A f t e r   t h a t   p r o c e s s e s   a r e   s o r t e d   a c c o r d i n g   t o   t h e   v a l u e   o f   M   a n d   t h e n   t h e   t i m e   q u a n t u m   ( Q T )   i s   c o n s i d e r e d   e q u a l   t o   P .   T o   e v a l u a t e   t h e   p e r f o r m a n c e ,   l e t ' s   c o n s i d e r   t h e   f o l l o w i n g   r e a d y   q u e u e   a s   s h o w n   i n   T a b l e   9   ( A l l   p r o c e s s e s   a r r i v e   a t   t = 0   a n d   Q T = 1 0   m s ) .   F o r   s i m p l e   R o u n d   R o b i n   a l g o r i t h m ,   w e   o b t a i n   t h e   f o l l o w i n g   G a n t t   c h a r t   a s   s h o w n   i n   F i g u r e   1 0 .   F o r   M o d u l o   B a s e d   R o u n d   R o b i n   A l g o r i t h m ,   t h e   G a n t t   c h a r t   i s   a s   f o l l o w s   a s   s h o w n   i n   F i g u r e   1 1 .   P e r f o r m a n c e s   o f   t h e   t w o   a l g o r i t h m s   a r e   r e s u m e d   i n   T a b l e   1 0   r e g a r d i n g   t o   t h e   a v e r a g e   W T   a n d   t h e   a v e r a g e   T T .       T a b l e   9 .   P r o c e s s ' s   I d   a n d   B u r s t   T i m e   P r o c e s s   I D   B u r s t   T i m e   ( m s )   P 1   1 0   P 2   2 0   P 3   3 0   P 4   4 0   P 5   5 0     T a b l e   1 0 .   C o m p a r i s o n   o f   R R   a n d   M o d u l o   B a s e d   R o u n d   R o b i n   A l g o r i t h m   A l g o r i t h m     A v e r a g e   W T   ( m s )     A v e r a g e   T T   ( m s )     R R     6 0   9 0   N I R R     5 2   8 2         Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I n t   J   E l e c   &   C o m p   E n g ,   V o l .   9 ,   N o .   1 ,   F e b r u a r y   2 0 1 9   :     1 9 0   -   2 0 2   1 9 4     F i g u r e   1 0 .   G a n t t   c h a r t   f o r   s i m p l e   R R       F i g u r e   1 1 .   G a n t t   c h a r t   f o r   M o d u l o   B a s e d   R o u n d   R o b i n   A l g o r i t h m       3 .   R E A L   T I M E   O P E R A T I N G   S Y S T E M   ( R T O S )   R e a l   T i m e   O p e r a t i n g   S y s t e m   ( R T O S )   i s   a   r e a c t i v e   O S   t h a t   m u s t   r e s p o n d   c o n t i n u o u s l y   t o   s t i m u l i   f r o m   a   p r o c e s s   t h a t   s e e k s   t o   c o n t r o l .   A   r e a l - t i m e   s y s t e m   i s   a   r e a c t i v e   s y s t e m   t h a t   m u s t   m e e t   t i m e   c o n s t r a i n t s   [ 1 1 ] .     A   r e a l - t i m e   s y s t e m   m u s t   b e   a b l e   t o   p r o c e s s   i n f o r m a t i o n   f r o m   t h e   p r o c e s s   w i t h i n   a   p e r i o d   t h a t   d o e s   n o t   a f f e c t   t h e   p r o c e s s   c o n t r o l .   R e a c t   t o o   l a t e   c a n   l e a d   t o   c a t a s t r o p h i c   c o n s e q u e n c e s   f o r   t h e   s y s t e m   i t s e l f   o r   t h e   p r o c e s s .   C o m p l i a n c e   w i t h   t i m e   c o n s t r a i n t s   i s   t h e   m a i n   c o n s t r a i n t   t o   s a t i s f y .   T h e   v a l i d i t y   o f   a   r e a l   t i m e   s y s t e m   d e p e n d s   n o t   o n l y   o n   t h e   r e s u l t s   o f   t h e   t r e a t m e n t   c a r r i e d   o u t   b u t   a l s o   t h e   t e m p o r a l   a s p e c t   ( a   f a i r   c a l c u l a t i o n   b u t   o u t   o f   t i m e   i s   a n   i n v a l i d   c a l c u l a t i o n ) .     3 . 1 .     R e a l - t i m e   s y s t e m s   c l a s s i f i c a t i o n   T h e   c r i t i c a l   t i m e   c o n s t r a i n t s   l e d   t o   c l a s s i f y   t h e   r e a l - t i m e   s y s t e m s   i n   t h e   f o l l o w i n g   t h r e e   c a t e g o r i e s   [ 1 2 ] :   a .   R e a l   t i m e   s t r i c t   s y s t e m :   a   s y s t e m   t h a t   i s   s u b j e c t   t o   s t r i c t   t i m e   c o n s t r a i n t s ,   t h a t   i s   t o   s a y   f o r   w h i c h   t h e   s l i g h t e s t   m i s t a k e   t i m e   c a n   h a v e   d e v a s t a t i n g   h u m a n   a n d   e c o n o m i c   c o n s e q u e n c e s .   M o s t   a p p l i c a t i o n s   i n   t h e   a v i o n i c s   f i e l d ,   a u t o m o b i l e ,   e t c . ,   a r e   s t r i c t   r e a l   t i m e ;   b .   R e a l - t i m e   f l e x i b l e   s y s t e m :   a   s y s t e m   t h a t   i s   s u b j e c t   t o   f l e x i b l e   t i m e   c o n s t r a i n t s ,   a   n u m b e r   o f   t i m i n g   e r r o r s   c a n   b e   t o l e r a t e d .   c .   R e a l - t i m e   m i x e d   s y s t e m :   a   s y s t e m   t h a t   i s   s u b j e c t   t o   s t r i c t   a n d   f l e x i b l e   t i m e   c o n s t r a i n t s .     3 . 2 .   R e a l - t i m e   t a s k   A   r e a l - t i m e   t a s k   c o n s i s t s   o f   a   s e t   o f   i n s t r u c t i o n s   t h a t   c a n   b e   r u n   i n   s e q u e n c e   o n   o n e   o r   m o r e   p r o c e s s o r s   a n d   m e e t   t i m e   c o n s t r a i n t s .   I n   t h e   f o l l o w i n g ,   w e   w i l l   a s s u m e   t h a t   a   t a s k   w i l l   n o t   r u n   i n   p a r a l l e l .   I t   c a n   b e   r e p e a t e d   a n y   n u m b e r   o f   t i m e s ,   p o s s i b l y   i n f i n i t e .   E a c h   o f   t h e s e   p e r f o r m a n c e s   i s   c a l l e d   i n s t a n c e   o r   w o r k   ( " j o b " ) .   A   r e a l - t i m e   s y s t e m   c o n s i s t s   o f   a   s e t   o f   r e a l - t i m e   t a s k s   s u b j e c t   t o   r e a l - t i m e   c o n s t r a i n t s   ( R e a l   t i m e   c o n s t r a i n t s ) .   A   r e a l - t i m e   t a s k   c a n   b e :   a .   P e r i o d i c :   i t s   i n s t a n c e s   ( v e r s i o n s )   a r e   r e p e a t e d   i n d e f i n i t e l y   a n d   t h e r e   i s   a   c o n s t a n t   t i m e   b e t w e e n   t w o   s u c c e s s i v e   a c t i v a t i o n s   o f   i n s t a n c e s   r e f e r r e d   p e r i o d .   b .   S p o r a d i c :   i t s   i n s t a n c e s   ( v e r s i o n s )   a r e   r e p e a t e d   i n d e f i n i t e l y   a n d   t h e r e   i s   a   m i n i m u m   t i m e   b e t w e e n   t w o   s u c c e s s i v e   i n s t a n c e s .   c .   A p e r i o d i c :   t h e r e   i s   n o   c o r r e l a t i o n   b e t w e e n   s u c c e s s i v e   i n s t a n c e s .     3 . 3     P e r i o d i c   t a s k s   T h e   c l a s s i c   m o d e l   o f   p e r i o d i c   t a s k s   c a l l e d   L i u   a n d   L a y l a n d   m o d e l s ,   t h e   m o s t   u s e d   i n   m o d e l i n g   r e a l - t i m e   s y s t e m s   [ 1 3 ] .   T h i s   m o d e l   a l l o w s   d e f i n i n g   m u l t i p l e   s e t t i n g s   f o r   a   j o b .   T h e s e   p a r a m e t e r s   a r e   o f   t w o   t y p e s :   s t a t i c   p a r a m e t e r s   f o r   t h e   t a s k   i t s e l f   a n d   t h e   d y n a m i c   p a r a m e t e r s   o n   e a c h   i n s t a n c e   o f   t h e   t a s k   a s   s h o w n   i n   F i g u r e   1 2 .   T h e   b a s i c   s t a t i c   p a r a m e t e r s   o f   a   p e r i o d i c   t a s k   τ i i s :     τ i   =   ( R i ,   C i ,   D i ,   T i )     ( 1 )     R i :   ( r e l e a s e   t i m e )   d a t e   o f   f i r s t   a c t i v a t i o n   o f   t a s k   i ,   w h e n   τ i   c a n   s t a r t   i t s   f i r s t   p e r f o r m a n c e .   C i :   ( c o m p u t i n g   t i m e ) :   e x e c u t i o n   t i m e   o f   τ i .   T h i s   p a r a m e t e r   i s   c o n s i d e r e d   i n   s e v e r a l   w o r k s   o n   r e a l - t i m e   s c h e d u l i n g   a s   t h e   w o r s t   c a s e   e x e c u t i o n   t i m e   ( W C E T   f o r   w o r s t - c a s e   e x e c u t i o n   t i m e )   o n   t h e   p r o c e s s o r   o n   w h i c h   i t   w i l l   r u n .   D i :   r e l a t i v e   m a t u r i t y   o r   c r i t i c a l   t i m e   f r a m e   f o r   e a c h   a c t i v a t i o n   o f   τ i .   T i :   i m p l e m e n t a t i o n   p e r i o d   τ i .       Evaluation Warning : The document was created with Spire.PDF for Python.
I n t   J   E l e c   &   C o m p   E n g     I S S N :   2 0 8 8 - 8 7 0 8       P r i o r i t y   b a s e d   r o u n d   r o b i n   ( P B R R )   C P U   s c h e d u l i n g   a l g o r i t h m   ( S o n i a   Z o u a o u i )   1 9 5     F i g u r e   1 2 .   C l a s s i c   m o d e l   i n   p e r i o d i c   t a s k s       O t h e r   s t a t i c   p a r a m e t e r s   a r e   d e r i v e d   f r o m   t h e   b a s i c   o n e s :   U i   =   ,   C P U   u t i l i z a t i o n   f a c t o r   f o r   τ i , U i 1 .   C H i   =   ,   t h e   d e n s i t y   o f   t h e   t a s k   τ i ,   C H i 1 .   C o n c r e t e /   n o   c o n c r e t e   t a s k s     I f   a l l   t h e   f i r s t   a c t i v a t i o n   d a t e s   o f   a l l   j o b s   a r e   k n o w n ,   i t   i s   s a i d   t h a t   t h e   t a s k s   a r e   c o n c r e t e .   O n   t h e   c o n t r a r y ,   i f   w e   d o   n o t   k n o w   t h e   d a t e s   o f   f i r s t   a c t i v a t i o n ,   i t   i s   s a i d   t h a t   t h e s e   t a s k s   a r e   n o t   c o n c r e t e .   a .   S y n c h r o n o u s /   a s y n c h r o n o u s   t a s k s     I f   a l l   t a s k s   a r e   p r a c t i c a l   a n d   h a v e   t h e   s a m e   d a t e   o f   f i r s t   a c t i v a t i o n ,   i t   i s   s a i d   t h a t   t h e   t a s k s   a r e   s y n c h r o n i z e d   a c t i v a t i o n s .   O t h e r w i s e ,   t h e y   a r e   a s y n c h r o n o u s   b .   R e a l - t i m e   c o n s t r a i n t s   I n   r e a l - t i m e   s c h e d u l i n g ,   t a s k s   c a n   b e   s u b j e c t   t o   s e v e r a l   c o n s t r a i n t s   s u c h   a s   t h e   c o n s t r a i n t s   o f   d e a d l i n e s ,   s t r i c t   p e r i o d i c i t y ,   d e p e n d e n c i e s   a n d   p r e c e d e n c e ,   e t c .   c .   D e a d l i n e s   T h e   c o n s t r a i n t s   o f   d e a d l i n e s   a l l o w   e x p r e s s i n g   a   c o n d i t i o n   o f   t h e   e n d   d a t e   o f   i m p l e m e n t a t i o n   a t   l a t e s t   o f   a   g i v e n   t a s k .   C o n s i d e r   a   s y s t e m   o f   p e r i o d i c   t a s k s ,   a c c o r d i n g   t o   t h e   r e l a t i o n s h i p   b e t w e e n   t h e   p e r i o d   T i   a n d   t h e   d e a d l i n e   f o r   e a c h   t a s k   i   D i ,   w e   d i s t i n g u i s h   t h r e e   t y p e s   o f   d e a d l i n e s :   D i   =   T i :   e a c h   a c t i v a t i o n   o f   t h e   t a s k   τ i   m u s t   b e   e x e c u t e d   b e f o r e   t h e   n e x t   a c t i v a t i o n .   W e   t a l k   a b o u t   d e a d l i n e s   o n   t a s k s   a c t i v a t i o n s ,   i m p l i c i t   d e a d l i n e s   o r   d e a d l i n e s   o n   r e q u e s t s .   D i T i :     e a c h   a c t i v a t i o n   o f   t h e   t a s k   τ i   m u s t   b e   e x e c u t e d   o n   o r   b e f o r e   a   d a t e   l e s s   t h a n   o r   e q u a l   t o   t h e   d a t e   o f   i t s   n e x t   a c t i v a t i o n .   W e   t a l k   a b o u t   s t r e s s   a t   w o r k   d e a d l i n e s .   D i T i :   t h e r e   i s   n o   c o r r e l a t i o n   b e t w e e n   a t   l a t e s t   e n d   d a t e   o f   e x e c u t i o n   o f   τ i   u p o n   a c t i v a t i o n   a n d   i t s   n e x t   a c t i v a t i o n   o f   τ i .   O n e   c a n   h a v e   ( D i T i )   o r   ( D i > T i ) ,   w e   s p e a k   h e r e   a b o u t   a r b i t r a r y   t a s k s   d e a d l i n e s .   d .   S t r i c t   p e r i o d i c i t y   C o n s i d e r   a   p e r i o d i c   t a s k   τ i   i n   a   r e a l   t i m e   t a s k   s y s t e m ,   s t r i c t   p e r i o d i c i t y   c o n s t r a i n t   r e q u i r e s   t h a t   t h e   t i m e   e l a p s e d   b e t w e e n   t w o   c o n s e c u t i v e   b e g i n n i n g s   o f   e x e c u t i o n   d a t e s     a n d     c o r r e s p o n d s   e x a c t l y   t o   t h e   p e r i o d   o f   t h e   t a s k   τ i .   T h e   a d v a n t a g e   o f   t h i s   c o n s t r a i n t   i s   t h a t   k n o w l e d g e   o f   t h e   a c t u a l   s t a r t   d a t e   o f   t h e   f i r s t   i n s t a n c e     i m p l i e s   k n o w l e d g e   o f   t h e   e f f e c t i v e s t a r t   d a t e   o f   a l l   s u b s e q u e n t   i n s t a n c e s   o f   t h e   s a m e   t a s k   [ 1 4 ] ,   t h i s   i s   e x p r e s s e d   b y   t h e   r e l a t i o n s h i p :       = + k T i   ( k   1 )   ( 2 )     e .   D e p e n d e n c i e s   b e t w e e n   t a s k s   A   d e p e n d e n c y   b e t w e e n   t w o   t a s k s   i   a n d   j   c a n   b e   o f   t w o   t y p e s :   A   p r e c e d e n c e   d e p e n d e n c y   a n d / o r   d a t a   d e p e n d e n c y .   A   p r e c e d e n c e   d e p e n d e n c y   b e t w e e n   ( i ,   j )   r e q u i r e s   t h a t   t h e   t a s k   j   s t a r t e d   r u n n i n g   a f t e r   t h e   t a s k   i   h a v e   c o m p l e t e l y   f i n i s h e d   r u n n i n g   [ 1 4 ,   1 5 ,   1 6 ,   1 7 ] .   T h e   p r e c e d e n c e   o f   c o n s t r a i n t s   i s   i n d i r e c t l y   r e a l - t i m e   c o n s t r a i n t s   a n d   w e   s a i d   t h a t   t h e   t a s k   i   i s   a   p r e d e c e s s o r   o f   t h e   t a s k   j   a n d   j   i s   a   s u c c e s s o r   o f   i .   I f   t a s k   i   r u n s   e x a c t l y   o n c e   b e f o r e   a   r u n   o f   t a s k   j ,   w e   h a v e   t h e n   a   s i m p l e   p r e c e d e n c e   c o n s t r a i n t   i f   n o t   i t s   a   w i d e   p r e c e d e n c e   [ 1 7 ,   2 ,   1 8 ] .   A   d a t a   d e p e n d e n c y   m e a n s   t h e   t a s k   i   p r o d u c e s   a   r e s u l t   t h a t   i s   c o n s u m e d   b y   j   [ 1 4 ,   1 5 ] ,   t h i s   d e p e n d e n c e   i n e v i t a b l y   l e a d s   t o   p r e c e d e n c e   b e t w e e n   t a s k s .   T a s k s   a r e   c a l l e d   i n d e p e n d e n t   i f   t h e y   a r e   d e f i n e d   o n l y   b y   t h e i r   t e m p o r a l   p a r a m e t e r s .   f .   L a t e n c y   L a t e n c y   i s   d e f i n e d   f o r   d e p e n d e n t   t a s k s   b y   t r a n s i t i v i t y   i n   t h e   c a s e   o f   a   p a t h   t a s k s .   L e t s   s u p p o s e   τ i   a n d   τ j   t w o   t a s k s ,   t h e   l a t e n c y   b e t w e e n   i   a n d   j   d e n o t e d   L   ( τ i ,   τ j )   i s   t h e   t i m e   b e t w e e n   t h e   s t a r t   o f   e x e c u t i o n   o f   τ i   a n d   t h e   e n d   o f   e x e c u t i o n   o f   τ j .     Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I n t   J   E l e c   &   C o m p   E n g ,   V o l .   9 ,   N o .   1 ,   F e b r u a r y   2 0 1 9   :     1 9 0   -   2 0 2   1 9 6 4 .   S C H E D U L I N G   4 . 1 .   S c h e d u l i n g   o b j e c t i v e s   a .   W h e n   d e s i g n i n g   a   s c h e d u l i n g   a l g o r i t h m ,   a   s y s t e m   d e s i g n e r   m u s t   t a k e   i n t o   c o n s i d e r a t i o n   m a n y   f a c t o r s   s u c h   a s   t h e   k i n d   o f   s y s t e m s   u s e d   a n d   u s e r ' s   n e e d s .   b .   M a x i m i z e   t h r o u g h p u t :   M a x i m i z i n g   t h e   t h r o u g h p u t   o f   a   s c h e d u l e r   i s   m a d e   b y   s e r v i c i n g   t h e   m a x i m u m   n u m b e r   o f   p r o c e s s e s   p e r   u n i t   o f   t i m e .   c .   A v o i d   a n   i n f i n i t e   b l o c k i n g   s t a t e   o r   s t a r v a t i o n :   A v o i d i n g   a n   i n f i n i t e   b l o c k i n g   s t a t e   o r   s t a r v a t i o n   i s   a v o i d i n g   p r o c e s s   t o   s t u c k   i n   w a i t i n g   s t a t e   f o r     u n b o u n d e d   t i m e   b e f o r e   o r   w h i l e   p r o c e s s   s e r v i c e .   d .   M i n i m i z e   o v e r h e a d :   U s i n g   s y s t e m   r e s o u r c e s   i n   a n   e f f e c t i v e   m a n n e r   t o   r e d u c e   s y s t e m   o v e r h e a d   ( s y s t e m   o v e r h e a d   c a u s e   r e s o u r c e s   w a s t a g e ) .   S o   o v e r a l l   s y s t e m   p e r f o r m a n c e   i m p r o v e s   g r e a t l y .   e .   E n f o r c e m e n t   o f   p r i o r i t i e s :   I f   a   s y s t e m   i s   b a s e d   o n   p r o c e s s e s   p r i o r i t i e s ,   t h e   s c h e d u l e r   s h a l l   p r i v i l e g e   h i g h e r   p r i o r i t y   p r o c e s s e s .   f .   A c h i e v e   b a l a n c e   b e t w e e n   r e s p o n s e   a n d   u t i l i z a t i o n :   S y s t e m   r e s o u r c e s   s h a l l   b e   k e p t   b u s y   b y   t h e   s c h e d u l e r .   T h e   s c h e d u l e r   c a n   p r e v e n t   s t a r v a t i o n   t h r o u g h   t h e   c o n c e p t   o f   a g i n g   a n d   b e   a b l e   t o   i n c r e a s e   t h r o u g h p u t   b y   p r o m o t i n g   p r o c e s s e s   h a v i n g   a   s h o r t   b u r s t   t i m e   a n d   c a n   b e   s a t i s f i e d   q u i c k l y .   A l s o ,   p r o c e s s e s   w h o s e   c o m p l e t i o n   b e c a u s e   o t h e r   p r o c e s s e s   t o   r u n   s h a l l   b e   f a v o r e d   b y   t h e   s c h e d u l e r   t o   a c c o m p l i s h   g o a l s   p r e v i o u s l y   s i t e d .     4 . 2 .   S c h e d u l i n g   p a r a m e t e r s   E a c h   C P U   s c h e d u l i n g   a l g o r i t h m   h a s   i t s   o w n   p r o p r i e t i e s ,   a n d   c h o o s i n g   a   p a r t i c u l a r   a l g o r i t h m   m a y   f a v o r   o n e   c l a s s   o f   p r o c e s s   o v e r   t h e   o t h e r .   M a n y   c r i t e r i a   m u s t   b e   c o n s i d e r e d   f o r   c o m p a r i n g   C P U   s c h e d u l i n g   a l g o r i t h m s   p e r f o r m a n c e .   T h o s e   c r i t e r i a   i n c l u d e   t h e   f o l l o w i n g :   a .   C P U   u t i l i z a t i o n :     t h e   m a x i m u m   r a t e   o f   k e e p i n g   t h e   C P U   b u s y   d o i n g   u s e f u l   w o r k .   b .   T h r o u g h p u t :   T h e   n u m b e r   o f   j o b s   p r o c e s s e d   p e r   t i m e   u n i t .   c .   T u r n a r o u n d   t i m e :   T h e   t i m e   n e e d e d   f o r   t h e   e x e c u t i o n   o f   o n e   p r o c e s s .   d .   W a i t i n g   t i m e :   T h e   t i m e   s p e n t   b y   t h e   p r o c e s s   w a i t i n g   i n   r e a d y   q u e u e .   e .   R e s p o n s e   t i m e :   T h e   t i m e   b e t w e e n   s u b m i s s i o n   o f   t h e   r e q u e s t   a n d   t h e   f i r s t   r e s p o n s e .   f .   T h e   s h a r i n g   o f   t h e   p r o c e s s o r   a n d   r e s o u r c e s   i n t r o d u c e d   s e v e r a l   s t a t e s   f o r   a   t a s k   a s   s h o w n   i n   F i g u r e   1 3 :   1 .   N e w :   t h e   t a s k   i s   n o t   y e t   a c t i v a t e d .   2 .   R e a d y :   t h e   t a s k   i s   e n a b l e d   a n d   h a s   a l l   t h e   r e s o u r c e s   i t   n e e d s   t o   r u n .   3 .   W a i t i n g :   t h e   t a s k   i s   w a i t i n g   f o r   r e s o u r c e s .   4 .   R u n n i n g :   t h e   t a s k   r u n s .   5 .   T e r m i n a t e d :   t h e   t a s k   h a s   n o   c u r r e n t   a p p l i c a t i o n ,   i t   h a s   t e r m i n a t e d .   T h e   s c h e d u l e r   i s   r e s p o n s i b l e   f o r   t h e   t r a n s i t i o n   f r o m   o n e   t a s k   s t a t e   t o   a n o t h e r .   F o r   e a c h   i n v o c a t i o n ,   t h e   s c h e d u l e r   u p d a t e s   t h e   l i s t   o f   r e a d y   t a s k s   b y   i n c l u d i n g   a l l   a c t i v e   t a s k s   a n d   w h o   h a v e   t h e i r   r e s o u r c e s   a n d   r e m o v i n g   t a s k s   t h a t   e n d e d   t h e i r   p e r f o r m a n c e s   o r   b l o c k e d   b y   w a i t i n g   a   r e s o u r c e .   T h e n   a m o n g   t h e   r e a d y   t a s k s ,   t h e   s c h e d u l e r   s e l e c t s   t h e   h i g h e s t   p r i o r i t y   t a s k   t o   r u n .   T h u s ,   a   t a s k   i n   t h e   n e w   s t a t e   c a n   m o v e   t o   t h e   r e a d y   s t a t e .   A   t a s k   i n   t h e   r e a d y   s t a t e   m a y   g o   t o   r u n n i n g   s t a t e   o r   w a i t i n g   s t a t e .   A   t a s k   i n   r u n n i n g   s t a t u s   m a y   r e t u r n   t o   t h e   r e a d y   s t a t e   i f   i t   i s   p r e e m p t e d   b y   a n o t h e r   h i g h e r - p r i o r i t y   t a s k ,   i t   c a n   g o   t o   t h e   w a i t i n g   s t a t e   i f   i t   i s   w a i t i n g   f o r   r e s o u r c e   l i b e r a t i o n   o r   h a s   f i n i s h e d   e x e c u t i n g ,   i t   p a s s e s   i n   t h e   p a s s i v e   s t a t e .           F i g u r e   1 3 .   P r o c e s s   s t a t e   t r a n s i t i o n   d i a g r a m       n e w   r e a d y   r u n n i g   t e r m i n a t e d   w a i t i n g   I n t e r r u p t   E x i t   a d m i t t e d   S c h e d u l e r   D i s p a t c h   I / O   o r   e v e n t   w a i t   I / O   o r   e v e n t   c o m p l e t i o n   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t   J   E l e c   &   C o m p   E n g     I S S N :   2 0 8 8 - 8 7 0 8       P r i o r i t y   b a s e d   r o u n d   r o b i n   ( P B R R )   C P U   s c h e d u l i n g   a l g o r i t h m   ( S o n i a   Z o u a o u i )   1 9 7 A   t a s k   c a n   m o v e   f r o m   t h e   w a i t i n g   s t a t e   t o   t h e   r e a d y   s t a t e ,   a n d   f i n a l l y   a   t a s k   c a n   m o v e   f r o m   t h e   p a s s i v e   s t a t e   t o   t h e   r e a d y   s t a t e .   F i g u r e   1 3   p r o v i d e s   a n   i l l u s t r a t i o n   o f   t h e   d i f f e r e n t   s t a t e s   a n d   t h e i r   t r a n s i t i o n s   [ 2 ] .       5 .   E X I S T I N G   C P U   S C H E D U L I N G   A L G O R I T H M S   T h e r e   a r e   v a r i e t i e s   o f   C P U   S c h e d u l i n g   a l g o r i t h m s .   T h e   m o s t   a n d   c o m m o n l y   u s e d   a r e   e x p l a i n e d .   a .   F i r s t - c o m e   f i r s t - s e r v e d   ( F I F O )   s c h e d u l i n g   p o l i c y   I t   i s   a   p o l i c y   o f   s e n i o r i t y   w i t h o u t   r e q u i s i t i o n :   T h e   C P U   i s   a l l o c a t e d   a c c o r d i n g   t o   t h e   p r o c e s s   s u b m i s s i o n   o r d e r .   I n   t h i s   p o l i c y ,   p r o c e s s e s   o f   l o w   e x e c u t i o n   t i m e   c a n   b e   p e n a l i z e d   b e c a u s e   a   l o n g   p r o c e s s   p r e c e d e s   t h e m   i n   t h e   q u e u e .   b .   S c h e d u l i n g   p o l i c y   " s h o r t e r   f i r s t "   s c h e d u l i n g   p o l i c y   T h i s   p o l i c y   t r i e s   t o   r e m e d y   t h e   d i s a d v a n t a g e   m e n t i o n e d   f o r   t h e   p r e v i o u s   p o l i c y .   T h e   C P U   i s   a l l o c a t e d   t o   t h e   p r o c e s s   o f   s m a l l e r   e x e c u t i o n   t i m e .   T h i s   p o l i c y   i s   a l s o   a   p o l i c y   w i t h o u t   r e q u i s i t i o n .   I t   h a s   t h e   p r o p e r t y   o f   m i n i m i z i n g   t h e   a v e r a g e   r e s p o n s e   t i m e   f o r   a l l   s c h e d u l i n g   a l g o r i t h m s   w i t h o u t   r e q u i s i t i o n i n g .   I t   p e n a l i z e s   l o n g   w o r k .   I t   a l s o   m a k e s   i t   n e c e s s a r y   t o   e s t i m a t e   t h e   d u r a t i o n   o f   t h e   p r o c e s s e s ,   w h i c h   a r e   n o t   u s u a l l y   k n o w n .   T h e r e   i s   a   v e r s i o n   w i t h   r e q u i s i t i o n   o f   t h i s   p o l i c y   c a l l e d   " t i m e   r e m a i n i n g   f i r s t   s h o r t e s t " :   i n   t h i s   c a s e ,   t h e   e x e c u t i n g   p r o c e s s   r e s t o r e s   t h e   p r o c e s s o r   w h e n   a   n e w   e x e c u t i o n   t i m e   p r o c e s s   l e s s   t h a n   i t s   r e m a i n i n g   e x e c u t i o n   t i m e   b e c o m e s   r e a d y   [ 1 8 ] .   c .   R o u n d   r o b i n   s c h e d u l i n g   p o l i c y   E a c h   p r o c e s s   p r e s e n t   i n   t h e   q u e u e   o f   r e a d y   p r o c e s s e s   a c q u i r e s   t h e   p r o c e s s o r   i n   t u r n   f o r   a   m a x i m u m   o f   a   t i m e   e q u a l   t o   t h e   q u a n t u m   o f   t i m e .   I f   t h e   p r o c e s s   h a s   c o m p l e t e d   i t s   e x e c u t i o n   b e f o r e   t h e   e n d   o f   t h e   q u a n t u m ,   i t   r e l e a s e s   t h e   p r o c e s s o r   a n d   t h e   n e x t   p r o c e s s   i n   t h e   q u e u e   o f   t h e   r e a d y   p r o c e s s e s   i s   e l e c t e d .   I f   t h e   p r o c e s s   h a s   n o t   c o m p l e t e d   b e f o r e   t h e   e n d   o f   t h e   q u a n t u m ,   i t   l o s e s   t h e   p r o c e s s o r   a n d   i s   r e i n s e r t e d   a t   t h e   e n d   o f   t h e   p r o c e s s .   T h i s   t u r n s t i l e   p o l i c y   i s   u s u a l l y   u s e d   i n   t i m e s h a r e   s y s t e m s .   I t s   p e r f o r m a n c e   l a r g e l y   d e p e n d s   o n   t h e   s i z e   o f   t h e   q u a n t u m .   T o o   l a r g e   q u a n t u m   i n c r e a s e s   t h e   r e s p o n s e   t i m e s   w h i l e   a   t o o   s m a l l   q u a n t u m   m u l t i p l i e s   t h e   c o n t e x t   s w i t c h e s   u n t i l   t h e y   a r e   n o t   n e g l i g i b l e   [ 1 9 ] .   d .   P r i o r i t y - b a s e d   S c h e d u l i n g :   A   f i x e d   p r i o r i t y   r a n k   i s   a s s i g n e d   t o   e a c h   p r o c e s s   a n d   t h e   s c h e d u l e r   s o r t   p r o c e s s e s   b a s i n g   o n   t h e i r   p r i o r i t i e s .   P r o c e s s   w i t h   h i g h e s t   p r i o r i t y   i s   p u t t e d   o n   t h e   h e a d   o f   t h e   q u e u e   a n d   t h e   p r o c e s s   w i t h   t h e   l o w e s t   p r i o r i t y   i n   t h e   t a i l   [ 2 0 ] .   e .   R a t e   M o n o t o n i c   ( R M )   R M   s c h e d u l i n g   a l g o r i t h m   w a s   i n t r o d u c e d   b y   L i u   a n d   L a y l a n d   i n   1 9 7 3   [ 1 3 ] .   T h i s   i s   a   p r e e m p t i v e   s c h e d u l i n g   a l g o r i t h m   w h i c h   a p p l i e s   t o   i n d e p e n d e n t   p e r i o d i c   t a s k s ,   a n d   d u e   u p o n   r e q u e s t   ( T i = D i ) .   T h e   t a s k   p r i o r i t y   i s   i n v e r s e l y   p r o p o r t i o n a l   t o   i t s   p e r i o d ,   t h a t   i s   t o   s a y ,   t h e   l o n g e r   t h e   p e r i o d   o f   a   t a s k   i s ,   t h e   h i g h e r   i s   t h e   p r i o r i t y .   T h i s   a l g o r i t h m   i s   o p t i m a l   i n   t h e   c l a s s   o f   a l g o r i t h m s   f o r   f i x e d   p r i o r i t y   p r e e m p t i v e   i n d e p e n d e n t   t a s k s   d u e   o n   s y n c h r o n o u s   r e q u e s t .   A   s u f f i c i e n t   c o n d i t i o n   f o r   s c h e d u l a b i l i t y   o f   t h e   R M   a l g o r i t h m   f o r   a   s e t   o f   p e r i o d i c   t a s k s   Γ n   m a t u r i n g   o n   r e q u e s t   i s   g i v e n   b y   [ 1 3 ] :           n ( 2   1 )   ( 3 )     f .   D e a d l i n e   M o n o t o n i c   ( D M )   T h e   D M   s c h e d u l i n g   a l g o r i t h m   w a s   i n t r o d u c e d   b y   L e u n g   a n d   W h i t e h e a d   i n   1 9 8 2   f o r   c o n d i t i o n e d   d e a d l i n e   t a s k s   [ 2 1 ] .   T h e   t a s k   p r i o r i t y   i s   i n v e r s e l y   p r o p o r t i o n a l   t o   i t s   r e l a t i v e   d e a d l i n e ,   t h a t   i s   t o   s a y ,   t h e   l o n g e r   t h e   r e l a t i v e   d e a d l i n e   i s   t h e h i g h e r   i s t h e   p r i o r i t y .   T h i s   a l g o r i t h m   i s   o p t i m a l   i n   t h e   c l a s s   o f   p r e e m p t i v e   a n d   f i x e d   p r i o r i t y   a l g o r i t h m s   f o r   i n d e p e n d e n t   p r e e m p t i v e   a n d   c o n d i t i o n e d   d e a d l i n e   t a s k s   ( D i     T i ) .   T h e   s u f f i c i e n t   c o n d i t i o n   f o r   s c h e d u l a b i l i t y   o f   t h e   D M   a l g o r i t h m   f o r   a   s e t   o f   p e r i o d i c   t a s k s   Γ n   d u e   t o   s t r e s s   i s   g i v e n   b y :     , + ( ) .   ( 4 )     W i t h   h p ( τ i )   i s   t h e   s e t   o f   Γ n   t a s k s   o f   p r i o r i t i e s   h i g h e r   t h a n   o r   e q u a l   t o   Γ n ,   n o t   i n c l u d i n g   Γ n .   D y n a m i c   p r i o r i t i e s .   A   d y n a m i c   p r i o r i t y   c h a n g e s   d u r i n g   t h e   e x e c u t i o n   o f   a n   i n s t a n c e   [ 2 2 ] .     a .   E a r l i e s t   D e a d l i n e   F i r s t   ( E D F )   T h e   E D F   s c h e d u l i n g   a l g o r i t h m   w a s   i n t r o d u c e d   b y   L u i   a n d   L a y l a n d   i n   1 9 7 3   [ 1 3 ] .   I t   i s   a   s c h e d u l i n g   a l g o r i t h m   w h i c h   c a n   b e   p r e e m p t i v e   o r   n o n - p r e e m p t i v e   a n d   a p p l i e d   f o r   i n d e p e n d e n t   p e r i o d i c   t a s k s   ( T i   =   D i ) .   T h e   h i g h e s t   p r i o r i t y   a t   t i m e   t   i s   a l l o c a t e d   t o   t h e   t a s k   w i t h   t h e   c l o s e s t   a b s o l u t e   d e a d l i n e .   Evaluation Warning : The document was created with Spire.PDF for Python.
                                I S S N :   2 0 8 8 - 8 7 0 8   I n t   J   E l e c   &   C o m p   E n g ,   V o l .   9 ,   N o .   1 ,   F e b r u a r y   2 0 1 9   :     1 9 0   -   2 0 2   1 9 8 E D F   i s   o p t i m a l   f o r   i n d e p e n d e n t   a n d   p r e e m p t i v e   t a s k s .   A   n e c e s s a r y   a n d   s u f f i c i e n t   c o n d i t i o n   o f   s c h e d u l a b i l i t y   o f   E D F   f o r   a   s e t   o f   p e r i o d i c   t a s k s   Γ n   i s   g i v e n   b y :     τ i Γ n         1   ( 5 )     b .   L e a s t - L a x i t y   F i r s t   ( L L F )   T h e   L L F   s c h e d u l i n g   a l g o r i t h m   i s   b a s e d   o n   t h e   l a x i t y .   T h e   t a s k   w h o s e   l a x i t y   i s   t h e   l o w e s t   c o m p a r e d   t o   a l l   t h e   r e a d y   t a s k s   h a v e   t h e   h i g h e s t   p r i o r i t y .   T h i s   a l g o r i t h m   i s   o p t i m a l   f o r   i n d e p e n d e n t   a n d   p r e e m p t i v e   t a s k s .   T h e   c o n d i t i o n   o f   s c h e d u l a b i l i t y   o f   L L F   a n d   t h e   E D F   a r e   t h e   s a m e .   T h a t   i s   t o   s a y   t h a t   t h e   n e c e s s a r y   a n d   s u f f i c i e n t   c o n d i t i o n   o f   s c h e d u l a b i l i t y   o f   L L F   f o r   a   s e t   o f   p e r i o d i c   t a s k s   Γ n i s   g i v e n   b y :     τ i Γ n         1   ( 6 )     A   d y n a m i c   p r i o r i t y   c h a n g e s   d u r i n g   t h e   e x e c u t i o n   o f   a n   i n s t a n c e .   T h e   m o s t   u s e d   s c h e d u l i n g   a l g o r i t h m   f o r   d y n a m i c   p r i o r i t i e s   i s   " L e a s t   l a x i t y   F i s r t " .       6 .   D R A W B A C K S   O F   R O U N D   R O B I N   S C H E D U L I N G   A L G O R I T H M S   R o u n d   R o b i n   s c h e d u l i n g   a l g o r i t h m   h a s   m a n y   d i s a d v a n t a g e s ,   w h i c h   a r e   a s   f o l l o w i n g :     6 . 1 .   H i g h   A v e r a g e   W a i t i n g   T i m e   F o r   r o u n d   r o b i n   a r c h i t e c t u r e ,   t h e   p r o c e s s   s p e n d s   t h e   t i m e   i n   t h e   r e a d y   q u e u e   w a i t i n g   h i s   t u r n   t o   o w n   t h e   p r o c e s s o r .   D u e   t o   t h e   p r e s e n c e   o f   t i m e   q u a n t u m ,   p r o c e s s e s   a r e   p u s h e d   t o   l e a v e   t h e   p r o c e s s o r   a n d   r e t u r n   t o   t h e   w a i t i n g   s t a t e .   T h i s   p r o c e d u r e   p r o d u c e s   a   h i g h   a v e r a g e   w a i t i n g   t i m e ,   w h i c h   p r e s e n t s   t h e   m a i n   d i s a d v a n t a g e .     6 . 2 .   L o w   t h r o u g h p u t   T h r o u g h p u t   p r e s e n t   t h e   n u m b e r   o f   p r o c e s s   c o m p l e t e d   p e r   t i m e   u n i t .   D u e   t o   i t s   t i m e   s l i c e ,   R o u n d   R o b i n   i s   c h a r a c t e r i z e d   b y   a   h i g h   n u m b e r   o f   c o n t e x t   s w i t c h e s ,   w h i c h   l e a d s   t o   o v e r a l l   d e g r a d a t i o n   o f   t h e   s y s t e m   p e r f o r m a n c e   ( t h r o u g h p u t ) .     6 . 3 .   C o n t e x t   s w i t c h   O n e s   t h e   t i m e   s l i c e   f i n i s h e d ,   t h e   p r o c e s s   i s   f o r c e d   t o   l e a v e   t h e   C P U .   T h e   s c h e d u l e r   s t o r e s   t h e   c o n t e x t   o f   t h e   c u r r e n t   p r o c e s s   i n   s t a c k   o r   a   r e g i s t e r   a n d   a l l o t s   t h e   C P U   t o   t h e   n e x t   p r o c e s s   i n   t h e   r e a d y   q u e u e .   T h i s   c o n c e p t   i s   k n o w n   b y   c o n t e x t   s w i t c h i n g   w h i c h   l e a d s   t o   t i m e   w a s t a g e   a n d   s c h e d u l e r   o v e r h e a d .     6 . 4 .   H i g h   r e s p o n s e   t i m e   R e s p o n s e   t i m e   i s   d e f i n e d   a s   t h e   t i m e   b e t w e e n   s u b m i s s i o n   o f   a   r e q u e s t   a n d   t h e   f i r s t   C P U   r e s p o n s e .   I n   g e n e r a l ,   r o u n d   r o b i n   m a d e   l a r g e r   r e s p o n s e   t i m e ,   w h i c h   c a u s e s   s y s t e m   p e r f o r m a n c e   d e g r a d a t i o n .   T o   a c h i e v e   h i g h   p e r f o r m a n c e ,   t h e   r e d u c t i o n   o f   r e s p o n s e   t i m e   s h a l l   b e   i n d i s p e n s a b l e .     6 . 5 .   V e r y   h i g h   t u r n a r o u n d   t i m e   T u r n a r o u n d   t i m e   i s   t h e   t i m e   b e t w e e n   s u b m i s s i o n   o f   a   p r o c e s s   a n d   i t s   c o m p l e t i o n .   R o u n d   R o b i n   s c h e d u l i n g   a l g o r i t h m   i s   c h a r a c t e r i z e d   b y   a   h i g h   t u r n a r o u n d   t i m e .   S o   a s   a   r e s u l t ,   t o   i m p r o v e   t h e   s y s t e m   p e r f o r m a n c e   t h i s   p a r a m e t e r   s h o u l d   b e   r e d u c e d .       7 .   E F F I C I E N C Y   O F   E X I S T I N G   A P P R O A C H E S   S c h e d u l i n g   p r o c e s s e s   i n   a   f a i r   m a n n e r   a n d   p r o d u c i n g   r e s u l t s   i n   m i n i m u m   a v e r a g e   w a i t i n g   t i m e   a n d   t u r n a r o u n d   t i m e   a r e   t h e   m a i n   c r i t e r i a   o f   a n   e f f i c i e n t   a l g o r i t h m .   I n   d i f f e r e n t   r e s e a r c h   p a p e r s ,   t h e   i s s u e   o f   t i m e   q u a n t u m   a n d   p r i o r i t y   d e c i s i o n   i s   t h e   b o t t l e n e c k   i n   v a r i o u s   C P U   s c h e d u l i n g   a l g o r i t h m .   F i n d i n g   t h e   o p t i m a l   t i m e   q u a n t u m   i n   r o u n d   r o b i n   a l g o r i t h m   i s   a   d i f f i c u l t   p r o b l e m   t o   s o l v e .   T h e   r e a l   m e a n i n g   o f   d y n a m i c i t y   i n   C P U   s c h e d u l i n g   a l g o r i t h m s   i s   n o t   g o a l   t o   a t t e m p t .   A   v a r i e t y   o f   o b j e c t i v e s   a r e   t o   b e   t a k e n   i n t o   c o n s i d e r a t i o n   a n d   s o l u t i o n s   m u s t   s a t i s f y   m o s t   o f   t h e   p e r f o r m a n c e   c r i t e r i a .   S o l u t i o n s   m u s t   b e   u n i v e r s a l l y   a c c e p t e d   b y   m o s t   o f   t h e   o p e r a t i n g   s y s t e m .   C o n c e r n i n g   d y n a m i c   t i m e   q u a n t u m   a n d   d y n a m i c   p r i o r i t y   c a l c u l a t i o n ,   m a n y   r e s e a r c h e r s   a r e   c a r r i e d   o u t   a n d   s o m e   o f   t h e m   p a i d   a t t e n t i o n   t o w a r d s   t h e   c o m b i n a t i o n   o f   t w o .   O t h e r   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t   J   E l e c   &   C o m p   E n g     I S S N :   2 0 8 8 - 8 7 0 8       P r i o r i t y   b a s e d   r o u n d   r o b i n   ( P B R R )   C P U   s c h e d u l i n g   a l g o r i t h m   ( S o n i a   Z o u a o u i )   1 9 9 r e s e a r c h e r s   p a y   b i g   a t t e n t i o n   t o   r e s p o n s e   t i m e   a n d   s o m e   o f   t h e m   e v e n   u s e d   a r t i f i c i a l   i n t e l l i g e n c e   i n   d e t e r m i n i n g   d y n a m i c   t i m e   q u a n t u m   o r   p r i o r i t y .   I n   g e n e r a l ,   m e a s u r e m e n t   a r e   n o t   f a r   f r o m   o u t l i e r s .   S o   g i v i n g   t h e   o p t i m u m   r e s u l t s   c a n n o t   b e   o b v i o u s   f o r   t h e   s e t   o f   p r o c e s s e s   h a v i n g   C P U   b u r s t   t i m e .   T h e   p r e s e n c e   o f   o u t l i e r s   i n   t h e   l i s t   i s   o b v i o u s   e s p e c i a l l y   w h e n   t h e   C P U   a l w a y s   t r i e s   t o   k e e p   a   m i x   o f   C P U   b o u n d   a n d   I / O   b o u n d   p r o c e s s e s .   D e c r e a s i n g   t h e   o u t l i e r   m a k e s   t h e   d a t a   m o r e   e x a c t   w h e n   f i n d i n g   m e a n   o r   m e d i a n   v a l u e   f o r   d e t e r m i n i n g   t i m e   q u a n t u m .       8 .   P R O P O S E D   A L G O R I T H M   T h i s   a p p r o a c h   o f   R o u n d   R o b i n   S c h e d u l i n g   A l g o r i t h m   e m p h a s i z e s   o n   s i m p l e   R o u n d   R o b i n   A l g o r i t h m   d r a w b a c k s .   T h i s   k i n d   o f   s c h e d u l i n g   g i v e s   t h e   s a m e   a m o u n t   o f   t i m e   t o   a l l   p r o c e s s e s .   P r o c e s s e s   a r e   e x e c u t e d   i n   f i r s t   c o m e   f i r s t   s e r v e d   w a y .   R o u n d   R o b i n   i s   n o t   e f f i c i e n t   w i t h   p r o c e s s e s   w i t h   s m a l l   e x e c u t i o n   t i m e .   T h e r e f o r e ,   a s   a   r e s u l t ,   t h e   w a i t i n g   t i m e   a n d   r e s p o n s e   t i m e   o f   p r o c e s s e s   i n c r e a s e   a n d   c o n s e q u e n t l y   t h e   s y s t e m   t h r o u g h p u t   d e c r e a s e s .   I n   t h i s   p r o p o s e d   a l g o r i t h m ,   w e   h a v e   i m p l e m e n t e d   R R   a l g o r i t h m   w h i l e   t a k i n g   i n t o   a c c o u n t   p r i o r i t y   b a s e d   f o r   t a s k s   m a n a g e m e n t .   I n   f a c t ,   a   p r i o r i t y   i n d e x   i s   a s s i g n e d   t o   e a c h   P r o c e s s .   P r o c e s s e s   i n   r e a d y   q u e u e   a r e   s o r t e d   a c c o r d i n g   t o   t h e i r   p r i o r i t i e s .   P r o c e s s   w i t h   s m a l l   p r i o r i t y   i n d e x   a r e   p l a c e d   i n   t h e   h e a d   o f   t h e   r e a d y   q u e u e   a n d   s o   o n .   T h e   p r o p o s e d   a l g o r i t h m   s o l v e s   t h e   p r o b l e m   o f   h i g h e r   a v e r a g e   w a i t i n g   t i m e ,   t u r n a r o u n d   t i m e ,   r e s p o n s e   t i m e   a n d   m o r e   c o n t e x t   s w i t c h e s   a n d   t h e r e b y   i m p r o v e s   t h e   s y s t e m   p e r f o r m a n c e .   T h e   p r o p o s e d   a l g o r i t h m   i s   d e s c r i b e d   i n   t h e   f o l l o w i n g   f l o w c h a r t   a s   s h o w n   i n   F i g u r e   1 4 .           F i g u r e   1 4 .   P B R R   f l o w c h a r t       Evaluation Warning : The document was created with Spire.PDF for Python.