Paging

Paging is a memory management scheme that permits the physical address space of a process to be non-contiguous. Support for paging is handled by hardware. It is used to avoid external fragmentation. Paging avoids the considerable problem of fitting the varying-sized memory chunks onto the backing store. When some code or data residing in the main memory needs to be swapped out, space must be found on the backing store.

Basic Method:

• Physical memory is broken into fixed-sized blocks called frames (f).
• Logical memory is broken into blocks of the same size called pages (p).
• When a process is to be executed its pages are loaded into available frames from the backing store.
• The blocking store is also divided into fixed-sized blocks of the same size as memory frames.

1. The logical address generated by the CPU is divided into two parts: page number (p) and page offset (d).
2. The page number (p) is used as an index to the page table. The page table contains the base address of each page in physical memory. This base address is combined with the page offset to define the physical memory ie., sent to the memory unit.

What is a Memory Page?

Processes are divided into pages of manageable size, say 1MB or 2MB, and the main memory of the computer is divided into frames of the same size, and any page of any process will fit into any frames. OS ensures all pages of a process for execution are made available in any frames, and priority is given to fit them in a contiguously available frame for better performance. Pages of the process which goes into hibernation are removed from the main memory, and pages of the new process waiting in the queue will be loaded.

OS maintains the page table by mapping the logical address of all the processes with the memory’s physical address. This Page table enables OS to get the physical address of any page of any process, access its contents stored in the memory, and execute it. Pages facilitate the utilization of the main memory optimally as well as the execution of multiple processes efficiently.

Page Replacement Algorithm

Whenever the CPU raises a page fault, OS does not immediately bring the required page from the virtual space. If there is a free frame (main memory page) available, OS will fill it with a new page brought from Virtual memory; otherwise, it has to clear a frame (after backing it up into virtual memory) to accommodate the new page. Any page cannot be removed randomly, and there should be some logic or algorithm in replacing the pages in the memory.

Importance of Page Replacement Algorithm

Page replacement algorithm handles two major aspects viz.,

1. No frames to be allotted for each process
2. Logic to decide upon which frame should be replaced

If the initial frame is the allocation is insufficient, it may result in thrashing. There will be more page faults as most of the pages reside in virtual memory, and excess frame allocation will result in internal fragmentation. Hence none of the frames allocated should be accurate for optimal performance.

Similarly, if the right algorithm is not chosen, it will result in too many page faults that will impact the performance. If the CPU immediately seeks a replaced page, it will result in an unwanted swap out, and swap in, and OS will be doing unwanted work and degrade the performance. It’s important to choose the right algorithm that will result in fewer page faults.

Types of Page Replacement Algorithms

There are different algorithms available, and each one has its own methods to decide on the pages to be replaced.

1. First in First Out (FIFO)

This method is the simplest of all the logics in which the system maintains the order of page loading from virtual to main memory in a queue. Whenever a page fault occurs, the page that came first, residing at the bottom in the queue, will be removed to pave the way for a new one.

This method has a lacuna with a possibility of more page faults. There is a high degree of possibility that the page that came first may be required in the immediate future, and removing that will duplicate efforts.

2. Optimal Page Replacement

The page that will not be referred to in the future by the CPU will be removed to give a new one. This method is not practically possible to adopt, and it may be used as a benchmark for evaluating the veracity of other methods.

3. Least Recently Used

Pages referred infrequently or not referred in the recent past will be replaced with new ones. It is effective in that it looks for past activities and decides the page to be removed. This is based on a probability theory that a page referred to frequently will continue to be used in the future also and vice versa. It is an effective algorithm overall since it was proved that it has the least page faults.

Demand paging:

• A demand paging system is similar to the paging system with a swapping feature.
• When we want to execute a process we swap it into the memory. A swapper manipulates the entire process whereas a pager is concerned with the individual pages of a process.
• The demand paging concept is using a pager rather than a swapper.
• When a process is to be swapped in, the pager guesses which pages will be used before the process is swapped out again.
• Instead of swapping in a whole process, the pager brings only those necessary pages into memory.

Procedure to handle page fault:

• If a process refers to a page that is not in physical memory then
• We check an internal table (page table) for this process to determine whether the reference was valid or invalid.
• If the reference was invalid, we terminate the process, if it was valid but not yet brought in, we have to bring that from main memory.
• Now we find a free frame in memory.
• Then we read the desired page into the newly allocated frame.
• When the disk read is complete, we modify the internal table to indicate that the page is now in memory.
• We restart the instruction that was interrupted by the illegal address trap. Now the process can access the page as if it had always been in memory.

A page fault causes the following sequence to occur:

1. Trap to the OS.
2. Save the user registers and process state.
3. Determine that the interrupt was a page fault.
4. Checks the page references were legal and determine the location of
   page on disk.
5. Issue a read from disk to a free frame.
6. If waiting, allocate the CPU to some other user.
7. Interrupt from the disk.
8. Save the registers and process states of other users.
9. Determine that the interrupt was from the disk.
10. Correct the page table and another table to show that the desired page is now in memory.
11. Wait for the CPU to be allocated to this process again.
12. Restore the user registration process state and new page table then resume the interrupted instruction.