Paging

Relocation

Special memory management hardware relocates memory accesses as they are made (as with the base and limit registers). The difference is that where as base-limit registers map a process's virtual memory to a contiguous are in physical memory. Paging creates a non-contiguous mapping, as we mentioned.

Protection (& sharing)

Using paging in this way, processes are automatically protected from each other, since they do not share address space, and therefore cannot access one another's memory. If two processes wish to share an area of memory, it is usually possible to map frames from two different processes' virtual memory into the same area of physical memory. Otherwise, if a particular frame has not been mapped into the virtual address space of a process, there is simply no way it can get at it.

For example, there is no way that process 1 can access frame #5 (which is part of process 2's virtual memory) in the example, below:

Sharing a page

On the other hand, both processes have access to frame #6. Note, though, that process 1 sees this shared frame as page #3, while process 2 sees it as page #4---it's mapped to a different location in their virtual address spaces.

Paging systems can be very flexible: generally they let any page in a particular process's virtual address space map to any frame in memory (or on disk).

Resizing processes

What if process 1 (in the example above) wishes to grow? With paging, simply allocate a new frame (or frames) from physical memory, and map it to the next page(s) in process 1's virtual memory.

Fragmentation

It should be clear by now that (external) fragmentation is no longer a problem in paging systems. The memory does get fragmented; processes' pages just get mapped to frames all over physical memory. So it's not a problem.

We do have the problem, though, of internal fragmentation. The pages are all of the same fixed size, a power of two, typically between 512bytes and 4K. Say a process needs 65537 bytes to run in. Say the page size is 1K. The process would be allocated 65 pages (66560 bytes), leading to the last 1023 bytes of the last page being wasted.

This is an extreme example (with the process using only one byte of its last frame). At the other extreme, a process might use all of its last page, and no memory would be wasted due to internal fragmentation. In the average case, half a page is wasted per process (more correctly, per virtual segment), in a paged memory system.

Not enough physical memory

This was the problem that paging was really invented to solve. The solution is that not all of a process's pages need be mapped to frames in memory. Some of them may be on disk. This is often known as a paged virtual memory system.

Pages which are on disk rather than in memory are marked by the MMU as 'absent'.

When a process attempts to access an address in a page which is not mapped on to a frame, the memory access is bound to fail. The MMU notices that the page is marked as 'absent' and causes a page fault, which causes a trap to the OS (rather like an interrupt). The OS reads in a page from the disk into a frame in physical memory, and maps the process's page to the new frame, then restarts the process's thread exactly at the instruction which caused the fault. The process need not know that anything untoward happened.

Where the virtual memory is larger than the physical memory, pages must occasionally be evicted from memory, to make way for other pages being brought in. A 'page replacement algorithm', decides which pages will not be used for a while and should be swapped out.

last updated 27 February 1998