Methods and apparatus, including computer systems and program products, for garbage collection of shared data entities. A computer program identifies a set of virtual machines (VMs), each operable to generate references to shared entities stored in shared memory. Each shared entity can include references to one or more of the other shared entities. The program waits for the VMs to independently identify the shared entities that they reference directly, and then initiates a shared garbage collection procedure to identify the shared entities that are not directly or indirectly referenced by any of the VMs and to reclaim the shared memory being used to store those shared entities. The VMs are prevented from generating new references to the shared entities solely during a portion of the shared garbage collection procedure. By minimizing the time during which access to the shared entities is restricted, performance and scalability can be increased.