Обзор систем параллельной обработки заявок

Обложка

Аннотация


Данная работа является первой в серии из двух статей, посвящённых обзору систем массового обслуживания вида «fork-join» (в западной классификации) или системам с расщеплением запросов. Указанная система является естественной моделью для многих других реальных систем. В статье описаны особенности построения этой модели и родственных ей систем, основные их характеристики. Отдельное внимание уделяется методам анализа времени отклика системы. Поскольку точное выражение для среднего времени отклика известно только для случая двух приборов, в статье приведено подробное описание подхода к получению точного выражения этой характеристики. Для случая, когда число приборов больше двух, различными методами получены аппроксимации среднего времени отклика,что объясняется сложностью исследований из-за существующей зависимости между очередями под запросов в силу общих моментов поступления. В работе представлено несколько методов приближенного анализа: различные варианты эмпирической аппроксимации, т.е. методы, уточняющие полученные характеристики благодаря использованию результатов имитационного моделирования; интерполяция с помощью предельных значений загрузки системы в случаях с отличными от экспоненциального распределениями для входящего потока и времени обслуживания.


А В Горбунова

Лицо (автор) для связи с редакцией.
gorbunova_av@rudn.university
Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Горбунова Анастасия Владимировна - ассистент кафедры прикладной информатики и теории вероятностей РУДН

И С Зарядов

zaryadov_is@rudn.university
Институт проблем информатики Федеральный исследовательский центр «Информатика и управление» РАН ул. Вавилова, д. 44, кор. 2, Москва, Россия, 119333

Зарядов Иван Сергеевич - кандидат физико-математических наук, доцент кафедры прикладной информатики и теории вероятностей РУДН, старший научный сотрудник ИПИ ФИЦ ИУ РАН

К Е Самуйлов

samuylov_ke@rudn.university
Российский университет дружбы народов ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Самуйлов Константин Евгеньевич - профессор, доктор технических наук, заведующий кафедрой прикладной информатики и теории вероятностей РУДН

Э С Сопин

sopin_es@rudn.university
Институт проблем информатики Федеральный исследовательский центр «Информатика и управление» РАН ул. Вавилова, д. 44, кор. 2, Москва, Россия, 119333

Сопин Эдуард Сергеевич - кандидат физико-математических наук, доцент кафедры прикладной информатики и теории вероятностей РУДН, старший научный сотрудник ИПИ ФИЦ ИУ РАН

  • Nelson R., Tantawi A. N. Approximate Analysis of Fork/Join Synchronization in Parallel Queues // IEEE Transactions on Computers. - 1988. - Vol. 37. - Pp. 739-743.
  • Thomasian A. Analysis of Fork/Join and Related Queueing Systems // ACM Computing Surveys (CSUR). - 2014. - Vol. 47, No 2. - Pp. 17:1-17:71.
  • Tsimashenka I., Knottenbelt W. J. Reduction of Subtask Dispersion in Fork-Join Systems // Computer Performance Engineering. - Springer Berlin Heidelberg, 2013. - Pp. 325-336.
  • Аппроксимация времени отклика системы облачных вычислений / А. В. Горбунова, И. С. Зарядов, С. И. Матюшенко, К. Е. Самуйлов, С. Я. Шоргин // Информатика и её применения. - 2015. - Т. 9, вып. 3. - С. 32-38.
  • Вышенский С. В., Григорьев П. В., Дубенская Ю. Ю. Идеальный синхронизатор маркированных пар в сети разветвление-объединение // Обозрение прикладной и промышленной математики. - 2008. - Т. 15, № 3. - С. 385-399.
  • Моисеева С. П., Ивановская И. А. Исследование математической модели параллельного обслуживания заявок смешанного типа // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2010. - Т. 317, № 5. - С. 32-34.
  • Моисеева С. П., Жидкова Л. А. Исследование системы параллельного обслуживания кратных заявок простейшего потока // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. - 2011. - Т. 17, № 4. - С. 49-54.
  • The Estimation of Probability Characteristics of Cloud Computing Systems with Splitting of Requests / A. V. Gorbunova, I. S. Zaryadov, S. I. Matushenko, E. S. Sopin // Proceedings of the Nineteenth International Scientific Conference Russia: Distributed computer and communication networks: control, computation, communications (DCCN-2016). - Vol. 3. - 2016. - Pp. 467-472.
  • Оценка вероятностных характеристик системы облачных вычислений с расщеплением запросов / А. В. Горбунова, И. С. Зарядов, С. И. Матюшенко, Э. С. Сопин // Информационные технологии и математическое моделирование (ИТММ- 2016): Материалы XV Международной конференции имени А. Ф. Терпугова. - 2016. - С. 167-172.
  • Mandelbaum M., Itzhak A.-B. Introduction to Queueing with Splitting and Matching // Israel Journal of Technology. - 1968. - Vol. 6, No 5. - Pp. 376-382.
  • Duda A., Czach´orski T. Performance Evaluation of Fork and Join Synchronization Primitives // Acta Informatica. - 1987. - Vol. 24, No 5. - Pp. 525-533.
  • Green L. A Queueing System in which Customers Require a Random Number of Servers // Operations Research. - 1980. - Т. 28, № 6. - С. 1335-1346.
  • Omahen K. J., Schrage L. A Queueing Analysis of a Multiprocessor System with Shared Memory // Proc. of the Symposium on Computer Communication Networks and Teletraffic. - 1972. - Pp. 77-88.
  • Thomasian A., Avizienis A. Dynamic Scheduling of Tasks Requiring Multiple Processors // Proceedings of the 11th IEEE Computer Society International Conference (COMPCON’75 Fall). - 1975. - Pp. 77-80.
  • Javidi T. Cooperative and Non-Cooperative Resource Sharing in Networks: a Delay Perspective // IEEE Transactions on Automatic Control. - 2008. - Vol. 53, No 9. - Pp. 2134-2142.
  • Kumar A., Shorey R. Performance Analysis and Scheduling of Stochastic Fork-Join Jobs in a Multicomputer System // IEEE Transactions on Parallel and Distributed Systems. - 1993. - Vol. 10, No 4. - Pp. 1147-1164.
  • Flatto L., Hahn S. Two Parallel Queues Created by Arrivals with Two Demands I // SIAM Journal on Applied Mathematics. - 1984. - Vol. 44, No 5. - Pp. 1041-1053.
  • Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications / G. Bolch, S. Greiner, H. de Meer, K. S. Trivedi. - John Wiley & Sons, 2006. - P. 896.
  • Baccelli F. Two Parallel Queues Created by Arrivals with Two Demands: the ||2 Symmetrical Case // INRIA Rapport de Recherche. - 1985. - Vol. 426.
  • Boyce W. E., DiPrima R. C. Elementary Differential Equations and Boundary Value Problems. - John Wiley & Sons, 2012. - P. 809.
  • Башарин Г. П. Введение в теорию вероятностей. - Москва: РУДН, 1990. - 228 с.
  • Бочаров П. П., Печинкин А. В. Теория массового обслуживания. - Москва: Изд-во РУДН, 1995. - С. 529.
  • Башарин Г. П. Лекции по математической теории телетрафика. - Москва: РУДН, 2009. - 342 с.
  • Queueing Theory / P. P. Bocharov, C. D’Apice, A. V. Pechinkin, S. Salerno. - Brill Academic ublishers, 2004. - P. 457.
  • Barlow R. E., Proschan F. Statistical Theory of Reliability and Life Testing: Probability Models. - John Wiley & Sons, 1981. - P. 290.
  • Varki E., Merchant A., Chen H. The | |1 Fork-Join Queue with Variable Subtasks. - http://www.cs.unh.edu/ ~ varki/publication/2002-nov-open.pdf.
  • Varki E. Response Time Analysis of Parallel Computer and Storage Systems // IEEE Transactions on Parallel and Distributed Systems. - 2001. - Vol. 12, No 11. - Pp. 1146-1161.
  • Varma S., Makowski A. M. Interpolation Approximations for Symmetric Fork-Join Queues // Performance Evaluation. - 1994. - Vol. 20. - Pp. 245-265.

Просмотры

Аннотация - 1114

PDF (Russian) - 643


© Горбунова А.В., Зарядов И.С., Самуйлов К.Е., Сопин Э.С., 2017

Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution 4.0 International License.