[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
2. Securely Managing Multiple Resources
2.1 The Original Framework
The resource management framework developed for lottery scheduling
[Wal94, Wal95, Wal96] is based on two key
abstractions, tickets and currencies. Tickets are used
to encapsulate resource rights. Resource principals receive resource
rights that are proportional to the number of tickets that they hold
for a resource; changing the number of tickets held by a resource
principal automatically leads to a change in its resource rights.
Tickets are issued by currencies, which allow resource principals to
be grouped together and isolated from each other. Principals funded by
a currency share the resource rights allotted to that currency;
currencies thus enable hierarchical resource management.
Each currency effectively maintains its own exchange rate with a
central base currency, and tickets from different currencies can be
compared by determining their value with respect to the base currency
(their base value). The more tickets a currency issues, the less each
ticket is worth with respect to the base currency, and their total
base value can never exceed the value of the tickets used to back the
currency itself.
The sample currency hierarchy shown in Figure 1
illustrates these concepts. The bob currency is funded by 100
of the 400 base-currency tickets, and it thus receives rights to
one-quarter of the resource. These rights are divided up by the tasks
funded by bob; for example, task3 holds 200 of the 300
bob tickets, and it thus receives rights to two-thirds of
bob's quarter share, or one-sixth of the total resource
rights. In other words, task3's 200 bob tickets have a
base value of approximately 67 (two thirds of 100). If task2 or
task3 forks off more tasks, causing the bob currency to
issue more tickets, the value of its tickets will decrease, because
its resource rights will be shared by a larger number of
tasks. However, the resource rights of processes funded by other
currencies will not be affected.
Figure 1. A sample resource hierarchy in which currencies
provide isolation between the tasks of different users. The base
values of the tasks' backing tickets are shown in italics.
While a lottery-scheduling resource hierarchy typically has a
tree-shaped structure like the one shown in Figure
1, it can more generally take the form of any directed acyclic
graph. The lottery-scheduling framework thus supports a greater
variety of configurations than most other, recently proposed schemes
for hierarchical resource management (see Section 6).
For example, on a system like the one depicted in
Figure 1, in which each user's applications are
funded by a currency specific to that user, two or more users could
pool their resources to support a single application that all of them
are using (the system developed by Banga et al.
[Ban99] also allows this).
2.2 Resource-Specific Tickets
Although prior implementations of lottery scheduling have focused
exclusively on single resources (primarily the CPU), the original
lottery-scheduling framework was designed to support multiple
resources. Waldspurger [Wal95] considered two
approaches to implementing a multi-resource system. In the first
approach, tickets can be applied to any resource, allowing resource
principals to shift tickets from one resource to another as needed,
while in the second, tickets are resource-specific. Waldspurger
favored the former approach because of its greater flexibility and
simplicity. However, allowing principals to devote tickets to
resources as they see fit violates the insulation properties of
currencies, because it can lead to changes in the total number of
tickets applied toward a given resource
[Sul99a].
We therefore chose to use resource-specific tickets. To avoid the
overhead of maintaining a separate currency configuration for each
resource, we extend currencies to encompass all of the resources being
managed. Concretely, this means that most pieces of currency state are
maintained as arrays indexed by resource type. Similarly, many
currency-related operations take a parameter that specifies the
resource type.
2.3 Currency Brokers
For the lottery-scheduling framework to be secure in a multi-user
setting, a system of access controls are needed. We encapsulate these
controls in a broker associated with each currency. A broker stores
the owner and group of the user who created the currency, along with a
UNIX-style mode specifying who may perform various operations on the
currency. Before these operations are carried out, the broker verifies
that the current thread belongs to a user with the requisite
permissions.
Like UNIX file modes, currency modes include three sets of
permissions: one for the currency's owner, one for the currency's
group, and one for all others. In a given set of permissions, the f
bit indicates whether a user is allowed to fund the currency; the c
bit indicates whether a user can "change" the currency by
removing some of its funding or destroying it entirely; and the i bit
indicates if a user is allowed to issue or revoke the currency's own
tickets. This fci collection of bits is comparable to the rwx
combination in UNIX file modes.
Table 1 provides more specifics about the permission
checks that brokers perform. In most cases, superusers are allowed to
override the ordinary permissions checks. If an attempt to fund a
currency would lead to a cycle in the currency graph, the attempt is
rejected.
Table 1. Permission checks performed by brokers
|
Operation
|
Permission check
|
|
create a currency
|
The caller must match both the user id and group id specified for the
new currency. (Note that the user and group ids must be
specified--and therefore checked--because superusers can create
currencies that have ids other than their own.)
|
|
destroy a currency
|
The appropriate c (change) bit must be set in the currency's
mode.
|
|
fund currency A with tickets issued by currency B
|
The appropriate f (fund) bit in A's mode and the appropriate
i (issue) bit in B's mode must be set.
|
|
take tickets issued by currency B away from currency A
|
Either the appropriate c (change) bit in A's mode
or the appropriate i (issue) bit in B's mode must be set.
|
2.4 Hard and Soft Resource Shares
The standard lottery-scheduling framework was primarily designed to
support soft resource shares whose absolute value may change over time
as principals enter and leave the competition for the
resource. However, Waldspurger and Weihl pointed out that absolute,
hard resource shares can be supported using the same framework by
fixing the total number of tickets issued by the system
[Wal96]. In particular, they proposed specifying
hard shares by issuing tickets from a hard currency that maintains a
fixed exchange rate with the base currency. When this hard currency
issues additional tickets, some of the funding of other,
"soft" currencies is transferred to the hard currency so
that its exchange rate can be maintained.
In our framework, we take a slightly different approach based on the
notion of hard and soft tickets, and we allow resource principals to
obtain hard shares from any currency. Under our approach, tickets
issued by a currency are ordinarily soft tickets that specify soft
shares of the currency's resource rights. However, when a currency
issues a hard ticket to specify a fixed percentage of its resource
rights, a separate currency is created and used to fund the currency's
soft tickets (Fig. 2). The number of hard tickets
used to fund this soft-ticket currency is adjusted as needed to ensure
that the total number of the currency's hard tickets remains fixed.
Figure 2. Offering Hard Shares of a Currency's Resource
Rights. The bob currency issues a hard ticket to task D
representing a fixed 20% (200/1000) of bob's resource rights.
As a result, a special currency (soft_tix) is created and used to fund
bob's soft tickets, isolating the hard tickets from changes in the
number of soft tickets. The funding given to the soft_tix currency is
adjusted as needed to ensure that the total number of hard tickets
issued by bob remains fixed at 1000.
Our approach requires no extra overhead in the common case of a
currency issuing only soft tickets, and yet it still allows hard
tickets to be issued by any currency. Users could use hard tickets to
give an application a fixed percentage of their resource rights, or to
specify hierarchical reservations in which absolute shares from the
base currency are divided into hard subshares. For a hard ticket to
represent a fixed-share reservation of the actual resource, all paths
from the root currency to the ticket must involve only hard
tickets.
____________________
1.
Note that even the base currency's soft tickets have a base value that
can change over time as the number of its hard tickets changes.
[top |
prev |
next]