Meters are described fully here. You will find some good introductory material there. See too “Meter service” in this section of an architecture paper. Meters in Keykos are object like things that are accessed by key. To run, a domain requires a meter. To be executed, user code thus requires a domain with a meter. The domain has a special slot that must hold a meter key before the domain will obey any machine instructions.

Meters may themselves hold meter keys from which they get their authority to consume CPU resources. This chain terminates in a special magic meter key that works even though it does not designate a real meter. For a domain to run there must be an unbroken chain of meters from the domain to the special meter key. There is thus a tree of meters with the special meter key at the root and domains at the leaves. We speak below as if the root is at the top. The tree is formed of meter keys pointing up towards the root.

Each meter has a number in it that runs backwards as domains below run. When that number in a meter reaches zero any domain below that meter stops running and an exception message is sent via a key found in that meter’s keeper slot. This key is normally a start key to user code called the “meter keeper”. The message includes a service key to the meter which lets the keeper change slots in the meter. The meter keeper is thus able to get control as resources are consumed under the meter. The keeper can immediately replenish the counter or can decide not to replenish it until later when CPU resources are less dear.

The meters form a tree with a counter and on-off switch at each node that is accessible to the holder of a meter service key. See more general pattern.

The kernel switches about every 105 instructions among domains that are ready for the CPU and have meters with resources. This round-robin effect could be produced outside the kernel but it was very easy to do it in the kernel and expensive in resources to do it outside. Here is why meters are much more efficient than the naïve logic described above.

It is sometimes proposed that it would be easier to implement if meters could “hold” consumption rights so that it would be unnecessary for the kernel to find the special meter key, up the chain, to run the domain. This model would not provide for turning off some particular computation at a particular unanticipated time. This current meter design does allow for this. The two designs are contrasted by the names the wire model and the battery model. If there are batteries in the system one cannot turn things off selectively and promptly. There is a trade-off; if one makes small grants of fuel, then these effects are limited. One must then be able to determine who has unused fuel whose consumption might come at a time when CPU cycles were critically short. The Engines available in some varieties of Scheme are a form of battery. One can do time slicing with meters but not batteries. We did time-slicing in the kernel because it was not efficient to do it with meters, and besides, we didn’t think of it then.

This is an application of these ideas to conventional problems of killing threads that hold locks.

Priority Inversion