Memory Management

Introduction

• Memory management is a complex technique that is solved using various memory management algorithms and techniques employed by operating systems to optimize memory usage.
• The different memory management techniques vary depending on the operating system and hardware architecture.
• Effective memory management is very crucial for the overall performance, stability, and reliability of computer systems.
• In memory management, various algorithms, data structures, and strategies are employed to handle memory efficiently based on the specific requirements of the operating system and hardware architecture.

Definition

• Memory management is an essential aspect of computer systems that involves allocating and managing the primary memory (RAM) to efficiently store and retrieve data.

Objectives

• The goal of memory management is to optimize the use of available memory resources and provide a smooth and efficient execution environment for applications.
• Effective memory management is essential for optimizing system performance, enabling multitasking, and ensuring the stability and reliability of computer systems.

Memory Manangement Techniques

The common critical technologies related to memory management are:

1. Memory Hierarchy:
   • Modern computer systems typically have multiple levels of memory, arranged in a hierarchy based on their speed and capacity.
   • The memory hierarchy includes registers, cache memory, main memory (RAM), and secondary storage devices (hard drives, solid-state drives).
   • Memory management involves efficiently utilizing this hierarchy to store and retrieve data as needed.
2. Address Spaces:
   • Each program or process running on a computer has its own address space, which is a range of memory addresses that it can use.
   • The memory manager is responsible for allocating and managing these address spaces, ensuring that processes do not interfere with each other’s memory.
3. Memory Allocation:
   • It refers to the process of assigning/reserving memory segments to different processes or programs.
   • There are various memory allocation techniques, such as fixed partitioning, variable partitioning, and dynamic partitioning.
   • Each memory allocation technique has its advantages and limitations.
4. Memory Deallocation/Reclamation:
   • When a program no longer needs a block of memory, it should release it so that it can be reused by other programs.
   • Memory deallocation involves freeing up the allocated memory and updating the memory management data structures accordingly.
   • Memory deallocation is the process of removal of unused or no longer in-use memory and making it available for other processes or free for next-time use.
   • Failure to deallocate memory properly can result in memory leaks, where memory remains allocated but unusable.
5. Memory Fragmentation:
   • Memory Fragmentation occurs when the available memory becomes logically divided into small, non-contiguous blocks due to the allocation and deallocation of memory segments.
   • Fragmentation can be internal (unused memory within allocated blocks) or external (unused memory outside allocated blocks).
   • It can lead to inefficient memory utilization and increased overhead.
6. Virtual Memory:
   • Modern operating systems use the concept of virtual memory, which allows a process to use more memory than what is physically available in the system.
   • Virtual memory is a memory management technique that allows the execution of processes that are larger than the physical memory available.
   • It uses a combination of RAM and disk space to create an illusion of a larger memory space.
   • Virtual memory enables efficient multitasking and memory sharing among multiple processes.
7. Paging and Swapping:
   • Paging is a memory management scheme that divides logical memory and physical memory into fixed-sized pages and frames, respectively.
   • Swapping involves moving entire processes in and out of the main memory to the disk when there is insufficient memory available. This technique helps in the efficient usage of memory resources.
8. Memory Protection:
   • Memory protection mechanisms ensure that one process cannot access or modify the memory assigned to another process without proper authorization.
   • It prevents accidental or malicious interference among processes, enhancing system stability and security.
9. Caching:
   • Caching involves temporarily storing frequently accessed data in a faster memory (cache) to reduce the access time to slower memory (such as RAM or disk).
   • Caching techniques exploit the principle of locality, which states that recently accessed data is likely to be accessed again in the near future.
10. Memory Sharing:
    1. Sometimes, multiple programs may need access to the same data. Memory management facilitates shared memory, allowing processes to communicate and share data efficiently.

Paging

• Paging is a memory management technique used by computer operating systems to manage and allocate physical memory (RAM) to processes.
• It allows for the efficient use of memory by dividing it into fixed-size blocks called Pages. The corresponding division of the process’s logical memory into fixed-size blocks is called Page Frames.
• The advantage of paging is efficient memory utilization, easy memory allocation & deallocation, simplified virtual memory management, protection between processes (as each process has its own page table), and simplified memory management. It allows processes to have a larger address space than the available physical memory, improving overall system performance and enabling the execution of larger and more complex programs.
• The disadvantage of paging is that it introduces overhead due to address translation and page table management. Caches, such as translation Look-Aside Buffers (TLBs), are often used to improve the efficiency of address translation by caching frequently accessed page table entries.

• Demand Paging:

  • Demand paging is a memory management technique that allows the operating system to bring in pages from secondary storage (such as a hard disk) into physical memory (RAM) only when they are actually needed by a process, rather than bringing the entire process into memory at once.
  • It is a variation of the paging technique and is designed to optimize memory usage and minimize the amount of data transferred between secondary storage and RAM.
  • It is closely related to the concept of virtual memory.
  • In demand paging, the operating system initially loads only a portion of a process into physical memory, typically the essential parts such as the program code and a few initial pages. The remaining pages are loaded into memory on-demand, triggered by a page fault when a process tries to access a page that is not currently in physical memory.
  • In other words, in demand paging, the entire process’s address space is not loaded into memory when the process is initially started. Instead, only the essential pages, such as the program’s instructions and critical data, are initially loaded into memory. As the process executes and references additional pages, the operating system dynamically fetches the required pages from secondary storage on demand.
  • Advantages:
    • Demand paging provides several advantages, including efficient memory utilization and reduced I/O overhead. Only the pages that are actually needed are loaded into memory, conserving physical memory resources and avoiding the unnecessary loading of unused pages.
    • This allows for the execution of larger processes that can fit entirely in memory.
    • Additionally, demand paging helps reduce the startup time of programs since only a portion of the program needs to be loaded initially.
  • Disadvantages
    • Demand paging can introduce performance overhead due to page faults and the need for frequent disk I/O operations to bring pages into memory. 

Terms of Paging Technique

1. Page Size:

   • The memory is logically divided into fixed-size pages, typically ranging from 4 KB to 64 KB in size.
   • The choice of page size is a trade-off between reducing internal fragmentation (unused space within a page) and reducing the overhead of page table management.

2. Page Table:

   • Each process has a page table that keeps track of the mapping between the logical addresses used by the process and the corresponding physical addresses in memory.
   • The page table contains entries for each page in the process’s logical memory, indicating the corresponding page frame in physical memory.

3. Address Translation:

   • When a process generates a memory reference (load or store instruction), the virtual address is divided into a page number and an offset within the page. The page number is used to index the page table, which retrieves the corresponding page frame number. The offset is combined with the page frame number to determine the actual physical address in memory.

4. Page Faults:

   • If a page required by a process is not currently present in physical memory(RAM), a page fault occurs. The operating system handles page faults by swapping out a page from memory to disk (if necessary) to make space for the requested page. Now, the page table is updated to reflect the new mapping.

5. Page Replacement:

   • When there is no free space in physical memory and a page fault occurs, the operating system selects a victim page to be evicted from memory and replaced with the requested page.
   • Various page replacement policies (e.g., FIFO, LRU, LFU) are used to determine which page to evict, based on factors such as access patterns, recency of use, or frequency of use.

6. Demand Paging:

   • Paging systems often employ a technique called demand paging, where pages are loaded into memory only when they are actually accessed by the process.
   • This approach reduces the initial memory footprint of a process and optimizes memory usage by loading pages on demand.
7. Resume Execution:
   • Once the required page is in memory, the operating system updates the process’s page table and resumes the interrupted process, allowing it to access the requested memory location.
8. Page-In:
   • After selecting a victim page, the required page is fetched from secondary storage (disk) and brought into an available physical frame. The page table is updated to reflect the new mapping between the virtual page and the physical frame.
9. Disk I/O:
   • If the victim page is modified (dirty), meaning it has been modified since it was brought into memory, it needs to be written back to disk before eviction. This involves performing disk I/O operations to store the page’s contents back to the secondary storage.

Segmentation or Memory Segmentation

• Definition
  • Memory segmentation is a memory management technique used in computer systems to divide the main memory into several small segments, each of which is used to store a specific type of data. Each segment is identified by a unique segment number or segment descriptor, which is used to access & manipulate the data stored within it.
• Characteristics
  • The purpose of memory segmentation is to provide a more flexible and efficient way of managing memory than using a simple linear address space. By dividing the memory into segments, it is possible to allocate memory more efficiently, reduce fragmentation, and improve the overall performance of the system.
  • Memory segmentation is used in many operating systems, including older versions of Windows, Linux, and Unix. It is also used in some embedded systems and real-time systems, where memory efficiency and performance are critical. 
  • In memory segmentation, each segment is assigned a base address and a limit address. The base address indicates the starting address of the segment in memory, while the limit address specifies the maximum size of the segment. The memory management unit (MMU) of the system uses these addresses to translate logical addresses into physical addresses.
• Advantages
  • By dividing memory into small segments, it is possible to allocate memory more efficiently and protect one segment from another. Instead of allocating a large block of memory for a single process, memory can be allocated in smaller, more manageable segments. This allows for more efficient use of memory and reduces the likelihood of memory fragmentation.
  • Memory segmentation provides better memory protection i.e., each segment can be assigned its own protection level, which determines whether it can be accessed or modified by other segments. This helps to prevent memory-related errors, such as buffer overflows and improves the security and stability of the system.
• Disadvantages
  • One of the disadvantages of memory segmentation is that it can lead to fragmentation of memory, which can reduce the amount of available memory and decrease performance. This is because memory segments can become fragmented as they are allocated and deallocated over time. 
  • It can be more complex to manage than other memory management techniques, and it may require more overhead in terms of memory and processing resources.
  • Some programming languages may not support memory segmentation, making it difficult to use in certain applications.

Fragmentation

Definition

• • Fragmentation in memory management refers to the phenomenon where the available memory space in a computer system becomes divided into small chunks that cannot be used efficiently, non-contiguous blocks due to the allocation and deallocation of memory.

Characteristics

• • This can occur in both the physical and virtual memory spaces.
  • In physical memory, fragmentation can occur when there are gaps between allocated memory blocks. This happens when a program allocates memory and then frees it, leaving behind a small block of unused memory. If this pattern continues, the memory space becomes divided into small, non-contiguous blocks, which can make it difficult to allocate large blocks of memory, even if the total amount of free memory is large enough.
  • In virtual memory, fragmentation can occur when the page file or swap file becomes fragmented. This happens when the operating system writes pages of memory to the hard disk and then retrieves them later when needed. If the page file becomes fragmented, the system may have to spend more time retrieving pages from different locations on the disk, which can slow down overall system performance.
  • There are several techniques that can be used to reduce fragmentation, including memory compaction and virtual memory paging algorithms.

Types of Fragmentation

• • Fragmentation can reduce the efficiency of memory usage in a system and can lead to performance degradation over time.
  • To address these issues, various memory management techniques such as compaction, paging, and virtual memory are used to optimize memory usage and minimize fragmentation.
  • There are two types of fragmentation in memory:

• • • External Fragmentation:

      • External fragmentation can occur in both physical and virtual memory systems.
      • External fragmentation occurs when there is a sufficient amount of total free memory available, but the memory is divided into small chunks that are too small to fulfill a memory request, even though the total amount of free memory is sufficient.
      • This happens because the memory allocation algorithm uses contiguous blocks of memory to allocate memory to processes. As a result, the free memory becomes fragmented into smaller chunks over time, and the memory manager may not be able to allocate large enough contiguous blocks to satisfy memory requests from processes.
      • External fragmentation occurs when free memory becomes fragmented into small chunks, but there is not enough contiguous memory available to satisfy a request for a larger block of memory. In this situation, the system cannot allocate memory efficiently, even if there is enough free memory available.
      • In physical memory systems, external fragmentation can occur when memory is allocated and deallocated in a way that creates small gaps between allocated memory blocks. Over time, these gaps can become fragmented and can no longer be used to allocate new memory.
      • In virtual memory systems, external fragmentation can occur when a process requests a contiguous block of memory that is larger than any single available block, but there are smaller free blocks available that cannot be used to fulfill the request.

    • Internal Fragmentation:

      • Internal fragmentation occurs when a memory allocation algorithm assigns more memory to a process than it actually requires, resulting in some of the allocated memory being unused.
      • This happens because most memory allocation algorithms allocate memory in fixed-size chunks, and if the size of the memory request is not an exact multiple of the chunk size, some of the allocated memory will be unused. This unused memory is called internal fragmentation, and it reduces the effective memory utilization of the system.
      • Internal fragmentation occurs when memory is allocated to a process, but some of the allocated memory is not actually used by the process. This unused memory creates small gaps between the allocated memory blocks, which cannot be used to allocate new memory.
      • Internal fragmentation only occurs in systems that allocate memory in fixed-size blocks, such as those that use paging.
      • In physical memory systems, internal fragmentation can occur when a process requests a block of memory that is slightly larger than the block size. The system may allocate a larger block to the process, leaving some unused memory in the allocated block.
      • In virtual memory systems, internal fragmentation can occur when a process requests a block of memory that is smaller than the page size. The system may allocate a full page to the process, leaving some unused memory on the page.

Compaction

• Compaction is a memory management technique that is used to reduce external fragmentation in a physical memory system.
• Compaction involves moving allocated memory to create larger contiguous blocks of free memory.
• The process of compaction involves identifying free memory blocks that are adjacent to each other, and then moving the allocated memory blocks so that the free memory blocks are adjacent to each other. This creates larger blocks of free memory that can be used to allocate new memory.
• Compaction involves moving allocated memory blocks closer together so that small gaps between the blocks can be combined to create larger contiguous blocks.
• Compaction is typically used in modern operating systems that use dynamic memory allocation. In these systems, memory allocation is done dynamically at runtime, and memory blocks are allocated and deallocated as needed and even frequently.
• Compaction can also be used in virtual memory systems, although the implementation is different. In a virtual memory system, pages that are no longer needed can be swapped out to disk, and the remaining pages can be compacted to create larger contiguous blocks of memory. This can help reduce external fragmentation and improve the overall performance of the system.
• Compaction can help to ensure that the system is able to allocate memory efficiently, even when there is a large amount of memory fragmentation.
• The goal of compaction is to free up larger contiguous blocks of memory by moving allocated memory blocks closer together and filling the gaps that are created.
• Compaction can be an effective way to reduce external fragmentation and improve the overall performance of the system.
• Compaction can be a time-consuming and expensive process, as it requires moving all of the allocated memory blocks in the system. This can impact the performance of the system, especially if there are many memory blocks that need to be moved.

Thrashing

• Thrashing refers to a situation in computer systems, particularly in virtual memory management, where the system spends a significant amount of time and resources on paging (transferring data between physical memory and secondary storage) with little or no progress in executing the actual tasks.
• Thrashing occurs when the system is excessively overloaded, typically due to insufficient physical memory (RAM) to accommodate the active processes’ memory demands. As a result, the system continually swaps pages between physical memory and disk, constantly replacing pages in memory with pages from disk and vice versa.
• This constant paging activity consumes a significant amount of CPU time and disk I/O bandwidth, resulting in poor overall performance and slowed progress of the tasks.
• The main disadvantage of thrashing is its identification and addressing which is crucial to maintain system performance.
• Thrashing ensures efficient resource utilization in virtual memory systems.

Characteristics of Thrashing 

• High Page Fault Rate: The system experiences a high rate of page faults, where a requested page is not found in physical memory and needs to be fetched from disk.
• Increased Disk Activity: The disk activity is significantly increased as pages are constantly swapped in and out of memory.
• Decreased CPU Utilization: The CPU spends a considerable amount of time handling page faults and managing the paging activity, leading to reduced CPU utilization for executing actual tasks.
• Decreased Throughput: The overall system throughput and performance suffer due to the excessive paging activity, resulting in delayed task completion.

Reason of Thrashing 

• Insufficient Physical Memory: When the system has inadequate RAM to accommodate the memory requirements of active processes, it leads to frequent swapping of pages between memory and disk.
• Over-Allocated Memory: If the system over-commits memory by allowing too many processes or allocating more memory than available physical memory, it can cause excessive paging.
• Improper Page Replacement Algorithms: Inefficient page replacement algorithms that fail to predict and satisfy the memory demands of processes can contribute to thrashing.

To Overcome Thrashing

• Increase Physical Memory: Adding more RAM to the system can provide more space for active processes and reduce the frequency of page swapping.
• Tune Virtual Memory Parameters: Adjusting virtual memory settings, such as page size or the size of the swap space, can help optimize memory management and reduce thrashing.
• Optimize Process Scheduling: Improved process scheduling algorithms can help distribute CPU time more efficiently among processes and reduce the occurrence of thrashing.
• Use Effective Page Replacement Algorithms: Implementing intelligent page replacement algorithms, such as the Optimal, Least Recently Used (LRU), or Working Set algorithms, can improve memory management and mitigate thrashing.

Page Replacement Policy

• Page replacement policy is a key component of virtual memory management in computer operating systems.
• Page replacement policy determines which pages in memory should be replaced when a new page needs to be brought in from disk due to memory demand exceeding the available physical memory. Thus, the page replacement policy is a strategy used by computer operating systems to manage the allocation of physical memory to virtual memory pages.
• The goal of a page replacement policy is to minimize the number of page faults, which occur when a requested page is not present in memory and needs to be loaded from disk.
• There are several page replacement algorithms that use different strategies to select the victim page for replacement. The choice of page replacement policy depends on factors such as system workload, memory size, and the cost of accessing the disk.
• Each page replacement algorithm has its own advantages and limitations, and the performance of a particular policy can vary depending on the characteristics of the workload. Therefore, different operating systems or applications may employ different page replacement policies based on their specific requirements.
• Different policies have different trade-offs in terms of complexity, efficiency, and the ability to minimize page faults (when a requested page is not found in memory). 
• The following are some commonly used page replacement policies:-

• • FIFO (First-In-First-Out):

    • This policy selects the oldest page in memory for replacement.
    • It maintains a queue of pages in the order they were brought into memory, and the page at the front of the queue is selected for eviction. When a page needs to be replaced, the page at the front of the queue, i.e., the oldest page, is selected.
    • FIFO is simple to implement but does not consider the usage patterns/criteria of pages.

  • LRU (Least Recently Used):

    • This policy selects the page that has not been used for the longest period of time for replacement.
    • It relies on the principle of temporal locality, assuming that pages that have not been accessed recently are less likely to be accessed in the near future.
    •  It requires maintaining a timestamp or a counter for each page to track when it was last accessed.
    • Evicting the least recently used page aims to minimize the likelihood of future access to that page.

  • LFU (Least Frequently Used):

    • This policy selects the page that has been accessed the fewest number of times for replacement.
    • It aims to replace pages that are infrequently used, assuming that they are less likely to be needed again.
    •  It requires maintaining a counter for each page to track the number of times it has been accessed.
    • Evicting the least frequently used page aims to prioritize pages that are accessed less frequently.
  • MFU (Most Frequently Used):
    • This policy selects the page that has been accessed the most number of times for replacement.
    • It requires maintaining a counter for each page to track the number of times it has been accessed.
    • Evicting the most frequently used page aims to retain pages that are heavily used.

  • Optimal:

    • The optimal page replacement algorithm is a theoretical algorithm that selects the page that will not be used for the longest duration in the future. It requires knowledge of the future memory access pattern, which is generally not feasible in practical systems.
    • The optimal algorithm serves as a benchmark for evaluating the efficiency of other algorithms.

  • Random:

    • This simple algorithm randomly selects a page for replacement, without considering any specific page access patterns/criteria.
    • Although it is not optimal, it can provide reasonable performance in some scenarios.