Dynamic Resource Allocation in Fork-Join Queues
ACM Transactions on Modeling and Performance Evaluation of Computing Systems · 31.03.2020 · 5 (1) · 1-28
DOI: 10.1145/3372376 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Modeling and Performance Evaluation of Computing Systems, online erschienen am 04.02.2020. Verfasst von Andrea Marin und 2 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 31 Literaturangaben.
Abstract (Originalsprache)
Fork-join systems play a pivotal role in the analysis of distributed systems, telecommunication infrastructures, and storage systems. In this article, we consider a fork-join system consisting of K parallel servers, each of which works on one of the K tasks that form each job. The system allocates a fixed amount of computational resources among the K servers, hence determining their service speed. The goal of this article is that of studying the resource allocation policies among the servers. We assume that the queueing disciplines of the fork- and join-queues are First Come First Served. At each epoch, at most K tasks are in service while the others wait in the fork-queues. We propose an algorithm with a very simple implementation that allocates the computational resources in a way that aims at minimizing the join-queue lengths, and hence at reducing the expected job service time. We study its performance in saturation and under exponential service time. The model has an elegant closed-form stationary distribution. Moreover, we provide an algorithm to numerically or symbolically derive the marginal probabilities for the join-queue lengths. Therefore, the expressions for the expected join-queue length and the expected response time under immediate join can be derived. Finally, we compare the performance of the proposed resource allocation algorithm with that of other strategies.
Zitieren
APA
Marin, A., Rossi, S., & Sottana, M. (2020). Dynamic Resource Allocation in Fork-Join Queues. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 5(1), 1-28. https://doi.org/10.1145/3372376
Vancouver
Marin A, Rossi S, Sottana M. Dynamic Resource Allocation in Fork-Join Queues. ACM Transactions on Modeling and Performance Evaluation of Computing Systems. 2020;5(1):1-28. doi:10.1145/3372376
BibTeX
@article{Marin2020,
author = {Marin, Andrea and Rossi, Sabina and Sottana, Matteo},
title = {Dynamic Resource Allocation in Fork-Join Queues},
journal = {ACM Transactions on Modeling and Performance Evaluation of Computing Systems},
year = {2020},
volume = {5},
number = {1},
pages = {1--28},
doi = {10.1145/3372376}
}
EUVIMED