Applying the Framework
-
-
- We adjusted the cost function on the basis that the system’s maximum utilization is maximum utilization by our algorithm. That is O(log n) times the optimal algorithm’s.
- We determined that a CPU’s “maximum utilization” is the smallest integral power of 2 larger than the highest load seen so far.
- We developed the Enhanced PVM Strategy. It places jobs online to greedily minimize cost.
Notes:
The original cost function took the form autilization, where 1 < a < 2. However, we interpret the competitive ratio to mean that we achieve performance equal to that of the optimal algorithm if given resources O(log n) larger. This means that our cost function should be aO(log n) * utilization. If we choose a correctly, this gives us nutilization as the appropriate cost function.
We had to adapt the model to correctly determine the maximum CPU load. Counting the number of jobs a typical CPU can handle while continuing to function gives us a maximum CPU load too large to be useful. For any reasonable load, the CPU cost would be negligible. To solve this problem, we took advantage of a doubling technique in the original theoretical proof. We adapted it to “discover” the maximum CPU load as the algorithm progresses. This did not change the competitive ratio.
The result: the Enhanced PVM Strategy. This strategy, developed with these changes and several other tweaks, is a new approach to job assignment on static systems. It takes advantage of the full power of the Cost-Benefit Framework theory.