Orthogonal Segmentation and Paging

The use of fixed size pages in a virtual memory has many advantages for operating systems, in particular with respect to the management of both the main memory and the secondary memory. On the other hand segmentation, which is based on variable length logical elements of programs (e.g. arrays, procedures), has protection advantages and maps onto the natural units with which a compiler works. There have been several attempts to combine these approaches and thus gain the advantages of both. For example in Multics and many later systems a segment is decomposed into pages. This works reasonably well for very large segments, but when used for the small segments into which a program or file typically decomposes (records, procedures, arrays) it leads to an unacceptable loss of memory through internal fragmentation and to overheads arising from superfluous page tables, etc. For this reason various alternative proposals were made in the 1960s and 1970s for combining segmentation and paging, e.g. that a page should be decomposed into segments (which leads to difficulties with large segments) or that multiple page sizes should be supported (which complicates memory organization).

In 1980 Prof. Keedy proposed an alternative model in which pages and segments are treated entirely orthogonally. This solves the problems mentioned above. The idea is described in:

Keedy, J.L. "Paging and Small Segments: A Memory Management Model", Proc. IFIP80, 8th World Computer Congress, Melbourne 1980, pp. 337-342.

This idea has been implemented in the Monads-PC and also has some similarities with the memory management model which was later used in some Intel processors. The basic idea is shown in the following diagram.

An address in a program consists of a segment number and an offset from the start of the segment, as in conventional segmentation schemes. This effective program address is evaluated by using the segment number as an index into a segment table. Each entry in the segment table describes an addressable segment. An entry contains the segment's access rights (e.g. read, write, execute), a segment length (which is compared with the offset in the effective program address to ensure that the address is not out of bounds) and a start address. The latter is the virtual address of the start of the segment.

An effective virtual address is formed by adding this virtual start address to the offset in segment. The result is then treated just like a virtual address in a conventional paging scheme. In the original paper the address translation unit (shown in the diagram as a black box) is described in terms of a conventional indexed page table, but in the Monads-PC it is implemented using an inverted page table technique, because the Monads-PC has very large virtual addresses.

The main advantage of this scheme is that segments and pages are orthogonal to each other: a segment need not begin on a page boundary and a page need not begin on a segment boundary. Consequently the scheme can effectively handle both small and large pages without a more significant loss to internal fragmentation than occurs in a conventional paging scheme (i.e. an average of half a page per program) while preserving all the advantages of paging and of segmentation.