Segmentation with Paging: MULTICS

Segmentation with Paging: MULTICS

If the segments are large, it may be inconvenient, or even impossible, to keep them in main memory in their entirety. This leads to the idea of paging them, so that only those pages that are really required have to be around. Many significant systems have supported paged segments. In this section we will explain the first one: MULTICS. In the next one we will describe a more recent one: the Intel Pentium. 

MULTICS ran on the Honeywell 6000 machines and their descendants and provided each program with a virtual memory of up to 218  segments (more than 250,000), each of which could be up to 65,536 (36-bit) words long. To implement this, the MULTICS designers chose to treat each segment as a virtual memory and to page it, combining the advantages of paging (uniform page size and not having 

Development of checkerboarding

to keep the whole segment in memory if only part of it is being used) with the advantages of segmentation (ease of programming, modularity, protection, sharing).

Each MULTICS program has a segment table, with one descriptor per segment. Since there are potentially more than a quarter of a million entries in the table, the segment table is itself a segment and is paged. A segment descriptor contains an indication of whether the segment is in main memory or not. If any part of the segment is in memory, the segment is considered to be in memory, and its page table will be in memory. If the segment is in memory, its descriptor includes an 18-bit pointer to its page table, as in Figure 2(a). Because physical addresses are 24 bits and pages are aligned on 64-byte boundaries (implying that the low-order 6 bits of page addresses are 000000), only 18 bits are required in the descriptor to store a page table address. The descriptor also includes the segment size, the protection bits, and a few other items. Figure 2(b) shows a MULTICS segment descriptor. The address of the segment in secondary memory is not in the  segment descriptor but in another table used by the segment fault handler.

Each segment is an ordinary virtual address space and is paged in the same way as the nonsegmented paged memory. The normal page size is 1024 words (although a few small segments used by MULTICS itself are not paged or are paged in units of 64 words to save physical memory). An address in MULTICS consists of two parts: the segment and the address within the segment. The address within the segment is further divided into a page number and a word within the page, as illustrated in Figure 3. When a memory reference occurs, the following algorithm is carried out.

The MULTICS virtual memory

1 . The segment number is used to find the segment descriptor.

2. A check is made to see if the segment's page table is in memory. If the page table is in memory, it is located. If it is not, a segment fault occurs. If there is a protection violation, a fault (trap) occurs. 

3 . The page table entry for the requested virtual page is examined. If the page itself is not in memory, a page fault is triggered. If it is in memory, the main memory address of the start of the page is extracted from the page table entry.

4. The offset is added to the page origin to give the main memory address where the word is located.

5 . The read or store finally takes place.

A 34-bit MULTICS virtual address

This process is shown in Figure 4. For simplicity, the fact that the descriptor segment is itself paged has been omitted. What actually happens is that a register (the descriptor base register) is used to locate the descriptor segment's page table, which, in turn, points to the pages of the descriptor segment. Once the descriptor for the required segment has been found, the addressing proceeds as shown in Figure 4.

Conversion of a two-part MULTICS address into a main memory address

As you have no doubt guessed by now, if the preceding algorithm were actually carried out by the operating system on every instruction, programs would not run very fast. In fact, the MULTICS hardware includes a 16-word highspeed TLB that can search all its entries in parallel for a given key. It is shown in Figure 5. When an address is presented to the computer, the addressing hardware first checks to see if the virtual address is in the TLB. If so, it gets the page frame number directly from the TLB and forms the actual address of the referenced word without having to look in the descriptor segment or page table.

A simplified version of the MULTICS TLB

The addresses of the 16 most recently referenced pages are kept in the TLB . Programs whose working set is smaller than the TLB size will come to equilibrium with the addresses of the entire working set in the TLB and therefore will run efficiently. If the page is not in the TLB, the descriptor and page tables are really referenced to find the page frame address, and the TLB is updated to include this page, the least recently used page being thrown out. The age field keeps track of which entry is the least recently used. The reason that a TLB is used is for comparing the segment and page numbers of all the entries in parallel.


Tags

segments, virtual memory, page frame, multics, address space