A New Approach for Investigation on Closed Type Network with Combination of HOL and Multi-Level RR Priorities Scheduling Strategies

• Autorzy: Oniszczuk W.

Warianty tytułu

PL

Nowe podejście (algorytmy) do modelowania procesu obsługi mieszanej z priorytetami i obsługą wieloetapową w sieciach typu zamkniętego

• Języki publikacji: EN

Abstrakty

EN

In this document, I propose a new algorithm for computation of main measures of effectiveness in a closed type, two-centre network. A novel priority scheduling strategy for this type of networks is presented. In such model, first priority tasks, tasks that need only one phase to get processed, coming from separate sources are served with head-of-line (HOL) priority algorithms. Ali lower priority tasks, incoming from different sources, get served according to a HOL round robin scheduling strategy. Any tasks that require multiple phases of processing arę moved to the back of the task queue and they are re-executed with a lower priority. Presented here algorithm belongs to a Mean Value Analysis (MVA) group and the model, that is being discussed, can be treated as M/G/l/N finite source (closed type) priority queue with multi-phase scrvicing based on round robin strategies. A constant or random length of time, called quantum, is set for each task and then processed by the server. If it takes lortger to process a given task than its assigned value, the task gets movcd to the end of the queue with a lower priority and then re-executed. Although, the paper primarily studies two-centre network performance, l also address performance issues of other computer systems where round robin priority scheduling strategies are used. Described above algorilhm is proved in diverse settings and then, numerous numerical results that show its efficiency are given.

PL

W pracy zostały przedstawione nowe algorytmy modelowania i obliczania miar wydajności w dwuwęzłowych sieciach typu zamkniętego. Pokazana jest tutaj nowa strategia szeregowania zadań w takich sieciach, gdzie zadania pierwszej klasy (priorytetu) napływają z wydzielonego źródła i obsługiwane są według priorytetu nierugującego (HOL), zaś zadania niższych priorytetów, napływające z innego źródła, obsługiwane są według algorytmu karuzelowego (HOL) z obniżaniem priorytetowej klasy. Zadania niższych priorytetów, na pierwszym etapie obsługi, otrzymują pewien kwant czasu, a gdy to nie wystarcza, cofane są na koniec kolejki z jednoczesnym obniżeniem priorytetu. Prezentowane algorytmy wywodzą się z metod wartości średnich (MVA) i traktowane są jako modele typu zamkniętego z priorytetami i czasem obsługi o rozkładzie dowolnym.

Słowa kluczowe

EN

Mean Yalue Analysis (MVA); Head-of-Line (HOL); round robin (RR) scheduling strategy; quality of service (QoS)

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2006
• Tom: Vol. 18, nr 4
• Strony: 241--260
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Oniszczuk W.

• Białystok University of Technology Faculty of Computer Science ul. Wiejska 45A 15-351 Białystok, Poland,

Bibliografia

• [1] Bryant R.M., Krzesinski A.E., Lakshmi M.S., Chandy K.M., The MVA Priority   Approximation, ACM Transaction on Computer Systems 2(4) (1984), pp. 335-359.
• [2] Ben Mamoun M., Pekergin N., Stochastic delay bounds off air queueing policies by analyzing weighted round robin - related policies, Performance Evaluation 47(2-3) (2002), pp. 181-196.
• [3] Cho K.-H., Yoon H., Design and analysis ofthe virtual-time-based round robin fair scheduling algorithm for QoS guarantees, Computer Communications 22(12) (1999), pp. 1151-1160.
• [4] Jaiswal N.K., Priority Queues (Academic Press, New York and London, 1968).
• [5] Jiang Y., Tham CH.-K., Ko CH.-CH., A probabilistic priority scheduling discipline for multi-service networks, Computer Communications 25(13) (2002), pp. 1243-1254.
• [6] Couvatsos D., Awan L., Entropy maximization and open queueing networks with priorities and blocking, Performance Evaluation 51(2-4) (2003), pp. 191-227.
• [7] Laevens K., Bruneel H., Discrete-time multiserver queues with priorities, Performance Evaluation 33(4) (1998), pp. 249-275.
• [8] Morris R.J.T., Priority Queuing Networks, The Bell System Technical Journal, 60(8) (1981), pp. 1745-1769.
• [9] Oniszczuk W., The MV A Algorithm for Closed Systems with Priority Round Robin Scheduling, IIAS-Transaction on System Research and Cybernetics: International Journal of the International Institute for Advanced Studies in System Research and Cybernetics (Canada) Vol. II, No l (2002), pp. 25-29.
• [10] Reiser M., Lavenberg S.S., Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the Association for Computing Machinery 27(2) (1980), pp. 313-322.
• [11] Reiser M., Mean-Value analysis and Convolution Method for Queue-Dependent Servers in Closed Queueing Networks, Performance Evaluation l (1981), pp. 7-18.
• [12] Shachnai H., Yu P.S., On analytic modeling of multimedia batching schemas, Performance Evaluation 33(3) (1998), pp. 201 -213.
• [13] Sharma V., Virtamo J.T., Afinite buffer queue with priorities, Performance Evaluation 47(1) (2002), pp. 1-22.
• [14] Walraevens J., Steyaert B., Bruneel H., Delay characteristics in discrete-time GI-G-1 Queues with non-preemptive priority ąueueing discipline, Performance Evaluation 50 (2002), pp. 53-75.
• [15] Wu Ch.S., Link-sharing method for ABR/UBR services in ATM networks, Computer Communications 21(13) (1998), pp. 1131-1142.