Previous Table of Contents Next


Case Study 19.1 The CPU time taken by two text-formatting programs, called LaTeX and troff, was measured using synthetic files of various sizes and complexity levels. Six factors, each with two levels were chosen for the study. The first two factors were the text-formatting programs and size of the files. The remaining four factors were number of equations, floats, tables, and footnotes in the file. The assignment of factors and their levels is shown in Table 19.6. A 26–1 fractional factorial design with the generator polynomial I = BCDEF was used. The largest effects and interactions, computed by the sign table method, are shown in Table 19.7. The following conclusions can be reached from these results:
1.  Over 90% of the variation is explained by the three factors Bytes, Program, and Equations and a second-order interaction.
TABLE 19.6 Factors and Levels for Text Formatting Programs

Symbol Factor Level –1 Level +1

A Program LaTeX troff
B Bytes 2100 25,000
C Equations 0 10
D Floats 0 10
E Tables 0 10
F Footnotes 0 10

TABLE 19.7 Effects for the Text Formatting Programs

Symbol Factor Effect Percentage of
Variation

B Bytes 12.0 39.4
A Program 9.4 24.4
C Equations 7.5 15.6
AC Program × Equations 7.2 14.4
E Tables 3.5 3.4
F Footnotes 1.6 0.7

2.  The text file sizes (in bytes) in these experiments were significantly different, making the effect more than that of the text-formatting programs being compared.
3.  The high percentage of variation explained by the “program × Equation” interaction indicates that the choice of the text-formatting program depends upon the number of equations in the text. If we consider only the programs and equations in isolation, the relative amount of CPU time for various combinations is shown in Table 19.8. This shows that troff takes too much CPU time if there are equations in the text.
4.  The “Program × Bytes” interaction is low. This indicates that changing the file size affects both programs in a similar manner.
TABLE 19.8 CPU Time for Various Program × Equation Combinations

Number of Equations
Program –1(0) 1(10)

–1(LaTeX) –9.7 –9.1
1(troff) –5.3 24.1

5.  If possible, the experiments should be redone with a reduced range of file sizes so that the programs rather than the workload come out as the most significant factor. Alternately, the number of levels of file sizes should be increased.
Case Study 19.2 This case study concerns the design of a scheduler for a WANG VS system. The system allows word processing, data processing, and background data processing. The designers wanted to find out what type of scheduler should be used for each of these three environments and whether the same scheduler could be used for all three classes of jobs. The scheduling policies that were studied had five parameters:
  Whether the scheduler is preemptive or not.
  Whether the time slice (quantum size) is small or large.
  Whether to have one or two queues. The second queue would have a lower priority by assigning it a smaller time slice.
  How many job classes to keep and into what ready queue to place the task when it becomes runable due to events, such as I/O completion, intertask message received, system locks release, and so on.
  Whether any jobs waiting for too long should be given preference to improve fairness.

The five factors and their level assignments are summarized in Table 19.9. A 25–1 fractional factorial design with 16 experiments was used to study the relative importance of these factors. The design was based on the generator I = ABCDE or, equivalently, E = ABCD. The level assignments for the five factors in the 16 experiment and the measured throughput using three different synthetic workloads is shown in Table 19.10. In the table, columns TW, TI, and TB denote throughput for word processing, interactive data processing, and batch data processing, respectively.

The mean effects and the percentage of variation explained for each the three workloads are listed in Table 19.11. The following conclusions can be drawn from this table:

  The ideal parameter setting for the three workloads is different. Looking at the percentage of variation explained, the effects that impact word processing throughput TW are A (Preemption), B (Time slice), and AB. For interactive jobs, important factors are E (Fairness), A (preemption), BE, and B (Time slice). For background jobs, the important factors are A (Preemption), AB, B (Time slice), and E (Fairness). Thus, it might be worthwhile to have different policies for different classes of workloads.
TABLE 19.9 Factors and Levels In the Scheduler Design Study

Symbol Factor Level –1 Level 1

A Preemption No Yes
B Time slice Small Large
C Queue assignment One queue Two queues
D Requeueing Two queues Five queues
E Fairness Off On


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.