Kieran Harty, David Cheriton, A Market Approach to Operating System Memory Allocation, in Scott H. Clearwater (ed.), Market-Based Control: A Paradigm for Distributed Resource Allocation, World Scientific Publishing Co., Singapore, 1996

(Summary by George Candea)

This paper proposes an interesting mechanism for managing the memory resource in an operating system, based on market principles. Each process has an account in which it can save money (currency is called dram), with which it can pay for leasing memory from the OS. The OS deposits drams in this account periodically, according to the system's resource allocation policy. Accounts are intialized with a non-zero number of drams.

When a process executes, it requests a quantity of physical memory for a specified period of time, gets charged for the memory over that time, after which it needs to release it back to the OS. Paging is managed by an application-controlled page-cache manager. Processes can request memory synchronously or asynchronously. Once it gets the memory, the process sets a timer to alert it before the lease runs out; the process must allow for page-in and page-out time. When a program runs overtime, it is charged at a penalty rate for a while, after which the memory is forcefuly reclaimed (possibly terminating the process).

A typical execution cycle has a program waiting for its savings to build up, then executes with leased memory until it runs out of drams, then goes to sleep and the cycle repeats; the period of this cycle is called a memory time-slice. This looks just like operating under a normal scheduler, except that the application can make its own tradeoffs. There is a limit on how many drams a process may save and an upper limit on the duration of a lease, to avoid monopolization of the system over unreasonable lengths of time. A process can query its account balance, the income rate, and the cost of pages (drams/sec).

There is separate charging for I/O, or else programs could cheat and overload the I/O system to reduce their memory requirements. As with memory, it is inappropriate to prevent a program from doing I/O if nobody else is using the I/O channel. Hence, one can submit low priority requests for I/O or memory; these get fulfilled only when there are no higher priority requests.

There are three priority levels ("low", "standard", "high"). Low priority leases have zero cost, but are preemptable on short or no notice, so apps will usually request this type of resource level only when they are out of drams (Geo: or if they use it for soft/expendable state). The other two levels each have a different fixed cost. If the price were not fixed, the app would have trouble planning its consumption, especially if the price goes up during a lease.

There are three main calls in the memory lease interface:

CreateMemoryLease Creates a lease. Specifies upper and lower bound on satisfactory number of pages, as well as the lease duration and optional flags.
WriteMemoryLease Allows modification of the lease (such as increasing/reducing amount of memory or duration).
TransferMemoryLease Allows independently issued leases to be consolidated into a single lease object.

The most complex functionality is the support for lease extensions and the transfer of state from one lease to another.

Some refinements: