To Implement Paging Technique for Memory Management

Introduction

Memory management is a critical function of an operating system that oversees and controls primary memory. It manages the allocation and deallocation of memory, ensuring that processes are efficiently loaded and moved between main memory and disk during their execution.
Key responsibilities of memory management include:

1. Tracking Memory Usage: Memory management monitors every memory location, whether it is currently in use by a process or not. It maintains a detailed record of which portions of memory are occupied and which are free.
2. Managing Memory Allocation: It handles the allocation of memory to processes based on their needs and ensures that memory is allocated efficiently and without conflict.
3. Handling Memory Deallocation: Memory management keeps track of when memory is released or becomes available again and updates the system's memory state accordingly. This includes managing memory that is no longer in use by processes and making it available for future allocations.

Terminologies Associated

• Logical Address or Virtual Address(L.A): It is the address generated by the CPU during program execution. It is used by programs to access memory and is independent of the actual hardware memory.
• Logical Address Space or Virtual Address Space(L.A.S): It refers to the range of addresses that a program can use. This space is determined by the architecture of the CPU and the operating system’s memory management.
• Physical Address(P.A): It is the actual location in the computer's RAM (or other physical memory) where data is stored. It is the address that corresponds to a specific location in physical memory hardware.
• Physical Address Space(P.A.S): It is the range of addresses that the physical memory (RAM) can address. It is determined by the total amount of physical memory in the system and the addressing capability of the hardware.
• Word: The word is the smallest unit of the memory. It is the collection of bytes. Every operating system defines different word sizes after analyzing the n-bit address that is inputted to the decoder and the 2 ^ n memory locations that are produced from the decoder.

Non-Contiguous Memory Allocation

Non-contiguous memory allocation is a memory allocation technique in which the different parts of a process are allocated to different places in the main memory.
In this type of memory allocation, a process can acquire several memory blocks at different locations in the memory according to its need. The available free space is distributed here and there, unlike contiguous memory allocation, where all the free space is allocated in one place. The execution of non-contiguous memory is slower than contiguous memory allocation.

1. Paging
   

   In paging, each process consists of fixed-size components called pages. The size of a page is defined by the hardware of a computer, and the demarcation of pages is implicit in it. The memory can accommodate an integral number of pages. It is partitioned into memory areas that have the same size as a page, and each of these memory areas is considered separately for allocation to a page. This way, any free memory area is exactly the same size as a page, so external fragmentation does not arise in the system. Internal fragmentation can arise because the last page of a process is allocated a page-size memory area even if it is smaller than a page in size.
   

   
   

   How Paging Works?

   It breaks physical memory into fixed-size blocks called “frames” and logical memory into blocks of the same size called “pages.” When a program runs, its pages are loaded into any available frames in the physical memory.
   Each program has a page table, which the operating system uses to keep track of where each page is stored in physical memory. When a program accesses data, the system uses this table to convert the program’s address into a physical memory address.
   It also supports virtual memory, letting parts of programs be stored on disk and loaded into memory only when needed. This way, even large programs can run without fitting entirely into main memory.

   General formula:
   

   1. Physical Address Space = M words
      • If Physical Address = 22 bit, then Physical Address Space = 2²² words = 4 M words (1 M = 2²⁰)
   2. Physical Address = log₂M = m bits
      
      • If Physical Address Space = 16 M words = 2⁴ * 2²⁰ words, then Physical Address = log₂ 2²⁴ = 24 bits
   3. Logical Address Space = L words
      • If Logical Address = 31 bit, then Logical Address Space = 2³¹ words = 2 G words (1 G = 2³⁰)
   4. Logical Address = log₂L = l bits
      
      • If Logical Address Space = 128 M words = 2⁷ * 2²⁰ words, then Logical Address = log₂ 2²⁷ = 27 bits
   5. Page Size = P words
   6. Page offset = log₂P = p bits

   Memory Management Unit

   The Memory Management Unit (MMU) is responsible for translating logical addresses into physical addresses. The logical address is produced by the CPU for each page, while the physical address refers to the actual location in memory where the page is stored. When the CPU needs to access a page using a logical address, the operating system must use the MMU to determine the corresponding physical address to retrieve the page from memory.
   
   • The Physical Address Space is conceptually divided into a number of fixed-size blocks, called frames.
   • The Logical Address Space is also split into fixed-size blocks, called pages.
   • Page Size = Frame Size
   The logical address has two parts:
   1. Page Number: Number of bits required to represent the pages in Logical Address Space or Page number.
   2. Page Offset: Number of bits required to represent a particular word on the page that the CPU wants to read.
   
   The physical address has two parts:
   1. Frame Number: Number of bits required to represent the frames in Physical Address Space or Frame number.
   2. Frame Offset: The number of bits required to represent the frame offset relies upon the size of every frame.
   
   Memory management unit of OS needs to convert the page number to the frame number.
   

   Page Table

   A Page Table is a data structure utilized by the operating system to manage the mapping between a process's virtual addresses and the corresponding physical addresses in the system's memory.
   A Page Table Entry (PTE) is a specific record within the Page Table that holds details about an individual memory page. Each PTE includes information such as the physical address of the page, whether the page is currently in memory, its writable status, and other access permissions.
   

   The size and format of a PTE can differ based on the system architecture and the operating system in use. Generally, a PTE contains sufficient information for the operating system to efficiently manage memory and safeguard against unauthorized or unintended access.
   
   

   Mapping from Page Table to Main Memory

   1. Generation of logical address: CPU generates logical address for each page of the process.
   2. Scaling: To determine the actual page number of the process, CPU stores the page table base in a special register. Each time the address is generated, the value of the page table base is added to the page number to get the actual location of the page entry in the table. This process is called scaling.

      Page Table Entry = Page Table Base Register(PTBR) + Page Number * Page Size

   3. Generation of physical Address: The frame number of the desired page is determined by its entry in the page table. A physical address is generated which also contains two parts : frame number and offset.
   4. Getting Actual Frame Number: The frame number and the offset from the physical address is mapped to the main memory in order to get the actual word address.
   
   
   

   Advantages

   • Eliminates external fragmentation.
   • Facilitates efficient use of memory.
   • Supports virtual memory.

   Disadvantages

   • Can lead to internal fragmentation.
   • Reduced performance due to increased memory access time.
   • Complexity in implementation.

2. Segmentation
   

   Segmentation is a memory management method used in operating systems that divides memory into portions of varying sizes. Each component is referred to as a segment, and each segment can be assigned to a process.
   A table called segment table stores information about each segment. One (or more) segments contain the segment table.
   The segment table primarily comprises two pieces of information regarding the segment:

   1. Base: This is the segment's starting address.
   2. Limit: The segment's length is the limit.
   
   
   

   How does Segmentation works?

   Segmentation divides a program into distinct logical segments, such as code, data, and stack. Each segment is independently allocated and managed, with the operating system maintaining a segment table that records the base address and length of each segment in physical memory.
   When a program accesses memory, it uses a logical address composed of a segment number and an offset. The segment number helps locate the segment table, which provides the base address; adding the offset to this base address yields the physical address.

   Advantages

   • Divides programs into logically related segments for easier management.
   • Allows segments to grow independently without affecting others.
   • Enables independent swapping of segments, potentially improving performance.

   Disadvantages

   • Requires maintaining segment tables and handling segment faults.
   • Leads to External Fragmentation.
   • May face challenges with systems that do not support segmentation.