230 Part 2 ½ Regions of Computer Space Section 2 ½ Memory Hierarchies and Multiple Processes

users, it must reside in Mp, since there will not be enough space in Mps (processor state) to hold a large amount of mapping information. However, when a program is being executed, some part of the mapping information becomes part of the Mps (i.e., at least the Mp address of the rest of the map).

Random-access memories for Mp constrain the mapping by requiring linear addresses of the form Mp[0:p], since the mapping calculation must be economical (as it is performed with very high frequency). We would not consider a map structure which provides every word in Mv to be mapped into an arbitrary word in Mp, for this would require a map exactly the same size as Mv. With many programs in Mp, there would be little room for anything but maps. Similarly, the amount of processing in the calculation must be minimal. These two aspects highly constrain the mapping scheme.

Three major types of mapping functions have been used. In the first, the identity function, there is no map. The processor virtual address space is identical to the physical memory space. This mapping function is used primarily on stand-alone, dedicated computers.

The second type is frequently referred to as paging and is depicted in Fig. 4. In paging, the processor-generated address is divided into two fields, a page number and a displacement within page. The page number is used to index into a page table, from which the physical page number is retrieved. The physical page number can be either concatenated or added to the displacement to create the final physical address. This form of address map is called a linear map, since manipulation of the virtual address, such as adding an index, can cause the page number in the virtual address to increase, thus accessing a different physical page potentially without warning to the user. Note that p' may contain more than, fewer than, or exactly as many bits as p.

The third type of mapping function is two-dimensional and is termed segmentation. Two major forms of segmentation have been used: linear and symbolic. Figure 5 illustrates the linear mapping. The processor-generated virtual address is composed of three fields: the segment number, the page number, and the

displacement. The segment number is used to index into a segment table. The starting address (base) of the page table is coupled with the virtual page number as an index to retrieve the physical page number. The physical page number is then concatenated or added to the displacement to generate the final physical address. The virtual page number is compared to a limit field in the selected segment table entry as a check on whether the page number is within bounds for this segment. This provides some measure, of protection so that virtual address manipulations do not cross segment boundaries without warning the user. (Note that a similar bounds check could have been made on the displacement field in the paging function outlined in Fig. 4.)

However, it is still possible in linear segmentation to inadvertently cross a segment boundary if the proper value is added to the virtual address. Symbolic segmentation prevents segmentation boundary crossing by computations on the virtual address. Figure 6 depicts symbolic segmentation. The virtual address is a duple: a segment number and a displacement. The main difference between symbolic segmentation and the prior schemes is that the hardware enforces a boundary between the segment and displacement virtual address fields. Adding a number to the displacement in a virtual address calculation cannot modify the segment field.

Figure 7 illustrates one implementation of symbolic segmentation used on the Burroughs B5000. The instruction pointer