|
This chapter solves the scheduling challenges from the application scenarios that were presented in Chapter 3 . Each application scenario, on its own, does not constitute a strong motivation for the flexibility provided by HLS, since a monolithic scheduler could be constructed that has equivalent functionality and (most likely) is more efficient. The motivation for HLS comes from the lack of overlap among the scenarios--if the scheduling hierarchy for any of the scenarios was used to run any of the others, it would not be possible for applications to obtain the desired scheduling properties. In principle, a monolithic scheduler that provides the scheduling properties of all three hierarchies could be developed.1 However, such a scheduler could easily turn into an engineering nightmare, and it would still be inflexible in face of the need for a new kind of scheduler, such as a gang scheduler.
Since no real-time scheduling is required, this scenario can be scheduled by a homogeneous hierarchy like the one shown in Figure 7.1 .Each scheduler in the hierarchy is a proportional share scheduler. At least PS1, PS5, and PS7 must be instances of a multiprocessor PS scheduler; for example, a multiprocessor version of BVT [20] or SFQ [27]. The scheduler should be augmented with a tunable processor affinity heuristic such as the one described by Chandra et al. [15]. The heuristic should be tuned for strong processor affinity to minimize the number of times threads migrate between processors, since throughput is a first-order concern in a web server. Also, a long scheduling quantum should be selected in order to allow most requests to complete within a single time quantum, minimizing the number of nonessential context switches.
|
In the hierarchy depicted in Figure 7.1, virtual server 1 (VS1), which is scheduled by PS2, receives a guarantee of PS 0.4, or 20% of the capacity of the two-processor machine. Since its share is less than 1, only one virtual processor is necessary to provide the CPU to PS2. However, since virtual server 2 (VS2) may be idle at times, it is advantageous to give VS1 two virtual processors in order to allow it to take advantage of both processors when VS2 is using less than its share. Rather than giving VS1 two guarantees of type PS 0.2, it is given a single guarantee of PS 0.4 to allow it to run on the same processor as often as possible. Within VS1, schedulers PS3 and PS4 each receive an equal share of the processor time allocated to VS1. VS2 receives guarantees of PS 1.0 and PS 0.6, or 80% of the total capacity of the machine. It allocates guarantees of PS 1.0 and PS 0.4 to PS7, and PS 0.2 to PS6.
A home computer must avoid starving time-sharing applications while supporting two classes of real-time applications. First, those that require an absolute share of the processor at a specific granularity since they provide little or no value when they miss deadlines. Second, those whose value degrades gracefully when they receive less CPU time than their full requirement.
A scheduling hierarchy that can meet the needs of these three classes of applications is shown in Figure 7.2.RES provides a basic, hard CPU reservation to real-time thread T1. Threads T2 and T3 are both part of the same application, and are being scheduled by a rate monotonic scheduler that has been given a CPU reservation (through join scheduler J2, which turns the hard, basic reservation into a soft, basic reservation) whose parameters have been calculated using the method from Section 6.1 .
The reservation scheduler gives a reservation to the start-time fair queuing scheduler SFQ through join scheduler J1. J1 schedules SFQ during its CPU reservation and also during any time left idle by RES, resulting in a soft, basic CPU reservation of 10 ms / 20 ms. Theorem 5.5 shows how to convert a soft, basic CPU reservation into a proportional share guarantee with bounded error. This hierarchy makes use of this theorem to convert the soft CPU reservation into a guarantee that the SFQ scheduler can use. The SFQ scheduler, in turn, provides bounded-error guarantees to the time sharing scheduler and two gracefully degrading real-time threads T7 and T8, which would represent applications such as those that perform voice recognition or display stored video.
The parameters of the proportional share guarantees provided by SFQ were calculated using Equation 5.2 . The guarantee received by the time sharing scheduler is PSBE 0.3 35, which means that its minimum guaranteed share of the CPU over a long time period is 0.3, and that during no time interval will its allocation fall more than 35 ms behind what it “should” have received. This corresponds to maximum starvation period of roughly 100 ms for time-sharing applications, which is acceptable.
The differing admission policies provided by RES and SFQ can be seen by looking at what happens when extra threads request service. Since 90% of RES’s overall capacity is reserved (10% for T1, 30% for J2, and 50% for J1), a new request for a CPU reservation with utilization more than 10% would have to be rejected. However, since SFQ is acting as a best-effort scheduler for applications whose performance gracefully degrades, it can grant any number of new requests. Of course, each new request that it grants will change the guarantees received by T7, T8, and TS1. The time-sharing scheduler TS1 can also admit any number of new threads, since it makes no guarantees. Time sharing scheduler TS2 represents a scheduler that is running an untrusted application that has created threads T5 and T6. The reason for adding an extra level to the scheduling hierarchy for an untrusted application is that no matter how many threads it creates, they will all be scheduled by TS2, which receives only a single thread’s worth of CPU allocation from TS1.
A scheduling hierarchy that could be used to solve the scheduling challenges posed by this scenario on a two-processor machine is depicted in Figure 7.3.In this example only two users are logged in to the terminal server. The relevant features of this hierarchy are:
A refinement of this scheduling hierarchy would be to dynamically change the weights assigned to TS1 and TS2 in order to grant each user a constant share over the entire scheduling hierarchy. For example, at the same time that user 1 is granted a CPU reservation with utilization 10%, the amount of time guaranteed to her time-sharing scheduler would be decreased by 10%. This would eliminate a performance isolation loophole in the hierarchy in Figure 7.3 that allows users with real-time threads to receive more CPU time than users who only have time sharing threads.
Using three example scenarios, this chapter has shown that HLS can support combinations of applications with complex scheduling requirements, as well as enforcing isolation between resource principals at multiple levels.
