As we have seen in the previous section, if jobs do not execute with high average efficiency, the mean response times obtained using scheduling algorithms that make allocation decisions based only on are quite high when compared with a scheduling algorithm that makes no use of job characteristics. This is because jobs are being allocated processors that they are not able to use effectively. In this section, we consider scheduling policies which only use information about a job's efficiency.
Various policies are considered by using different values of to allocate processing power according to the efficiency with which a job executes. Positive values of will allocate more processors to jobs with higher efficiency while negative values allocate more processors to jobs with low efficiency (an obviously bad approach). Since under our workload model the efficiency of each job is characterized by , we set and use:
The graph in Figure 5 plots the mean response time against different values (representing different scheduling policies) and shows results for = 1 and 5. ( yields such a pronounced v-shape that it is not included because it hides the distinction between and .) This graph shows that as increases, in both positive and negative directions, the mean response time also increases. These experiments were conducted using and and a low target load (30%). Even under this light load we find that with performance degrades significantly for and . We use this light load to demonstrate the general shape of the response time curves since at higher loads the differences in mean response times for the various algorithms change drastically (i.e., the v-shape becomes more pronounced more quickly). Under this scheme, positive values imply that more processors are given to jobs with higher efficiency. Significantly increasing the number of processors allocated to efficient jobs, while improving the degree to which processors are efficiently utilized, does not improve mean response time. This is because jobs that might potentially take a short amount of time to execute can become stuck behind jobs that take a long time to execute.
Figure 5: Mean response time versus scheduling policy ( );
Note that the mean response time obtained when is relatively close to that obtained when . In fact in most cases it yields mean response times that are statistically equal to those obtained with . Because the and values are so similar we now more closely examine these algorithms and also consider another point on the spectrum of algorithms ( ).
Table 2 contains the mean response times and 90% confidence intervals for = 0, 0.5, and 1.0 for workloads with = 1, 5, and 30 and ranges of effective efficiency of 1-50%, 1-99%, and 50-99%. The column labelled ``%Impr'' gives the percent by which the mean response time of is reduced if is used. (A negative value indicates the mean response time has increased, however, these negative differences can not be considered to be statistically significant.) Each experiment was run using an arrival rate that produces observed loads of approximately 90%. Interestingly, when average efficiency is relatively low, the algorithm obtained when using produces mean response times that are lower than those obtained when or .
Table 2: Comparison of mean response times for different policies based on efficiency
We believe that with too many processors are allocated to jobs that are not capable of utilizing them effectively. Because of the nature of how determines the efficiency of each job we expect that the improved mean response times obtained for are more indicative of how to schedule using than how to schedule using other characteristics of a job's efficiency. (For example, we expect that if was used might perform better than .) However, these results do demonstrate that a characteristic of each job's efficiency, in this case, can be used to make processor allocation decisions and produce mean response times that are statistically lower than an equipartition strategy. However, these differences are quite small.