Mastering Algorithms with C

Linked List Example: Frame Management

An interesting application of linked lists is found in the way some systems support virtual memory. Virtual memory is a mapping of address space that allows a process (a running program) to execute without being completely in physical memory, the real memory of the system. One advantage of this is that a process can make use of an address space that is much larger than that which the physical memory of the system would allow otherwise. Another advantage is that multiple processes can share the memory of the system while running concurrently.

A process running in virtual memory deals with virtual addresses. These are addresses that seem like physical addresses to the process, but that the system must translate before using. Address translation takes place using a page table and is fast due to dedicated hardware. Each process has its own page table that maps pages of its virtual address space to frames in physical memory. When a process references a particular virtual address, the appropriate entry in its page table is inspected to determine in which physical frame the page resides (see Figure 5.5). When a process references a virtual address not yet in a frame, a page fault occurs and a frame is allocated in physical memory. Why pages of a process are removed from physical memory is another matter. One occasion for removing a page, however, is when a page is accessed infrequently relative to other pages and its frame is needed elsewhere. ...