Explain about demand paging and page replacements

These are two very important concepts of memory management strategies in the computer operating systems namely demand paging and paging replacements. 

About Demand Paging

- Demand paging is just the opposite concept of the anticipatory paging. 

- Demand paging is actually a memory management strategy developed for managing the virtual memory.

- The operating system that makes use of demand paging technique, a copy of the disk page is made and kept in the physical memory whenever a request is made for it i.e., whenever a page fault occurs. 

- It is obvious that the execution of a process starts with none of its page loaded in to the main memory and follows by a number of page faults occurring one after the other until all of its required pages have been loaded in to the main memory. 

- Demand paging comes under the category of the lazy loading techniques. 

- This strategy follows that only if the process in execution demands a page, then only it should be brought in to the main memory. 

- That’s why the strategy has been named as demand paging. Sometimes it is even called as the lazy evaluation. 

- Page table implementation is required for using the demand paging technique.

- The purpose of this table is to map the physical memory to the logical memory. 

- This table uses a bit wise operator for marking a page as valid or invalid. 

The following steps are carried out whenever a process demands for a page:

1. An attempt is made for accessing the page.
2. If page is present in the memory the usual instructions are followed.
3. If page is not there i.e., is invalid then a page fault is generated.
4. Memory reference to a location in the virtual memory is checked if it is valid or not. If it’s an illegal memory access then the process is terminated. If not the requested page has to be paged in.
5. The disk operations are scheduled for reading the requested page in to the physical memory.
6. Restarting the instruction that raised the page fault trap.

- The nature of this strategy is itself of great advantage. 

- Upon availability of more space in the physical memory, it allows execution of many processes leading to a decrease in the context switching time.

- At the time of program start up, less latency occurs during loading. 

- This is because the inflow and outflow of the data between main memory and secondary memory is very less.

About Page Replacement

- When less number of real memory frames is available, it leads to invoking a page stealer. 

- This stealer searches through the PFT (page frame table) for pages to steal. 

- This table stores references to the pages which are required and modified. 

- If the requested page is found by the page stealer, it does not steal it but the reference flag is reset for that page. 

- So in the pass when the page stealer comes across this page, it steals this page. 

- Note that in this pass the page was flagged as un-referenced. 

- Any change made to the page is indicated by means of the modify flag.

- If the modify flag of the page to be stolen is set, then a page out call has to be made before the page stealer does its work. 

- Thus, the pages that form a part of the currently executing segments are written to so called paging space and the persisting segments are in turn written to the disk. 

- The page replacement is carried by the algorithms called the page replacement algorithms. 

- Besides this, these also keep a track of the faults. 

Concept of page fault in memory management

Page fault is also known as the pf or #pf and can be thought of as a trap that the hardware raises for the software whenever the program tries to access a page that has been mapped to an address space in the virtual memory but has not been loaded in the main memory. 

In most cases, the page fault is handled by the operating system by helping in accessing the required page at an address space in the main or the physical memory or sometimes by terminating the program if it makes an illegal attempt to the access the page.

- Memory management unit is the hardware that is responsible for detecting the page faults and is located in the processor. 

- The software that helps the memory management unit in handling the page faults is the exception handling software and is seen as a part of the OS. 

- ‘Page fault’ is not always an error.

- These are often seen as a necessary role player in increasing the memory. 

- This can be made available to the software applications that makes use of the virtual memory of  the operating system for execution.

- Hard fault is the term used by the Microsoft instead of page fault in the resource monitor’s latest versions.

Classification of Page Faults

Page faults can be classified in to three categories namely:

1. Minor: 

- This type of fault is also called the soft page fault and is said to occur when the loading of the page in to the memory takes place at the time of the fault generation, but the memory management unit does not mark it as being loaded in the physical memory. 

- A page fault handler is included in the operating system whose duty is to make an entry for the page that is pointed to by the memory management unit. 

- After making the entry for it, its task is to give an indication that the page has been loaded. 

- However, it is not necessary that the page must be read in to the memory. 

- This is possible if the different programs share the memory and the page has been loaded in to the memory for the various applications. 

- In the operating systems that apply the technique of secondary page caching, the page can be removed from the working set of the process but not deleted or written to the disk.

2. Major: 

- Major fault is actually a fault that many operating systems use for increasing the memory for the program that must be available as demanded by the program. 

- The loading of the parts of the program is delayed by the operating system from the disk until an attempt is made by the program for using it and generating the page fault.

- In this case either a non – free page or a page in the memory has to be found by the page fault handler. 

- When the page is available, the data from it can be read by the operating system to the new page in the main memory, thus easily making an entry for the required page.

3. Invalid: 

- This type of fault occurs whenever a reference is made to an address that does not exists in the virtual address space and therefore it has no page corresponding to it in the memory. 

- Then the code by which the reference was made has to be terminated by the page fault handler and give an indication regarding the invalid reference. 

Define the Virtual Memory technique?

Modern operating systems come with multitasking kernels. These multitasking kernels often run in to the problems related to memory management. Physical memory does not suffice for them to execute the tasks assigned to them because of being fragmented. So they have to take some additional from the secondary memory. But they cannot use this memory directly. Virtual memory offers a solution to this problem. 

What is Virtual Memory technique?

- Using this technique makes the fragmented main memory available to the kernels as a contiguous main memory. 

- Since it is really not the main memory but just appears to be, it has been named as the virtual memory and this technique is called the virtual memory technique. 

- Since, it helps in managing the memory, it is essential a memory management technique. 

- The main storage gets fragmented because of many programming and processing problems. 

- The main memory available to the processes and the tasks is virtualized by the virtual memory technique and then it appears to the process as a contiguous memory location. 

- This memory is a global address space. 

- Virtual address spaces such as these are managed by the operating system. 

- The real memory is assigned to the virtual memory by the operating system itself. 

- The virtual addresses of the allocated virtual address spaces are translated in to the physical addresses automatically by the CPU. 

- It achieves this with the help of some memory management hardware specially designed for this purpose. 

- The processes continue to execute uninterrupted as long as this hardware properly translates the virtual addresses in to real memory addresses properly. 

- If it fails in doing so at any point of time, the execution comes to a halt and the control is transferred to the operating system. 

- The duty of the operating system now is to move the requested memory page to the main memory from the backing store. 

- Once done with this, it then returns the control again to the process that was interrupted. 

- It greatly simplifies the whole execution process. 

- Even if the application would require more data or code that would fit in real memory, it does not have to be moved to and fro between the backing store and the real memory. 

- Furthermore, this technique also offers protection to the processes that are provided distinct address spaces by the isolation of the memory allocate to them from other tasks.

- Application programming has been made a lot easier with the help of the virtual memory technique since it hides the fragmentation defects of the real memory. 

- The burden of memory hierarchy management is delegated to the kernel which eliminates the need for the explicit handling of the overlays by the program. 

- Thus each process can execute in an address space that is dedicated to it. 

- The need for relocating the code of the program is obviated along with using relative addressing for accessing the memory. 

- The concept of virtual memory was generalized and eventually named as memory virtualization. 

- Gradually, the virtual memory has become an inseparable part of the architecture of the modern computers. 

- For implementing it, dedicated hardware support is absolutely necessary. 

- This hardware is built in to the CPU in some sort of memory management hardware. - If required for boosting the performance of the virtual memory, some virtual machines and emulators may employ some additional hardware support. 

- The older mainframe computers did not have any support for the virtual memory concept. 

- In virtual memory technique, each program can solely access the virtual memory.

What is a virtual memory?

- Virtual Memory is a memory management technique that is a compulsory requirement for the multi-tasking kernels. 

- With this technique, the architecture of a computer can be virtualized to different types of computer data storage such as disk drive storage and RAM i.e., the random access memory. 

- With this, programmers do not have to worry about designing applications that will suit this kind of storage. 

- The programs can be designed keeping in consideration only one kind of memory i.e., the virtual memory. 

- This memory behaves just like the usual memory but more than that. 

- It offers a direct as well as contiguous memory space for various operations. - Some of us might think that the programming the software might get difficult with the virtual memory. But this is not so.

- Instead the task becomes easy because the fragmentation of the main physical memory is hidden. 

- For achieving this, the burden of the management of the memory hierarchy is delegated to the kernel.

- This has another added advantage which is that the need for handling of overlays in an explicit way via program is eliminated.

- The need for the relocation of a program code or accessing the memory is obviated via relative addressing. 

- This lets the process to be executed in its own dedicated space. 

- The concept of the virtual memory in a more generalized form is called the memory virtualization.

- The modern computer architecture cannot do without the virtual memory. 

- The only requirement for implementing the virtual memory is the hardware support that is provided through the memory management unit that is in-built in CPU. 

- For increasing the performance of these virtual memory implementations hardware support can be employed by the virtual machines and emulators. 

- Computer systems with old operating systems such as DOS in mainframes  do not possess any functionality of the virtual memory. 

- The first computer that featured the virtual memory was the Apple Lisa that was designed in the year of 1980. 

- It appears that with the use of virtual memory as if every program has a sole access to it. 

- However, there were some older operating systems that had single address space Oss. 

- These operating systems used to process tasks in a single space. 

- This space is consisted of the virtual memory. 

- Very consistent response times are a requirement of the special purpose computer systems such as the embedded systems. 

- These systems do not prefer to use the virtual memory as it may decrease the determinism. 

- The unpredictable traps producing unwanted jitter while carrying out the I/O operations might be triggered by the virtual memory systems. 

- This happens because the cost of the embedded hardware is kept low. 

- The operations are included in the software rather than including them in the hardware. 

- This technique is termed as the bit banging. 

- The older programs needed to have logic for the management of both primary and secondary memory. 

- One such logic was that of the overlaying. 

- Therefore, virtual memory was introduced as a method for extending the primary memory and make this extension easy for the programmers.  

- In order to allow multi–tasking and multi–programming, the memory in the early systems was divided between many programs. 

Implementation of the virtual memory saw many problems. One among those problems was of the dynamic address translation that was difficult to be implemented and  quite expensive also. 

Demand Segmentation

Although demand paging is considered the most efficient virtual memory system, a significant amount of hardware is required to implement it. When this hardware is lacking, less efficient means are sometimes devised to provide virtual memory. A case in point is demand segmentation.
Operating system allocates memory in segments, rather than in pages. It keeps track of these segments through segment descriptors, which include information about the segment's size, protections, and location. A process does not need to have all its segments in memory to execute. Instead, the segment descriptor contains a valid bit for each segment to indicate whether the segment is currently in memory. If the segment is in memory, the access continues unhindered. If the segment is not in memory, a trap to the operating system occurs. Operating system then swaps out a segment to secondary storage, and brings in the entire requested segment. The interrupted instruction then continues.
To determine which segment to replace in case of segment fault, operating system uses another bit in the segment descriptor called an accessed bit. It is set whenever any byte in the segment is either read or written. A queue is kept containing an entry for each segment in memory. After every time slice, the operating system places at the head of the queue any segments with a set access bit.
It then clears all access bits. In this way, the queue stays ordered with the most recently used segments at the head.
Demand segmentation requires considerable overhead. Thus, demand segmentation is not an optimal means for making best use of the resources of a computer system.