OS - Unit-4 - Paging Answered

Paging Concept

• Describe paging with the hardware diagram.

• Explain paging and its hardware with a neat diagram. What are the advantages of paging?
• With a neat diagram of paging hardware, explain the concept of paging. How does paging differ from segmentation? Explain with an example.
• Exemplify the process of paging and segmentation of memory.
• Paging vs Segmentation: Explain with examples and differences.

Answer :

Paging is a memory management technique that solves the problems of external fragmentation and simplifies memory allocation. It allows the physical memory used by a process to be noncontiguous, which means that a process can be stored in different parts of memory, not necessarily in a continuous block. This helps utilize memory more efficiently.

Paging divides physical memory into fixed-size blocks called frames, and breaking logical memory (used by processes) into blocks of the same size, called pages.

When a process is executed, its pages are loaded into available memory frames from their source (e.g., a file system or backing store) which can be located anywhere in physical memory.

Each address generated by the CPU is divided into two parts:

• Page number (p): Indexes into a page table to find the corresponding frame number.
• Page offset (d): Specifies the exact location within the frame being referenced.

Each process has its own page table, which stores the Base address (frame number) for every page.

The base address is combined with the page offset to get the actual physical memory address. Which is then used to access memory. This address translation is handled by the Memory Management Unit (MMU).

Paging is the most common memory-management technique in modern computer systems. Which is implemented by collaboration between the operating system and the computer hardware.

Advantages of Paging

• It simplifies memory management by using fixed-size blocks of frames and pages.

• When using a paging scheme, there is no external fragmentation: any free frame can be allocated to a process that needs it. Efficiency of memory usage is increased due to reduced space wasting.

• It allows processes to run even when not all of their memory is in one place. There is no need for contiguous memory allocation.

• A process can only access memory within it’s own page table which are the pages it owns. Each process is protected, since the memory access is controlled through its page table.

Disadvantages of Paging

• Paging may cause internal fragmentation. This happens when the last page of a process does not completely fill a frame, leaving some memory unused.

• Maintaining a separate page table for each process consumes memory and may cause overhead.

• Address translation may also slow down performance, though this is often optimized using hardware features like the Translation Lookaside Buffer (TLB).

Difference Between Paging and Segmentation

• Paging divides memory into fixed-size blocks, while segmentation divides memory into variable-sized logical units based on the program structure.

• Paging does not reflect the logical structure of the program, whereas segmentation does.

• In paging, the size of each page and frame is the same. In segmentation, each segment can be a different size.

• In paging, internal fragmentation may occur. In segmentation, external fragmentation may occur because segments vary in size.

Translation Look-Aside Buffer (TLB)

• With a neat diagram, explain paging hardware with TLB.
• With a neat diagram and example, demonstrate the working procedure of paging hardware with TLB.
• Explain with the help of a neat diagram how TLB can be used to improve Effective Access Time.

Answer :

In a computer system that uses paging. When a program has to accesses memory, it generates a logical address, which must be translated into a physical address.

To perform this translation, the system first indexes into page table with the page number, and combine it with the frame number to produce the actual address. Looking up the page table for every memory access is slow, because it requires two memory accesses:

1. One to access the page table (to find the frame number).
2. One to access the actual data in memory.

To solve this problem and speed up address translation, a Translation Lookaside Buffer (TLB) is used. TLB is a small, fast-lookup hardware memory that stores a cache of recent page table entries (i.e., recent page number to frame number mappings).

The search in the TLB is fast, as a TLB lookup in modern hardware is part of the instruction pipeline, essentially adding no performance penalty.

When the CPU generates a logical address:

• The page number part of the address is checked in the TLB.
• If the page number is found in the TLB (called a TLB hit), the corresponding frame number is immediately used to access memory immediately.
• If the page number is not found in the TLB (called a TLB miss), the system accesses the page table in main memory to get the frame number, and this entry is then added to the TLB for future references.

Some entries in the TLB, especially those used by the operating system or critical processes, are wired down, meaning they are fixed and not removed or replaced.

The percentage of times that the page number of interest is found in the TLB is called the hit ratio. For example, an 80% hit ratio means the desired page number is found in the TLB 80% of the time.

Virtual Memory Management

Memory protection in a paged environment is accomplished through protection bits associated with each frame. One additional bit, called the valid-invalid bit, is generally attached to each page table entry.

• When the bit is set to valid, the page is part of the process’s logical address space and is therefore a legal (valid) page.

• When the bit is set to invalid, the page is not part of the process’s logical address space, and illegal address references are trapped using the valid-invalid bit.

The operating system sets this bit for each page to allow or disallow access to the page. If a page’s valid-invalid bit is set to invalid, the computer traps to the operating system in case of an invalid page reference.

Page Faults and Handling

• Under what circumstances do page faults occur? Describe the actions taken by the OS when page faults occur.
• With a neat diagram, describe the steps in handling a page fault.
• Describe the steps in handling a page fault with a neat diagram.

Answer :

In virtual memory systems that use demand paging, only the necessary pages of a program are loaded into memory on demand. The rest remain on secondary storage until needed.

A page fault occurs when a running program tries to access a page that is not currently loaded into main memory (RAM).

Common reasons for a page fault include:

• The process is accessing part of its logical address space but it has not yet been loaded into main memory.

• The page was previously in memory but was swapped out to disk to make room for other pages.

• The page table entry is marked as invalid for the accessed page, indicating the page is not in memory.

The memory management unit (MMU), during address translation, checks the page table entry’s valid-invalid bit. If the bit is set to invalid, a page fault is triggered. Control is transferred to the operating system indicating the required page needs to be loaded into memory.

Actions Taken by the Operating System on a Page Fault

1. Check the validity of the memory reference: The OS checks internal table (in PCB) to determine if memory access is legal.

2. If the access is invalid (accessing a restricted area), the process is terminated. If it is valid but the page is simply not in memory, the OS proceeds to load the page.

3. Locate the page on secondary storage: The OS finds the missing page in the process’s swap space on the disk.

4. Find a free frame: The OS checks the list of free frames in memory. If no free frame is available, it selects a victim page to remove using a page replacement algorithm.

5. Read the page into memory: The required page is loaded from disk into the selected frame in physical memory. If the victim page was modified, it is written back to disk before being replaced.

6. Update the page table: The OS updates the page table to reflect the new location of the page now in memory and marks it as valid.

7. Restart the instruction: The CPU restarts the instruction that caused the page fault. From the program’s point of view, the page is now available in memory.

Secondary storage (usually a portion of the hard drive or SSD) is used to store pages that are not in main memory. This area is called swap space. The page table tracks whether each page is in memory or on disk.

Swapping and Memory Techniques

• Write short notes on the following: Swapping process in memory.
• Illustrate the facts and concepts for the following terms: Swapping.
• Write a note on thrashing.

Answer :

Swapping is a memory management technique where a process is temporarily moved out of main memory (RAM) to a secondary storage (such as a hard disk or SSD) and brought back later when needed for execution. This allows the system to free up physical memory for other processes.

Swapping enables the operating system to manage more processes than the available physical memory can accommodate at once.

• The space on disk where swapped-out processes are stored is often referred to as the backing store or swap space.

• When a process is swapped out, all its memory contents are copied to the disk.

• When swapped back in, the contents are loaded into memory, and the process resumes execution from where it left off.

Modern operating systems (like Windows and Linux) rarely swap out entire processes. Instead, they use paging, where only individual pages of a process are moved in and out of memory. This is more efficient because only the portions of memory that are actually in use are swapped.

Thrashing is a condition in a virtual memory system where the system spends more time servicing page faults than executing actual processes. it causes:

• Drastic drop in CPU utilization because the CPU is waiting on memory all the time.
• System performance degrades severely, sometimes to the point where the system becomes unresponsive.

Causes of Thrashing:

• Occurs when a process does not have enough memory frames to hold all the pages it is actively using.

• High degree of multiprogramming: Too many processes are competing for limited memory.

• Poor page replacement algorithms: Important pages may be removed from memory too often.

• Processes with frequent context switching and random memory access patterns.

Page Replacement Algorithms

Various page-replacement algorithms exist to determine which page to swap out when a page fault occurs. These include:

FIFO Page Replacement

The simplest page-replacement algorithm is First-In-First-Out (FIFO). The FIFO algorithm associates each page with the time it was brought into memory. When a page must be replaced, the oldest page is selected.

Optimal Page Replacement

The optimal page-replacement algorithm selects the page that will not be used for the longest time in the future. This approach guarantees the lowest possible page-fault rate but requires knowledge of future page references, which makes it impractical for real-world systems. As such, it is typically used for comparison studies.

LRU Page Replacement

The Least Recently Used (LRU) algorithm approximates the optimal page-replacement strategy. It replaces the page that has not been used for the longest period of time, using past access patterns to predict future behavior.

LRU is widely used as a page-replacement algorithm and is considered to be effective.

Page Replacement Problems

1. A process references 5 pages (A, B, C, D, E) in the following order: A, B, C, D, A, E, B, C, E, D. Assuming the replacement algorithms are FIFO, LRU, and Optimal, find out the number of page faults during the sequence of references, starting with an empty main memory with 3 frames.

2. Illustrate any two page-replacement algorithms for the following reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. compare the number of page faults for algorithms algorithms using three frames.

3. Given the page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6, and 3 frames, compare the number of page faults for the following page replacement algorithms: LRU, FIFO, Optimal page replacement algorithm.

4. A small computer has 4 page frames. A process makes the following list of page references: 1, 2, 3, 4, 0, 3, 2, 1, 5, 2, 3, 1, 2, 5, 0. How many page faults occur using FIFO, LRU, and Optimal page replacement algorithms?

5. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 3, 6. Find out the number of page faults, assuming 3 frames, using: FIFO, LRU, Optimal page replacement algorithm.

6. Consider the following page reference string: 1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6. How many page faults would occur in the case of: FIFO, LRU, Optimal page replacement algorithms assuming three and four frames?

7. A computer has 4 page frames. A process makes the following list of page references: 1, 2, 3, 4, 6, 3, 2, 1, 5, 2, 3, 1, 2, 5, 6. How many page faults occur using: FIFO, LRU, Optimal page replacement algorithms? Consider that initially 3 frames are filled for FIFO, 2 frames are filled for LRU, and 1 frame is filled for Optimal page replacement.

8. Consider the reference string 7, 2, 3, 4, 3, 2, 1, 4, 5, 2, 3, 1, 8, 7, 3, 2, 4, 1, 1, 2 with 3 memory frames. Determine the page faults using: FIFO, LRU, Optimal page replacement algorithm. Consider that initially 3 frames are filled.

9. Consider the reference string 1, 2, 3, 4, 2, 2, 5, 3, 2, 1, 6, 3, 4, 5, 3, 1 with 3 memory frames. Determine the page faults using: FIFO, LRU, Optimal page replacement algorithm.

10. A small computer has 3 page frames. A process makes the following list of page references: 5, 4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5. How many page faults occur using FIFO, LRU, and Optimal page replacement algorithms?

11. Consider the reference string 1, 2, 3, 4, 6, 5, 2, 5, 5, 6, 4, 1, 1, 2, 3, 4 with 4 memory frames. Determine the page fault using: FIFO, LRU, Optimal page replacement algorithm.