Memory Paging

What is it and how it works?

Paging is one of the memory management schemes in which a computer can store and retrieve data from a secondary storage device for use in main memory. In the paging memory management scheme, the operating system retrieves data from a secondary storage device into blocks of a same size called pages. The main advantage of paging over memory segmentation is that it allows the physical address space of a process to be non-contiguous.

The basic method to implement paging is to divide the physical memory into fixed size blocks called frames and divide the logical memory into blocks of the same size called pages. When a process is to be executed, its pages are loaded in any frame of the secondary storage memory. This is divided into blocks of fixed size of the same size as the frames in memory.



Paging Hardware

The page size (like the page frame) is defined by hardware. The size of a page is typically a power of 2, varying between 512 B and 16 MB per page, depending on the architecture of the computer. Selecting a power of 2 as the page size makes the translation of a logical address to a page number and page offset somewhat easy. If the size of the logical address space is 2^m and the page size 2^n address units (bytes or words), then the m-n higher order bits of the logical address designate the page number, and the n bits of lower order designate the page offset.

Any address generated by the CPU is divided into two parts: a page number (p) and a page offset (d). The page number is used as an index on a page table. The page table contains the base addresses of each page in the physical memory. This base address is combined with the page offset to define the physical memory address that is sent to the memory unit.



Page Table

The page table is a data structure used by the virtual memory system, in an operating system to store the relationship between a virtual address in memory and physical addresses.

• Structure of a Page table
  The page table is stored in main memory, and to access it, 2 structures are required, which are known as:
  
  
  
  • PTBR: Page Table Base Register, which points to the page table.
  
  
  • PTLR: Page Table Length Register, whose function is to indicate the size of the page.
  
  
  
  

Now, each address, either data or instruction requires 2 accesses to memory, one for the page table and another for the instruction.

With respect to size, what happens if the page table is very large?: An immediate response is that those spaces that are not small, but not large enough to accommodate a process, would be lost. That is why there are techniques for large tables of pages, which are:

• Hierarchical Pagination: It is characterized by dividing the logical space into multiple page tables.

• Use of Hash: In general, the common address space is greater than 32 bits. The virtual page number is used as the key of a hash page table. This page table contains a list of the elements associated with the same record, so the virtual page number in the list is compared by searching for a match, if it is found, the page frame is extracted.

• Use of Table of inverted pages: The special particularity of this method is that it decreases the memory waste, but it increases the search time and to deal with this, it uses the hash table.

 

PDF File: Memory Paging - Vega, Ernesto