An Asynchronous Garbage Collector for the Cap Filing System

The CAP filing system [Needham and Birrell 1977] is able to produce garbage or ‘lost objects’ on disc, because its directory structure is a general naming network containing, in principle, cyclic substructures. Such substructures may become inaccessible as a result of deletion of capabilities or file direct- ory entries. Up to now the tidy-up of the disc which occurs on system restart has been relied on to recover such space; this is somewhat inelegant and makes one nervous about leaving the system running for long periods. Accordingly an asynchronous garbage collector has been introduced.