Demand Paging in Operating System

Demand paging in operating system is a fetch policy for a virtual memory that determines when a page should be brought into the main memory. In demand paging, a page is brought to the main memory only when demanded. Thus, we refer to it as demand paging.

There is an alternative fetch policy for virtual memory that we refer to as prepaging. In prepaging, the pages other than the demanded ones are brought into the main memory by page fault. Before proceeding further, we must have a basic idea of the paging technique.

What is Paging?

Paging is a memory management technique that allows the physical address space of a process in the main memory to be non-contiguous. It does so by dividing the main memory space into fixed-sized blocks that we refer to as frames.

Further, it divides the logical memory space of the process into same-sized blocks, and we refer to these blocks as pages. Now when a particular process is to be executed, the system loads its pages into available memory frames, which are not necessary to be contiguous.

In this way, paging avoids external fragmentation, raises the degree of multiprogramming, offers large virtual address space and allows a process larger than the main memory to execute simultaneously with other processes.

Now let’s get back to our topic of demand paging, where the page is loaded to main memory only when demanded.

Demand Paging in Operating System

1. What is Demand Paging?
2. Why Demand Paging?
3. How Does the Demand Page Work?
4. Performance of Demand Paging
5. Compare with Prepaging
6. Advantages and Disadvantages

What is Demand Paging?

At the earliest, when the process starts, none of their pages are in the main memory. As soon as the CPU tries to access the first instruction of the process, it gets a page fault. In response, the operating system brings the page with the first instruction of the process to the main memory.

Subsequently, the page fault for global variables and stack rises. The operating system quickly responds to these page faults by loading the required pages to the main memory. After a while, the CPU has most of the required pages of the process it needs, and it starts executing the process with relatively few page faults.

This paging, where the system loads the page when demanded, is demand paging.

Why Demand Paging?

Consider that we need to execute a program, and the operating system loads the entire program into the main memory at the time of execution. Now, the operating system may not require the entire program initially. The program may start with a list of options from which the user has to select one to proceed.

In this case, loading the entire program in the main memory means loading executable code for all options in the main memory, loading executable code for all the options regardless of the fact that the user can and will select only one option. This results in wastage of main memory space, which could be used to load executable code of the process of some other program.

This is why we use the demand paging technique, in which the operating stem loads pages only when demanded during program execution.

How Does the Demand Page Work?

The demand paging is similar to the paging technique accompanied by swapping. In paging, as we know at first, the process resides in the disk. When we have to execute this process, the operating system swaps the process into the main memory.

Here, the operating system employs a lazy swapper that swaps only the demanded pages of the process to the main memory instead of swapping the entire process. We refer to this lazy swapper as a pager. As in the operating system, a swapper is used to swap the entire process, and a pager is concerned with the individual pages of the process.

Now whenever we have to swap a process into the main memory, this pager identifies which pages will be required and brings in only those pages to the main memory. This prevents OS from reading unwanted memory pages, reduces the swap time, and optimizes the amount of main memory required.

So, to implement the strategy of demand paging, we require some form of hardware support that will help the system identify the pages present in the main memory and the page available in secondary memory(disk). For this, the system implements a valid-invalid bit scheme.

• If a bit is valid – It means the page is valid (present in logical memory) and present in main memory.
• If a bit is invalid – It means the page is either not valid (not present in logical memory) or, if valid, currently present on the disk.

When a page is brought into the main memory, its table entry is valid. But the page table entry for the page not in the main memory is either marked invalid or marked with the address of that page on disk.

The page marked invalid would not affect the execution of the process until, through the execution, the process tries to access that page. Thus, the pager must cleverly identify and page in only those pages that are actually needed.

What if the process tries to access the page that is not in the main memory?

When a process tries to access an invalid page, it causes a page fault. The system handles the page fault with the following steps.

Step 1: The page table checks whether the bit is valid or invalid for a particular page referred.

Step 2: If the reference is invalid, the system terminates the process. If the reference is valid, but the page is present on the disk, the pager will now bring it in.

Step 3: First, the system identifies a free frame in the main memory. This free frame will accommodate the page into the main memory.

Step 4: A disk operation is scheduled to read the desired page into the newly identified frame.

Step 5: The disk is read for the desired page. Also the page table is modified to valid to indicate that the page is now in the main memory.

Step 6: Restart with the instruction for which the page fault occurred. Now the process accesses the page now present in memory.

Case 2:

It might be the case that the execution of a new process started, and no pages of it are in the main memory. The instruction pointer points to the first instruction of the process, and as the page is not present in the memory, it causes the page fault.

The required page is brought to the main memory, and faults keep on occurring until every page that the process needs is brought to the main memory. After all the desired pages are page in the main memory, the process can execute with no more faults. This would subsequently reduce the performance of the system.

This is a pure demand paging in operating system.

Case 3:

It might be the case that a process could access several pages of each instruction execution, which would result in multiple page faults per instruction. It would ultimately reduce the performance of demand paging.

Performance of Demand Paging

We measure the performance of demand paging in terms of effective access time. Effective access time is the time required to access memory if the cost of page fault gradually reduces overall memory access.

ea = (1 – p) * ma + p*pft

• ea = effective access time
• ma = physical memory (core) access time
• pft = page fault time
• p = probability of a page fault occurs
• (1-p) = the probability of accessing memory in an available frame

The page fault time is the sum of the additional overhead associated with accessing a page on the disk. This includes additional context switches, disk latency and transfer time associated with page-in and page-out operations, & the overhead of executing an operating system trap.

Compare with Prepaging

Demand Paging	Prepaging
Page is loaded into main memory only if only when a process refers to that page.	Required pages are loaded to the main memory even before they are referenced.
The number of page faults is more.	The number of page faults is less in some specific cases.
The loading time of pages can not be reduced in any case.	The loading time of pages reduces if the pages of the process are stored contiguously in secondary memory.
The pages loaded in the main memory are certainly used.	The pages loaded in the main memory may or may not be used.
It prevents resource wastage as it loads the page only when referenced.	Waste resources as it loads the page even if not required.

Advantages and Disadvantages of Demand Paging

Advantages

• Raises the degree of multiprogramming as pages of multiple processes can be loaded simultaneously.
• Efficient use of main memory.
• Prevent external fragmentation.
• With demand paging, we could have large virtual memory.

Disadvantages

• The amount of overhead in demand paging is noticeable.
• It has a probability of internal fragmentation.
• Memory access time is longer.
• Page Table Length Register (PTLR) limits the scale for virtual memory.

So, this was all about demand paging in operating system. It is a common way to implement virtual memory. Pure demand paging is when a page is not brought to the main memory until referenced. The performance of demand paging is acceptable until the page fault rate is reasonably low.