Explain the page replacement algorithms - FIFO, LRU, and Optimal

- Paging is used by most of the computer operating systems for the purpose of virtual memory management. 

- Whenever a page fault occurs, some pages are swapped in and swapped out. Who decides which pages are to be replaced and how? 

- This purpose is served by the page replacement algorithms. 

- Page replacement algorithms only decide which pages are to be page out or written to the disk when a page of the memory has to be allocated. 

- Paging takes place only upon the occurrence of a page fault.

- In such situations a free cannot suffice because either one is not available or because the number of available pages is less than threshold. 

- If a previously paged out page is reference again, then it has to be read in from the disk again. 

- But for doing this, the operating system has to wait for the completion of the input/ output operation. 

- The quality of a page replacement algorithm is denoted by the time it takes for a page in. 

- The lesser it is, the better the algorithm is. 

- The information about the access to page as provided by the hardware is studied by the page replacement algorithm and then it decides which pages should be replaced so that the number of page faults can be minimized. 

In this article we shall see about some of the page replacement algorithms.

FIFO (first – in, first – out): 

- This one being the simplest of all the page replacement algorithms has the lowest overhead and works by book – keeping in place of the OS. 

- All pages are stored in a queue in the memory by the operating system.

- The ones that have recently arrived are kept at the back while the old ones stand at the front end of the queue.

- While making replacement, the oldest page is selected and replaced. 

- Even though this replacement algorithm is cheap as well as intuitive, practically it does not perform well. 

- Therefore, it is rarely used in its original form. 

- VAX/ VMS operating systems make use of the FIFO replacement algorithm after making some modifications. 

- If a limited number of entries are skipped you get a partial second chance. 

Least recently used (LRU): 

- This replacement algorithm bears resemblance in name with the NRU. 

- However, difference is there which is that this algorithm follows that the page usage is tracked for a certain period of time. 

- It is based on the idea that the pages being used many times in current set of instructions will be used heavily in the next set of the instructions also. 

- Near optimal performance is provided by LRU algorithm in the theory however in practical it is quite expensive to be implemented. 

- For reducing the costs of the implementation of this algorithm, few implementation methods have been devised. 

- Out of these the linked list method proves to be the costliest. 

- This algorithm is so expensive because it involves moving the items about the memory which is indeed a very time consuming task. 

- There is another method that requires hardware support.

Optimal page replacement algorithm: 

- This is also known as the clairvoyant replacement algorithm. 

- The page that has to be swapped in, it is placed in place of the page which according to the operating system will be used in future after a very long time. - In practical, this algorithm is impossible to be implemented in case of the general purpose OS because approximate time when a page will be used is difficult to be predicted. 

Explain about the Paged Memory and Segmentation techniques?

Paging and segmentation, both are memory management techniques. 

What is Paging?

- This technique has been designed so that the system can store or retrieve data from the virtual memory or secondary memory of the system to be loaded in the main memory and used. 

- In this scheme, the data from the secondary memory is retrieved by the operating system in blocks of same size commonly known as the paging. 

- This is why the technique has been called the paging memory – management scheme. 

- This memory management scheme has a major advantage over the segmentation scheme. 

- The advantage is that non-contiguous address spaces are allowed. 

- In segmentation, non-contiguous physical address spaces are not allowed. 

- Before the paging actually came in to use, the whole program had to be fitted in to the contiguous memory space by the systems. 

- This in turn led to a number of issues related to fragmentation and storage. 

- Paging is very important for the implementation of the virtual memory in many of the operating systems that are general purpose. 

- With the help of paging memory management technique, the data that cannot be fitted in to the physical memory i.e., RAM can be easily used. 

- Paging actually comes in to play whenever a program makes an attempt for accessing the pages that have not been presently mapped to the main memory (RAM). 

- Such situation is termed as the page fault. 

- At this point the control is handed over to the operating system for handling the page fault.

- This is done in a way that it is not visible to the interrupt raising program. 

The operating system has to carry out the following instructions:

1. Determining the location of the requested data from the auxiliary storage.
2. Obtaining a page frame in the main memory that is empty to be used for storing the requested data.
3. Loading the data requested in to the empty page obtained above.
4. Making updates to the page table so that new data is only available.
5. Returning the control interrupting program and retrying to execute the same instruction that caused the fault.

What is Segmentation?

- This memory management technique involves dividing the main memory in to various sections or segments.

- In the system that makes use of this management technique, a value identifying the segment and its offset is contained in the reference to that memory location. 

- Object files that are produced during the compilation of the programs make use of the segments when they have to be linked together to form an image of the program and this image has to be loaded in to the memory.  

- For different program modules, different segments might be created. 

- Some programs may even share some of the segments.

- In one way, memory protection is implemented by means of memory segmentation only.

- Paging and segmentation can be combined together for memory protection. 

- The size of memory segment is not always fixed and can be as small as a byte. 

- Natural divisions such as the data tables or the individual routines are represented by the segments.

- This is to make the segmentation visible to the programmer. 

- With every segment, a set of permissions and length is associated. 

- A segment can be referred to by the process only in a way that is permitted by this set of permissions. 

- If this is not done, a segmentation fault is raised by the operating system. 

- Segments also consist of a flag that indicates the presence of the segment in the main memory of the system. 

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. 

What is the cause of thrashing? How does the system detect thrashing? Once it detects thrashing, what can the system do to eliminate this problem?

- Thrashing takes place when the sub-system of the virtual memory of the computer system is involved in a state of paging constantly.

- It rapidly exchanges data in the memory with the data available on the disk excluding level of processing of most of the applications. 

- Thrashing leads to the degradation of the performance of the computer or may even cause it to collapse. 

- The problem may further worsen until the issue is identified and addressed. 

- If there are not enough pages available for the job, it becomes very likely that your system will suffer from thrashing since it’s an activity involving high paging. 

- This also leads to high rate of page fault. 

- This in turn cuts down the utilization of the CPU. 

- Modern systems utilize the concept of the paging system for executing many programs.

- However, this is what makes them prone to thrashing. 

- But this occurs only if the system does not have at present sufficient memory as required by the application or if the disk access time is too long. 

- Thrashing is also quite common in the communication systems where the conflicts concerning the internal bus access is common. 

- The order of magnitude or degree by which the latency and throughput of a system might degrade depends up on the algorithms and the configuration that is being used. 

- In systems making use of virtual memory systems, workloads and programs presenting insufficient locality of reference may lead to thrashing. 

- Thrashing occurs when the physical memory of the system is not able to contain in itself the workload or the program. 

- Thrashing can also be called as the constant data swapping.

- Older systems were low end computers i.e., the RAM they had was insufficient to be employed in modern usage patterns. 

- Thus, when their memory was increased they became noticeably faster. 

- This happened because of the availability of more memory which reduce the amount of swapping and thus increased the processing speed. 

- IBM system/ 370 (mainframe computer) faced this kind of situation. 

- In it a certain instruction consisted of an execute instruction pointing over to another move instruction. 

- Both of these instructions crossed the page boundary and also the source from which the data has to be moved and the destination where it was to be placed both crossed the page boundary. 

- Thus, this particular instruction altogether required 8 pages and that too at the same time in memory. 

- Now if the operating system allocated less than 8 pages, a page fault is sure to occur. 

- This page fault will lead to thrashing of all the attempts of restarting the failing instruction. 

- This may even reduce the CPU utilization to almost zero!

How can a system handle thrashing?

For resolving the problem of thrashing, the following things can be done:

1. Increasing the amount of main memory i.e., the RAM in the system. This is the best ever solution for this and will be helpful for a long term also.

2. Decreasing the number of programs to be executed by the system.

3. Replacing the programs that utilize heavy memory with their less memory utilizing equivalents.

4. Making improvements in the spatial locality.

- Thrashing can also occur in cache memory i.e., the faster storage space that is used for speeding up the data access. 

- Then it is called cache thrashing. 

- It occurs when the cache is accessed in a way that it leaves it of no benefit. 

- When this happens many main memory locations compete with each other for getting the same cache lines that it turn leads to a large number of cache misses.

What is Paging? Why it is used?

- Paging is a very important concept for the computer operating systems required for managing the memory. 

- It is essentially a memory management scheme which is used for storing as well as retrieving data from the secondary memory devices.

- Under this scheme, the data is retrieved from the secondary storage devices and handed over to the operating systems. 

- The data is in the form of blocks all having the same size. 

- These data blocks are called as the pages. 

- In paging, for a process the physical address space can be kept as non–contiguous itself. 

- Paging is a very important concept for implementing the virtual memory in the operating systems designed for contemporary and general use. 

- This allows the disk storage to be used for the data that is not able to fit in to the RAM. 

- The main functions of the paging technique are carried out when a program attempts to access the pages that have no mapping to the physical RAM. 

- This situation is commonly known as the page fault. 

- In this situation, the OS comes to take control of the error. 

- This is done in a way that is invisible to the application. 

The operating system carries out the following tasks in paging:

Ø  Locates the data address in an auxiliary storage.

Ø Obtains a vacant page frame in the physical memory to be used for storing the data.

Ø  Loads the data requested by the application in to the page frame obtained in the previous step.

Ø  Make updates to the page table for showing the new data.

Ø Gives back the execution control to the program.This maintains a transparency. it again tries to execute the instruction because of which the fault occurred.

- If space is not available on RAM for storing all the requested data, then another page from RAM cannot be removed. 

- If all of the page frames are filled up, then a page frame can be obtained from the table which contains data that will be shortly emptied. 

- A page frame is said to become dirty if it is modified since its last read operation in to the RAM. 

- In such a case it has to be written back in to its original location in the drive before it is freed. 

- If this is not done, a fault will occur which will require obtaining an empty frame and reading the contents from drive in to this page. 

- The paging systems must be efficient so as to determine which frames are to be emptied. 

- Presently many page replacement algorithms have been designed for accomplishing this task. 

- Some of the mostly used for replacement are:

Ø  LRU or least recently used

Ø  FIFO or first in first out

Ø  LFU or least frequently used.

- To further increase responsiveness, paging systems may employ various strategies to predict which pages will be needed soon. 

- Such systems will attempt to load pages into main memory preemptively, before a program references them. 

- When demand paging is used, paging takes place only when some data request and not prior to it. 

- In a demand pager, execution of a program begins with none of the pages loaded in to the RAM. 

Page Buffering Algorithm

There are some other procedures that are often used in addition to a specific page replacement algorithm.

- System commonly keep a pool of free frames. When a page fault occurs, a victim frame is chosen as before. However, the desired page is read into a free frame from the pool before the victim is written out. This procedure allows the process to restart as soon as possible, without waiting for the victim page to be written out. When the victim is later written out, its frame is added to the free-frame pool.
- Whenever the paging device is idle, a modified page is selected and is written to the disk. Its modify bit is then reset. This scheme increases the probability that a page will be clean when it is selected for replacement, and will not need to be written out.
- Another modification is to keep a pool of free frames, but to remember which page was in each frame. Since the frame contents are not modified when a frame is written to the disk, the old page can be reused directly from the free-frame pool if it is needed before that frame is reused. No I/O is needed in this case. When a page fault occurs, we first check whether the desired page is in the free-frame pool. If it is not, we must select a free frame and read into it.

This technique is used in VAX/VMS system, with a FIFO replacement algorithm. When the FIFO replacement algorithm mistakenly replaces a page that is still in active use, that page is quickly retrieved from the free-frame buffer, and no I/O is necessary.

Not Recently Used (NRU) Page Replacement Algorithm

The not recently used (NRU) page replacement algorithm is an algorithm that favors keeping pages in memory that have been recently used. This algorithm works on the following principle: when a page is referenced, a referenced bit is set for that page, marking it as referenced. Similarly, when a page is modified (written to), a modified bit is set. The setting of the bits is usually done by the hardware, although it is possible to do so on the software level as well.

- When a page fault occurs, the operating system inspects all the pages and divides them into four categories based on the current values of their R (referenced; read or written) and M (modified) bits:
* Class 0: not referenced, not modified.
* Class 1: not referenced, modified.
* Class 2: referenced, not modified.
* Class 3: referenced, modified.
- Although class 1 pages seems, at first glance, impossible, they occur when a class 3 page has its R bit cleared by a clock interrupt. Clock interrupts do not clear the M bit because this information is needed to know whether the page has to be rewritten to disk or not. Clearing R but not M leads to a class 1 page.
- The NRU (Not Recently Used) algorithm removes a page at random from the lowest numbered nonempty class.
- It is better to remove a modified page that has not been referenced in at least one clock tick (typically 20 msec) than a clean page that is in heavy use.
- The main attraction of NRU is that it is easy to understand, moderately efficient to implement, and gives a performance that, while certainly not optimal, may be adequate.