Paging

Paging allows the physical address space of a process to be non-contiguous. 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.

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.

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.

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 already 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 increase 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.

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.