Paging in Operating Systems

---

What is Paging?

---

Most virtual memory systems use a technique called paging. On any computer, there exists a set of memory addresses that programs can produce. When a program uses an instruction like MOV REG,1000, it does this to copy the contents of memory address 1000 to REG (or vice versa, depending on the computer). Addresses can be generated using indexing, base registers, segment registers, and other ways.

These program-generated addresses are called virtual addresses and form the virtual address space. On computers without virtual memory, the virtual address is put directly onto the memory bus and causes the physical memory word with the same address to be read or written. When virtual memory is used, the virtual addresses do not go directly to the memory bus. Instead, they go to an MMU (Memory Management Unit) that maps the virtual addresses onto the physical memory addresses as illustrated in Figure.

The Figure displays a fairly straightforward illustration of how this mapping functions. In this illustration, a computer that can produce 16-bit addresses from 0 to 64K is used. The virtual addresses are as follows. However, this computer only has 32 KB of physical memory, thus even if 64 KB applications can be created, they cannot be fully loaded and executed in memory. However, in order for components to be brought in when required, a complete copy of a program's core image, up to 64 KB, must be stored on the disk.

Pages are the smallest units used to break up the virtual address space. Page frames are the names for the equivalent elements in the physical memory. The size of the pages and page frames is constant. Although they are 4 KB in this example, real systems have employed pages that range in size from 512 bytes to 64 KB. We get 16 virtual pages and 8 page frames with 64 KB of virtual address space and 32 KB of real memory. The units of transfer between RAM and disk are always pages.

The number of the page frame corresponding to that virtual page is obtained by using the page number as an index into the page database. A trap is set off for the operating system if the Present/Absent bit is set to 0. If the bit is set to 1, the output register's high-order 3 bits are transferred with the 12-bit offset from the incoming virtual address along with the page frame number from the page table. They combine to provide a 15-bit physical address. The physical memory address is then transferred from the output register to the memory bus.

In order to locate the record for that virtual page, the virtual page number is utilized as an index into the page database. The page frame number, if any, can be obtained from the page table item. In place of the virtual page number, the page frame number is joined to the high-order end of the offset to provide a physical address that may be transferred to the memory.

Despite this simple description, two major issues must be faced: (i) The page table can be extremely large. and (ii) The mapping must be fast.

The simplest design (at least conceptually) is to have a single page table consisting of an array of fast hardware registers, with one entry for each virtual page, indexed by virtual page number, as shown in Fig. 4-11. When a process is started up, the operating system loads the registers with the process‘ page table, taken from a copy kept in main memory. During process execution, no more memory references are needed for the page table. The advantages of this method are that it is straightforward and requires no memory references during mapping. A disadvantage is that it is potentially expensive (if the page table is large). Having to load the full page table at every context switch hurts performance.

At the other extreme, the page table can be entirely in main memory. All the hardware needs then is a single register that points to the start of the page table. This design allows the memory map to be changed at a context switch by reloading one register. Of course, it has the disadvantage of requiring one or more memory references to read page table entries during the execution of each instruction. For this reason, this approach is rarely used in its most pure form, but below we will study some variations that have much better performance.

To get around the problem of having to store huge page tables in memory all the time, many computers use a multilevel page table. A simple example is shown in the following Figure. In Fig. (a) we have a 32-bit virtual address that is partitioned into a 10-bit PT1 field, a 10-bit PT2 field, and a 12-bit Offset field. Since offsets are 12 bits, pages are 4 KB. and there are a total of 220 of them.

The secret to the multilevel page table method is to avoid keeping all the page tables in memory all the time.

On the left we have the top-level page table, with 1024 entries, corresponding to the 10-bit PT1field. When a virtual address is presented to the MMU, it first extracts the PT1 field and uses this value as an index into the top-level page table. Each of these 1024 entries represents 4M because the entire 4-gigabyte (i.e.. 32-bit) virtual address space has been chopped into chunks of 1024 bytes.

---

What is Demand Paging?

---

The basic idea behind demand paging is that when a process is swapped in, its pages are not swapped in all at once. Rather they are swapped in only when the process needs them(On demand). This is termed a lazy swapper, although a pager is a more accurate term.

Initially, only those pages are loaded which will be required the process immediately.

The pages that are not moved into the memory, are marked as invalid in the page table. For an invalid entry, the rest of the table is empty. In the case of pages that are loaded in the memory, they are marked as valid along with the information about where to find the swapped-out page.

When the process requires any of the pages that are not loaded into the memory, a page fault trap is triggered, and the following steps are followed,

• The memory address which is requested by the process is first checked, to verify the request made by the process.
• If it's found to be invalid, the process is terminated.
• In case the request by the process is valid, a free frame is located, possibly from a free-frame list, where the required page will be moved.
• A new operation is scheduled to move the necessary page from the disk to the specified memory location. ( This will usually block the process on an I/O wait, allowing some other process to use the CPU in the meantime. )
• When the I/O operation is complete, the process's page table is updated with the new frame number and the invalid bit is changed to valid.
• The instruction that caused the page fault must now be restarted from the beginning.

There are cases when no pages are loaded into the memory initially, pages are only loaded when demanded by the process by generating page faults. This is called Pure Demand Paging.

The only major issue with Demand Paging is after a new page is loaded, the process starts execution from the beginning. It is not a big issue for small programs, but for larger programs, it affects performance drastically.

Happy Exploring!