Paging

Paging allows the physical address space of a process to be noncontiguous. It avoids the external fragmentation and
there is no need for compaction.

Fragmentation problem affects the backing store (disk) of the main memory where processes are swapped in or out.
The compaction is not possible due to the slow access speed of the backing store. The paging method solves this problem
by storing chunks of memory in the backing store.

The paging is supported by paging hardware, but recently paging is done both by operating system and hardware,
especially on 64-bit microprocessors.

Basic implementation of Paging

The physical memory is broken into fixed-sized blocks called frames and logical memory is broken into blocks of
the same size called.pages

When a process is executed, its pages are loaded into available memory frames from file or backing store. The
backing store is also divided into blocks of the same size as frames. Every process contains its own page table. Not all
pages are sent to physical memory, only a few pages called working set are loaded into the physical memory or
frames.

Virtual Address and Physical Address
Virtual Address and Physical Address

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

Page Table
Page Table

The size of the page is a power of 2, varying between 512 bytes to 16 MB per page, depending on computer
architecture.

Virtual Address Translation

The page contains logical address spaces, hence, the logical address space must be translated into a page number
and page offset.

Suppose the virtual address is 16-bit address and page size is 512 bytes. Then:

Virtual address = (page_number * maximum_offset_value ) + offset_value

maximum_offset_value = 512 bytes
offset value = log2 (512) = 9 bits
page_number = 16 - 9 = 7 bits

The virtual address higher order 7 bit is used for the page number and lower order 9 bit is reserved for offset_value.

Example:

The 16 bit virtual address is split into page number and offset value.

0000011 000000110 = (page_number, offset) = (3, 6)

Therefore, memory address location = 3 * 512 + 6 = 1536 + 6 = 1542

For 16-bit physical memory address, the higher order 7 bits represents frame number (f) and the offset value (d) is
same for the physical address as the virtual address.

Virtual Address Space and Physical Address Space With Paging
Virtual Address Space and Physical Address Space With Paging

Example:

00000100 00010000 = (frame_number, offset_value) = (4, 16)

physical memory location = [(frame_number * maximum_offset_value) + offset_value]

Therefore, frame memory address location = 4 * 512 + 16 = 2048 + 16 = 2064

The physical address must equal to or greater than the virtual memory. If there are n pages then at least n frames are required. Each page requires only one frame. The mapping is hidden from the users. The address mapping is done using address-translation hardware.

Page Table

We alreadty know that a page table is indexed on page numbers. In its simplest form, a page table contains the
frame numbers with the offset value gives the physical address and its location in page frame.

You will learn more about the page table in the next article.

Internal Fragmentation vs. Page size

There is no external fragmentation because any free frame is allocated to a process in execution. But we there may
be internal fragmentation.

For example, if page size = 2048 bytes
process size = 72766 bytes need 72766/2048 = 35 pages + 1086 bytes

The process will be allocated 36 frames for 35 pages, resulting in an excess of 2048 – 1086 = 0962 bytes wasted
space. Smaller page size means less internal fragmentation, however, page table entries increases leading to more
page table overheads.

The page size in recent years have increases between 4 KB to 8 KB and some system support larger pages. This is
due to the larger main memory sizes. The larger page table entries have two advantages – less disk I/O and less page
table entry overheads.

Example:
Solaris uses 4 KB and 8 KB pages.

Frame Table

When the process is executed, the pages are allocated frames. The operating system keeps track of physical
memory by listing free frames, frames not available, number of frames and so on. It does that with the help of a data
structure called the frame table.

Frame Table
Frame Table

The frame table has one entry for each page frame. The entry indicates whether the frame is free or allocated, if allocated, then the process and the page number.

References

The University of Texas () Virtual Memory, Available at: http://www.cs.utexas.edu/users/witchel/372/lectures/15.VirtualMemory.pdf (Accessed: 5/23/2019).

Abraham Silberschatz, Peter B. Galvin, Greg Gagne (July 29, 2008) Operating System Concepts, 8 edition edn., : Wiley.

Skip to content