Paging Scheme in Operating System | OS Tutorials

Most virtual memory systems use a technique called paging, since a process can be viewed as consisting of pages numbered from 0 onwards. Each page is of size s bytes. The memory of the computer system is viewed as consisting of page frames, where a page frame is a memory area that has the same size as a page.

Paging Scheme

Page frames are numbered from 0 to nf-1, such that $nf \cross s$ is the size of the memory. The physical address space consists of addresses from 0 to $nf \cross s$. At any moment, a page frame may be free, or it may contain a page of some process. Each logical address used in a process is considered to be a pair (p_i, b_i), where p is a page number, and b is an offset in p_i. 0≤b_i, s. The size of a page is chosen to be a power of 2.

Structure of a Page Table Entry

The address generated by the CPU consists of two parts:

The exact layout of an entry is highly machine dependable but the kind of information present is roughly the same from machine to machine. A typical page table entry is shown in Figure 2.

• The most important field is the page frame number. The goal of the page mapping is to output this value.
• Present/Absent bit: If this bit is 1, the entry is valid and can be used. If it is 0, the virtual page to which the entry belongs is not currently in memory. Accessing a page table entry with this bit set to 0 causes a page fault.
• Protection bit: It tells what kind of access is permitted. Generally, it contains 1 bit; since 0 is for read/write and 1 for read-only, we also consider 3 bits, one bit each for enabling reading, writing, and executing the page.
• Modified bit: It keeps track of page usage. This bit has a value when the OS decides to reclaim a page frame.
• If the page in it has been modified “dirty” it must be written back to the disk.
• If it has not been modified “clean” it can just be abandoned, since the disk copy is still valid.
• The bit is sometimes called a dirty bit, since it reflects the page’s state.
• Referenced bit: is set whenever a page is referenced either for reading or writing. Its value helps the OS to choose a page to discard when a page fault occurs.
• Finally, the last bit allows caching to be disabled for the page. This feature is important for pages that map onto device registers rather than memory.

Page Table Structure

The basic mechanism for reading a word from memory involves the translation of a virtual, or logical address, consisting of page number and offset, into a physical address consisting of frame number and offset using a page table. Because the page table is of variable length, depending on the size of the process, we cannot hold it in registers. Instead, it must be in main memory to be accessed.

Address Translation in a Paging System

• Figure 3 suggests a hardware implementation. When a particular process is running, a register holds the starting address of the page table for that process.
• The page number of a virtual address is used to index that table and look up the corresponding frame number.
• This is combined with the offset portion of the virtual address to produce the desired real addresses.
• Typically, the page number field is longer than the frame number field (n > m).

• In most systems, there is one page table per process. But each process can occupy a huge amount of virtual memory.
• Most virtual memory schemes store page tables in virtual memory rather than real memory.
• If the capacity of physical memory is “m” and the size of each page is “p”, then the number of frames in the physical memory will be $f = \frac{m}{p}$
• The number of frames in the physical memory and the number of pages in the logical memory are identical.

Advantages of Paging Scheme

• Since paging itself is a form of dynamic relocation. Every logical address is bound by the paging hardware to some physical address.
• When we use a paging scheme, we have no external fragmentation. Any free frame can be allocated to a process that needs it. We may have some internal fragmentation.

Frames are allocated as units. If the memory requirements of a process do not happen to fall on page boundaries, the last frame allocated may not be full.

Hardware Support for Paging

• The hardware implementation of the page table can be done in several different ways. We can implement the page table as a set of dedicated registers.
• Use of registers for the page table is satisfactory if the page table is reasonably small. The page table is kept in main memory, and a page table base register (PTBR) points to it.
• The problem with this approach is the time required to access a user memory location.
• If we want to access location i, we must first index it in the page table using the PTBR offset by the page number for i.
• We obtain the frame number by this, which is further combined with the page offset to produce the actual address.
• With this scheme, two memory accesses are needed to access a byte (one for the page table and one for the byte). Thus, memory access is slowed by a factor of 2. This delay would not be considerable.

Two-Level Paging System

• Figure 4 shows an example of a two-level scheme typical for use with a 32-bit address.
• If we assume byte-level addressing and 4 k-byte (2¹²) pages, then the 4 G bytes (2³²) virtual address space is composed of 2²⁰ pages.
• If each of these pages is mapped by a 4-byte page table entry, we can create a user page table composed of 2³⁰ PTEs, requiring 4 M bytes (2²²) bytes.
• This huge page table occupying 2¹⁰ pages can be kept in virtual memory and mapped by a root page table with 2¹⁰ PTEs occupying 4 k bytes (2¹²) of main memory.

Hardware for Address Translation in Two-Level Paging System

• Figure 5 shows the steps involved in address translation for this scheme. The root page always remains in main memory.
• The first 10 bits of a virtual address are used to index into the root page to find a PTE (Page Table Entry) for a page of the user page table.
• If that page is not in main memory, a page fault occurs; if that page is in main memory, then the next 10 bits of the virtual address are used to index into the user PTE page to find the PTE for the page that is referenced by the virtual address.

• Both ‘m’ and ‘p’ are usually an integer power of 2, thus resulting in ‘f’ being also an integer.
• The page’s size is similar to the frame size and is defined by the hardware, and it varies according to the architecture of the computer system.
• For the convenience of mapping, if the size of the logical address space is 2^m and the page size is 2ⁿ units, then the high-order m-n units of the logical address designate the page number, and the n-lower-order units designate the page offset.

Why are Page Sizes Always Power of Two?

Since there is a problem in the paging scheme: how does the compiler generate a 2d address? As we know, the compiler can generate only a 1-D address in binary form. Then how is it possible to separate this address into two components ‘p’ and ‘d’?

To solve this problem, we take the size of pages as an integral power of 2, such as 32, 64, … 1K, 2K, etc., because the single binary address can be shown to be the same as a 2d array; i.e., the high-order units correspond to ‘p’ and lower-order units correspond to ‘d’, which is stated earlier. It generates only a single binary address, but it can be interpreted as a 2d address. This helps in separating ‘p’ from the logical address and translating it to ‘f’, and then concatenating the same ‘d’ to achieve the physical address.