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 schedul...

Full description

Saved in:
Bibliographic Details
Published in:Simulation modelling practice and theory 2006, Vol.14 (1), p.1-24
Main Authors: Ramos, Jorge R., Rego, Vernon, Sang, Janche
Format: Article
Language:English
Subjects:
Batch arrivals
Batch departures
Event
Kernel
Lookahead
Red–black
Scheduling
Threads
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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( n 2), 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.
ISSN:1569-190X
1878-1462
DOI:10.1016/j.simpat.2005.02.008