The problem with compaction is that it's expensive, in terms of the context switches required and the amount of data that has to be moved. On the other hand, if context switches are going on and data are being moved for other reasons, such as for swapping, then combining swapping with compaction amortizes the overhead with just doing compaction.
Combining compaction and swapping trades off cost for completeness: compaction is cheaper than it would be if done alone, but it is incomplete because it can only be done when swapping occurs.
The working-set size should be small. Because there is no locality, the working set has to be roughly as big as the program to provide the usual paging characteristics for the process. However, a large working-set size punishes other processes that do exhibit locality of reference (by hogging up page frames), and it's better to penalize the process with poor locality than to penalize processes that are good citizens with respect to working set size.
2n units, where n is the number of bits in a virtual address.
Best, first, and worst fit are all free-list management policies based purely on block size, and can be implemented with a priority queue in ascending or descending order of block size.
Next fit is based not only on block size, but also on the location of the last allocated block (which is where the search for the next block begins). A queue of block sizes is inadequate for next fit because, first, the queue provides external references to only the head and tail of the queue. A ring provides better support as all entries in the ring are externally available. Second, the ring has to be organized by address rather than block size.
This page last modified on 21 August 2002.