[top |
prev |
next]
Isolation with Flexibility:
A Resource Management Framework for Central Servers
David G. Sullivan,
Margo I. Seltzer
Division of Engineering and Applied Sciences
Harvard University, Cambridge, MA 02138
{sullivan,margo}@eecs.harvard.edu
3. Isolation with Greater Flexibility
Currencies, like all mechanisms for providing isolation, necessarily
impose limits on the flexibility with which resource allocations can
be modified. In the following sections, we demonstrate that currencies
enforce both upper and lower limits on resource allocations. We also
describe the mechanisms that we have developed to safely overcome
these limits so that applications can obtain allocations that better
meet their differing and dynamically changing needs.
3.1 Problem: Currencies Impose Upper Limits
When a resource principal is funded by a currency other than the root
currency, its resource rights can usually be increased by giving it
extra tickets from that currency. 2 For example,
in Figure 1, task2's resource
rights could be boosted by giving it 200 bob tickets rather
than 100. However, doubling the tickets held by task2 does not
double its resource rights; rather, task2 goes from having
one-third of the bob currency's overall resource rights (a base
value of 33) to having one-half of those rights (a base value of
50). This smaller increase reflects the fact that issuing additional
bob tickets decreases their value. No matter how many currency
tickets a resource principal receives, the resource rights imparted by
those tickets cannot exceed the overall rights given to the currency
itself. This upper limit is essential to providing isolation. Without
it, the resource rights of principals funded by other currencies could
be reduced.
Despite the need for the upper limits imposed by currencies, these
limits may often be unnecessarily restrictive. This is especially true
on central servers, because the large number of resource principals
that a server must accommodate makes it difficult for a single
allocation policy to adequately address their different and
dynamically changing resource needs. Instead, some simple policy for
ensuring fairness is likely to be used, such as giving users equal
resource rights to divide among their applications, or allocating
resource shares based on how much a user has paid.
3.2 Solution: Ticket Exchanges
Because certain resources may be more important than others to the
performance of an application, applications may benefit from giving up
a fraction of their resource rights for one resource in order to
receive a larger share of another resource. We have therefore
developed a mechanism called ticket exchanges that allows applications
to take advantage of their differing resource needs by bartering with
each other over resource-specific tickets. For example, a
CPU-intensive application could exchange some of its disk tickets for
some of the CPU tickets of an I/O-intensive application.
While ticket exchanges allow principals to obtain additional resource
rights, they do so without compromising the isolation properties of
the lottery-scheduling framework. As the scenario depicted in
Figure 3
illustrates, only the resource rights of principals participating in
an exchange are affected by it; the resource rights of
non-participants remain the same.
Ticket exchanges are not, however, guaranteed to preserve the actual
resource shares that non-participants received before the
exchange. Because the principals involved in an exchange typically
make greater use of the resource for which they obtain extra tickets
than the principal who traded the tickets away, resource contention
will likely increase. As a result, non-participants who previously
received larger resource shares than their tickets guaranteed may see
those shares reduced. For example, if a CPU-intensive process trades
some of its disk tickets to a process that regularly accesses the
disk, those previously inactive disk tickets will suddenly become
active, and the disk tickets of other processes accessing the disk may
decline in value. 3
However, principals should always receive at least the minimal shares
to which their tickets entitle them.
Ticket exchanges and currencies complement each other. Exchanges allow
for greater flexibility in the face of the upper limits imposed by
currencies, while currencies insulate processes from the malicious use
of exchanges. For example, a process could fork off children that use
exchanges to give the parent process all of their tickets. With
currencies, however, this tactic would only affect the resource rights
of tasks funded by the same currency as the malicious process.
Figure 3: Ticket Exchanges Insulate Non-Participants. Tasks A
and B exchange tickets. Task C is unaffected, because it still has
one-third of the total of each ticket type.
3.2.1 Determining and Coordinating Exchanges. Ticket exchanges enable
applications to coordinate with each other in ways that are mutually
beneficial and that may increase the overall efficiency of the
system. Various levels of sophistication could be employed by
applications to determine what types of exchanges they are willing to
make and at what rates of exchange.
Certain types of resource principals may primarily need extra tickets
for one particular resource. For example, consider two Web sites that
are virtually hosted on the same server. Site A has a small number of
frequently accessed files that it could keep in memory if it had
additional memory tickets for its currency. Site B has a uniformly
accessed working set that is too large to fit in memory; it would
benefit from giving up some of its currency's memory tickets for some
of A's disk tickets.
Applications could also apply economic and decision-theoretic models
to determine, based on information about their performance (such as
how often they are scheduled and how many page faults they incur) and
the current state of the system, when to initiate an exchange and at
what rate. This determination could be made by the application process
itself, or by a separate resource negotiator process that monitors the
relevant variables and initiates exchanges on the application's
behalf. Resource negotiators are similar to the application managers
proposed by Waldspurger [Wal95].
Applications are free to cancel exchanges in which they are
involved. This allows them to take a trial-and-error approach,
experimenting with exchange rates until they achieve an acceptable
level of performance and adapting their resource usage over time.
Applications or their negotiators initiate exchanges by sending the
appropriate information to a central dealer. The dealer maintains
queues of outstanding exchange proposals, attempts to match up
complementary requests, and carries out the resulting exchanges. If an
exchange request cannot be immediately satisfied, the dealer returns a
message that includes any proposals with conflicting exchange rates
(e.g., process A requests 20 CPU tickets for 10 memory tickets, while
process B requests 10 memory tickets for 10 CPU tickets). In this way,
an application can decide whether to modify its proposed exchange rate
and try again for a compromise deal. In environments where isolation
is less important, the dealer could be modified to carry out exchanges
that processes propose on the processes themselves (e.g., to take away
20 CPU tickets from a process and give it 20 memory tickets in
return), giving an approach equivalent to the one suggested by
Waldspurger (see Section 2.2).
Future research is needed to develop negotiators suitable for a wide
variety of applications and environments. Among the questions that
still need to be addressed are: How can a negotiator determine what
exchanges are beneficial to its associated process? When should a
negotiator accept a trade less desirable than the one it proposed?
Will a system involving dynamic ticket exchanges be stable (i.e., how
can oscillatory behavior be avoided)? Can general-purpose negotiators
be written that avoid the need to craft one for each application? In
addition, the central dealer must be designed to deal fairly with
requests that have complementary but differing exchange rates.
3.2.2 Carrying Out an Exchange. Once a complementary set of
exchange requests is found, the funding of the resource principals
involved must be modified to reflect the exchange. In a
non-hierarchical system with only a base currency, this could be
accomplished by directly modifying the number of tickets that the
principals hold for the resources involved. However, the presence of
non-base currencies complicates matters, because the base value of
their tickets can change over time, whereas tickets used in exchanges
should have a constant value.
To address this problem, we issue four tickets directly from the base
currency: two for the amounts being exchanged, and two negatively
valued tickets for the opposite amounts. For example, if task A trades
disk tickets with a base value of 50 for some of task B's memory
tickets with a base value of 20, then A is given 20 base-currency
memory tickets and -50 base-currency disk tickets, and B is given 50
base-currency disk tickets and -20 base-currency memory
tickets. Because scheduling and allocation decisions are based on the
total base value of a principal's backing tickets, the negative
tickets reduce the principals' resource rights by the amount they have
traded away. And because principals cannot manipulate their own
backing tickets, exchanged tickets cannot be misused (e.g., to reduce
another currency's allocations). If a principal's tickets for a
resource are temporarily deactivated (see footnote 3),
the funding it
has obtained through exchanges for that resource is temporarily
transferred to the principal's other funders to preserve
isolation.
An exchange is undone if one of the exchanging principals exits,
cancels the exchange, or loses the resource rights that it traded
away. This last scenario can occur if the tickets funding the
principal decrease in value to the point that their base value is less
than the value of the tickets that the principal gave away. In such
cases, the principal's total base value for that resource becomes
negative, and the exchange must be revoked.
3.3 Problem: Currencies Impose Lower Limits
Currencies can also impose lower limits on resource rights. These
limits materialize when only one of the resource principals funded by
a currency is actively competing for a resource. In such
circumstances, that principal receives all of the currency's resource
rights, no matter how few tickets have been used to fund it.
As a result, currencies make it difficult for lottery scheduling to
support the semantics of the nice utility found on conventional UNIX
systems. For example, a user running a CPU-intensive job may reduce
its CPU funding as a favor to other users. But if the other tasks
funded by the same currency are all idle, the CPU-intensive job will
still get the currency's full CPU share (Fig. 4,
top). The user would presumably be allowed to decrease the number of
tickets backing the user currency itself, but then other jobs funded
by that currency would be adversely affected when they became
runnable.
Figure 4: Currencies Impose Lower Limits. The user
bob tries to lower the priority of hog, a CPU-intensive
process, by giving it only 10 tickets (top). However, if
task2 becomes idle, hog will still receive all of
bob's resource rights. One solution is to fund hog
directly from the base currency (bottom).
3.4 Solution: Limited Permission to Issue Base-Currency Tickets
While upper limits are necessary for providing isolation, lower limits
are an undesirable side-effect of isolation. These limits could be
overcome by funding CPU-intensive applications directly from the base
currency (Fig. 4, bottom). However, for reasons of
security, currency access controls (Section 2.3)
would ordinarily prevent unprivileged users from issuing
base-currency tickets.
To circumvent this restriction, our framework allows a user to issue
base-currency tickets as long as the total value of currencies owned
by that user never exceeds some upper bound. In this way, users can
give up a small amount of their currencies' funding and then issue
that same amount from the base currency to fund resource-intensive
jobs. This approach leaves the user's total resource rights unchanged
(preserving the isolation of other users), and it allows jobs to run
at a reduced priority without crippling the rest of the user's
applications. Section 4.6 describes how we
implement this policy.
____________________
2.
This is not always the case. If a resource principal is the sole
recipient of a currency's tickets, giving it more tickets from the
currency does not affect its resource rights.
3.
When a resource principal temporarily leaves the competition for a
resource (e.g., when a thread is not performing I/O), its tickets are
deactivated. As a result, the resource rights of other principals
funded by the same currency or currencies are temporarily increased
until the principal reenters the competition and its tickets are
reactivated.
[top |
prev |
next]