Information Technology Reference
In-Depth Information
Figure 5. Execution Time as a Function of Processes' Total Size
are not full, and some shared memory can be
present, so the ratio between the number of page
faults is actually less than two.
Figure 5 shows the same time slices but with
more processes. This test was conducted using the
synthetic benchmark SYN8. It can be clearly seen
that the effect of increasing time slice damages
the execution time when processes for more than
one bin are present.
of swaps using each of the methods. First Fit sorts
the processes according to their shared size; hence
usually processes that share a portion of memory
will be in the same group. As was explained in
section 4.3 processes that share memory typi-
cally have the same number of shared pages. As
a result, they will be in adjacent positions in the
sorted list and probably will be put in the same
group. Therefore, less page faults will occur.
Best-Fit cannot guarantee this quality; hence, the
performance will not be as good as the First-Fit
performance. The higher number of page faults
causes a longer execution time as can be seen in
Figure 6b.
the bin packing approximations
There are more than a few approximations for
the Bin-Packing optimal solution. Some of them
have been mentioned in section 3. Figure 6a and
Figure 6b compare two of these approximations.
The First-Fit Approximation (Also known as the
greedy approximation) is described in section 4.1.
The Best-FitApproximation finds for each process
the most unfilled bin and put the process in it.
When there is almost no shared memory, the
performance of both of the methods will be almost
the same. However, when a significant amount
of shared memory is allocated, the First-Fit ap-
proach outperforms the Best-Fit approach. The
benchmark that was used in Figures 6a and 6b is
SYNSHARED. Figure 6a compares the number
priority implementation evaluation
The priority can be implemented by another ap-
proximation which first determines how many
bins should be. Next, it sorts the processes by
their priority and finally, it fills the bins in a
Round-Robin manner. This method can scatter
the higher priority processes (and the lower
priority processes) among the bins, more or less
equally. However, the shared memory handling
requires a sorting by the shared size; hence, if
there are many processes with shared memory
Search WWH ::




Custom Search