278
R. Hamers and S.-S. Jongmans
Fig. 13. Microbenchmarks on lisa: Ring
(blue), OOO (red), and OAO (yellow);
number of threads (x-axis) vs. scalability
relative to n = 2 (y-axis)
Fig. 14. Whole-program benchmarks on
vm2: Chess (left) and NPB (right); play
time (x-axis, left) and program (x-axis,
right) vs. monitoring slowdown (y-axis)
Fig. 15. Whole-program benchmarks on lisa: CG, FT, IS, and MG (from left to right);
number of threads (x-axis) vs. monitoring slowdown (y-axis)
– Ring (blue) scales sub-linearly. This is because at any point in time, only one
worker thread contends for monitor access (the current receiver or sender;
the others are blocked, waiting for incoming channels to become non-empty).
– OOO (red) scales linearly, stabilizing around a constant factor of 1.4. This
is because the number of branches in the monitor’s internal state machine
grows linearly in the number of worker threads. Thus, the cost of using the
monitor grows proportionately, but the factor is constant.
– OAO (yellow) scales super-linearly, getting progressively worse as the number
of worker threads increases. This is because all worker threads contend for
monitor access all the time, and the number of branches in the monitor’s
state machine increases linearly.
To conclude, Ring (which exercises sequential composition) enjoys excellent scalability, while OOO (which exercises alternative composition) enjoys decent scalability, even under the adversarial microbenchmark conditions. Scalability of
OAO (parallel composition) can be improved; we discuss one avenue in Sect. 7.