Virtual Memory
The RAM in a computer system is a limited resource, with all of the running processes on the system competing for a share of it. When there are multiple applications running on a system, it is not unusual for the total amount of memory allocated by all processes to exceed the amount of RAM on the system.
An operating system that supports virtual memory allows a process to allocate and use more memory than the amount of RAM installed on the system; that is, the address space of a process is not constrained by the amount of physical RAM. With virtual memory, the operating system uses a backing store on secondary storage, such as the hard disk, to keep portions of a process address space that will not fit into RAM. The CPU, however, can still access only addresses that are resident in RAM, so the operating system must swap data between the disk backing store and RAM in response to memory accesses made by the process as it runs.
At a particular time, a process may only need to reference a small subset of the total memory that has been allocated. This is known as the working set of the process and, as long as the operating system keeps this working set in RAM, there is negligible impact on the execution speed imposed by virtual memory. The working set is a dynamic entity, and it changes based on the data that is actively being used as the process runs. If a process accesses a memory address that is not resident in RAM, the corresponding data is read from the backing store on disk and brought into RAM. If there is no free RAM available to load the data into, some of the existing data in RAM will need to be swapped out to disk beforehand, thus freeing up physical RAM.
Virtual memory is handled by the operating system. A user process plays no part in its implementation, and is unaware that portions of its address space are not in physical RAM or that data it has accessed needed to be swapped into main memory.
A consequence of virtual memory is that the addresses used by a process do not correspond to addresses in physical RAM. This is apparent if you consider that a process's address space may be larger than the amount of RAM on the system. Therefore, the addresses that a process reads from and writes to need to be translated from the process's virtual address space into a physical RAM address. Since every memory access requires an address translation, this is performed by the CPU to minimize the impact on execution speed.
Operating systems typically use a scheme known as “paging” to implement virtual to physical address translation. Under a paged memory scheme, physical memory is divided into fixed-sized blocks known as page frames. Most operating systems, including both Mac OS X and iOS, use a frame size of 4096 bytes. Similarly, the virtual address space of each process is divided into fixed-size blocks, known as pages. The number of bytes per page is always the same as the number of bytes per frame. Each page in a process can then be mapped to a frame in physical memory, as shown in Figure 1-5.
Figure 1-5. The pages in a process's address space can be mapped to any page frames in memory.
Another advantage of virtual memory is it allows a buffer that occupies a contiguous range of pages in the process's virtual address space to be spread over a number of discontiguous frames in physical memory, as seen in Figure 1-5. This solves the problem of fragmentation of physical memory, since a process's memory allocation can be spread over several physical memory segments and is not limited to the size of the longest contiguous group of physical page frames.
As part of launching a process, the operating system creates a table to map addresses between the process's virtual address space and their corresponding physical address. This is known as a “page table.” Conceptually, the page table contains an entry for each page in the process's address space containing the address of the physical page frame to which each page is mapped. A page table entry may also contain access control bits that the CPU uses to determine whether the page is read-only and a bit that indicates whether the page is resident in memory or has been swapped out to the backing store. Figure 1-6 describes the steps that the CPU performs to translate a virtual address to a physical address.
Figure 1-6. Virtual to physical address translation for a 32-bit address with a page size of 4096 bytes (12 bits)
If a process accesses a memory address that the CPU cannot translate into a physical address, an error known as a “page fault” occurs. Page faults are handled by the operating system, running at privileged execution level. The operating system determines whether the fault occurred because the address was not in the process's address space, in which case the process has attempted to access an invalid address and is terminated. If the fault occurred because the page containing the address has been swapped out to the backing store, the operating system performs the following steps:
- A frame in physical memory is allocated to hold the requested page; if no free frames are available in memory, an existing frame is swapped out to the backing store to make room.
- The requested page is read from the backing store into memory.
- The page table for the process is updated so that the requested page is mapped to the allocated frame.
- Control returns to the calling process.
The calling process re-executes the instruction that caused the fault, but this time around, the CPU finds a mapping for the requested page in the page table and the instruction completes successfully.
An understanding of virtual memory and paging is essential for kernel developers. Although the kernel handles requests on behalf of user applications, it also has an address space of its own, so parameters often need to be copied or mapped from a process's address space to the kernel's address space. In addition, kernel code that interfaces to hardware devices often needs to obtain the physical address of memory. Consider a disk driver that is handling a read request for a user process. The destination for the data read from disk is a buffer that resides in the address space of the user process. As with the CPU, the hardware controlled by the driver can write only to an address in main memory, and not to a destination in the backing store. Therefore, to handle the read request, the driver needs to ensure that the user buffer is swapped into main memory and remains in main memory for the duration of the read operation. Finally, the driver needs to translate the address of the destination buffer from a virtual address into a physical address that the hardware can access. We describe this in further detail in Chapter 6.
It's worth noting that although iOS provides a page table for each process, it does not support a backing store. At first, it may seem that this completely defeats the purpose of paging. However, it serves two very important purposes. First, it provides each process with the view that it has sole access to memory. Second, it avoids problems caused by the fragmentation of physical memory.