Paging in COA: Equal-sized blocks known as “Pages” are used to divide the virtual memory area. Equal-sized blocks known as Page Frames (also known as pages) are also used to split the Physical Memory space, also known as Main Memory. Virtual Memory pages are loaded into any free page frame in physical memory.

For instance: Take the 80386 processor as an example. 4 GB of physical memory. Page Size is 4KB. Physical memory size is 4 GB divided by 4 KB, or 1M. (2 32 / 2 12 = 2 20) 

The processor determines whether the required page is present in the physical memory when a page is required. If it is discovered, it is referred to as a “HIT” and an operation is carried out on the Physical Memory. A MISS or page fault occurs when the intended page is not present in the physical memory. In the event of a page fault, the required page is loaded from virtual memory into physical memory. A “Page Replacement” is carried out if no vacant page frame is present in physical memory. A new, desired page from the Virtual Memory is substituted for an outdated page in the Physical Memory. 

To choose which page of the physical memory has to be updated, common methods like FIFO (First in first out), LRU (Least Recently utilised), or LFU (Least Frequently Used) are utilised. The system is said to be thrashing if there are too many page faults. This should be prevented. When replacing, the “Dirty Bit” is examined to see if a page in Physical Memory has been updated. 

If the Dirty bit is set to 1, the page has been modified (and is therefore “Dirty”), and it must be copied back into virtual memory before being replaced in order to preserve the modified data. The page can be immediately replaced if the Dirty bit is set to 0. A “Page Table” is needed to provide the mapping between the Virtual Memory page number and Physical Memory page frame number since any page of Virtual Memory can be loaded into any page frame of Physical Memory. 

Virtual addresses are comprised on two components: Ideally, page number I should be located. 

The Physical Address is comprised of two parts: Present Page Frame I’s position on the page 

The Page Table links the required page number to the physical memory’s page frame number, if one exists. Address translation is carried out in this manner. However, this procedure moves quite slowly. We must first access the matching entry in the page table before we can access any location, and only then can we access the page. 

The memory also contains the Page Table. This implies that we must travel to the memory again merely to access the_page table before we can access any other address in memory. A “Translation Look-aSide Buffer” (TLB) is employed to speed up the procedure. 

The processor’s on-chip cache is called the TLB. 

It saves the 32 Page table entries that were utilised most recently. 

Because the page table does not need to be accessed, future access to these pages—whose data is cached in the TLB—is substantially quicker. The processor can immediately access the page by asking the TLB for the starting address of the page frame. 

As a result of the “Locality of reference” principle, the majority of systems achieve a hit ratio of >98% on the TLB, which speeds up processes. Several pages may be needed for an application. Physical Memory does not load them all at once. Instead, pages are loaded only when the processor specifically requests them. Demand Paging is the term for this. 

Paging vs Segmentation:

Paging	Segmentation
A physical partition of memory called paging.	A logical separation of the memory is called segmentation.
The size of pages is fixed.	The sizes of segments vary.
Due to restricted page sizes, there is a high rate of fragmentation (wastage of wasted space).	As segments vary in size, fragmentation is low.
entirely hidden from the coder.	managed by a programmer.
offers limited control over the protection method.	We can give segments varying levels of privilege since segments are programmer-controlled. Consequently, it gives the protective mechanism better control.
fails to distinguish between code and data.	Data and code segments receive separate treatment.
Algorithms like FIFO, LRU, and LFU are used to load pages.	Algorithms like First Fit, Best Fit, and others are used to load segments.
does not permit the interchange of code or data among various processes or tasks.	Segments may be local or global in scope. All global parts can be shared

Page Replacement Algorithms: 

A page replacement algorithm is required in an operating system that employs paging to manage memory in order to determine which page has to be replaced when a new page is received. 

A page fault occurs when an active programme tries to access a memory page that is loaded in virtual memory but not physically in the system. Page errors occur because actual physical memory is substantially less than virtual memory. In the event of a page fault, the operating system might have to swap out one of the current pages for the one that is now required. Different page replacement algorithms offer various suggestions for selecting the appropriate replacement page. All algorithms strive to lower the number of page defects. 

1)First In First Out (FIFO)

The simplest page replacement algorithm is First In First Out (FIFO). The operating system maintains a queue for all of the memory pages in this method, with the oldest page at the front of the queue. The first page in the queue is chosen for removal when a page needs to be replaced.

Take page references 1, 3, 0, 3, 5, 6, and 3 with three page frames as an example.Determine the quantity of page errors. 

Since all slots are initially empty, when 1, 3, and 0 arrive they are allotted to the empty spaces, resulting in 3 Page Faults. 

Since 3 is already in memory when it arrives, there are no page faults. Then page number 5 appears; it cannot fit in memory, therefore it takes the position of the oldest page slot, which is 1. —>1 Page Fault. When page 6 arrives, it is also not in memory, therefore it takes the position of the oldest page slot, which is 3 —>1 Page Fault. Finally, 3 replaces 0 because it is unavailable when it comes, causing a page fault. 

Belady’s anomaly demonstrates that employing the First in First out (FIFO) page replacement mechanism with more page frames can result in more page faults.  For instance, if we take into account reference strings with 3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, and 3 slots, we end up with 9 total page faults, but if we raise the number of slots to 4, we end up with 10 page faults.

2)OPTIMAL REPLACEMENT ALGORITHM

1. “Optimal Replacement Algorithm” (OPT) is a different proposed replacement algorithm. 

2. The pages that will be used in the near future must be known in advance.

 3. The pages that are utilised first will be kept. 

4. New pages will be added to those that have been inactive the longest. 

5. It is obviously hard to foresee which pages will be used in the future.

 6. However, if we have performed several test runs of the programme in a simulator, we can safely estimate its behaviour using that data as a guide. 

Take a look at the page numbers 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with the 4 page frame. Find the page error number. 

When 7 0 1 2 are allocated to the vacant slots (which are initially all empty), 4 Page Faults result. 

As 0 is already present, the page fault code is 0. Since 3 is used for the shortest period of time going forward, it will replace 7 when it arrives.Page fault: 1. As 0 is already present, the page fault code is 0. 1 will be replaced by 4 because 1 Page Fault. 

The additional page reference string is now 0 Page Fault since they are already present in the memory. 

Although ideal, optimal page replacement is not practical since the operating system is unable to predict future requests. Optimal Page replacement is used to create a baseline so that other replacement methods can be measured against it.

3)LEAST RECENTLY USED

The page that hasn’t been viewed in a while will be replaced by this algorithm. 

Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with four page frames as an example. Count the number of page errors.

When 7 0 1 2 are allocated to the vacant slots, which are all initially empty, 4 Page faults result because 0 is already there, resulting in 0 Page fault. Because it hasn’t been used as much as 7, when 3 arrived it will replace 7 —>1 Page fault 

0 Page Fault because 0 is already in memory. 

1 will be replaced by 4 because it is a page fault. 

The additional page reference string is now 0 Page Fault since they are already present in the memory. 

4)MOST RECENTLY USED(MRU): This algorithm replaces pages that have recently been used. This algorithm is susceptible to the Belady anomaly.