Page 435 - DCAP103_Principle of operating system

Principles of Operating Systems

Notes 14.4.6 Virtual Address Space Representation
The virtual address space is divided into homogeneous, contiguous, page aligned areas
or regions. That is to say, each area consists of a run of consecutive pages with the same
protection and paging properties. The text segment and mapped files are examples of areas.
There can be holes in the virtual address space between the areas. Any memory reference to
a hole results in a fatal page fault. The page size is fixed, for example, 4 KB for the Pentium
and 8 KB for the Alpha. Starting with the Pentium, which supports page frames of 4 MB,
Linux can support jumbo page frames of 4 MB each. In addition, in a PAE (Physical Address
Extension) mode, which is used on certain 32 bit architecture to increase the process address
space beyond 4 GB, page sizes of 2 MB are supported. Each area is described in the kernel
by a vm_ area_ struct entry. All the vm_ area_ structs for a process are linked together in a
list sorted on virtual address so all the pages can be found. When the list gets too long (more
than 32 entries), a tree is created to speed up searching. The vm_ area_ struct entry lists
the area’s properties. These include the protection mode (e.g., read only or read/write), whether
it is pinned in memory (not pageable), and which direction it grows in (up for data segments,
down for stacks).

The vm_ area_ struct also records whether the area is private to the process or shared with one
or more other processes. After a fork, Linux makes a copy of the area list for the child process,
but sets up the parent and child to point to the same page tables. The areas are marked as
read/write, but the pages are marked as read only. If either process tries to write on a page,
a protection fault occurs and the kernel sees that the area is logically writable but the page is
not, so it gives the process a copy of the page and marks it read/write. This mechanism is how
copy on write is implemented.
The vm_ area_ struct also records whether the area has backing storage on disk assigned, and
if so, where. Text segments use the executable binary as backing storage and memory-mapped
files use the disk file as backing storage. Other areas, such as the stack, do not have backing
storage assigned until they have to be paged out.
A top-level memory descriptor, mm_ struct, gathers information about all virtual memory areas
belonging to an address space, information about the different segments — text, data, stack,
about users sharing this address space, etc. All vm_ area_ struct elements of an address space
can be accesses through its memory descriptor in two ways. First, they are organized in a linked
lists, ordered by virtual memory addresses. This way is useful when all virtual memory areas
need to be accessed, or when the kernel is searching to allocated a virtual memory region of
a specific size. In addition, the vm_ area_ struct entries are organized in a binary ‘’red-black’’
tree, a data structure optimized for fast lookups. This method is used when a specific virtual
memory needs to be accessed. By enabling access to elements of the process address space via
these two methods, Linux uses more state per process but allows different kernel operations to
use the access method which is more efficient for the task at hand.

14.4.7 Paging in Linux
Early UNIX systems relied on a swapper process to move entire processes between memory
and disk, whenever not all active processes could fit in the physical memory. Linux, as well as
other modern UNIX versions, no longer move entire processes. The main memory management
unit is a page and almost all memory management components, operate on a page granularity.
The swapping subsystem also operates on page granularity and is tightly coupled with the Page
Frame Reclaiming Algorithm, described later in this section.
The basic idea behind paging in Linux is simple: a process need not be entirely in memory in
order to run. All that is actually required is the user structure and the page tables. If these are

428 LOVELY PROFESSIONAL UNIVERSITY