[Home] [Tech Library]
2. Processor scheduling
This section describes initial market strategies for both sellers and buyers. In processor scheduling, we will term the time-seller (or agent for the seller) an auction house, and a time-buyer (or agent for a buyer) a bidder. A system may have any number of competing sellers.2.1. Auctioning processor time: the escalator algorithm
A standard approach to scheduling processes uses a "first-come, first-served" queue. A newly-ready process always joins the tail of the queue, and the processor always runs the process at the head of the queue. This ensures that each process will eventually run (regard- less of processor demand), guaranteeing what is known as non-starvation or fairness. This mechanism does not enable market trade-offs among the needs of different processes, how- ever. A natural approach to doing so is the "highest-bid, first-served" queue. This corresponds to auctioning time-slices, with the queue corresponding to an auction house. Naïvely applied, this would lead to disaster: if the market price of the processor stays above a process's posted bid, the process will never run, and hence never learn that it needs to raise its bid. This defines a central problem in auctioning processor time.2.1.1. Auction-house initial strategies
A basic question in an auction-based strategy is the nature of the auction: kinds include the double auction, English auction, Dutch auction, and first-price and second-price sealed-bid auctions [5,6]. In a double auction, sellers offer lower and lower prices while buyers offer higher and higher prices until they meet. In the familiar English auction, buyers bid higher and higher prices until the process plateaus; the seller accepts the highest bid. In a Dutch auction, a seller offers lower and lower prices until a buyer claims the item at the present price. In a first-price sealed-bid auction, fixed bids are submitted, and the highest is accepted; in a second-price sealed-bid auction, the highest is accepted, but the highest bidder pays the amount bid by the second-highest.These auction institutions have differing applicability to the sale of time slices. The double, English, and Dutch auctions (at least in naïve implementations) require that processes be active while bidding for the very processor they need in order to be active-a major problem. Sealed-bid auctions avoid this problem, but they fail to guarantee non-starvation: if the processor price remains above what a process has bid, it will never be scheduled-and if the process is never scheduled, it cannot raise its bid. Thus, auctioning processor time is a bit like trying to auction wakeup pills to a sleeping crowd.
The approach explored here will be a variant of a sealed-bid auction, but the choice between first- and second-price forms remains. In laboratory experiments with human bidders, second-price sealed-bid auctions are known to give results similar to those of English auctions, and both lead to efficient markets (as does the double auction) [5,6]. In the English auction, the winning bidder pays only slightly more than the second-highest bidder; a second-price sealed-bid auction yields a similar result directly. Dutch and first-price sealed-bid auctions lead to less efficient markets.
First-price sealed-bid auctions give an incentive to guess what the next-highest bid will be, and to bid just slightly more. This strategic guessing serves no useful purpose in a market system. Second-price auctions give an incentive to consider only the question: "At what given price would my best decision change from `buy' to `don't-buy'?" This is the price one should bid, since bidding any other price might result in buying (or not buying) when one should not. Estimating this price means estimating actual value, which serves a decidedly useful purpose in the market system.
We have selected a variant of a second-price, sealed-bid auction for our initial market strategy. It may be called an escalating-bid auction.
This system may be visualized as an auction house full of escalators (admittedly a strange image). A process enters the auction by placing a bid on one of the escalators-the greater the bid, the greater the initial height. Each escalator rises at a different rate, raising its bids at that rate. (A special stationary escalator holds fixed bids.) Together, the initial bid and escalation rate are a form of priority. A processor always runs the highest-bidding process. A house rule sets a maximum allowable initial bid-you can get on only at (say) the first five floors.
Each auction house owns or leases a processor, or a certain fraction of its operating time. Escalator data structures make the highest bid readily available (i.e., each escalator is a priority queue). Each non-stationary escalator is characterized by a rate of escalation, escalationRate, measured in currency units per time unit. At a time t, the value of a bid of zero initial value placed on an escalator at time timeOfBid is simply escalationRate * (t - timeOfBid). A non-zero initial bid of value initialBid is assigned a virtual bid-time, timeOfBid, equal to t - (initialBid/escalationRate), and entered accordingly. Thus, each non-stationary escalator is marked with a fixed escalationRate and holds a current list of bids, sorted in time- OfBid order. Each bid includes its timeOfBid, a suspended process, and access to an expense account. The stationary escalator is a special case; instead of a timeOfBid it records a fixed initialBid. (A negative initialBid is acceptable on a moving escalator. We assume that two idle processes are entered with zero bids on the stationary escalator to avoid accepting a negative bid-value; the first always stands ready to run, at the price set by the second.)
To place a bid on an escalator, one sends a suspended process, an initial bid, and access to an expense account from which the auction house is to withdraw money. When the bid is placed, the auction house immediately withdraws from the expense account enough funds to cover the worst-case cost of handling that bid.
At the beginning of each time slice, the auction house examines the top bid on each escalator, taking the highest bid among them (and promoting its follower) while noting the second-highest bid (taking into account the newly-promoted bid). It then charges the high bidder the amount of the second-highest bid, and gives the high bidder a slice of processor time. If the highest bidder's expense account fails to cover the (escalated) bid, however, it is removed without running, and a bid equaling the balance of its expense account is entered for this bidder on the stationary escalator.
The escalating-bid auction seems well suited to the processor scheduling problem. It avoids the sleeping-bidder problem and it ensures that a processor can accept a bid at any time-crucial, when the commodity to be sold is as perishable as time itself.
2.1.2. Bidder initial strategies
A sufficient initial strategy for a bidder is simply to place a zero bid on the fastest escalator backed by the bidder's own expense account. Note that, among initial-strategy bidders, the escalator algorithm reduces to a round-robin scheduler. In a slight variation, a negative initialBid can be placed to ensure a delay of at least (- initialBid/escalationRate) until the bidder next runs.2.1.3. Analysis
In an open system, where total processor capacity and demand will be responsive to market forces, the market price of time on a processor will be bounded. Accordingly, a bid placed on any non-stationary escalator will eventually grow large enough to ensure that it is accepted. Thus, non-starvation would be ensured.Where too much of the demand is unresponsive to price, other conditions are necessary to ensure non-starvation, such as limiting the maximum initial bid, maxInitialBid, to some fixed value (the "fifth floor") as suggested above. Consider a process Z with a bid on a moving escalator. Z will either run or have its bid escalated past maxInitialBid within a fixed time; at that time, only a finite number of other processes can have bids higher than Z's, and if Z is riding the fastest escalator, no new process can be scheduled to run ahead of it. Thus, the auction house guarantees non-starvation to any process that follows the strategy of always entering a bid on the fastest escalator.
The relationship among bids, prices, and rates of use is simple in certain illustrative cases. Assume a stable price for time-slices, equal to P, and an escalator that raises bids at a rate R per time slice; an object that repeatedly reschedules itself after running by placing a zero initial bid on this escalator will receive a fraction of the processor time roughly equal to R/P. Consider an auction house in which a fixed number of processes repeatedly run and reschedule themselves, placing bids with zero initial values and a fixed distribution across the various escalators; assume further that bids are numerous enough and uniform enough to make second-highest bids approximately equal to highest bids. There will then be a steady-state price for a time-slice (with small fluctuations); this price will equal the sum over the escalators of the number of bids on each times the amount of escalation during a time-slice. (This quantity equals the per-time-slice increase in the sum of the bids, and all the money bid is eventually spent on processor time.) Non-zero initial bids will have an effect roughly like that of different escalation rates, and fluctuating rates of bid-placement will cause fluctuations in processor price.
Given fluctuating prices (see Figure 1), faster escalation rates will result in higher average costs per time slice. If scheduled at random times, rapidly-escalating bids will strike the market-price line at nearly random times (random sampling would hold strictly if escalation were infinitely fast). As may be seen, slowly escalating bids are unable to strike the price line at the top of sharp price peaks; they are more likely to strike the down-side of price troughs. Figure 1 also illustrates how a strategy of re-bidding at zero on an escalator after every run will, on the average, use more time-slices during broad troughs than during broad peaks, yielding a cost per time slice that is lower than the average cost; conversely, bids placed on fast escalators will pay a higher than average cost.
The overhead of the escalator algorithm is modest and insensitive to the number of bids being escalated. Assume N is the number of bids on an escalator and M is the number of escalators. Placing or removing a bid is then an operation taking a time proportional to log(N), given a suitable choice of escalator data structure (a priority queue). Finding the highest and second-highest bids by searching the top bids is an operation taking a time proportional to M.
2.1.4. Variations
The simplest auction-house initial strategy provides a fixed set of escalators, as described; more complex strategies could create and delete escalators to suit bidder demand. Other extensions would allow bidding for multiple time-slices as a block (up to some maximum size), or enable refunding payment on unused portions of a time slice (and starting the next full time-slice early). Where multiple processors are equally accessible, a single auction house could serve them all. Finally, the owner of a processor could run an auction procedure for a fraction of the available time slices and an entirely different procedure (perhaps some form of futures market for real-time scheduling) in another.As described, the simplest bidder initial strategy is to schedule a zero bid on the fastest escalator. A more complex strategy might use a fast escalator only for fast service at a (likely) higher price, or slower escalators for slower service, at a (likely) lower price. A positive initial bid on a slow escalator can speed service while still giving better odds of running at a low price than does a bid on a fast escalator. Tasks of strictly limited value (which need not be completed) can be scheduled on the stationary escalator; they will run only if the price of processor time falls low enough. A regularly-scheduled rebidding agent can be used to implement a very broad class of strategies, taking into account new information from bid to bid.
There are several open issues in this approach to processor scheduling. These include finding procedures for:
- choosing maxInitialBid (where this parameter is needed),
- choosing the numbers and rates of escalators, and
- charging for bid-record storage.
2.2. Expense accounts
We have described initial market strategies for the relationship between owners and bidders; we also need strategies among bidders, to ensure that they can pay for processing time. Since bidders typically need processing time in order to satisfy external requests, the initial market strategy should follow the dynamic structure of relationships created by request messages from client objects to their consultants.When a client requests service from a consultant, we assume the client will pay to satisfy the request. We need an initial strategy that enables consultants to charge and clients to pay, all with a minimum of programmer attention (the following strategy does, however, require that objects distinguish between request and response messages). The initial strategy should itself provide neither profit nor loss, and hence should simply require that consultants charge for their operating costs, and that clients pay for them. This initial market strategy must (as always) interact smoothly with other strategies. The initial strategy must accommodate clients wishing to monitor charges or limit payments, and consultants wishing to charge less or more than their expenses (e.g., to promote a new service or to collect royalties).
The initial strategy is as follows: Each process draws operating expenses from its current expense account. A client includes access to its current expense account in each outgoing request. The consultant then uses this account as its current expense account while satisfying the request. This strategy is identical to the protocol specified in the Act 2 language [7] for passing sponsors. Like expense accounts, these give bounded access to processor time [8].
In a set of objects following this initial market strategy, all computation serving an external request will be paid for by the account contained in that request. Since no computation will be cut off while that account remains solvent, well-funded computations will be completed.
In variations on this strategy, a consultant may charge according to whatever policy it wishes, since it is free to draw funds from the incoming account and to use a different account to pay for its computation. If a consultant requires a minimum sum to complete a computation, it can ensure access to this sum by transferring it to a new account at the outset.
A client may limit its payments to a consultant by sending a new account with the request and placing a limited sum in that account. This is like a threshold pointer, in that the client limits its liability at the risk of cutting off valid computation.
A client may monitor its payments to a consultant by sending a shadow account which passes charges through to an actual account while remembering their sum. When the consultant finishes, the client recovers the record of the total charges and shuts down the shadow account. This enables clients to accumulate cost information to guide further requests.
 |
 |
[Home] [Tech Library]