PERFORMANCE OF PRIORITY QUEUE STRUCTURES IN A VIRTUAL MEMORY ENVIRONMENT

In this paper we study the performance of data structures in a Virtual Memory (VM) environment. As an example, we investigate the performance of priority queues which are used to implement the event-list in discrete event simulation programs. We treat this problem empirically, and present measurements of page fault performance for a few implementations under different settings. Some measurements are done on a real system, and others are obtained by simulating a VM environment. We suggest new versions of existing data structures which are tailored specifically for use in a VM environment. We investigate alternative page replacement and node alignment strategies and discuss their effect on performance.