Slide 8 of 47
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.
