1. Would it be more valuable to add swapping to an operating system that used paged virtual memory system or to a pure segmented virtual memory system? Explain your answer.

   ---

   Swapping moves processes between primary and secondary memory, usually starting and ending with primary memory.

   Paged virtual memory implements a form of swapping, but it works on pages rather than entire processes. Pure segmented virtual memory has no inherent mechanism for swapping. Such a mechanism would be useful, for example, in dealing with idle processes. In a paging virtual memory, the idle process will eventually have its pages moved to secondary memory as part of the normal paging process. In a pure segmented virtual memory, the idle process would have to be explicitly recognized as being idle and then explicitly swapped out.

   ---

2. Suppose you are designing an operating system and want to use random page replacement in conjunction with a working-set estimator. In terms of minimizing paging rates, and just considering random replacement and the working-set estimator, is it better if your estimator over-estimates or under-estimates the size of a process's working set? Explain your answer.

   ---

   Random page replacement throws out any page in primary memory; the problem with random page replacement is that it could throw out a page that's in a process's working set.

   If the working-set estimator under-estimated a process's working set, it's almost certain that a randomly selected page will be missed as soon as it ejected. On the other hand, if the estimator over-estimated working set sizes, some of the pages associated with each process will be expendable, in the sense that they haven't been used recently and probably won't be used in the near future. In this case, random page replacement is less likely to eject an active page than it would be if the working set size was under-estimated, so over-estimating is preferred.

   ---

3. A colleague of yours is designing a virtual memory system in software and wants to know your opinion of the following optimization: rather than use a reference bit and a modified bit per page frame, just use a reference bit. After all, if a page was modified, it was obviously referenced, so one bit should be enough. What do you say to your colleague? Explain yourself in enough detail so that your colleague will see the wisdom of your opinion.

   ---

   It's not a good optimization. Although you do save a bit per page frame, you loose the ability to determine if a page has been written to or just read, which means every ejected page has to be written to secondary memory in case it's been changed since it was paged in. This doubles the paging overhead on only-read pages, makes paging more expensive than it needs to be.

   ---

4. Explain the difference between internal and external fragmentation. Suppose you are designing an operating system and can minimize either internal or external fragmentation, but not both. Which do you chose?

   ---

   Internal fragmentation occurs when a process address space is not a multiple of the page size; the extra, unused space in the last page is evidence of internal fragmentation. External fragmentation occurs when a changing population of variably-sized segments result in holes of unusable size in physical memory.

   In general, it is more important to control external fragmentation than internal fragmentation. Internal fragmentation wastes a fraction of a page per process, and even if it were reclaimed, that wasted space could not be used by another process. External fragmentation could waste up to half of physical memory or more, and that wasted space, if reclaimed, could be put to use by other processes.

   ---

This page last modified on 6 March 2000.