کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
493565 721934 2006 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
An efficient burst-arrival and batch-departure algorithm for round-robin service
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
An efficient burst-arrival and batch-departure algorithm for round-robin service
چکیده انگلیسی

Simulations of CPU scheduling or waiting-line models that involve a server dispersing shared service quanta across jobs can require significant processing time, especially when simulations are supported by thread-based systems. To effect a reduction in simulation time we reduce the number of scheduled events, without affecting simulation results. We present an algorithm for such enhanced round-robin service in discrete-event simulation and implement and test it on a threads-based simulator. The algorithm predicts potential job departures and schedules them in advance, using cancellation and rescheduling when necessary. We generalize and improve upon a previous approach in which a single arrival and a single departure event is handled at a time. While the prior proposal offered a run-time complexity of O(n2), the new algorithm accomplishes this in time O(n log n). Further, the generalization also accommodates burst arrivals and batch departures with the reduced time complexity. Empirical results are presented to compare performance with previously proposed algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Simulation Modelling Practice and Theory - Volume 14, Issue 1, January 2006, Pages 1–24
نویسندگان
, , ,