MC78 Homework 3 (Fall 1998)

Due: October 12, 1998

Consider parallel parking along downtown streets. In some parts of town, there are white lines painted on the pavement, perpendicular to the curb and spaced at regular intervals. Each pair of consecutive lines marks one parking space. In other parts of town, there are no painted lines, and so each driver simply parks wherever there is room. Which kind of fragmentation is each part of town subject to? Explain. (Fragmentation of tail lights doesn't count.)
Do exercise 9.9 from pages 332-333.
Programs written in Scheme (and other Lisp-family languages) often process lists constructed from two-component structures known as pairs or cons-cells. One component (the car) points to an element of the list, while the other component (the cdr) points to the next pair in the list.
```
+---+---+     +---+---+     +---+---+
| * | *----- >| * | *------>| * | *----> ...
+-|-+---+     +-|-+---+     +-|-+---+
  |             |             |
  V             V             V
element1      element2      element3
```
Note that in the above diagram, element1, element2, etc. may themselves be arbitrary objects, including pairs.
The Scheme system has the freedom to change the location in memory of a pair, provided that it appropriately updates all the pointers pointing to that pair to reflect the new address. One possible strategy would be for the system to try to relocate pairs so that the car pointer usually points to another location on the same page of memory. Another possible strategy would be to try to relocate pairs so that the cdr pointer usually points to another location on the same page. Which strategy is likely to have better performance in a demand-paged virtual memory system? Why?

Instructor: Max Hailperin