What do you mean by virtual memory? Discuss how paging helps in implementing virtual memory.

It is useful for three reasons. A program bigger than RAM can still run. Many programs can stay in memory together. The programmer need not care where the program is loaded.

How paging helps

In paging, the virtual address space is cut into equal fixed-size blocks called pages. The main memory is cut into blocks of the same size called frames. Any page can be placed in any free frame. So there is no external fragmentation, and finding space is easy. Only the pages in use are brought into memory, and this is called demand paging.

Address translation

A virtual address has two parts: the page number and the offset inside the page. A table called the page table is kept in main memory. It has one entry per page. Each entry holds the frame number, a valid (present) bit, a modified bit and protection bits. The page number selects the entry. If the valid bit is 1, the frame number is joined with the offset to form the physical address.

Virtual address        Page table            Physical address
+-----------+--------+                      +-----------+--------+
| page no.  | offset |                      | frame no. | offset |
+-----------+--------+                      +-----------+--------+
      |         |         +-------------+        ^           ^
      +-------->+-------->| valid|frame |--------+           |
                |         +-------------+                    |
                +--------------------------------------------+

For example, take a page size of 4 KB, so the offset has 12 bits. In a 32-bit virtual address the page number has 20 bits. The virtual address $\text{0x00003ABC}$ has page number 3 and offset $\text{0xABC}$. If page 3 sits in frame 7, then the physical address is $\text{0x00007ABC}$.

Page fault

If the valid bit is 0, the page is not in memory and a page fault occurs. The operating system finds the page on disk and picks a free frame. If no frame is free, it removes a victim page using a replacement rule such as FIFO or LRU. A modified victim is first written back to disk. The new page is loaded, the page table is updated and the instruction is restarted.

Speeding up with a TLB

Reading the page table costs one extra memory access for every reference. A small, fast cache of recent translations, called the translation lookaside buffer (TLB), avoids most of these extra accesses.

Merits and limits

Paging gives a large virtual space, easy memory sharing and protection, and good memory use. Its costs are the space taken by page tables and the time lost when page faults are frequent. Too many faults cause thrashing, where the system spends more time moving pages than doing useful work.