Separate Instruction and Data Spaces / Shared Pages

Separate Instruction and Data Spaces / Shared Pages

Separate Instruction and Data Spaces

The majority of computers have a single address space that holds both programs and data, as shown in Figure 1(a). If this address space is large enough, everything works fine. On the other hand, it is often too small, forcing programmers to stand on their heads to fit everything into the address space.

One address space

One solution, pioneered on the (16-bit) PDP-11, is to have separate address spaces for instructions (program text) and data, called I- space and D-space, respectively, as shown in Figure 1(b). Each address space runs from 0 to some maximum, usually 216 - 1 or 232 - 1. The linker must know when separate l- and D-spaces are being used, because when they are, the data are relocated to virtual address 0 instead of starting after the program.

With this design, both address spaces can be paged, independently from one another in a computer. Each one has its own page table, with its own mapping of virtual pages to physical page frames. When the hardware wants to fetch an instruction, it knows that it must use I-space and the I-space page table. Likewise, references to data must go through the D-space page table. Other than this distinction,
having separate I- and D-spaces does not introduce any special complications and it does double the available address space.

Shared Pages

Sharing is another design issue. In a large multiprogramming system, it is common for various users to be running the same program at the same time. It is clearly more efficient to share the pages, to avoid having two copies of the same page in memory at the same time. One problem is that not all pages are sharable. Particularly, pages that are read-only, such as program text, can be shared, but data pages cannot.

If separate I- and D-spaces are supported, it is relatively straightforward to share programs by having two or more processes use the same page table for their I-space but different page tables for their D-spaces. Normally in an implementation that supports sharing in this way, page tables are data structures independent of the process table. Each process then has two pointers in its process table: one to the I-space page table and one to the D-space page table, as shown in Figure 2. When the scheduler chooses a process to run, it uses these pointers to locate the appropriate page tables and sets up the MMU using them. Even without separate I- and D-spaces, processes can share programs (or sometimes, libraries), but the mechanism is more difficult.

Two processes sharing the same program sharing its page table

When two or more processes share some code, a problem takes place with the shared pages. Assume that processes A and B are both running the editor and sharing its pages. If the scheduler decides to remove A from memory, removing all its pages and filling the empty page frames with some other program will cause B to generate a large number of page faults to bring them back in again.

Likewise, when A terminates, it is important to be able to discover that the pages are still in use so that their disk space will not be freed by accident. Searching all the page tables to see if a page is shared is generally too expensive, so special data structures are required to keep track of shared pages, especially if the unit of sharing is the individual page (or run of pages), rather than an entire page table.

Sharing data is trickier than sharing code, but it is not impossible. Particularly, in UNIX, after a fork system call, the parent and child are required to share both program text and data. In a paged system, what is often done is to give each of these processes its own page table and have both of them point to the same set of pages. Thus no copying of pages is done at fork time. On the other hand, all the data pages are mapped into both processes as READ ONLY.

As long as both processes just read their data, without modifying it, this situation can continue. As soon as either process updates a memory word, the violation of the read-only protection causes a trap to the operating system. A copy is then made of the offending page so that each process now has its own private copy. Both copies are now set to READ-WRITE, so subsequent writes to either copy proceed without trapping. This strategy means that those pages that are never modified (including all the program pages) need not be copied. Only the data pages that are actually modified need to be copied. This approach, called copy on write, improves performance by reducing copying.


Tags

address space, virtual pages, system call, page frames