Building a Practical Event-Scheduler for a Multi-Processor Architecture

Abstract — We describe a scheduler that processes a high number of typed events per second while enabling certain event types to be allocated more resources than others in a work-conserving fashion. The scheduler is the core of a high volume messaging system, it uses a lock-free approach allowing it to scale with increasing number of processors. The scheduler threads coordinate using a lock-free concurrent priority queue. As far as we know, no formal analysis of this lock-free data structure has been given so far in the literature. We analyze the expected behavior of the scheduler and report on its actual performance on a multiprocessor machine. Index Terms — Scheduling, Event System, Lock-Free, Middle-ware I