Lock-free scheduling of logical processes in parallel simulation

J. Liu, D. M. Nicol, K. Tan

Research output: Contribution to conferencePaperpeer-review


With fixed lookahead information in a simulation model, the overhead of asynchronous conservative parallel simulation lies in the mechanism used for propagating time updates in order for logical processes to safely advance their local simulation clocks. Studies have shown that a good scheduling algorithm should preferentially schedule processes containing events on the critical path. This paper introduces a lock-free algorithm for scheduling logical processes in conservative parallel discrete-event simulation on shared-memory, multiprocessor machines. The algorithm uses fetch&add operations that help avoid inefficiencies associated with using locks. The lock-free algorithm is robust. Experiments show that, compared with the scheduling algorithm using locks, the lock-free algorithm exhibits better performance when the number of logical processes assigned to each processor is small or when the workload becomes significant. In models with large number of logical processes, our algorithm shows only modest increase in execution time due to the overhead in the algorithm for extra bookkeeping.

Original languageEnglish (US)
Number of pages10
StatePublished - 2001
Externally publishedYes
Event15th Workshop on Parallel and Distributed Simulation (PADS 2001) - Lake Arrowhead, CA, United States
Duration: May 15 2001May 18 2001


Other15th Workshop on Parallel and Distributed Simulation (PADS 2001)
Country/TerritoryUnited States
CityLake Arrowhead, CA

ASJC Scopus subject areas

  • Engineering(all)


Dive into the research topics of 'Lock-free scheduling of logical processes in parallel simulation'. Together they form a unique fingerprint.

Cite this