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.