Atomic heap transactions and fine-grain interrupts

Languages such as Java, ML, Scheme, and Haskell provide automatic storage m anagement, that is, garbage collection. The two fundamental operations perf ormed on a garbage-collected heap are "allocate" and "collect." Because the heap is in an inconsistent state during these operations, they must be per formed atomically. Otherwise, a heap client might access the heap during a time when its fundamental invariants do not hold, corrupting the heap. Standard techniques for providing this atomicity guarantee have large laten cies and other performance problems that impede their application in high-p erformance, interruptladen, thread-based systems applications. In particula r, the standard techniques prevent thread shcedulers schedulers' from switc hing threads on VM page faults. We cast the space of possible implementations into a general taxonomy, and describe a new technique that provides a simple, low-overhead, low-latency interlock. We have implemented this technique in a version of SML/NJ, and, because of its applicability to thread-based systems, are currently impleme nting it in the scheduler of our raw-hardware SML-based kernel, ML/OS. Our technique can be exrtended to provide other atomic sequences besides storag e allocation.